字节跳动---面试算法刷题（1~10）（python）

- 日理万妓 2022-11-11 15:54 273阅读 0赞

### 目录 ###

*   *  一：最长回文子串（动态规划）：
     *  二：子数组的最大乘积（动态规划）：
     *  三：股票交易的最大收益（动态规划）：
     *  四：最长公共子串（动态规划）：
     *  五：最长递增子序列（动态规划+二分）：
     *  六：字符串的排序(递归+回溯)：
     *  八：矩阵的最小路径之和(动态规划)：
     *  九：最大的正方形（动态规划）：
     *  十：最长公共子序列（动态规划）：

## 一：最长回文子串（动态规划）： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70]  
思路：循环遍历这个字符串，会出现两种情况，一种是最长回文串是奇数的时候，另外一种是回文串是偶数的时候，基于两种情况，我们使用双指针更新最大值就可以了。

class Solution:
        def getLongestPalindrome(self, A, n):
            # 1：特殊：如果是个空子串则直接返回0
            if n == 0: return 0
            # 2: 假设是最长回文串是奇数，则
            res = 1 # 最长的至少是1
            for i in range(1, n - 1):
                count = 1
                left = i - 1 # 指向左边
                right = i + 1 # 指向右边
                while(left >= 0 and right <= n - 1):
                    if A[left] == A[right]:
                        count += 2
                        left -= 1
                        right += 1
                    else:
                        break
                res = max(res, count)
            # 3: 假设最长回文串是偶数，则
            for i in range(1, n):
                left = i - 1 # 指向左边
                right = i # 指向右边
                count = 0
                while(left >= 0 and right <= n - 1):
                    if A[left] == A[right]:
                        count += 2
                        left -= 1
                        right += 1
                    else:
                        break
                res = max(res, count)
            return res

## 二：子数组的最大乘积（动态规划）： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 1]  
分析： 这个题难度在于当前的最大值可能是上一位的最小值乘以一个负数，或者上一位的最大值乘以正数得到。因此我们可以创建两个DP数组，分别存储两个状态，然后遍历更新状态，最终返回状态的最大值就可以了。

class Solution:
        def maxProduct(self , arr ):
            n = len(arr)
            # 1: 特殊：如果长度是0，则直接返回0
            if n == 0: return 0
            # 2: 定义两个数组，分别存储正数最大和负数最小的状态
            dp_min = [1.0] * n # 初始化第一个
            dp_max = [1.0] * n # 初始化第一个
            dp_min[0] = arr[0] # 初始化第一个
            dp_max[0] = arr[0] # 初始化第一个
            res = arr[0]
            # 3: 进行遍历
            for i in range(1, n):
                # 如果是正数
                if arr[i] > 0:
                    dp_min[i] = min(arr[i], dp_min[i - 1] * arr[i])
                    dp_max[i] = max(arr[i], dp_max[i - 1] * arr[i])
                else:
                    dp_min[i] = min(arr[i], dp_max[i - 1] * arr[i])
                    dp_max[i] = max(arr[i], dp_min[i - 1] * arr[i])
                res = max(res, dp_max[i])
            return res

## 三：股票交易的最大收益（动态规划）： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 2]  
思路：动态规划问题思路： 1： 搞清楚有几个状态。 2：寻找DP状态方程。  
1：几个状态？？？  
答： 5个状态： 未操作状态， 从第一次买入到第一次卖出状态， 从第一次卖出到第二次买入状态， 从第二次买入到第二次卖出状态，从第二次卖出到最后。此时我们可以适应DP\[i\]\[0\]代表没有操作状态， DP\[i\]\[1\]代表 第一次买入状态，DP\[i\]\[2\]代表 第一次卖出状态，DP\[i\]\[3\]代表第二次买入状态，DP\[i\]\[4\]代表第二次卖出状态。  
2： DP方程式是什么？  
2.1：当前没有操作，则收益状态跟上一个是一样的，即：DP\[i\]\[0\] = DP\[i-1\]\[0\]  
2.2：第一次买入状态：两种情况，如果之前已经买了则： DP\[i\]\[1\] = DP\[i-1\]\[1\], 如果之前没有买，本次进行购买(之间没买的收益 - 当前的价格 )： DP\[i\]\[1\] = DP\[i - 1\]\[0\] - prices\[i\]。而此时的最大收益应该是两种情况的最大的那个。  
2.3：第一次卖出状态：两种情况，如果之前已经卖出了，则 DP\[i\]\[2\] = DP\[i-1\]\[2\], 如果卖出了，则是第一次买入状态加上此时的价格，即DP\[i\]\[2\] = Dp\[i-1\]\[1\] + prices\[i\]。  
以此类推，可以推出剩余两个状态的状态方程式。

## 四：最长公共子串（动态规划）： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 3]  
分析：典型的动态规划问题：方案—（打表）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 4]  
思路: 如果两个相等则数 = 左上角 + 1 ， 如果不是则为0。

class Solution:
        def LCS(self , str1 , str2 ):
            n = len(str1)
            m = len(str2)
            if n == 0 or m == 0:
                return ""
            dp = [[0] * (m+1) for _ in range(n+1)]
            start = 0
            end = 0
            max_length = 0
            for i in range(1, n+1):
                for j in range(1, m+1):
                    if str1[i-1] == str2[j-1]:
                        dp[i][j] = dp[i-1][j-1] + 1
                        if dp[i][j] > max_length:
                            max_length = dp[i][j]
                            start = i - max_length
                            end = i 
            return str1[start:end]

