704.二分查找
简单题，使用常见的二分查找即可，注意while的判断条件为start<=end即可
public int search(int[] nums, int target) {
int len = nums.length;
int start = 0;
int end = len - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (nums[mid] == target) return mid;
if (target < nums[mid])
end = mid - 1;
if (target > nums[mid])
start = mid + 1;
}
return -1;
}
时间复杂度：O(logn)
空间复杂度：O(1)
27.移除元素
使用暴力解法的话，一个for循环遍历数组，另一个for循环将当前要删除的元素后面的元素往前移动，推荐使用双指针解法。
fast指针遍历数组中的元素，也可以理解为寻找新数组中的元素。
新数组是指删除掉全部值为val的元素的数组。
slow指针指向新数组最后一个元素的下一个位置，理解为指向更新位置。循环里面逻辑如下：
如果nums不等于val，则将nums[fast]赋值给nums[slow]，然后slow指针后移，最后slow会等于新数组长度。
public int removeElement(int[] nums, int val) {
//新数组是删除掉所有等于val的数之后的数组
int slow = 0; //slow指向新数组的最后一个元素的下一个元素
for (int fast = 0; fast < nums.length; fast++) { //fast用来搜索新数组的元素
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
977.有序数组的平方
最简单的方法，对数组中的每个元素进行平方后对整个数组进行快排，快排可以调用java的Arrays.sort()，但是时间复杂度是O(n + nlogn)，达不到要求。
使用双指针法，关键思想：新建立一个新数组result存放排好序的元素，因为元素是非降序的，所以数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
i指向原数组的左端，j指向原数组的右端，k指向新数组的末尾。
如果nums[i] * nums[i] > nums[j] * nums[j]，则result[k] = nums[i] * nums[i]，i往右移，k往左移。否则result[k] = nums[j] * nums[j]，j往左移，k往左移。
注意整个while循环的判断条件为k>=0。
public int[] sortedSquares(int[] nums) {
//关键思想：原来数组是非降序的情况下，数组的平方的最大值一定是在数组的两侧，不是在左边就是在右边
int i = 0, j = nums.length - 1, k = nums.length - 1;
int[] result = new int[nums.length];
while (k >= 0) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
result[k--] = nums[i] * nums[i];
i++;
} else {
result[k--] = nums[j] * nums[j];
j--;
}
}
return result;
}
209.长度最小的子数组
直接使用暴力的解法，时间复杂度为O(n^2)，达不到要求的O(n)。思路是使用2个for循环寻找所有符合条件的子数组，i代表子数组的起始位置，j代表子数组的结尾，当前起始位置找到后直接break找下一个起始位置（因为要求的是最短子数组）。代码如下：
public int force(int target, int[] nums) {
int result = Integer.MAX_VALUE; //用来存储最终的返回结果
int subLen = 0; //子数组的长度
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum = 0; //每次开始寻找新的子数组都要先将sum置为0
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum >= target) { //符合条件
subLen = j - i + 1; //计算子数组的长度
result = subLen < result ? subLen : result;
break; //符合条件的话当前其实位置不用再继续往下找了，因为求的是最短子数组
}
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
O(n)级别的算法使用滑动窗口算法，难点在于滑动窗口起点和终点的更新（最外层的for循环是end还是start）。
起点start：如果sum >= target，start就要往后移（滑动窗口该缩小了）。
终点end：遍历整个数组，即最外层的for循环的指针。
更新start的时候使用的是while不是if，因为对于[1,1,1,1,100]的这种情况，start可能在固定end的情况下连续后移。
start在移动之前，需要在sum减去当前位置的值，即sum-=nums[start]。
public int minSubArrayLen(int target, int[] nums) {
int i = 0, j;
int sum = 0;
int result = Integer.MAX_VALUE;
int subLen = 0;
for (j = 0; j < nums.length; j++) {
sum += nums[j];
while (sum >= target) { //注意这里是要持续性地将i向后移动，所以使用while而不用if
subLen = j - i + 1;
result = subLen < result ? subLen : result;
sum -= nums[i]; //在往后移动的时候还要减去之前位置的值
i++;
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
59.螺旋矩阵Ⅱ
主要是模拟这个打印过程，属于模拟类型的题目，关键在于处理开区间和闭区间。按习惯使用左闭右开。按下图进行理解。
分析知道要转n/2圈，如果n是奇数，还会存在中心点需要额外处理。先定义几个变量：
startx，starty：每一圈的起始点，初始为（0，0），进入下一圈要加一。
count：用来计数，1~n^2。
i，j：索引，用来遍历每个点。
offset：每一圈的偏移量，例如第一圈上面的边要去掉最后一个位置，所以第一圈的offset为1，进入下一圈要加一。
难点在于for循环的判断条件。因为有上下左右4个方向，所以是一个while循环里面嵌套4个for循环。
public int[][] generateMatrix(int n) {
int[][] nums = new int[n][n];
int loop = n / 2; //要转多少圈
int startx = 0, starty = 0; //每个loop的起始点
int offset = 1; //每圈的偏移量，例如第一圈上面的边要去掉最后一个节点，所以offset为1
int count = 1; //用来计数，1~n^2
int i, j;
while (loop-- != 0) {
//处理上面
for (j = starty; j < n - offset; j++)
nums[startx][j] = count++;
//处理右边
for (i = startx; i < n - offset; i++)
nums[i][j] = count++;
//处理下面
for (; j > starty; j--)
nums[i][j] = count++;
//处理左边
for (; i > startx; i--)
nums[i][j] = count++;
offset++;
startx++;
starty++;
}
if (n % 2 == 1) {
nums[startx][starty] = count;
}
return nums;
}
75.颜色分类
单指针法，两个for循环，第一个for循环将0交换到前面，第二个for循环将1交换到前面，剩下后面的都是2。ptr指向头部（第一次头部是全为0的数组，第二次是全为1的数组），每次交换后ptr要往后移。
public void sortColors(int[] nums) {
int ptr = 0; //指向头部，第一个for循环头部是全为0数组，第二个是全为1的数组
int temp;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
//将为0的元素交换到头部
temp = nums[ptr];
nums[ptr] = nums[i];
nums[i] = temp;
//ptr往后移动
ptr++;
}
}
for (int i = ptr; i < nums.length; i++) {
if (nums[i] == 1) {
//将为1的元素交换到头部
temp = nums[ptr];
nums[ptr] = nums[i];
nums[i] = temp;
//ptr右移
ptr++;
}
}
}
395.至少有k个重复字符的最长字符串
这道题在leetcode的题解上使用两种解法，分别为分治和滑动窗口，这里使用了滑动窗口。滑动窗口实现的逻辑较为复杂，建议还是使用分治。
关键在于如何枚举子串（即滑动窗口）。最简单的就是枚举所有的子串然后判断它们是否符合条件，当然会超时。
最外层的for循环，遍历该字符串可能包含的字符种类t。因为有26个英文字母，所以使用遍历的范围为1~26。
for循环里面要定义以下几个变量：
left，right：子串的左右边界，初始化为0；
cnt：一个记录子串中每种字符的出现次数的数组，长度为26；
total：子串内部的字符种类数目；
less：当前子串出现次数 在for循环内部，使用两个while循环来遍历right和left，遍历left的while是嵌套在right里面的。 第一个while：当right<原字符串的长度。 第二个while：当子串内部的字符种类数目 > t。 每次移动right和left都要更新cnt（子串中每种字符的出现次数）。 对于移动right的情况： 如果当前右边界对应的字符出现次数 == 1（某个字符出现的次数从0->1），则total++（代表有新字符出现在该子串），less++（这里不是很明白）。 如果当前右边界对应的字符出现次数 == k （某个字符出现的次数从k-1->k），则less--（不再小于k）。 移动左边界也是类似的逻辑。left的while循环的判断条件是total > t，因为这样对于任何一个right，都可以找到lmin，使得s[lmin...right]之间的字符种类数目不大于t（跳出while后total <= t，这里想一下应该可以明白了）。 public int longestSubstring(String s, int k) { int result = 0; //记录最终返回的结果 int len = s.length(); for (int t = 1; t <= 26; t++) { int left = 0, right = 0; int[] cnt = new int[26]; //cnt代表子串每种字符的出现次数，使用一个数组来记录，英文字母有26个所以长度为26 int total = 0, less = 0; //total代表子串内部的字符种类数目，less代表当前出现次数 while (right < len) { //第一个while，移动right cnt[s.charAt(right) - 'a']++; //更新cnt，出现次数加一 //对于移动右边界right的情况而言 if (cnt[s.charAt(right) - 'a'] == 1) { total++; //如果出现次数为1，表示有新字符出现，total要加一 less++; //小于k的字符数量+1（不明白） } if (cnt[s.charAt(right) - 'a'] == k) { less--; //等于k表示不再小于k，所以要-1 } while (total > t) { //第二个while，移动left cnt[s.charAt(left) - 'a']--; if (cnt[s.charAt(left) - 'a'] == k - 1) { less++; } if (cnt[s.charAt(left) - 'a'] == 0) { total--; less--; } left++; //left右移 } if (less == 0) { //如果该子串符合条件 result = Math.max(result, right - left + 1); } right++; //right右移 } } return result; } 相关链接
您阅读本篇文章共花了：
发表评论