目录
算法：数组
算法：数组
数组相关题目
56. 合并区间
Arrays.sort的比较器：
//第一种：
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
// TODO Auto-generated method stub
return a[0] - b[0];
}
});
//第二种：lambda表达式
Arrays.sort(arr, (a,b) -> a[0] - b[0]);
//第三种：
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
解法：先进行排序，然后遍历将存在公共区间的合并。
public int[][] merge(int[][] arr) {
if(arr == null || arr.length<=1) {
return arr;
}
List<int[]> list = new ArrayList<>();
Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
// TODO Auto-generated method stub
return a[0] - b[0];
}
});
//Lambda表达式
//Arrays.sort(arr, (a,b) -> a[0] - b[0]);
for (int i = 0; i < arr.length; i++) {
int left = arr[i][0];
int right = arr[i][1];
while (i+1 < arr.length && right >= arr[i+1][0]) {
right = Math.max(right, arr[i+1][1]);
i++;
}
list.add(new int[] {left, right});
}
return list.toArray(new int[list.size()][2]);
}
435. 无重叠区间
面试题 01.08. 零矩阵
public void setZeroes(int[][] matrix) {
boolean col = false;
boolean row = false;
int n = matrix.length, m = matrix[0].length;
for (int i = 0; i < n; i++) {
if (matrix[i][0] == 0) {
col = true;
}
}
for (int i = 0; i < m; i++) {
if (matrix[0][i] == 0) {
row = true;
}
}
for (int i = 1; i <n; i++) {
for (int j = 1; j <m; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = 1; i <n; i++) {
for (int j = 1; j < m; j++) {
if (matrix[i][0] ==0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (row) {
for (int i = 0; i <m; i++) {
matrix[0][i] = 0;
}
}
if (col) {
for (int i = 0; i <n; i++) {
matrix[i][0] = 0;
}
}
}
分治
169. 多数元素
查找数组中元素出现次数超过数组长度的一半的元素。
利用分治算法，因为次数超过一半的元素，在数组分成两部分的时候，该元素也是左或右部分的众数。
public int majorityElement(int[] nums) {
return majorityElement(nums, 0, nums.length - 1);
}
public int majorityElement(int[] nums, int l, int r){
if (l == r){
return nums[l];
}
int mid = (r - l) / 2 + l;
int left = majorityElement(nums, l, mid);
int right = majorityElement(nums, mid + 1, r);
if (left == right){
return left;
}
return count(nums, l, r, left, right);
}
public int count(int[] nums, int l, int j, int left, int right){
int res1 = 0;
int res2 = 0;
for (int i = l; i <= j; i++) {
if (nums[i] == left){
res1 ++;
}
if (nums[i] == right){
res2 ++;
}
}
return res1 > res2 ? left : right;
}
双指针技巧
快慢指针常用算法
移除重复的元素
public int removeDuplicates(int[] nums) {
int left = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[left]) {
nums[++left] = nums[i];
}
}
return left+1;
}
80. 删除有序数组中的重复项 II
public int removeDuplicates(int[] nums) {
if (nums.length <= 2) {
return nums.length;
}
int left = 2;
for (int i = 2; i < nums.length; i++) {
if (nums[i] != nums[left-2]) {
nums[left++] = nums[i];
}
}
return left;
}
283. 移动零
int i = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] != 0) {
nums[i++] = nums[j];
}
}
while (i < nums.length) {
nums[i++] = 0;
}
141. 判断环形链表
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode n1 = head;
ListNode n2 = head.next;
while (n1 != null && n2 != null && n2.next != null) {
if (n1 == n2) {
return true;
}
n1 = n1.next;
n2 = n2.next.next;
}
return false;
}
142. 环形链表 II返回环形的初始节点
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode n1 = head;
ListNode n2 = head;
while (n1 != null && n2 != null && n2.next != null) {
n1 = n1.next;
n2 = n2.next.next;
if (n1 == n2) {
n1 = head;
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
}
return null;
}
876. 返回链表的中间结点
public ListNode middleNode(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode n2 = head;
while (n2 != null && n2.next != null) {
head = head.next;
n2 = n2.next.next;
}
return head;
}
4、寻找链表的倒数第 k 个元素
我们的思路还是使用快慢指针，让快指针先走 k 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 k 个链表节点（为了简化，假设 k 不会超过链表长度）：
ListNode slow, fast;
slow = fast = head;
while (k-- > 0)
fast = fast.next;
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
左右指针常用算法
15. 三数之和
首先 使用 左右指针需要先进行排序
三数之和为0，-> 两数之后等于第三个数的相反数 ->双子针，记得排除重复的数
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
11. 盛最多水的容器
public int maxArea(int[] height) {
int left = 0,right = height.length-1;
int max = 0;
while (left < right) {
if (height[left] > height[right]) {
max = Math.max(max, height[right]*(right-left));
right--;
}else {
max = Math.max(max, height[left]*(right-left));
left++;
}
}
return max;
}
167. 两数之和 II - 输入有序数组
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length-1;
while (left < right) {
if (numbers[left] + numbers[right] == target) {
break;
}else if (numbers[left] + numbers[right] > target) {
right--;
}else if (numbers[left] + numbers[right] < target) {
left++;
}
}
return new int[] {left+1, right+1};
}
75. 颜色分类
public void sortColors(int[] nums) {
if (nums.length <= 1) {
return;
}
int left = 0, right = nums.length-1;
for (int i = 0; i <= right; i++) {
if (nums[i] == 0) {
swap(nums, left++, i);
}else if (nums[i] == 2) {
swap(nums, right--, i--);
}
}
}
27. 移除元素
public int removeElement(int[] nums, int val) {
int i = 0;
for (int j = 0; j < nums.length; j++) {
if (val != nums[j]) {
nums[i] = nums[j];
i++;
}
}
return i;
}
二分查找
/**
* 查找元素，存在返回索引，不存在返回-1
* @param arr
* @param target
* @return
*/
public static int binarySearch(int[] arr, int target) {
int left = 0,right = arr.length-1; //注意
while (left <= right) { //注意
//这样写是为了防止溢出
int mid = right - (right - left)/2;
if (arr[mid] > target) {
right = mid-1;
}else if(arr[mid] < target) {
left = mid +1;
}else {
return mid;
}
}
return -1;
}
框架：
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = (right + left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
查找元素
存在返回索引，不存在返回-1
注意：
1. 为什么 while 循环的条件中是 <=，而不是 < ？
答：因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。
while(left <= right)的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见****这时候搜索区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。
**while(left < right)的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，**这时候搜索区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就可能出现错误。
当然，如果你非要用 while(left < right) 也可以，我们已经知道了出错的原因，就打个补丁好了：
//...
while(left < right) {
// ...
}
return nums[left] == target ? left : -1;
/**
* 查找元素，存在返回索引，不存在返回-1
* @param arr
* @param target
* @return
*/
public static int binarySearch(int[] arr, int target) {
int left = 0,right = arr.length-1; //注意
while (left <= right) { //注意
//这样写是为了防止溢出
int mid = right - (right - left)/2;
if (arr[mid] > target) {
right = mid-1;
}else if(arr[mid] < target) {
left = mid +1;
}else {
return mid;
}
}
return -1;
}
3. 此算法有什么缺陷？
答：至此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。
比如说给你有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。
这样的需求很常见。你也许会说，找到一个 target 索引，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分查找对数级的复杂度了。
我们后续的算法就来讨论这两种二分查找的算法。
寻找左侧边界的二分搜索
/**
* 查找元素，存在返回最左侧的索引，不存在返回-1
* @param arr
* @param target
* @return
*/
public static int binarySearch(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = (left + right)/2;
//这两个值不一定相同。
System.out.println((right + (left - right)/2) == ((left + right)/2));
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
// target 比所有数都大
if (left == nums.length) return -1;
// 类似之前算法的处理方式
return nums[left] == target ? left : -1;
}
寻找右侧边界的二分查找
/**
* 查找元素，存在返回最右侧的索引，不存在返回-1
* @param arr
* @param target
* @return
*/
public static int binarySearch(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = (left + right)/2;
//这两个值不一定相同。
System.out.println((right + (left - right)/2) == ((left + right)/2));
if (nums[mid] == target) {
left = mid+1; //注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;
}
总结
梳理一下这些细节差异的因果逻辑：
第一个，最基本的二分查找算法：
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1
因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回
第二个，寻找左侧边界的二分查找：
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid+1 和 right = mid
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界
第三个，寻找右侧边界的二分查找：
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid+1 和 right = mid
因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界
又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一
1. 分析二分查找代码时，不要出现 else，全部展开成 else if 方便理解。
2. 注意「搜索区间」和 while 的终止条件，如果存在漏掉的元素，记得在最后检查。
3. 如需要搜索左右边界，只要在 nums[mid] == target 时做修改即可。搜索右侧时需要减一。
例题
875. 爱吃香蕉的珂珂
public int minEatingSpeed(int[] piles, int h) {
int right = piles[0];
for (int i = 1; i < piles.length; i++) {
right = Math.max(right, piles[i]);
}
int left = 1;
int time;
int mid = 0;
right++;
while (left < right) {
mid = (right + left) /2;
time = 0;
for (int i = 0; i < piles.length; i++) {
time += piles[i] / mid + (piles[i] % mid == 0 ? 0 : 1);
}
if (time <= h) {
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
1011. 在 D 天内送达包裹的能力
class Solution {
// 寻找左侧边界的二分查找
public int shipWithinDays(int[] weights, int D) {
// 载重可能的最小值
int left = getMax(weights);
// 载重可能的最大值 + 1
int right = getSum(weights) + 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(weights, D, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// 如果载重为 cap，是否能在 D 天内运完货物？
public boolean canFinish(int[] w, int D, int cap) {
int i = 0;
for (int day = 0; day < D; day++) {
int maxCap = cap;
while ((maxCap -= w[i]) >= 0) {
i++;
if (i == w.length)
return true;
}
}
return false;
}
public int getSum(int[] nums) {
int sum = 0;
for (int j2 = 0; j2 < nums.length; j2++) {
sum += nums[j2];
}
return sum;
}
public int getMax(int[] nums) {
return nums[nums.length -1];
}
}
难153. 寻找旋转排序数组中的最小值
public int findMin(int[] nums) {
int left = 0, right = nums.length -1;
while (left < right) {
int mid = (left + right)/2;
if (nums[mid] < nums[right]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[left];
}
上一题的进阶154. 寻找旋转排序数组中的最小值 II
public int findMin(int[] nums) {
int left = 0, right = nums.length-1;
while (left < right) {
int mid = (left +right)/2;
if (nums[mid] < nums[right]) {
right = mid;
}else if (nums[mid] > nums[right]) {
left = mid +1;
}else if (nums[mid] == nums[right]) {
right--;
}
}
return nums[left];
}
两数之和（给定的数组是有序的）
public int[] twoSum(int[] nums, int target) {
int left = 0,right = nums.length-1;
while (left <= right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[] {left,right};
}else if (sum > target) {
right = right -1;
}else if (sum < target) {
left = left + 1;
}
}
return null;
}
反转数组
void reverse(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
// swap(nums[left], nums[right])
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++; right--;
}
}
滑动窗口常见算法
做题明确四个问题：
**1、**当移动
right扩大窗口，即加入字符时，应该更新哪些数据？**2、**什么条件下，窗口应该暂停扩大，开始移动
left缩小窗口？**3、**当移动
left缩小窗口，即移出字符时，应该更新哪些数据？**4、**我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？
一套滑动窗口算法的代码框架，在哪里做输出 debug 都写好了，以后遇到相关的问题，就默写出来如下框架然后改三个地方就行，还不会出边界问题：
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
76. 最小覆盖子串
class Solution {
public static String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
//窗口的区间是[left,right)
Map<Character, Integer> window = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
need.put(c, need.getOrDefault(c, 0)+1);
window.put(c, 0);
}
//指针
int left = 0, right = 0;
int len = Integer.MAX_VALUE;
int start = 0;
int end = 0;
while (right < s.length()) {
char add = s.charAt(right);
right ++;
if (need.containsKey(add)) {
window.put(add, window.getOrDefault(add, 0)+1);
}
//判断当前窗口[left,right)是否已经存了所有的值
//对left操作
while (judgeWindoe(window, need)) {
if (right - left < len) {
start = left;
end = right;
len = right - left;
}
char remove = s.charAt(left);
left ++;
if (window.containsKey(remove)) {
window.put(remove, window.get(remove) -1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, end);
}
public static boolean judgeWindoe(Map<Character, Integer> window, Map<Character, Integer> need) {
Set<Character> setKey = need.keySet();
for (Character key : setKey) {
if (need.get(key) > window.get(key)) {
return false;
}
}
return true;
}
}
567. 字符串的排列
public boolean checkInclusion(String p, String s) {
Map<Character, Integer> needMap = new HashMap<>();
Map<Character, Integer> windowMap = new HashMap<>();
for (int i = 0; i < p.length(); i++) {
needMap.put(p.charAt(i), needMap.getOrDefault(p.charAt(i), 0)+1);
}
int left = 0,right = 0;
int valid = 0;
while (right < s.length()) {
char add = s.charAt(right);
right++;
if (needMap.containsKey(add)) {
windowMap.put(add, windowMap.getOrDefault(add, 0)+1);
if (windowMap.get(add).equals(needMap.get(add))) {
valid++;
}
}
if (right - left == p.length()) {
if (valid == needMap.size()) {
return true;
}
char remove = s.charAt(left);
left ++;
if (needMap.containsKey(remove)) {
if (windowMap.get(remove).equals(needMap.get(remove))) {
valid--;
}
windowMap.put(remove, windowMap.get(remove)-1);
}
}
}
return false;
}
438. 找到字符串中所有字母异位词
public List<Integer> findAnagrams(String s, String p) {
List<Integer> list = new ArrayList<>();
Map<Character, Integer> needMap = new HashMap<>();
Map<Character, Integer> windowMap = new HashMap<>();
for (int i = 0; i < p.length(); i++) {
needMap.put(p.charAt(i), needMap.getOrDefault(p.charAt(i), 0)+1);
}
int left = 0,right = 0;
int valid = 0;
while (right < s.length()) {
char add = s.charAt(right);
right++;
if (needMap.containsKey(add)) {
windowMap.put(add, windowMap.getOrDefault(add, 0)+1);
if (windowMap.get(add).equals(needMap.get(add))) {
valid++;
}
}
if (right - left == p.length()) {
if (valid == needMap.size()) {
list.add(left);
}
char remove = s.charAt(left);
left ++;
if (needMap.containsKey(remove)) {
if (windowMap.get(remove).equals(needMap.get(remove))) {
valid--;
}
windowMap.put(remove, windowMap.get(remove)-1);
}
}
}
return list;
}
3. 无重复字符的最长子串
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int res = 0; // 记录结果
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 进行窗口内数据的一系列更新
window.put(c, window.getOrDefault(c, 0)+1);
// 判断左侧窗口是否要收缩
while (window.get(c) > 1) {
char d = s.charAt(left);
left++;
// 进行窗口内数据的一系列更新
window.put(d, window.get(d)-1);
}
// 在这里更新答案
res = Math.max(res, right - left);
}
return res;
}
209. 长度最小的子数组
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int left = 0;
int right = 0;
int min = nums.length+1;
while (right < nums.length) {
sum += nums[right];
while (sum >= target) {
min = Math.min(min, right-left+1);
sum = sum - nums[left];
left++;
}
right++;
}
return min == nums.length+1 ? 0 : min;
}
给我 O(1) 时间，我能查找/删除数组中的任意元素
可以做到！对数组尾部进行插入和删除操作不会涉及数据搬移，时间复杂度是 O(1)。
所以，如果我们想在 O(1) 的时间删除数组中的某一个元素val，可以先把这个元素交换到数组的尾部，然后再pop掉。
数组去重
316. 去除重复字母
利用栈来解决。
栈：后入先出。
public String removeDuplicateLetters(String s) {
Stack<Character> stack = new Stack<>();
int[] counts = new int[255];
for (int i = 0; i < s.length(); i++) {
counts[s.charAt(i)] = i;
}
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!stack.contains(c)) {
while (!stack.isEmpty() && c < stack.peek() && counts[stack.peek()] > i) {
stack.pop();
}
stack.push(c);
}
}
String string = "";
while (!stack.empty()) {
string = stack.pop() + string;
}
return string;
}
我们顺序遍历字符串s，通过「栈」这种顺序结构的 push/pop 操作记录结果字符串，保证了字符出现的顺序和s中出现的顺序一致。
这里也可以想到为什么要用「栈」这种数据结构，因为先进后出的结构允许我们立即操作刚插入的字符，如果用「队列」的话肯定是做不到的。
要求三、我们用类似单调栈的思路，配合计数器count不断 pop 掉不符合最小字典序的字符，保证了最终得到的结果字典序最小。
当然，由于栈的结构特点，我们最后需要把栈中元素取出后再反转一次才是最终结果。
83. 删除排序链表中的重复元素
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast != null) {
if (fast.val != slow.val) {
// nums[slow] = nums[fast];
slow.next = fast;
// slow++;
slow = slow.next;
}
// fast++
fast = fast.next;
}
// 断开与后面重复元素的连接
slow.next = null;
return head;
}
26. 删除有序数组中的重复项
public int removeDuplicates(int[] nums) {
if(nums.length < 2) {
return nums.length;
}
int i = 0;
for (int j = 1; j < nums.length; j++) {
if(nums[i] != nums[j]) {
i++;
nums[i] = nums[j];
}
}
return i+1;
}
27. 移除元素
public int removeElement(int[] nums, int val) {
int i = 0;
for (int j = 0; j < nums.length; j++) {
if (val != nums[j]) {
nums[i] = nums[j];
i++;
}
}
return i;
}
283. 移动零
public void moveZeroes(int[] nums) {
int i = 0;
for (int j = 0; j < nums.length; j++) {
if (nums[j] != 0) {
nums[i++] = nums[j];
}
}
while (i < nums.length) {
nums[i++] = 0;
}
}
小而美的算法技巧
前缀和数组
前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。
要计算数组中子数组的和为k的有多少个？
普通解法：把所有的子数组列出来，在判断。
利用前缀和数组：新建立起来一个数组prefix，记录0-i的和，包括本身。即prifix[i] = nums[0-i] 的和。找出一个子数组的和就是prifix[i] - prifix[i-1];
560. 和为K的子数组
解法：
public int subarraySum(int[] nums, int k) {
int[] prefix = new int[nums.length+1];
//得到前缀和数组
for (int i = 0; i < nums.length; i++) {
prefix[i+1] = prefix[i] + nums[i];
}
int sum = 0;
for (int i = 1; i < prefix.length; i++) {
for (int j = 0; j < i; j++) {
if (prefix[i] - prefix[j] == k) {
sum++;
}
}
}
return sum;
}
利用哈希表优化算法。（和求一个数组中等于target的两个元素的索引的题类似）
public int subarraySum(int[] nums, int k) {
int preSum = 0;
int count = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0,1);
for (int i = 0; i < nums.length; i++) {
preSum += nums[i];
if (map.containsKey(preSum-k)) {
count+=map.get(preSum-k);
}
map.put(preSum, map.getOrDefault(preSum, 0) + 1);
}
return count;
}
差分数组
差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。
构造差分数组：
//构造差分数组 原：2,3,5,1,2,6
int[] diff = new int[nums.length];
diff[0] = nums[0];
for (int i = 1; i < diff.length; i++) {
diff[i] = nums[i] - nums[i-1];
}
System.out.println(Arrays.toString(diff));//[2, 1, 2, -4, 1, 4]
还原差分数组：
//差分数组还原
int[] res = new int[diff.length];
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
res[i] = diff[i]+res[i-1];
}
System.out.println(Arrays.toString(res));//[2, 3, 5, 1, 2, 6]
差分数组特性：
回想
diff数组反推nums数组的过程，diff[i] += 3意味着给nums[i..]所有的元素都加了 3，然后diff[j+1] -= 3又意味着对于nums[j+1..]所有元素再减 3，那综合起来，是不是就是对nums[i..j]中的所有元素都加 3 了？
示例：
1109. 航班预订统计
public static int[] corpFlightBookings(int[][] bookings, int n) {
//差分数组
int[] diff = new int[n];
for (int i = 0; i < bookings.length; i++) {
//因为first是从1开始的所以减一
int first = bookings[i][0]-1;
int end = bookings[i][1];
int seats = bookings[i][2];
diff[first] += seats;
//如果增加到最后一位了，就不需要减操作了
if (end < diff.length) {
diff[end] -= seats;
}
}
int[] res = new int[n];
res[0] = diff[0];
//还原数组
for (int i = 1; i < res.length; i++) {
res[i] = res[i-1]+diff[i];
}
return res;
}
快排亲兄弟：快速选择算法详解
215. 数组中的第K个最大元素
第k个最大的元素就是排好序之后索引为len-k的的值。寻找他，可以利用快速排序的思维，只要寻找到索引就可以，不需要把整个数组排序。
class Solution {
Random random = new Random();
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
public int quickSelect(int[] a, int l, int r, int index) {
int q = randomPartition(a, l, r);
if (q == index) {
return a[q];
} else {
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}
}
public int randomPartition(int[] a, int l, int r) {
int i = random.nextInt(r - l + 1) + l;
swap(a, i, r);
return partition(a, l, r);
}
public int partition(int[] a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a, ++i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
使用优先级队列实现：实际写算法的时候推荐使用。
int findKthLargest(int[] nums, int k) {
// 小顶堆，堆顶是最小元素
PriorityQueue<Integer>
pq = new PriorityQueue<>();
for (int e : nums) {
// 每个元素都要过一遍二叉堆
pq.offer(e);
// 堆中元素多于 k 个时，删除堆顶元素
if (pq.size() > k) {
pq.poll();
}
}
// pq 中剩下的是 nums 中 k 个最大元素，
// 堆顶是最小的那个，即第 k 个最大元素
return pq.peek();
}
分治算法详解：表达式的不同优先级
最典型的分治算法就是归并排序了，核心逻辑如下：
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
/****** 分 ******/
// 对数组的两部分分别排序
sort(nums, lo, mid);
sort(nums, mid + 1, hi);
/****** 治 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
}
241. 为运算表达式设计优先级
解决本题的关键有两点：
1、不要思考整体，而是把目光聚焦局部，只看一个运算符。
解决递归相关的算法问题，就是一个化整为零的过程，你必须瞄准一个小的突破口，然后把问题拆解，大而化小，利用递归函数来解决。
2、明确递归函数的定义是什么，相信并且利用好函数的定义。
因为递归函数要自己调用自己，你必须搞清楚函数到底能干嘛，才能正确进行递归调用。
相信定义：
该题：求一个式子的在不同优先级下的计算结果，就可是以每个运算符分隔开来的两个式子的和，由此递归求出结果。
//备忘录
Map<String, List<Integer>> memo = new HashMap<>();
//返回一个式子的在不同优先级下的计算结果
public List<Integer> diffWaysToCompute(String expression) {
// 避免重复计算
if (memo.containsKey(expression)) {
return memo.get(expression);
}
List<Integer> res = new ArrayList<>();
for (int i = 0; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (ch == '-' || ch == '+' || ch == '*') {
/****** 分 ******/
// 以运算符为中心，分割成两个字符串，分别递归计算
List<Integer> left = diffWaysToCompute(expression.substring(0,i));
List<Integer> right = diffWaysToCompute(expression.substring(i+1));
/****** 治 ******/
// 通过子问题的结果，合成原问题的结果
for (Integer r : right) {
for (Integer l : left) {
if (ch == '-') {
res.add(l-r);
}
if (ch == '*') {
res.add(l*r);
}
if (ch == '+') {
res.add(l+r);
}
}
}
}
}
// 如果 res 为空，说明算式是一个数字，没有运算符
if (res.isEmpty()) {
res.add(Integer.parseInt(expression));
}
memo.put(expression,res);
return res;
}
解决上述算法题利用了分治思想，以每个运算符作为分割点，把复杂问题分解成小的子问题，递归求解子问题，然后再通过子问题的结果计算出原问题的结果。把大规模的问题分解成小规模的问题递归求解
特殊的排序算法
剑指 Offer 45. 把数组排成最小的数
public String minNumber(int[] nums) {
List<String> list = new ArrayList<>();
for (int num : nums) {
list.add(String.valueOf(num));
}
list.sort((o1, o2) -> (o1 + o2).compareTo(o2 + o1));
return String.join("", list);
}
- 数组相关题目
- 56. 合并区间
- 435. 无重叠区间
- 面试题 01.08. 零矩阵
- 分治
- 169. 多数元素
- 双指针技巧
- 快慢指针常用算法
- 移除重复的元素
- 80. 删除有序数组中的重复项 II
- 283. 移动零
- 141. 判断环形链表
- 142. 环形链表 II返回环形的初始节点
- 876. 返回链表的中间结点
- 4、寻找链表的倒数第 k 个元素
- 左右指针常用算法
- 15. 三数之和
- 11. 盛最多水的容器
- 167. 两数之和 II - 输入有序数组
- 75. 颜色分类
- 27. 移除元素
- 二分查找
- 框架：
- 查找元素
- 寻找左侧边界的二分搜索
- 寻找右侧边界的二分查找
- 总结
- 例题
- 875. 爱吃香蕉的珂珂
- 1011. 在 D 天内送达包裹的能力
- 难153. 寻找旋转排序数组中的最小值
- 上一题的进阶154. 寻找旋转排序数组中的最小值 II
- 两数之和（给定的数组是有序的）
- 反转数组
- 滑动窗口常见算法
- 76. 最小覆盖子串
- 567. 字符串的排列
- 438. 找到字符串中所有字母异位词
- 3. 无重复字符的最长子串
- 209. 长度最小的子数组
- 给我 O(1) 时间，我能查找/删除数组中的任意元素
- 数组去重
- 316. 去除重复字母
- 83. 删除排序链表中的重复元素
- 26. 删除有序数组中的重复项
- 27. 移除元素
- 283. 移动零
- 小而美的算法技巧
- 前缀和数组
- 560. 和为K的子数组
- 差分数组
- 1109. 航班预订统计
- 快排亲兄弟：快速选择算法详解
- 215. 数组中的第K个最大元素
- 分治算法详解：表达式的不同优先级
- 241. 为运算表达式设计优先级
- 特殊的排序算法
- 剑指 Offer 45. 把数组排成最小的数