记录2025面试找工作刷题。。。。。
740. 删除并获得点数
Note: 进阶版本打家劫舍，考虑nums[i], nums[i - 1], nums[i + 1]，即相邻不能“偷”，原始数组通过累加得到新数组；对新数组进行动态规划即可；
class Solution : def deleteAndEarn (self, nums: List [int ] ) -> int : max_num = max (nums) num_list = [0 ] * (max_num + 1 ) for num in nums: num_list[num] += num dp = [0 ] * len (num_list) for i in range (max_num + 1 ): if i == 0 : dp[i] = num_list[i] else : dp[i] = max (dp[i - 1 ], dp[i - 2 ] + num_list[i]) return dp[max_num]
746. 使用最小花费爬楼梯
Note: 因为最小花费，则动态规划方程中，前一次可以选择不爬，前前一次则必须爬到当前位置，所以方程为： dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
class Solution : def minCostClimbingStairs (self, cost: List [int ] ) -> int : n = len (cost) dp = [0 ] * n for i in range (n): if i < 2 : dp[i] = cost[i] else : dp[i] = min (dp[i - 1 ], dp[i - 2 ]) + cost[i] return min (dp[n - 1 ], dp[n - 2 ])
62. 不同路径
Note: 初始i == 0 or j == 0表示在边界，仅有一种方法能到达，因此初始化为1；
class Solution : def uniquePaths (self, m: int , n: int ) -> int : dp = [[0 ] * n for _ in range (m)] for i in range (m): for j in range (n): if i == 0 : dp[i][j] = 1 elif j == 0 : print (i, j) dp[i][j] = 1 else : dp[i][j] = dp[i][j - 1 ] + dp[i - 1 ][j] return dp[m - 1 ][n - 1 ]
63. 不同路径 II
Note: 遇到障碍物，则当前到达不了，直接为0；另外要初始化第一行，第一列的单独情况，有障碍物，则后续都无法到达，则为0；
class Solution : def uniquePathsWithObstacles (self, obstacleGrid: List [List [int ]] ) -> int : if obstacleGrid[0 ][0 ] == 1 : return 0 m, n = len (obstacleGrid), len (obstacleGrid[0 ]) dp = [[0 ] * n for _ in range (m)] for i in range (m): if obstacleGrid[i][0 ] == 1 : break dp[i][0 ] = 1 for j in range (n): if obstacleGrid[0 ][j] == 1 : break dp[0 ][j] = 1 for i in range (1 , m): for j in range (1 , n): if obstacleGrid[i][j] == 1 : dp[i][j] = 0 else : dp[i][j] = dp[i - 1 ][j] + dp[i][j - 1 ] return dp[m - 1 ][n - 1 ]
80. 删除有序数组中的重复项 II
Note: 题目要求是空间复杂度是1，移除超过计数为2的，那么只要设置计数器count，然后仅在< 2时候进行更新，否则继续遍历，或更新快慢指针，以及对应的数组下标和数组元素。
class Solution : def removeDuplicates (self, nums: List [int ] ) -> int : count = 1 i = 0 n = len (nums) for j in range (1 , n): if nums[j] == nums[i]: if count < 2 : count += 1 i += 1 nums[i] = nums[j] else : i += 1 nums[i] = nums[j] count = 1 return i + 1
300. 最长递增子序列
Note: 动态规划中，则每次更新前一个状态的最大的长度，如果满足条件，
后续的状态在前一状态上+1；贪心+二分查找中，主要是维护一个最长子序列，然后每次取最小的替换并加入到维护的最长子序列中。
class Solution : def lengthOfLIS (self, nums: List [int ] ) -> int : n = len (nums) dp = [1 ] * len (nums) for i in range (n): for j in range (i): if nums[i] > nums[j]: dp[i] = max (dp[i], dp[j] + 1 ) return max (dp)
class Solution : def lengthOfLIS (self, nums: List [int ] ) -> int : valid_list = [] for i in range (len (nums)): if not valid_list or nums[i] > valid_list[-1 ]: valid_list.append(nums[i]) else : l, r = 0 , len (valid_list) - 1 loc = r while l <= r: mid = (l + r) // 2 if valid_list[mid] >= nums[i]: loc = mid r = mid - 1 else : l = mid + 1 valid_list[loc] = nums[i] return len (valid_list)
