跟着卡哥的刷题路线，为了巩固知识点，一周做一次力扣刷题总结，每道题我都会将原题写出来，写出我的解题思路，核心代码，时间复杂度和空间复杂度，如果有错误的地方也欢迎大家指正
本周小节
本周做完了数组模块的训练，收获满满。
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：
- 你可以假设
nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
解题思路
因为数组是有序并且无重复元素的所以使用双指针这也是使用双指针的条件，int miidle = left + (right - left) / 2防止超过int类型的范围
核心代码
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1, flag = -1;
while(left <= right) {
int miidle = left + (right - left) / 2;
if(nums[miidle] == target) {
flag = miidle;
break;
}
if(nums[miidle] > target) {
right = miidle - 1;
continue;
}
if(nums[miidle] < target) {
left = miidle + 1;
continue;
}
}
return flag;
}
}
时间复杂度
O(log n)，总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
由于n/2k取整后>=1，即令n/2k=1，可得k=logn,（是以2为底，n的对数），所以时间复杂度可以表示O(logn)
空间复杂度
O(1)
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0
示例 5:
输入: nums = [1], target = 0
输出: 0
提示:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums 为无重复元素的升序排列数组
- -104 <= target <= 104
解题思路
在原本二分查找的基础上还需要将数组查找不到的元素返回插入位置的索引，二分查找关于区间的定义，本题我们采用左闭右闭的区间且left <= right有意义，因为在最后二分查找结束后left指针一定指向插入位置
核心代码
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int middle = left + (right - left) / 2;
if(nums[middle] == target) {
return middle;
}
if(nums[middle] > target) {
right = middle - 1;
continue;
}
if(nums[middle] < target) {
left = middle + 1;
continue;
}
}
return left;
}
}
时间复杂度
O(log n)，总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
由于n/2k取整后>=1，即令n/2k=1，可得k=logn,（是以2为底，n的对数），所以时间复杂度可以表示O(logn)
空间复杂度
O(1)
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums 是一个非递减数组
- -109 <= target <= 109
解题思路
因为是非递减无重复数组所以可以使用双指针，寻找数组的左边界和右边界，寻找右边界的时候让左指针移动因为只有左指针可以记录元素最后出现的位置，反之寻找左边界就让右指针移动因为只有右指针可以记录元素最开始出现的位置，我就只说明左指针寻找右边界的原因了，二分查找的基础上如果中间值小于等于目标值那么就记录其下标，这样做可以记录元素出现的最后一次位置的右边，如果没有该元素可以记录该元素插入的位置。右指针寻找左边界也是同样的道理。
核心代码
class Solution {
public int[] searchRange(int[] nums, int target) {
int rightBorder = searchRight(nums,target);
int leftBorder = searchLeft(nums,target);
if(rightBorder == -2 || leftBorder == -2) {
return new int[]{-1,-1};
} else if(rightBorder - leftBorder > 1) {
return new int[]{leftBorder + 1,rightBorder - 1};
} else {
return new int []{-1, -1};
}
}
public int searchRight(int[] nums, int target) {
int left = 0, right = nums.length -1, flag = -2;
while(left <= right) {
int middle = left + (right - left) / 2;
if(nums[middle] <= target) {
left = middle + 1;
flag = left;
} else {
right = middle - 1;
}
}
return flag;
}
public int searchLeft(int[] nums, int target) {
int left = 0, right = nums.length - 1, flag = -2;
while(left <= right) {
int middle = left + (right - left) / 2;
if(nums[middle] >= target) {
right = middle - 1;
flag = right;
} else {
left = middle + 1;
}
}
return flag;
}
}
时间复杂度
O(log n)
空间复杂度
O(1)
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
解题思路
这道题和34题很像，不过不同的是34题寻找的是左右边界而这道题寻找的是左边界，值得注意的是判断算数平方根的条件是x / middle < middle防止越界
核心代码
class Solution {
public int mySqrt(int x) {
int left = 1, right = x / 2;
if(x == 0) {
return 0;
}
if(x == 1) {
return 1;
}
while(left <= right) {
int middle = left + (right - left) / 2;
if(x / middle < middle) {
right = middle - 1;
} else if(x / middle == middle){
return middle;
} else {
left = middle + 1;
}
}
return right;
}
}
时间复杂度
O(log n)
空间复杂度
O(1)
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
示例 2：
输入：num = 14
输出：false
提示：
解题思路
这道题和69题很像不同的是这题是判断是否为完全平方数所以在69题的基础上还要多加一层判断num % middle == 0来确定是否为完全平方数，如果不加这一层判断那么像21478367 / 4634 = 4634就会判错
核心代码
class Solution {
public boolean isPerfectSquare(int num) {
if(num == 1) {
return true;
}
int left = 1, right = num / 2;
while(left <= right) {
int middle = left + (right - left) / 2;
if(num / middle < middle) {
right = middle - 1;
} else if (num / middle == middle && num % middle == 0) {
return true;
} else {
left = middle + 1;
}
}
return false;
}
}
时间复杂度
O(log n)
空间复杂度
O(1)
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104-104 <= nums[i] <= 104nums 已按 非递减顺序 排序
解题思路
因为数组是有序非递减的，用双指针分别指向数组头部和数组尾部，比较两数平方的大小，让大的数字加入新的数组，移动指针继续进行比较
核心代码
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0, right = nums.length - 1,k = right;
int[] newNums = new int[nums.length];
while(left <= right) {
if(absolute(nums[left]) > absolute(nums[right])) {
newNums[k] = square(nums[left]);
left++;
} else {
newNums[k] = square(nums[right]);
right--;
}
k--;
}
return newNums;
}
public int absolute(int num) {
return num > 0 ? num : -num;
}
public int square(int num) {
return num * num;
}
}
时间复杂度
O(log n)
空间复杂度
O(n)，内存开销随着数组的大小而发生改变
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
解题思路
数组元素的删除只能覆盖不能删除，双指针删除元素的原理在于两个指针的错位，在没有查找到目标时两个指针从相同的起点同速度出发，当遍历到需要删除的结点的时候，使一个指针停留在删除元素的位置让另一个指针继续移动，下次循环就会直接覆盖删除元素
核心代码
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0;
for(int fast = 0;fast < nums.length;fast++) {
if(nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
}
时间复杂度
O(n)
空间复杂度
O(1)
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
解题思路
和27题思路一致不同的在于对错位的操作，因为需要删除重复项所以应该保留一个元素所以慢指针的移动为++slow，
核心代码
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 0;
for(int fast = 0; fast < nums.length; fast++) {
if(nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
}
时间复杂度
O(n)
空间复杂度
O(1)
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
解题思路
这道题和移除元素基本一致，只是需要将剩余的数组元素置为0
核心代码
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
for(int fast = 0; fast < nums.length; fast++) {
if(nums[fast] != 0) {
nums[slow++] = nums[fast];
}
}
for(int i = slow;i < nums.length; i++) {
nums[i] = 0;
}
}
}
时间复杂度
O(n)
空间复杂度
O(1)
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
示例 1：
输入：s = "ab#c", t = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 “”。
示例 3：
输入：s = "a##c", t = "#a#c"
输出：true
解释：s 和 t 都会变成 “c”。
示例 4：
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。
提示：
1 <= s.length, t.length <= 200s 和 t 只含有小写字母以及字符 '#'
解题思路
这道题和1047. 删除字符串中的所有相邻重复项基本一致，总共有三种解题思路
- 双指针，双指针从后往前遍历， 双指针从后往前遍历？为什么是从后往前而不是向往常题一样从前往后呢？因为#代表的是退格，#取决于退格的个数但是消除元素却不一定能和#匹配
- 栈，让字符串依次进栈，如果遇到’#'就弹出，最后栈中剩余元素就是删除后的字符串
- 用StringBuffer模拟栈
核心代码
这里只提供一种解题思路的代码
class Solution {
public boolean backspaceCompare(String s, String t) {
s = remove(s);
t = remove(t);
return s.equals(t);
}
public String remove(String s) {
LinkedList<Character> c = new LinkedList<>();
char temp;
for(int i = 0; i < s.length(); i++) {
temp = s.charAt(i);
if(temp != '#') {
c.push(temp);
} else if(!c.isEmpty() && temp == '#'){
c.pop();
}
}
String result = "";
while(!c.isEmpty()) {
result += c.pop();
}
return result;
}
}
时间复杂度
O(n)
空间复杂度
O(n)
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
解题思路
对于查找连续符合题意的字符串或是数组滑动窗口的思想很好用，通过一直右移右窗口直到满足题目要求，再移动左窗口直到不符合要求，然后再移动右窗口直到遍历完所有元素
核心代码
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0;
int sum = 0;
int min = 10000;
while(right < nums.length) {
sum += nums[right];
while(sum >= target) {
if(right - left + 1 < min)
min = right - left + 1;
sum -= nums[left++];
}
right++;
}
return min == 10000 ? 0 : min;
}
}
时间复杂度
O(n)，滑动窗口的时间复杂度是个小难点为什么循环嵌套不是O(n^2)呢？因为实际上每个元素都只是操作了两次即2n
空间复杂度
O(1)
滑动窗口类型题的关键在于剥丝抽茧明白何时移动左窗口
在一排树中，第 i 棵树产生 tree[i] 型的水果。
你可以从你选择的任何树开始，然后重复执行以下步骤：
-
把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。 -
移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。
你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果树的最大总量是多少？
示例 1：
输入：[1,2,1]
输出：3
解释：我们可以收集 [1,2,1]。
示例 2：
输入：[0,1,2,2]
输出：3
解释：我们可以收集 [1,2,2]
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。
示例 3：
输入：[1,2,3,2,2]
输出：4
解释：我们可以收集 [2,3,2,2]
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。
示例 4：
输入：[3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：我们可以收集 [1,2,1,1,2]
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 棵水果树。
提示：
1 <= tree.length <= 400000 <= tree[i] < tree.length
解题思路
这道题描述很不友好，总结下来就是求两个连续元素的最长子序列最后要得到两个序列长度的和，我们可以使用哈希表来模拟篮子，依次遍历数组元素，如果哈希表中存在这个key那么就让value+1否则就将键值对加入哈希表中，判断哈希表的大小，如果大于2那么就移动左窗口逐个删除元素直到哈希表的大小为2。
核心代码
class Solution {
public int totalFruit(int[] fruits) {
int left = 0, right = 0;
int result = 0;
HashMap<Integer,Integer> map = new HashMap<>();
while(right < fruits.length) {
if(map.containsKey(fruits[right])) {
map.replace(fruits[right],map.get(fruits[right]) + 1);
} else {
map.put(fruits[right],1);
}
while(map.size() > 2) {
map.replace(fruits[left],map.get(fruits[left]) - 1);
if(map.get(fruits[left]) == 0) {
map.remove(fruits[left]);
}
left++;
}
result = Math.max(result,right - left + 1);
right++;
}
return result;
}
}
时间复杂度
O(n)
空间复杂度
O(n)
这道题拿下以后59. 螺旋矩阵 II和剑指 Offer 29. 顺时针打印矩阵也是直接简单做掉
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 10
- -100 <= matrix[i][j] <= 100
解题思路
模拟题，我们的思路是一圈一圈的遍历，对于特殊情况一行或者一列的这种二维数组，我们使用一个numEle来记录多少个元素防止重复添加
核心代码
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
LinkedList<Integer> result = new LinkedList<>();
if (matrix == null || matrix.length == 0) return result;
int left = 0;
int right = matrix[0].length - 1;
int top = 0;
int bottom = matrix.length - 1;
int numEle = matrix.length * matrix[0].length;
while (numEle >= 1) {
for (int i = left; i <= right && numEle >= 1; i++) {
result.add(matrix[top][i]);
numEle--;
}
top++;
for (int i = top; i <= bottom && numEle >= 1; i++) {
result.add(matrix[i][right]);
numEle--;
}
right--;
for (int i = right; i >= left && numEle >= 1; i--) {
result.add(matrix[bottom][i]);
numEle--;
}
bottom--;
for (int i = bottom; i >= top && numEle >= 1; i--) {
result.add(matrix[i][left]);
numEle--;
}
left++;
}
return result;
}
}
时间复杂度
O(m * n)，本题的时间复杂度取决于数组的大小
空间复杂度
O(m * n)
总结
本来数组模块这周日就已经刷完了但是一边每天抽出时间刷题一边学习JVM，刷题总结就一直没有落实。导致这份总结迟到了四天，今天才好不容易学完康师傅的JVM后才补齐，这周已经把卡哥的链表的模块刷完了争取这周刷题总结不迟到。
|