## 五：最长递增子序列（动态规划+二分）： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 5]  
思路： \*\*我们可以使用一个DP数组来存储每个作为最后一个元素的最长子序列，而DP(i) = 之前遍历的节点值小于当前节点，而且之前的DP中最大的那个（两个条件缺一不可）。\*\*这样做的时间复杂度是O(n2)。能否进行优化呢？

## 六：字符串的排序(递归+回溯)： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 6]

class Solution:
        def __init__(self):
            self.my_list = list() # 每次的list
            self.res = list() # 返回值
            
        def dfs(self, x):
            # 1： 递归边界了，将每次的list转换成字符串，添加到返回数组中。
            if x == len(self.my_list) - 1:
                self.res.append(''.join(self.my_list))
                return 
            # 2：定义一个集合用于标记遍历过的值
            my_set = set()
            # 3： 从没有固定的位置到最后遍历
            for i in range(x, len(self.my_list)):
                # 3.1：如果这个值遍历过了，则直接退出
                if self.my_list[i] in my_set:
                    continue
                # 3.2：标记成遍历过了
                my_set.add(self.my_list[i])
                # 3.3：然后后面的每一个值都在x这个没有固定的位置进行固定。
                self.my_list[i], self.my_list[x] = self.my_list[x], self.my_list[i]
                # 3.4：递归下一个没有固定的位置
                self.dfs(x +1)
                # 3,5：恢复交换
                self.my_list[i], self.my_list[x] = self.my_list[x], self.my_list[i]
                
        def Permutation(self, ss):
            # 1： 初始化每次的列表
            self.my_list = list(ss)
            # 2：开始在0位置开始
            self.dfs(0)
            # 3： 排序的原因是牛客大傻叉必须让字符串顺序输出。
            self.res.sort()
            return self.res

## 八：矩阵的最小路径之和(动态规划)： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 7]

class Solution:
        def minPathSum(self , matrix ):
            n = len(matrix)
            m = len(matrix[0])
            for i in range(1, n):
                matrix[i][0] = matrix[i-1][0] + matrix[i][0]
            for j in range(1, m):
                matrix[0][j] = matrix[0][j-1] + matrix[0][j]
            for i in range(1, n):
                for j in range(1, m):
                    matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1]) + matrix[i][j]
            return matrix[n-1][m-1]

## 九：最大的正方形（动态规划）： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 8]  
思路： 首先我们知道，对于第一列或者第一行来说，如果是1，则DP肯定是1，如果是0，DP肯定是0。一般情况呢？对于一个中间的位置，我们可以得到，肯定是左边或者上面,左上角的那个中最小的+1。

class Solution:
        def solve(self , matrix ):
            n = len(matrix) # 行数
            m = len(matrix[0]) # 列数
            # 特殊： 如果行数是0或者列数是0，则肯定是0
            if n == 0 or m == 0:
                return 0
            # 定义DP矩阵,全部初始化为0
            dp = [[0 for i in range(m+1)] for j in range(n+1)]
            
            # 定义最大长度
            max_length = 0
            for i in range(n):
                for j in range(m):
                    if matrix[i][j] == '1':
                        if i == 0 or j == 0:
                            dp[i][j] = 1
                        else:
                            dp[i][j] = min(dp[i-1][j -1], dp[i-1][j], dp[i][j-1]) + 1
                            if dp[i][j] > max_length:
                                max_length = dp[i][j]
            return max_length**2

## 十：最长公共子序列（动态规划）： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 9]

分析：  
1: 分析最优子结构的性质：  
从后向前进行分析，假设两个最后一个字符是相等的，则最后这个肯定是在公共子序列之中的。因此，同时去掉最后一个元素，则S\[k-1\] = S1\[n-1\] 和S\[m-1\]的最长公共子序列的。  
如果最后两个元素是不相等的， 他们是不属于最长公共子序列的，此时S\[k\]会是S1\[n-1\]和S2\[m\]的最长公共子序列或者是S1\[n和S2\[m-1\]的最长公共子序列。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 10]  
2： 分析建立递推方程式：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 11]  
3： 案例分析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 12]

class Solution:
        def LCS(self , s1 , s2 ):
            n = len(s1)
            m = len(s2)
            # 1: 如果一个字符串是空，则直接返回-1
            if n == 0 or m == 0:
                return "-1"
            # 2： 创建二维DP数组
            dp = [[0 for i in range(m+1)] for j in range(n+1)]
            # 3: 根据DP方成熟填表
            for i in range(1, n+1):
                for j in range(1, m+1):
                    if s1[i - 1] == s2[j - 1]:
                        dp[i][j] = dp[i-1][j-1] + 1
                    else:
                        dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                        
            # 4:如果此时最优一个的长度还是0，则表示没有最长子序列返回-1
            if dp[n][m] == 0: return '-1'
            # 5: 逆向寻找
            res = ''
            i, j = n, m
            while(i > 0 and j > 0):
                if s1[i - 1] == s2[j - 1]: # 如果值相等则追加进来，指针向前移动
                    res += s1[i - 1]
                    i -= 1
                    j -= 1
                else:
                    if dp[i][j-1] > dp[i-1][j]: # 如果左边大于上边，说明是从左边过来的
                        j -= 1
                    else:
                        i -= 1
            return res[::-1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70]: /images/20221022/c5b3c63459fd432da264e5fcef363995.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 1]: /images/20221022/2672f0389df3451a85e97d47e2a02cc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 2]: /images/20221022/b40b93a1df2e459d9a0a6d771deaf108.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210322101136653.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20210322102546723.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210322125256454.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210322131355294.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20210322155747173.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20210322155950169.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20210322163459997.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20210322190611250.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20210322191859485.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20210322192125399.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3,size_16,color_FFFFFF,t_70