算法练习

链接：https://leetcode.cn/problems/binary-search

给定一个 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]之间。

链接：https://leetcode.cn/problems/find-smallest-letter-greater-than-target

给你一个字符数组 letters，该数组按非递减顺序排序，以及一个字符 target。letters 里至少有两个不同的字符。

返回 letters 中大于 target 的最小的字符。如果不存在这样的字符，则返回 letters 的第一个字符。

示例 1：

输入: letters = [“c”, “f”, “j”]，target = “a” 输出: “c” 解释：letters 中字典上比 ‘a’ 大的最小字符是 ‘c’。 示例 2:

输入: letters = [“c”,“f”,“j”], target = “c” 输出: “f” 解释：letters 中字典顺序上大于 ‘c’ 的最小字符是 ‘f’。 示例 3:

输入: letters = [“x”,“x”,“y”,“y”], target = “z” 输出: “x” 解释：letters 中没有一个字符在字典上大于 ‘z’，所以我们返回 letters[0]。

提示：

2 int n = letters.length; int low = 0; int high = n - 1; while (low if (mid == 0 || letters[mid - 1] high = mid - 1; } } else { low = mid + 1; } } return letters[0]; } } 4 搜索插入位置

链接：https://leetcode.cn/problems/search-insert-position

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 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

提示:

1 int n = nums.length; int low = 0; int high = n - 1; while (low if (mid == 0 || nums[mid - 1] high = mid - 1; } } else { low = mid + 1; } } return n; } } 5 在排序数组中查找元素的第一个和最后一个位置

链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array

给你一个按照非递减顺序排列的整数数组 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 int low = 0; int n = nums.length; int high = n - 1; int left = -1; while (low if (mid == 0 || nums[mid - 1] != target) { left = mid; break; } else { high = mid - 1; } } else if (nums[mid] > target) { high = mid - 1; } else { low = mid + 1; } } low = 0; int right = - 1; high = n - 1; while (low if (mid == n - 1 || nums[mid + 1] != target) { right = mid; break; } else { low = mid + 1; } } else if (nums[mid] > target) { high = mid - 1; } else { low = mid + 1; } } return new int[] {left, right}; } } 6 稀疏数组搜索

链接：https://leetcode.cn/problems/sparse-array-search-lcci

稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。

示例1:

输入: words = [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”,“dad”, “”, “”], s = “ta” 输出：-1 说明: 不存在返回-1。 示例2:

输入：words = [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”,“dad”, “”, “”], s = “ball” 输出：4 提示:

words的长度在[1, 1000000]之间

链接：https://leetcode.cn/problems/search-in-rotated-sorted-array

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 int n = nums.length; int low = 0; int high = n - 1; while (low if (target >= nums[low] && target low = mid + 1; } } else { if (target > nums[mid] && target high = mid - 1; } } } return -1; } } 8 寻找旋转数组中的最小值

链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。 示例 2：

输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。 示例 3：

输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

提示：

n == nums.length 1 int n = nums.length; int low = 0; int high = n - 1; while (low return nums[mid]; } if (mid != 0 && nums[mid] low = mid + 1; } else { high = mid - 1; } } return -1; } } 9 山脉数组的峰顶索引

链接：https://leetcode.cn/problems/peak-index-in-a-mountain-array

符合下列属性的数组 arr 称为 山脉数组 ： arr.length >= 3 存在 i（0 < i < arr.length - 1）使得： arr[0] < arr[1] < … arr[i-1] < arr[i] arr[i] > arr[i+1] > … > arr[arr.length - 1] 给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。

示例 1：

输入：arr = [0,1,0] 输出：1 示例 2：

输入：arr = [0,2,1,0] 输出：1 示例 3：

输入：arr = [0,10,5,2] 输出：1 示例 4：

输入：arr = [3,4,5,1] 输出：2 示例 5：

输入：arr = [24,69,100,99,79,78,67,36,26,19] 输出：2

提示：

3 int n = arr.length; int low = 0; int high = n - 1; while (low low = mid + 1; } else if (mid == n - 1) { high = mid - 1; } else if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) { return mid; } else if (arr[mid] > arr[mid - 1]) { low = mid + 1; } else { high = mid - 1; } } return -1; } } 10有效的完全平方数

链接：https://leetcode.cn/problems/valid-perfect-square

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16 输出：true 解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。 示例 2：

输入：num = 14 输出：false 解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

提示：

1 int low = 1; int high = num; while (low return true; } else if (mid2 > num) { high = mid - 1; } else { low = mid + 1; } } return false; } } 11 搜索二维矩阵

链接：https://leetcode.cn/problems/search-a-2d-matrix

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true 示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 输出：false

提示：

m == matrix.length n == matrix[i].length 1 int m = matrix.length; int n = matrix[0].length; int low = 0; int high = m * n - 1; int mid, midValue; while (low return true; } else if (target low = mid + 1; } } return false; } }