力扣题目链接
题目
给定一个 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]之间。
思路
我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。
区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：
while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
例如在数组：1,2,3,4,7,9,10中查找元素2，如图所示：
代码实现
public class _704_二分查找 { public int search(int[] nums, int target) { if (target < nums[0] || target > nums[nums.length - 1]) { return -1; } int left = 0; // 定义target在左闭右闭的区间里，[left, right] int right = nums.length - 1; // 当left==right，区间[left, right]依然有效，所以用 <= while (left <= right) { // 防止溢出 等同于(left + right)/2 int mid = left + ((right - left) / 2); if (nums[mid] > target) { // target 在左区间，所以[left, middle - 1] right = mid - 1; } else if (nums[mid] < target) { // target 在右区间，所以[middle + 1, right] left = mid + 1; } else { // nums[middle] == target return mid; // 数组中找到目标值，直接返回下标 } } // 未找到目标值 return -1; }}
35、搜索插入位置力扣题目链接
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2输出: 1
提示
1 <= nums.length <= 104-104 <= nums[i] <= 104nums 为无重复元素的升序排列数组-104 <= target <= 104
代码实现
public class _35_搜索插入位置 { public int searchInsert(int[] nums, int target) { int n = nums.length; int left = 0; // 定义target在左闭右闭的区间里，[left, right] int right = n - 1; // 当left==right，区间[left, right]依然有效 while (left <= right) { // 防止溢出 等同于(left + right)/2 int mid = left + ((right - left) / 2); if (nums[mid] > target) { // target 在左区间，所以[left, mid - 1] right = mid - 1; } else if (nums[mid] < target) { // target 在右区间，所以[mid + 1, right] left = mid + 1; } else { // nums[mid] == target return mid; } } // 分别处理如下四种情况 // 目标值在数组所有元素之前 [0, -1] // 目标值等于数组中某一个元素 return middle; // 目标值插入数组中的位置 [left, right]，return right + 1 // 目标值在数组所有元素之后的情况 [left, right]， return right + 1 return right + 1; }}
34、在排序数组中查找元素的第一个和最后一个位置力扣题目链接
题目
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 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] <= 109nums 是一个非递减数组-109 <= target <= 109
思路
寻找target在数组里的左右边界，有如下三种情况：
情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
这三种情况都考虑到，说明就想的很清楚了。
代码实现
public class _34_在排序数组中查找元素的第一个和最后一个位置 { public int[] searchRange(int[] nums, int target) { int leftBorder = getLeftBorder(nums, target); int rightBorder = getRightBorder(nums, target); // 情况一 if (leftBorder == -2 || rightBorder == -2) { return new int[]{-1, -1}; } // 情况三 if (rightBorder - leftBorder > 1) { return new int[]{leftBorder + 1, rightBorder - 1}; } // 情况二 return new int[]{-1, -1}; } // 二分查找，寻找target的右边界（不包括target） // 如果rightBorder为没有被赋值（即target在数组范围的左边，例如数组[3,3]，target为2），为了处理情况一 public int getRightBorder(int[] nums, int target) { int left = 0; // 定义target在左闭右闭的区间里，[left, right] int right = nums.length - 1; // 记录一下rightBorder没有被赋值的情况 int rightBorder = -2; while (left <= right) { // 当left==right，区间[left, right]依然有效 // 防止溢出 等同于(left + right)/2 int mid = left + ((right - left) / 2); if (nums[mid] > target) { // target 在左区间，所以[left, middle - 1] right = mid - 1; } else { // 当nums[mid] == target的时候，更新left，这样才能得到target的右边界 left = mid + 1; rightBorder = left; } } return rightBorder; } // 二分查找，寻找target的左边界leftBorder（不包括target） // 如果leftBorder没有被赋值（即target在数组范围的右边，例如数组[3,3],target为4），为了处理情况一 public int getLeftBorder(int[] nums, int target) { int left = 0; // 定义target在左闭右闭的区间里，[left, right] int right = nums.length - 1; // 记录一下leftBorder没有被赋值的情况 int leftBorder = -2; while (left <= right) { int mid = left + ((right - left) / 2); if (nums[mid] < target) { left = mid + 1; } else { // 寻找左边界，就要在nums[mid] == target的时候更新right right = mid - 1; leftBorder = right; } } return leftBorder; }}
69、x 的平方根力扣题目链接
题目
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4输出：2
示例 2：
输入：x = 8输出：2解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：
0 <= x <= 231 - 1
思路
整数x的平方根一定小于或等于x除0之外的所有整数的平方根都大于或等于1整数x的平方根一定是在1到x的范围内，取这个范围内的中间数字mid，并判断mid的平方是否小于或等于x，如果mid的平方小于x
那么接着判断(mid+1)的平方是否大于x，如果(mid+1)的平方大于x，那么mid就是x的平方根 如果mid的平方小于x并且(mid+1)的平方小于x，那么x的平方根比mid大，接下来搜索从mid+1到x的范围如果mid的平方大于x，则x的平方根小于mid，接下来搜索1到mid-1的范围然后在相应的范围内重复这个过程，总是取出位于范围中间的mid
代码实现
public class _69_x的平方根 { public int mySqrt(int x) { // 整数x的平方根一定是在1到x的范围内 int left = 1; int right = x; while (left <= right) { // 中间值 下面这样写是防止溢出 int mid = left + ((right - left) / 2); // 判断mid的平方是否小于或等于x，如果mid的平方小于x if (mid <= x / mid) { // 等价于：mid * mid <= x // 判断(mid+1)的平方是否大于x，如果(mid+1)的平方大于x，那么mid就是x的平方根 if ((mid + 1) > x / (mid + 1)) { return mid; } // 如果mid的平方小于x并且(mid+1)的平方小于x，那么x的平方根比mid大，接下来搜索从mid+1到x的范围 left = mid + 1; } else if (mid > x / mid) { // 等价于：mid * mid > x // 如果mid的平方大于x，则x的平方根小于mid，接下来搜索1到mid-1的范围 right = mid - 1; } } // 如果输入参数是0，left等于1而right等于0，就直接返回0 return 0; }}
367、有效的完全平方数力扣题目链接
题目
给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
进阶：不要 使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16输出：true
示例 2：
输入：num = 14输出：false
提示：
1 <= num <= 2^31 - 1
代码实现
public class _367_有效的完全平方数 { public boolean isPerfectSquare(int num) { long left = 1; long right = num; while (left <= right) { long mid = left + ((right - left) / 2); long res = mid * mid; if (res == num) { return true; } else if (res < num) { left = mid + 1; } else { // res > num right = mid - 1; } } return false; }}
27、移除元素力扣题目链接
题目
给你一个数组 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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
思路
代码实现
public class _27_移除元素 { public int removeElement(int[] nums, int val) { // 快慢指针 int slow = 0; int fast = 0; while (fast < nums.length) { if (nums[fast] != val) { nums[slow] = nums[fast]; slow++; } fast++; } return slow; }}
26、删除有序数组中的重复项力扣题目链接
题目
给你一个有序数组 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 。不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 10^4-10^4 <= nums[i] <= 10^4nums 已按升序排列
代码实现
public class _26_删除有序数组中的重复项 { public int removeDuplicates(int[] nums) { if (nums.length == 0) { return 0; } int slow = 0; int fast = 0; while (fast < nums.length) { if (nums[fast] != nums[slow]) { slow++; // 维护 nums[0..slow] ⽆重复 nums[slow] = nums[fast]; } fast++; } // 数组⻓度为索引 + 1 return slow + 1; }}
283、移动零力扣题目链接
题目
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]输出: [0]
提示 :
1 <= nums.length <= 10^4-2^31 <= nums[i] <= 2^31 - 1
代码实现
public class _283_移动零 { public void moveZeroes(int[] nums) { int n = nums.length; int slow = 0; int fast = 0; while (fast < n) { if (nums[fast] != 0) { nums[slow] = nums[fast]; slow++; } fast++; } while (slow < n) { nums[slow] = 0; slow++; } }}
844、比较含退格的字符串力扣题目链接
题目
给定 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 只含有小写字母以及字符 '#'
代码实现
public class _844_比较含退格的字符串 { public boolean backspaceCompare(String s, String t) { char[] sarr = s.toCharArray(); char[] tarr = t.toCharArray(); // 求出s的结果字符串 int slow = 0; int fast = 0; while (fast < s.length()) { if (sarr[fast] != '#') { sarr[slow] = sarr[fast]; slow++; } else if (sarr[fast] == '#' && slow > 0) { slow--; } fast++; } int sLength = slow; // 求出t的结果字符串 slow = 0; fast = 0; while (fast < t.length()) { if (tarr[fast] != '#') { tarr[slow] = tarr[fast]; slow++; } else if (tarr[fast] == '#' && slow > 0) { slow--; } fast++; } int tLength = slow; if (sLength != tLength) { return false; } for (int i = 0; i < sLength; i++) { if (sarr[i] != tarr[i]) { return false; } } return true; }}
977、有序数组的平方力扣题目链接
题目
给你一个按 非递减顺序 排序的整数数组 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 <= 10^4-10^4 <= nums[i] <= 10^4nums 已按 非递减顺序 排序
思路
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，left指向起始位置，right指向终止位置。
定义一个新数组 res，和A数组一样的大小，让 j 指向 res 数组终止位置。
代码实现
public class _977_有序数组的平方 { public int[] sortedSquares(int[] nums) { int left = 0; int right = nums.length - 1; int[] res = new int[nums.length]; int j = nums.length - 1; while (left <= right) { if (nums[left] * nums[left] > nums[right] * nums[right]) { res[j] = nums[left] * nums[left]; j--; left++; } else { res[j] = nums[right] * nums[right]; j--; right--; } } return res; }}
209、长度最小的子数组力扣题目链接
题目
给定一个含有 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 <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^5
思路
以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下查找的过程：
最后找到 4，3 是最短距离。
代码实现
public class _209_长度最小的子数组 { public int minSubArrayLen(int target, int[] nums) { int left = 0; // 滑动窗口起始位置 int sum = 0; // 滑动窗口数值之和 int result = Integer.MAX_VALUE; for (int right = 0; right < nums.length; right++) { sum += nums[right]; // 注意这里使用while，每次更新 left（起始位置），并不断比较子序列是否符合条件 while (sum >= target) { result = Math.min(result, right - left + 1); sum -= nums[left]; left++; } } // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列 return result == Integer.MAX_VALUE ? 0 : result; }}
904、水果成篮力扣题目链接
题目
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
示例 1：
输入：fruits = [1,2,1]输出：3解释：可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2]输出：3解释：可以采摘 [1,2,2] 这三棵树。如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入：fruits = [1,2,3,2,2]输出：4解释：可以采摘 [2,3,2,2] 这四棵树。如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]输出：5解释：可以采摘 [1,2,1,1,2] 这五棵树。
提示：
1 <= fruits.length <= 10^50 <= fruits[i] < fruits.length
代码实现
public class _904_水果成篮 { public int totalFruit(int[] fruits) { HashMap
力扣题目链接
题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"
示例 2：
输入：s = "a", t = "a"输出："a"
示例 3:
输入: s = "a", t = "aa"输出: ""解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
提示：
1 <= s.length, t.length <= 10^5s 和 t 由英文字母组成
代码实现
public class _76_最小覆盖子串 { public String minWindow(String s, String t) { HashMap
力扣题目链接
题目
给你一个正整数 n，生成一个包含 1到 n^2所有元素，且元素按顺时针顺序螺旋排列的 n x n正方形矩阵 matrix。
示例 1：
输入：n = 3输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1输出：[[1]]
提示：
1 <= n <= 20
思路
生成一个 n×n 空矩阵 mat，随后模拟整个向内环绕的填入过程：
定义当前左右上下边界 l,r,t,b，初始值 num = 1，迭代终止值 tar = n * n；当 num <= tar 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后：
执行 num += 1：得到下一个需要填入的数字；更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。 使用num <= tar而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。 最终返回 mat 即可。
代码实现
public class _59_螺旋矩阵_II { public int[][] generateMatrix(int n) { int[][] res = new int[n][n]; int l = 0; // 左 int r = n - 1; // 右 int t = 0; // 上 int b = n - 1; // 下 int num = 1, tar = n * n; while (num <= tar) { for (int i = l; i <= r; i++) { res[t][i] = num++; // left to right. } t++; for (int i = t; i <= b; i++) { res[i][r] = num++; // top to bottom. } r--; for (int i = r; i >= l; i--) { res[b][i] = num++; // right to left. } b--; for (int i = b; i >= t; i--) { res[i][l] = num++; // bottom to top. } l++; } return res; }}
54、螺旋矩阵力扣题目链接
题目
给你一个 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.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
代码实现
public class _54_螺旋矩阵 { public List
力扣题目链接
题目
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 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]
限制：
0 <= matrix.length <= 1000 <= matrix[i].length <= 100
代码实现
public class _剑指Offer29_顺时针打印矩阵 { public int[] spiralOrder(int[][] matrix) { int m = matrix.length; //行 if (m == 0) { return new int[0]; } int n = matrix[0].length; //列 int[] res = new int[m * n]; int t = 0; // 上 int b = m - 1; // 下 int l = 0; // 左 int r = n - 1; // 右 int index = 0; while (true) { for (int i = l; i <= r; i++) { res[index++] = matrix[t][i]; // left to right. } t++; if (t > b) { break; } for (int i = t; i <= b; i++) { res[index++] = matrix[i][r]; // top to bottom. } r--; if (r < l) { break; } for (int i = r; i >= l; i--) { res[index++] = matrix[b][i]; // right to left. } b--; if (b < t) { break; } for (int i = b; i >= t; i--) { res[index++] = matrix[i][l]; // bottom to top. } l++; if (l > r) { break; } } return res; }}