还是从现在开始就先刷刷经典的leetcode吧

数组 / 字符串

合并两个有序数组

双指针+辅助数组

那就经典的搞个辅助数组，然后用双指针p、q遍历数组1、2，将其中较小的放入辅助数组中，最后将辅助数组复制给数组1

逆双指针

由于题目中数组1的长度为m+n，后面的空间是空着的。那么就可以从后向前的向数组1中写入数据（从后向前的获取数组1、2中较大的数组），可以使用tmp暂存较小的数据。
也就是优化了空间复杂度

移除元素

双指针

写的时候倒是没考虑是双指针，只是想着因为删除元素不好做，那就让非val的值按顺序排列就行

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != val) {
                nums[count] = nums[i];
                count += 1;
            }
        }
        return count;
    }
}

后面看题解也确实有点双指针的意思（贴下题解的内容吧：
右指针 right 指向当前将要处理的元素，左指针 left 指向下一个将要赋值的位置。

  • 如果右指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；
  • 如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位。

整个过程保持不变的性质是：区间 [0,left) 中的元素都不等于 val。当左右指针遍历完输入数组以后，left 的值就是输出数组的长度。

删除排序数组中的重复项

感觉应该是双指针

就是用左指针标记空位，右指针遍历，当有不同的，就进行填空

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int removeDuplicates(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i] != nums[i+1]) {
                nums[++count] = nums[i+1];
            }
        }
        return count + 1;
    }
}

删除有序数组中的重复项 II

本题是将保留的项从上面的1个变动为2个，再往后肯定是还可以增加的，因此需要找到通解

宫水三叶解法

关键就在于要保留的数目k，关键思想就是要存进数组里的值 != 其index-k的值，就是间隔k不相等，关键啊（看到别人的好解法就羡慕啊，我怎么想不到😭
感觉和官方题解的双指针思想是一样的，就是写法不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int removeDuplicates(int[] nums) {
        return process(nums, 2);
    }

    public int process(int[] nums, int k){
        int u = 0; //数组下标
        for(int x: nums){
            if(u<k || nums[u-k] != x){//前k个直接存，后续的与距离为k的比较，不等就存
                nums[u++] = x;
            }
        }
        return u;
    }
}

多数元素

也就是求众数

哈希表统计法

记得408书上好像也有这题，当时好像是用int[nums中的最大数]来代替哈希表的，反正思想是一样的。都是对num出现的次数建立索引，然后遍历哈希表，随便写个伪代码吧

1
2
3
4
5
6
7
Init：
	map、half
Process：
	for num of nums:
	  map[num]++
	  if(map[num]>half)
	  	return num

排序法

有点取巧。思路就是如果数组里有众数，那么排序后中间的数就是众数

摩尔投票法（精彩

先大致说下思路，总体来说就是如果有众数，把众数视为+1，其他视为-1，最后的结果肯定>0
且数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n−a) 个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的 众数仍为 x 。基于此便是摩尔投票法
随便写个伪代码

1
2
3
4
5
6
7
count = 0
candidate = 0
for num of nums:
	if count == 0:
		condidate = num
	count += (num == candidate) : 1 : -1
return candidate

轮转数组

辅助数组

使用辅助数组保存旋转后的数组即可

数组翻转

有点找规律的意思吧，反正你只要意识到就能做
向右轮转 k 个位置 就等于

  1. 翻转整个数组
  2. 翻转前k个、后n-k个
    what can i say？

买卖股票的最佳时机

这一题不断进阶，但都能用动态规划做
最简单的情况是某天买入某天卖， 只需计算出以前的最低，然后不断更新就行了

动态规划

经典解法，但我目前有点看不懂且不想看

跳跃游戏

意识到当前能跳的距离是nums[i]+i以及只要有一种路线能到终点就返回true还是挺容易的，但是写出来循环和终止条件的算法就比较难了

贪心

这题是贪心，思路就是在可以达到的范围内，如果最大能跳的距离（不断维护更新）能 >= len-1就返回true。从i=1到n不难想，关键在于 if (i <= remote) {remote = Math.max(remote, nums[i] + i);}这个才是精髓

跳跃游戏 II

双指针

验证回文串

方法毫无疑问最好是用双指针。当然也可以取巧，将字符串中的其他符合去除并小写后，判断反转后的数组是否相等即可。感觉这个双指针的写法很经典（想起了快排的算法，简略贴下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while (i < j) {
	while (i < j && !Character.isLetterOrDigit(s.charAt(i)))
		i++;
    while (i < j && !Character.isLetterOrDigit(s.charAt(j)))
        j--;
    if (i < j) {
        if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
        	return false;
         	}
         i++;
         j--;
     }
}
return true;

判断子序列

双指针

这里最容易想到的方法就是用两个指针依次遍历两个字符串，去判断字符是否相等。写的时候对于返回条件稍微绕了个弯，我是用count变量计算相等的数目，然后判断 它 == s.length()；看了题解发现还可以用 i == s.length()（因为如果完全匹配了，最后i还会+1的

动态规划

byd万物可动态规划是吧
不太想看
进阶题似乎也挺有意思的，也不想看

两数之和 II - 输入有序数组

双指针来做还是比较简单容易想到解法的

滑动窗口

长度最小的子数组

经典滑动窗口问题，贴一下代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int i = 0, j = 0, sum = 0;
        while (j < nums.length) {
            sum += nums[j];
            while (sum >= target) {
                res = Math.min(res, j - i + 1);
                sum -= nums[i];
                i++;
            }
            j++;
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}