云霄县建设局网站,工厂的网站在哪里做的,镜像站wordpress,江苏建设厅文章目录 20 位运算20.1 【位运算】二进制求和20.2 【位运算】颠倒二进制位20.3 【位运算】位1的个数20.4 【位运算】只出现一次的数字20.5 【哈希表】【位运算】只出现一次的数字 II20.6 【位运算】数字范围按位与 21 数学21.1 【双指针】回文数21.2 【数学】加一21.3 【数学】… 文章目录 20 位运算20.1 【位运算】二进制求和20.2 【位运算】颠倒二进制位20.3 【位运算】位1的个数20.4 【位运算】只出现一次的数字20.5 【哈希表】【位运算】只出现一次的数字 II20.6 【位运算】数字范围按位与 21 数学21.1 【双指针】回文数21.2 【数学】加一21.3 【数学】阶乘后的零21.4 【二分】69. x 的平方根21.5 【快速幂】50. Pow(x, n)21.6 【暴力】直线上最多的点数 22 一维动态规划22.1 【动态规划】爬楼梯22.2 【动态规划】打家劫舍22.3 【动态规划】单词拆分22.4 【动态规划】零钱兑换22.5 【动态规划】【二分】最长递增子序列 23 多维动态规划23.1 【动态规划】三角形最小路径和23.2 【动态规划】最小路径和23.3 【动态规划】不同路径 II23.4 【动态规划】最长回文子串23.5 【动态规划】交错字符串23.6 【动态规划】编辑距离23.7 【三维dp】买卖股票的最佳时机 III23.8 【三维dp】买卖股票的最佳时机 IV23.9 【二维dp】最大正方形 20 位运算
20.1 【位运算】二进制求和
题目地址https://leetcode.cn/problems/add-binary/description/?envTypestudy-plan-v2envIdtop-interview-150 按位逆序运算。
class Solution:def addBinary(self, a: str, b: str) - str:la,lb len(a)-1,len(b)-1ans flag 0while la0 or lb0:num_a 1 if (la0 and a[la]1) else 0num_b 1 if (lb0 and b[lb]1) else 0cur num_a num_b flagif cur 1:cur cur-2flag 1else:flag 0ans str(cur)if la0:la - 1if lb0:lb - 1if flag:ans 1ans ans[::-1]return ans20.2 【位运算】颠倒二进制位
题目地址https://leetcode.cn/problems/reverse-bits/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码。
class Solution:def reverseBits(self, n: int) - int:ans 0for i in range(32):ans ans 1ans n 1n n 1return ans20.3 【位运算】位1的个数
题目地址https://leetcode.cn/problems/number-of-1-bits/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码。
class Solution:def hammingWeight(self, n: int) - int:ans 0for i in range(32):if n 1 :ans 1n n 1return ans20.4 【位运算】只出现一次的数字
题目地址https://leetcode.cn/problems/single-number/description/?envTypestudy-plan-v2envIdtop-interview-150 异或操作。
class Solution:def singleNumber(self, nums: List[int]) - int:ans 0for n in nums:ans ans ^ nreturn ans20.5 【哈希表】【位运算】只出现一次的数字 II
题目地址https://leetcode.cn/problems/single-number-ii/description/?envTypestudy-plan-v2envIdtop-interview-150 方法一哈希表 方法二模3运算
# 方法一哈希表
class Solution:def singleNumber(self, nums: List[int]) - int:ht {}for n in nums:if n in ht:ht[n] 1else:ht[n] 1for h in ht:if ht[h] 1:return h
# 方法二模3运算
class Solution:def singleNumber(self, nums: List[int]) - int:a,b 0,0for n in nums:b (b^n)(~a)a (a^n)(~b)return b20.6 【位运算】数字范围按位与
题目地址https://leetcode.cn/problems/bitwise-and-of-numbers-range/description/?envTypestudy-plan-v2envIdtop-interview-150 找公共前缀。
class Solution:def rangeBitwiseAnd(self, left: int, right: int) - int:t 0while left right:left left 1right right 1t 1return left t21 数学
21.1 【双指针】回文数
题目地址https://leetcode.cn/problems/palindrome-number/description/?envTypestudy-plan-v2envIdtop-interview-150 将数字的每一位取出来然后双指针前后分别判断是否相等。
class Solution:def isPalindrome(self, x: int) - bool:if x 0:return Falsenum []while x0:n x % 10num.append(n)x x // 10left,right 0,len(num)-1while left right:if num[left] ! num[right]:return Falseleft 1right - 1return True21.2 【数学】加一
题目地址https://leetcode.cn/problems/plus-one/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码。
class Solution:def plusOne(self, digits: List[int]) - List[int]:l len(digits)t 1for i in range(l-1,-1,-1):digits[i] digits[i] tif digits[i] 9:digits[i] - 10t 1else:t 0if t 1:return [1]digitselse:return digits21.3 【数学】阶乘后的零
题目地址https://leetcode.cn/problems/factorial-trailing-zeroes/description/?envTypestudy-plan-v2envIdtop-interview-150 统计因子中5的个数即可。
class Solution:def trailingZeroes(self, n: int) - int:ans 0while n0:n n//5ans nreturn ans21.4 【二分】69. x 的平方根
题目地址https://leetcode.cn/problems/sqrtx/description/?envTypestudy-plan-v2envIdtop-interview-150 二分查找。
class Solution:def mySqrt(self, x: int) - int:left,right 0,x1while left right:m (leftright)//2if m*m x:return melif m*m x:left m1else:right mreturn left-121.5 【快速幂】50. Pow(x, n)
题目地址https://leetcode.cn/problems/powx-n/description/?envTypestudy-plan-v2envIdtop-interview-150 快速幂。
class Solution:def myPow(self, x: float, n: int) - float:if x 0.0:return 0.0ans 1if n 0:x,n 1/x,-nwhile n:if n 1:ans * xx * xn n 1return ans21.6 【暴力】直线上最多的点数
题目地址https://leetcode.cn/problems/max-points-on-a-line/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码。
class Solution:def maxPoints(self, points: List[List[int]]) - int:n, ans len(points), 1for i, x in enumerate(points):for j in range(i 1, n):y points[j]cnt 2for k in range(j 1, n):p points[k]s1 (y[1] - x[1]) * (p[0] - y[0])s2 (p[1] - y[1]) * (y[0] - x[0])if s1 s2: cnt 1ans max(ans, cnt)return ans22 一维动态规划
22.1 【动态规划】爬楼梯
题目地址https://leetcode.cn/problems/climbing-stairs/?envTypestudy-plan-v2envIdtop-interview-150 斐波那契数列求值。
class Solution:def climbStairs(self, n: int) - int:if n 1:return 1dp_0,dp_1 1,1ans 0for i in range(2,n1):ans dp_0 dp_1dp_0,dp_1 dp_1,ansreturn ans22.2 【动态规划】打家劫舍
题目地址https://leetcode.cn/problems/house-robber/description/?envTypestudy-plan-v2envIdtop-interview-150
利用动态规划首先定义数组 d p [ i ] [ 2 ] dp[i][2] dp[i][2]状态转移如下所示 d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示第 i i i家不被偷则前一家可能被偷也可能没有被偷取最大值即可 d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示第 i i i家被偷则前一家一定没有被偷所以为 d p [ i − 1 ] [ 0 ] n u m s [ i ] dp[i-1][0]nums[i] dp[i−1][0]nums[i]。
最后在第 i i i家的时候取被偷和未被偷之间的最大值即可。
class Solution:def rob(self, nums: List[int]) - int:n len(nums)dp_0,dp_1 0,nums[0]for i in range(1,n):last_0 dp_0dp_0 max(dp_0,dp_1)dp_1 last_0 nums[i]return max(dp_0,dp_1)22.3 【动态规划】单词拆分
题目地址https://leetcode.cn/problems/word-break/description/?envTypestudy-plan-v2envIdtop-interview-150 将 w o r d D i c t wordDict wordDict中的单词看成一个个的跳跃长度代表如果首字母匹配上了一步可以跳多远那么最远的距离就是 T r u e True True最后只需查看满足了所有跳跃规则之后能否到达字符串 s s s的末尾即可。
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:l len(s)dp [False]*(l1)dp[0] Truefor i in range(l1):if dp[i]:for j in range(i1,l1):if s[i:j] in wordDict:dp[j] Truereturn dp[-1]22.4 【动态规划】零钱兑换
题目地址https://leetcode.cn/problems/coin-change/description/?envTypestudy-plan-v2envIdtop-interview-150 动态规划题目的基本做题策略
确定 d p dp dp数组以及下标的含义 d p [ j ] dp[j] dp[j]为凑齐总额为j的钱币的最小次数确定递推公式 d p [ j ] m i n ( d p [ j ] , d p [ j − c o i n ] 1 ) dp[j] min(dp[j],dp[j-coin]1) dp[j]min(dp[j],dp[j−coin]1) d p dp dp数组如何初始化 d p [ 0 ] dp[0] dp[0]为 0 0 0剩下的初始化为最大钱币金额 1 1 1确定遍历顺序。
class Solution:def coinChange(self, coins: List[int], amount: int) - int:dp [amount1]*(amount1)dp[0] 0for j in range(1,amount1):for coin in coins:if j coin:dp[j] min(dp[j],dp[j-coin]1)if dp[amount] amount1:return dp[amount]else:return -122.5 【动态规划】【二分】最长递增子序列
题目地址https://leetcode.cn/problems/longest-increasing-subsequence/description/?envTypestudy-plan-v2envIdtop-interview-150 方法一动态规划构造 d p [ i ] dp[i] dp[i]表示 i i i索引为序列末尾元素的最长序列长度。 方法二二分查找维护一个递增序列 a r r arr arr遍历时取小的放入序列中最后返回序列长度。
# 动态规划
class Solution:def lengthOfLIS(self, nums: List[int]) - int:l len(nums)dp [1]*ldp_max 1for i in range(1,l):for j in range(0,i):if nums[j] nums[i]:dp[i] max(dp[i],dp[j]1)dp_max max(dp_max,dp[i])return dp_max# 二分查找
class Solution:def lengthOfLIS(self, nums: List[int]) - int:arr [0]*len(nums)ans 0for num in nums:left,right 0,answhile left right:mid (leftright) // 2if arr[mid] num:left mid 1else:right midarr[left] numif right ans:ans 1return ans23 多维动态规划
23.1 【动态规划】三角形最小路径和
题目地址https://leetcode.cn/problems/triangle/description/?envTypestudy-plan-v2envIdtop-interview-150 自底向上进行动态规划每次都选择下一层的 k k k和 k 1 k1 k1之间最小的数与该层的数相加最后返回 d p [ 0 ] dp[0] dp[0]即可。
class Solution:def minimumTotal(self, triangle: List[List[int]]) - int:l len(triangle)dp [0]*lfor i in range(len(triangle[-1])):dp[i] triangle[-1][i]for j in range(l-2,-1,-1):for k in range(j1):dp[k] min(dp[k],dp[k1]) triangle[j][k]return dp[0]23.2 【动态规划】最小路径和
题目地址https://leetcode.cn/problems/minimum-path-sum/description/?envTypestudy-plan-v2envIdtop-interview-150 每次遍历时找出两个步骤的最小值然后相加也是自顶向下的思路。
class Solution:def minPathSum(self, grid: List[List[int]]) - int:row len(grid)col len(grid[0])for i in range(1,col):grid[0][i] grid[0][i-1]for j in range(1,row):grid[j][0] grid[j-1][0]for i in range(1,row):for j in range(1,col):grid[i][j] min(grid[i][j-1],grid[i-1][j])return grid[row-1][col-1]23.3 【动态规划】不同路径 II
题目地址https://leetcode.cn/problems/unique-paths-ii/description/?envTypestudy-plan-v2envIdtop-interview-150 计算可以走到每个格子的路线数最后相加。
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) - int:row len(obstacleGrid)col len(obstacleGrid[0])dp [[0]*col for _ in range(row)]for i in range(row):for j in range(col):if not obstacleGrid[i][j]:if i j 0:dp[i][j] 1else:up dp[i-1][j] if i0 else 0left dp[i][j-1] if j0 else 0dp[i][j] up leftreturn dp[-1][-1]23.4 【动态规划】最长回文子串
题目地址https://leetcode.cn/problems/longest-palindromic-substring/description/?envTypestudy-plan-v2envIdtop-interview-150 d p [ i ] [ j ] dp[i][j] dp[i][j]表示 s [ i : j 1 ] s[i:j1] s[i:j1]是否为回文子串状态转移的思路是如果 d p [ i 1 ] [ j − 1 ] dp[i1][j-1] dp[i1][j−1]为 T r u e True True并且 s [ i ] s [ j ] s[i]s[j] s[i]s[j]的话那么 d p [ i ] [ j ] dp[i][j] dp[i][j]也为 T r u e True True在每个为 T r u e True True的情况下记录此时字符串的长度同时更新初始坐标最后选择最长的子串即可。
class Solution:def longestPalindrome(self, s: str) - str:l len(s)dp [[0]*l for _ in range(l)]max_len 1start 0for j in range(1,l):for i in range(j):# (j-1)-(i1) 0if j-i 2:if s[i] s[j]:dp[i][j] 1cur_len j-i1else:if s[i] s[j] and dp[i1][j-1]:dp[i][j] 1cur_len j-i1if dp[i][j] and cur_len max_len:max_len cur_lenstart ireturn s[start:startmax_len]23.5 【动态规划】交错字符串
题目地址https://leetcode.cn/problems/interleaving-string/description/?envTypestudy-plan-v2envIdtop-interview-150 d p [ i ] [ j ] dp[i][j] dp[i][j]表示 s 1 s_1 s1的前 i i i个字符和 s 2 s2 s2的前 j j j个字符能否构成 s 3 s3 s3的前 i j ij ij个字符。
class Solution:def isInterleave(self, s1: str, s2: str, s3: str) - bool:l1 len(s1)l2 len(s2)l3 len(s3)if l1 l2 ! l3:return Falsedp [[False]*(l21) for _ in range(l11)]dp[0][0] Truefor i in range(1,l11):dp[i][0] (dp[i-1][0] and s1[i-1]s3[i-1])for i in range(1,l21):dp[0][i] (dp[0][i-1] and s2[i-1]s3[i-1])for i in range(1,l11):for j in range(1,l21):dp[i][j] (dp[i-1][j] and s1[i-1]s3[ij-1]) or (dp[i][j-1] and s2[j-1]s3[ij-1])return dp[-1][-1]23.6 【动态规划】编辑距离
题目地址https://leetcode.cn/problems/edit-distance/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码注释。
class Solution:def minDistance(self, word1: str, word2: str) - int:l1 len(word1)l2 len(word2)# 初始化dpdp[i][j]表示从word1[:i]到word2[:j]所需要转换的次数dp [[0]*(l21) for _ in range(l11)]# 此时word2为空则word1需要转换的次数为此时的长度for i in range(l11):dp[i][0] i# 此时word2为空则word1需要转换的次数为此时的长度for j in range(l21):dp[0][j] j# 首先判断i和j索引处的字符是否相同如果相同则dp[i][j]dp[i-1][j-1]# 否则不管是删除还是替换都会在之前的基础上改变一位字符# 则dp[i][j]min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])1for i in range(1,l11):for j in range(1,l21):if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1]else:dp[i][j]min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])1return dp[-1][-1]23.7 【三维dp】买卖股票的最佳时机 III
题目地址https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码注释。
class Solution:def maxProfit(self, prices: List[int]) - int:l len(prices)# dp[第几天][是否持有股票][已经卖了几次股票]dp [[[0,0,0],[0,0,0]] for _ in range(l)]# 第一天初始化dp[0][0][0] 0dp[0][0][1] -float(inf)dp[0][0][2] -float(inf)dp[0][1][0] -prices[0]dp[0][1][1] -float(inf)dp[0][1][2] -float(inf)# 接下来几天状态更新for i in range(1,l):# 未持有股票已经卖了0次股票dp[i][0][0] 0# 未持有股票已经卖了1次股票可能是今天卖的也可能是前几天卖的dp[i][0][1] max(dp[i-1][1][0]prices[i],dp[i-1][0][1])# 未持有股票已经卖了2次股票可能是今天卖的也可能是前几天卖的dp[i][0][2] max(dp[i-1][1][1]prices[i],dp[i-1][0][2])# 已持有股票已经卖了0次股票可能是今天买的也可能是前几天买的dp[i][1][0] max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])# 已持有股票已经卖了1次股票可能是今天买的也可能是前几天买的dp[i][1][1] max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])# 已持有股票已经卖了2次股票dp[i][1][2] -float(inf)return max(dp[l-1][0][1],dp[l-1][0][2],0)23.8 【三维dp】买卖股票的最佳时机 IV
题目地址https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码注释。
class Solution:def maxProfit(self, k: int, prices: List[int]) - int:# dp[第几天][已经完成几笔交易][是否持股]l len(prices)dp [[[0]*2 for _ in range(k1)] for _ in range(l)]for i in range(1,k1):dp[0][i][1] -prices[0]for i in range(1,l):for j in range(1,k1):# 未持股今天卖掉了或者昨天也未持股dp[i][j][0] max(dp[i-1][j][1]prices[i],dp[i-1][j][0])# 持股今天买入股票或者昨天持股dp[i][j][1] max(dp[i-1][j-1][0]-prices[i],dp[i-1][j][1])return dp[l-1][k][0]23.9 【二维dp】最大正方形
题目地址https://leetcode.cn/problems/maximal-square/submissions/515490547/?envTypestudy-plan-v2envIdtop-interview-150 详见代码注释。
class Solution:def maximalSquare(self, matrix: List[List[str]]) - int:max_length 0row len(matrix)col len(matrix[0])# dp[i][j]表示matrix[:i][:j]的正方形最大边长dp [[0]*(col1) for _ in range(row1)]# 状态转移为在左、上、左上中取最小值1因为需要保证正方形内所有元素均为1for i in range(1,row1):for j in range(1,col1):if matrix[i-1][j-1] 1:dp[i][j] min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) 1max_length max(max_length,dp[i][j])return max_length*max_length
