-
Notifications
You must be signed in to change notification settings - Fork 116
数组相关算法
给定一个整数数组 nums和一个整数目标值 target,请你在该数组中找出 和为目标值的那两个整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。你可以按任意顺序返回答案。
- 解法一:双重循环
public static int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
int result = target - nums[i];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == result) {
return new int[] { i, j };
}
}
}
return null;
}
- 解法二:使用HashMap
public static int[] twoSum1(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[] { map.get(target - nums[i]), i };
}
map.put(nums[i], i);
}
return null;
}
给定一个包含红色、白色和蓝色,一共n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
public class Solution {
/**
* 解题思路:
* <p>
* 1.通过双指针第一趟扫描0号球,快指针遍历,慢指针指向第一个非0位置,等到快指针扫
* 描到0后与慢指针交换位置。直到快指针遍历完整个数组,此时慢指针指向第一个非0位置
* 2. 第二趟从上一趟慢指针位置开始遍历,扫描1号球,思想与第一步类似。完成此次遍历
* 与交换后便完成了三色球的排序
*/
public void sortColors(int[] nums) {
// 慢指针
int p = 0;
// i 为快指针
for (int i = 0; i < nums.length; i++) {
// 遍历到0号球
if (nums[i] == 0) {
// p 一定是小于等于i的,等于i时候说明两个指针指向同一个小球,不需要交换
if (p < i)
// 将i处的0号球与慢指针位置的球交换
swap(nums, p, i);
// 满指针加1,指向下一个非0球
p++;
}
}
// 第二趟查找1号球
for (int i = p; i < nums.length; i++) {
if (nums[i] == 1) {
if (p < i)
swap(nums, p, i);
p++;
}
}
}
private void swap(int[] nums, int n, int m) {
int temp = nums[n];
nums[n] = nums[m];
nums[m] = temp;
}
}
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
public class Solution {
/**
* 解题思路:
* 双指针法,左指针指向起始位置,右指针指向末尾位置。左指针如果不是字母或者数字就不断加1,
* 右指针如果不是字母或者数字就不断减1。左右指针都指向数字的时候比较两个字符是否相等(忽略大小写),
* 如果不相等,则返回false,如果相等,则继续比较下一个,直到所有字符对比完成,则返回true。
*
*
*/
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
// 循环终止条件,左指针小于右指针
while (left < right) {
// 左指针如果指向的不是字母或数字则不断加1,需要保证left小于right
// 注意这里 Character.isLetterOrDigit 的API
while (!Character.isLetterOrDigit(s.charAt(left)) && left < right) {
left++;
}
// 右指针如果指向的不是字母或数字,则不断减1,同样需要保证左指针小于右指针
while (!Character.isLetterOrDigit(s.charAt(right)) && left < right) {
right--;
}
// 忽略大小写,比较左右指针指向的字符是否相等,注意Character.toLowerCase的API
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
// 不相等,则不是回文字符,返回false
return false;
}
// 完成一次对比左指针加1,右指针减1
left++;
right--;
}
return true;
}
}
给定一个已按照 非递减顺序排列 的整数数组numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ,所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
- 解法一:暴力法
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
for (int i = 0; i < numbers.length; i++) {
int t = target - numbers[i];
for (int j = i + 1; j < numbers.length; j++) {
if (t == numbers[j]) {
result[0] = i + 1;
result[1] = j + 1;
break;
}
}
}
return result;
}
- 解法二:双指针
/**
* 由于是一个有序数组,因此可以使用双指针,一个指针指向数组头,另一个指针指向数组尾。如果两个指针位置的元素相加小于target
* 那么就让左指针向右移动一次,如果相加之和大于target,则让右指针向左移动一次,如果相加等于target,则返回向指针的位置即可。
* 边界条件是左指针小于右指针
*/
public int[] twoSum(int[] numbers, int target) {
int p1 = 0, p2 = numbers.length - 1;
while (p1 <= p2) {
if (numbers[p1] + numbers[p2] > target) {
p2--;
} else if (numbers[p1] + numbers[p2] < target) {
p1++;
} else {
return new int[]{p1 + 1, p2 + 1};
}
}
return new int[]{-1,-1};
}
给定一个数组,将数组中的元素向右移动k个位置,其中k是非负数。
进阶:
尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为O(1) 的原地算法解决这个问题吗?
public void rotate(int[] nums, int k) {
k = k % nums.length;
int[] n = new int[k];
for (int i = 0; i < k; i++) {
n[i] = nums[nums.length - k + i];
}
for (int i = nums.length - k - 1; i >= 0; i--) {
nums[i + k] = nums[i];
}
for (int i = 0; i < n.length; i++) {
nums[i] = n[i];
}
}
给定一个数组,将数组中的元素向右移动k个位置,其中k是非负数。
进阶:
尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为O(1) 的原地算法解决这个问题吗?
/**
* 用两个指针同时从0位置开始移动,一个快指针为i,一个慢指针j。快指针每次都移动,慢指针只有在指向的位置不等于0的时候
* 才移动一次,并将快指针指向的值赋值给慢指针的位置。这样当快指针j指向数组最后一个元素的时候,慢指针i指向位置之后的
* 所有元素都应该是0,因此,从慢指针i的位置开始遍历,将所有值改为0。
*
*/
public void rotate(int[] nums, int k) {
k = k % nums.length;
int[] n = new int[k];
if (k >= 0) {
System.arraycopy(nums, nums.length - k, n, 0, k);
}
if (nums.length - k - 1 + 1 >= 0) {
System.arraycopy(nums, 0, nums, k, nums.length - k - 1 + 1);
}
if (n.length >= 0) {
System.arraycopy(n, 0, nums, 0, n.length);
}
}
给定一个整数数组 nums,求出数组从索引 i 到 j(i ≤ j)范围内元素的总和,包含 i、j 两点。
实现 NumArray 类:
NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j(i ≤ j)范围内元素的总和,包含 i、j 两点(也就是 sum(nums[i], nums[i + 1], ... , nums[j]))
示例:
输入: ["NumArray", "sumRange", "sumRange", "sumRange"] [-2, 0, 3, -5, 2, -1, [0, 2], [2, 5], [0, 5]] 输出: [null, 1, -1, -3]
解释: NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3) numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
- 解法1
class NumArray {
private final int[] nums;
public NumArray(int[] nums) {
this.nums=nums;
}
public int sumRange(int left, int right) {
if(nums==null){
return 0;
}
int sum = 0;
for(;left<=right;left++){
sum += nums[left];
}
return sum;
}
}
- 解法2
public class NumArray {
private final int[] sums;
public NumArray(int[] nums) {
int n = nums.length;
sums = new int[n + 1];
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + sums[i + 1];
}
}
public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
}
给定 n
个整数,找出平均数最大且长度为 k
的连续子数组,并输出该最大平均数。
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
if (nums.length == k) {
return (double) sum / k;
}
int maxSum = sum;
if (k == 1) {
for (int i = 1; i < nums.length - 1; i++) {
maxSum = Math.max(maxSum, nums[i]);
}
return maxSum;
}
for (int i = 0; i < nums.length - k; i++) {
sum = sum - nums[i] + nums[i + k];
maxSum = Math.max(maxSum, sum);
}
return (double) maxSum / k;
}
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
public int[] sortedSquares(int[] nums) {
if (nums[0] >= 0) {
for (int i = 0; i < nums.length; i++) {
nums[i] = nums[i] * nums[i];
}
return nums;
} else if (nums[nums.length - 1] <= 0) {
int[] newArray = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
newArray[i] = nums[nums.length - 1 - i] * nums[nums.length - 1 - i];
}
return newArray;
} else {
int[] newArray = new int[nums.length];
int i = 0, j = nums.length - 1, k = nums.length - 1;
while (i <= j) {
int ii = nums[i] * nums[i];
int jj = nums[j] * nums[j];
if (ii >= jj) {
newArray[k--] = ii;
i++;
} else {
newArray[k--] = jj;
j--;
}
}
return newArray;
}
}
- JMM与volatile关键字
- synchronized的实现原理
- synchronized等待与唤醒机制
- AQS的实现原理
- ReentrantLock的实现原理
- ReentrantLock等待与唤醒机制
- CAS、Unsafe类以及Automic并发包
- ThreadLocal的实现原理
- 线程池的实现原理
- Java线程中断机制
- 多线程与并发常见面试题
- Android基础知识汇总
- MVC、MVP与MVVM
- SparseArray实现原理
- ArrayMap的实现原理
- SharedPreferences
- Bitmap
- Activity的启动模式
- Fragment核心原理
- 组件化项目架构搭建
- 组件化WebView架构搭建
- 为什么 Activity.finish() 之后 10s 才 onDestroy ?
- Binder与AIDL
- Binder实现原理
- Android系统启动流程
- InputManagerService
- WindowManagerService
- Choreographer详解
- SurfaceFlinger
- ViewRootImpl
- ActivityManagerService
- APP启动流程
- PMS安装与签名校验
- Dalvik与ART
- 内存优化策略
- UI界面及卡顿优化
- App启动优化
- ANR问题
- 包体积优化
- APK打包流程
- 电池电量优化
- Android屏幕适配
- 线上性能监控1--线上监控切入点
- 线上性能监控2--Matrix实现原理
- Glide实现原理
- OkHttp实现原理
- Retrofit实现原理
- RxJava实现原理
- RxJava中的线程切换与线程池
- LeakCanary实现原理
- ButterKnife实现原理
- ARouter实现原理
- Tinker实现原理
- 2. 两数相加
- 19.删除链表的倒数第 N 个结点
- 21. 合并两个有序链表
- 24. 两两交换链表中的节点
- 61. 旋转链表
- 86. 分隔链表
- 92. 反转链表 II
- 141. 环形链表
- 160. 相交链表
- 206. 反转链表
- 206 反转链表 扩展
- 234. 回文链表
- 237. 删除链表中的节点
- 445. 两数相加 II
- 面试题 02.02. 返回倒数第 k 个节点
- 面试题 02.08. 环路检测
- 剑指 Offer 06. 从尾到头打印链表
- 剑指 Offer 18. 删除链表的节点
- 剑指 Offer 22. 链表中倒数第k个节点
- 剑指 Offer 35. 复杂链表的复制
- 1. 两数之和
- 11. 盛最多水的容器
- 53. 最大子序和
- 75. 颜色分类
- 124.验证回文串
- 167. 两数之和 II - 输入有序数组 -169. 多数元素
- 189.旋转数组
- 209. 长度最小的子数组
- 283.移动0
- 303.区域和检索 - 数组不可变
- 338. 比特位计数
- 448. 找到所有数组中消失的数字
- 643.有序数组的平方
- 977. 有序数组的平方