-
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;
}
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 void sortColors(int[] nums) {
int p1 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
if (i != p1)
swap(nums, p1, i);
p1++;
}
}
for (int i = p1; i < nums.length; i++) {
if (nums[i] == 1) {
if (i != p1)
swap(nums, p1, i);
p1++;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
public static boolean isPalindrome(String s) {
int right = s.length() - 1;
int left = 0;
while (left < right) {
char leftChar = s.charAt(left);
while (!Character.isLetterOrDigit(leftChar) && left < right) {
leftChar = s.charAt(++left);
}
char rightChar = s.charAt(right);
while (!Character.isLetterOrDigit(rightChar) && left < right) {
rightChar = s.charAt(--right);
}
if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
return false;
}
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;
}
- 解法二:双指针
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) 的原地算法解决这个问题吗?
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. 有序数组的平方