作者： 千石
支持：点赞、收藏、谈论
欢迎各位在谈论区沟通
前言
本文内容来自我平常学习的一些积累，如有过错，还请纠正
在标题实战部分，我将代码完成和代码解说设置在了解题思路的下方，便利各位作为参阅刷题
一些话
本文内容来自我平常学习的一些积累，如有过错，还请纠正
在标题实战部分，我将代码完成和代码解说设置在了解题思路的下方，便利各位作为参阅刷题
标题练习过程：
- 给自己10分钟，读题并考虑解题思路
- 有了思路以后开始写代码，假如在上一过程中没有思路则中止考虑而且看该题题解
- 在看懂题解（暂时没看懂也没关系）的思路后，背诵默写题解，直至能熟练写出来
- 隔一段时间，再次测验写这道标题
刷题
704. 二分查找 – 力扣（LeetCode）
给定一个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]之间。
来历：力扣（LeetCode）
链接：leetcode.cn/problems/bi…
著作权归领扣网络一切。商业转载请联络官方授权，非商业转载请注明出处。
题解
这道题是经典的二分查找问题，因为数组是有序的，所以能够通过二分查找来寻觅目标值。
详细完成方法是，每次查找数组中心的元素，判别是否等于目标值，假如是，直接回来该下标；假如不是，则依据巨细关系缩小查找规模。假如中心元素小于目标值，则在右半部分持续查找；假如中心元素大于目标值，则在左半部分持续查找。重复以上过程直到找到目标值或许查找规模缩小为0。
以下是Python的完成代码：
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
在代码中，变量left和right表明当时查找规模的左右边界，初始化为数组的第一个元素和最后一个元素。每次查找时，首先计算中心元素的下标mid，然后依据mid所在方位与target的巨细关系来更新left和right的值，直到找到目标值或许查找规模缩小为0。假如最终没找到目标值，回来-1即可。
该算法的时间复杂度是O(logn)，因为每次查找都将查找规模缩小一半，一共最多需求查找logn次。
27. 移除元素 – 力扣（LeetCode）
给你一个数组 nums和一个值 val，你需求 原地 移除一切数值等于val的元素，并回来移除后数组的新长度。
不要运用额外的数组空间，你有必要仅运用 O(1) 额外空间并原地修正输入数组。
元素的次序能够改变。你不需求考虑数组中超出新长度后边的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该回来新的长度 2, 而且 nums 中的前两个元素均为 2。 你不需求考虑数组中超出新长度后边的元素。
示例2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该回来新的长度 5, 而且 nums 中的前五个元素为 0, 1, 3, 0, 4。
你不需求考虑数组中超出新长度后边的元素。
题解
这道题能够运用双指针法来解决，一个指针用于遍历整个数组，另一个指针用于指向需求修正的方位。详细过程如下：
- 界说一个指针 index，初始值为 0。
- 遍历整个数组，假如当时元素不等于 val，就将其赋值到 index 指向的方位，然后将 index 加 1。
- 遍历完毕后，回来 index 的值即可。
def removeElement(nums, val):
index = 0
for num in nums:
if num != val:
nums[index] = num
index += 1
return index
977. 有序数组的平方 – 力扣（LeetCode）
给你一个按 非递减次序 排序的整数数组 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]
题解
这道题的解法也很简单，因为数组现已依照非递减次序排序，所以我们能够运用双指针法，别离指向数组的头部和尾部，比较两个指针所指的元素的平方巨细，将较大的那个元素平方参加成果数组的末尾，然后移动指针。
详细过程如下：
- 界说两个指针 left 和 right，别离指向数组的头部和尾部。
- 界说一个成果数组 res，长度为原数组的长度。
- 遍历整个数组，比较 left 和 right 指向的元素的平方巨细，将较大的那个元素平方参加成果数组的末尾，然后移动指针。
- 遍历完毕后，将成果数组反转即可。
代码如下：
def sortedSquares(nums):
n = len(nums)
res = [0] * n
left, right = 0, n - 1
for i in range(n - 1, -1, -1):
if abs(nums[left]) > abs(nums[right]):
res[i] = nums[left] * nums[left]
left += 1
else:
res[i] = nums[right] * nums[right]
right -= 1
return res
