首先要知道数组在内存中的存储方式，这样才能真正理解数组相关的面试题
Coding Problems
看讲解前
这道题之前做过。这次做思路更清晰了，但是还是改了两次才通过。最后的通过代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right: # left 可以等于 right
pivot = left + (right - left) // 2
if nums[pivot] == target:
return pivot
elif nums[pivot] < target:
left = pivot + 1
else:
right = pivot - 1
return -1 # 不要忘写
|
第一个错误是while循环结束后没写return语句，也就是没写第 13 行代码，结果找不到target时，输出了None而不是-1。这是个说大不大说小不小的错误。说不大是因为看到 output 和 expected 的对比，很容易就可以改对。说不小是因为在写代码的时候，一定要搞清楚对 output 的要求，不然会耽误很多时间 debug。
第二个错误是while语句的边界条件没考虑到left == right的情况，也就是第 4 行代码的条件里只写了小于没写等于。这属于经验主义错误，写代码时没认真考虑。当数组只有一个数值时，left == right，这没有任何问题，所以之前是做什么题的时候让自己变得如此畏畏缩缩不敢加那个小小的=呢？感觉可以以后留心总结一下。
下面贴一下我上次做这题时写的答案吧。感觉自己进步了。过去写的代码好繁琐啊，为啥一定要追求指针也是答案这个点呢？现在的我可能审美变了，不是很能理解当时的想法了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
left, right = 0, len(nums) - 1
while left + 1 < right:
pivot = (left + right) // 2 # 有数值溢出的风险
if nums[pivot] < target:
left = pivot
elif nums[pivot] == target:
right = pivot
else:
right = pivot
if nums[left] == target:
return left
if nums[right] == target:
return right
return -1
|
看讲解后
待更新
看讲解前
这是一道没做过的题。但是感觉关键在于找到val和去掉val这两步。找到val很容易，上一题已经实践过了。去掉val是这题需要解决的新问题。Carl 讲过的数组的底层结构对解决这个问题就很关键了。数组里删去元素更像是用目标坐标后的元素依次往前挪一位，所以我想到的办法就是用一个while循环。代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left <= right:
pivot = left + (right - left) // 2
if nums[pivot] == val:
count += 1
while pivot + 1 < len(nums):
nums[pivot] = nums[pivot + 1]
pivot += 1
right -= 1
elif nums[pivot] < val:
left = pivot + 1
else:
right = pivot - 1
return len(nums) - count
|
看讲解后
待更新