看了好多攻略，打算第一遍刷题顺序跟着 代码随想录 ：数组、链表、哈希表、字符串、双指针法、栈与队列、二叉树、回溯算法 、贪心算法、动态规划、单调栈
题外话：小白一枚，打算刷题提高编程能力，由于现在在公司算法部门实习，所以使用python语言，打算明年秋招之前用java或者c++再刷一遍。下面纯记录个人刷题日记及代码。
代码随想录：代码随想录 (programmercarl.com)
DAY 1 704.二分查找704. 二分查找 - 力扣（LeetCode）
class Solution1:
def search(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
middle = (left + right) // 2
if nums[middle] < target:
left = middle + 1
elif nums[middle] > target:
right = middle - 1
else:
return middle
return -1
emp1 = Solution1()
emp1.search([-1,3,5,7,9,14,55,48],55)
#输出：6
35.搜索插入位置
class Solution3:
def search(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
middle = (left + right) // 2
if nums[middle] < target:
left = middle + 1
elif nums[middle] > target:
right = middle - 1
else:
return middle
return right + 1
emp3 = Solution3()
emp3.search([-1,3,5,7,9],8)
#输出：4
34.在排序数组中查找元素的第一个和最后一个位置
class Solution4:
def search(self, nums, target):
def result(nums,target):
left, right = 0, len(nums) - 1
while left <= right:
middle = (left + right) // 2
if nums[middle] < target:
left = middle + 1
elif nums[middle] > target:
right = middle - 1
else:
return left
return -1
index = result(nums,target)
if index==-1:return [-1,-1]
left,right=index,index
while left -1 >=0 and nums[left - 1] == target: left -=1
while right+1 < len(nums) and nums[right + 1] == target:right +=1
print([left,right])
emp4 = Solution4()
nums=[-1,3,5,6,7,9,9,9,9,9]
target=9
emp4.search(nums,target)
#输出：[5,9]
69.x 的平方根
方法一：
class Solution5:
def mySqrt(self, x: int) -> int:
l, r, ans = 0, x, -1
while l <= r: #不能漏掉l=r的情况
mid = (l + r) // 2
if mid * mid <= x:
ans = mid
l = mid + 1
else:
r = mid - 1
return ans
emp5 = Solution5()
emp5.mySqrt(9)
#输出：3
方法二：
class Solution6:
def mySqrt(self, x):
if x == 0:
return 0
x0,C = float(x),float(x)
while True:
xi = 0.5 * (x0 + C/x0)
if abs(x0 - xi) < 1e-7:
break
x0 = xi
return int(x0)
emp6 = Solution6()
emp6.mySqrt(10)
#输出：3
DAY 2
27.移除元素
方法一：双指针法，快指针、慢指针
class Solution8:
def removeElement(self, nums,val):
fast = 0
slow = 0
for fast in range(len(nums)):
if nums[fast] == val:
continue
else:
nums[slow] = nums[fast]
slow +=1
return slow
emp8 = Solution8()
nums=[3,2,2,3]
val = 3
length=emp8.removeElement(nums,val)
for i in range(length):
print(nums[i])
#输出：2
# 2
方法二：双指针法、左指针、右指针
class Solution9:
def removeElement(self, nums,val):
right = len(nums)-1
left = 0
while left <= right:
if nums[left] == val:
nums[left] = nums[right]
right -= 1
else:
left += 1
return nums[0:left]
emp9 = Solution9()
nums=[3,2,2,2,3,6,7,5,3]
val = 2
emp9.removeElement(nums,val)
#输出：[3, 3, 5, 7, 3, 6]
26.删除有序数组中的重复项
class Solution10:
def removeDuplicates(self, nums):
fast = 1
slow = 0
for fast in range(len(nums)):
if nums[fast] == nums[slow]:
fast +=1
else:
slow +=1
nums[slow] = nums[fast]
return nums[0:slow]
emp10 = Solution10()
nums=[3,2,2,2,3,6,7,5,3]
emp10.removeDuplicates(nums)
#输出：[3, 2, 3, 6, 7, 5]
283.移动零
class Solution11:
def moveZeroes(self, nums):
right = 0
left = 0
for right in range(len(nums)):
if nums[right]:
nums[left],nums[right] = nums[right],nums[left]
left += 1
right +=1
return nums
emp11 = Solution11()
nums=[3,0,2,0,3,6,0]
emp11.moveZeroes(nums)
#输出：[3, 2, 3, 6, 0, 0, 0]
844.比较含退格的字符串
class Solution12:
def backspaceCompare(self,s,t):
def build(str):
ret = list()
for i in str:
if i != '#':
ret.append(i)
elif ret:
ret.pop() #保证ret里面有字符才能pop
return ret
return build(s) == build(t)
emp12 = Solution12()
s='a##c'
t='#a#c'
emp12.backspaceCompare(s,t)
#输出：True
977.有序数组的平方
方法一：直接排序
class Solution13:
def sortedSquares(self, nums):
return sorted(num * num for num in nums)
emp13 = Solution13()
nums=(2,3,4,7,8,-1,-3)
emp13.sortedSquares(nums)
#输出：[1, 4, 9, 9, 16, 49, 64]
方法二：双指针法，重点是有序数组，最大值是最右边或者最左边、左右指针
class Solution14:
def sortedSquares(self, nums):
n = len(nums)
result = [-1]*n
i,j,k = 0,n-1,n-1
while i <= j:
lm = nums[i]**2
rm = nums[j]**2
if lm > rm:
result[k] = lm
i +=1
else:
result[k] = rm
j -=1
k -=1
return result
emp14 = Solution14()
nums=(-3,-1,0,4,6,9)
emp14.sortedSquares(nums)
#输出：[0, 1, 9, 16, 36, 81]
DAY 3
209.长度最小的子数组
滑动窗口、双指针法
class Solution15:
def minSubArrayLen(self, nums,target):
res = float("inf") #设为无穷大
sum = 0
i = 0
for j in range(len(nums)):
sum += nums[j]
while sum >= target:
res = min(res,j-i+1)
sum -= nums[i]
i += 1
if res == float("inf"):
return 0
else:
return res
emp15 = Solution15()
nums = (2,3,1,2,4,3)
target = 7
emp15.minSubArrayLen(nums,target )
#输出：2
DAY 4
904.水果成篮
class Solution16:
def totalFruit(self, fruits: List[int]) -> int:
ans = i = 0
count = collections.Counter()
for j, x in enumerate(fruits):
count[x] += 1
while len(count) >= 3:
count[fruits[i]] -= 1
if count[fruits[i]] == 0:
del count[fruits[i]]
i += 1
ans = max(ans, j - i + 1)
return ans
emp16 = Solution16()
fruits = (2,3,1,2,2,1,3)
emp16.totalFruit(fruits)
#输出：4
DAY 5
