Skip to content

Ceruleanacg/Crack-Interview

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

94 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

LeetCode

题解 - Solutions

数组与字符串 - Array and Strings

1. Two Sum

  • 给定一个整型数组和一个目标数,返回整型数组中两个数的和为目标数的下标(题目保证有解,数组中每一个数只能使用一次。

  • 初始化字典dic,其键值为数组中某元素与其下标,遍历数组中每个元素arr[i],目标值targetarr[i]的差记为diff,在dic中查找键diff,如果存在,则返回diff的下标与i,如果不存在,为dic建立arr[i]i的键值对。

125. Valid Palindrome

  • 给定一个字符串,判断该字符串是否是回文串。回文串是从前后方向阅读都相同的串。

  • 同时从字符串正序、逆序遍历字符串,如果所有字符都相同,则是回文串,否则不是回文串。

8. String to Integer

  • 给定一个字符串,字符串可能包含非数字字符,例如字母和符号。如果以负号以外的非数字开头,则返回0,否则将字符串数字,含符号,转化为32位整型。

  • 略。

344. Reverse String

  • 给定一个字符串,将字符串逆置。

  • 同时从字符串的正序、逆序遍历字符串,交换两个字符的位置,直到两下标相等。

20. Valid Parentheses

  • 给定一个字符串表达式,判断表达式中的括号是否合法,一个合法的括号应该像:{[()]},这样的形式。

  • 维护一个栈,记作stack,然后遍历字符串,如果遇到左括号字符,则将该字符入栈,如果遇到右括号字符,则将栈顶出栈,判断括号是否匹配,如果匹配失败,则返回False,如果匹配成功,则继续遍历直到结束。如果遍历结束,栈不为空,则匹配失败,否则匹配成功。

5. Longest Palindromic Substring

  • 给定一个字符串,返回这个字符串的最大回文子串。

  • 由于枚举所有长度的子串,并判断该子串是否是回文子串的复杂度(O(n * m * m))过高,故考虑动态规划。在外层循环以下标j遍历字符串下标,j代表了子串的右界(0 <= j <= len(s)),内层循环以下标i遍历子串下标(0 <= i <= j),易知,当j=i时,原字符串s的子串sub_s,即s[i:j+1]是回文的,而当j-i=1时,如果s[i]=s[j]则子串sub_s,是回文的,而当j-i>1时,子串sub_s是否回文,取决于是否s[i]=s[j]s[i+1:j-1]是否为真,如果为真,则sub_s回文。所以,我们维护一个dp二维数组,其下标i,j表示原字符串从下标i开始到j结束(包含j)的子串是否为回文子串。在便利过程中不断更新最长的下标i, j最后返回最长回文子串。

49. Group Anagrams

  • 给定一个字符串型数组,将具有相同字符组成的字符串分别保存为一个字符串型数组,返回一个字符串型数组型的数组,作为结果。

  • 维护一个字典记作dic,其键值分别为按字典序排序后的字符串和字符串型数组。遍历字符串型数组,对每一个字符串s,按字典序排序,结果记作s_sorted,在dic中取s_sorted的值resres是一个字符串型的数组,然后将s添加进res,最后返回dicvalues作为结果。

42. Trapping Rain Water

  • 接雨水,给定一个整型数组height,数组内每个元素的值代表了“墙”的高度,墙的高度差可以用来储水,求给定一组墙高,能储多少水。

  • 首先遍历height,找到最高“墙”的下标i_max_height,初始化一个i_cur_peak=0代表当前“左高峰”,然后从左到i_max_height遍历墙高,期间,如果当前“左高峰”小于当前墙高,则更新“左高峰”,否则,更新雨水总量rain+=i_cur_peak-height[i],即“左高峰”减去当前墙高,直到遍历到墙的最高处为止。然后从右到i_max_height遍历墙高,逻辑同上。最后返回雨水总量。

15. 3Sum

  • 给定一个整型数组num,例如[-1, 0, 1, 2, -1, -4],返回一组结果,每个结果是一个数组,满足:在nums中选3个数字,这3个数字的和为0,过滤重复解。

  • 首先,3个数字a, b, c的和为0,即a + b = c,则将问题转化为了一个Two Sum问题,所以,我们先排序数组nums,并初始化targets数组:[-num for num in nums]。以下标i进入循环,初始化y_maptarget = targets[i]y_map用来记录是否y已经查找过。然后遍历nums[i + 1:]的每一个元素x,将target - x记作y,如果yy_map中,则添加结果-target, x, y作为一个解。否则,y_map[x] = x,记录当前xy_map字典中。最后去重结果并返回。

48. Rotate Image

  • 给定一个二维数组matrix,将它顺时针旋转90°,不可以申请新空间。

  • 首先,将matrix转置,以i, j为行列,进入循环,即对于每一个元素matrix[i][j] = matrix[j][i],需注意,此处ji开始,因为只需遍历matrix的上三角矩阵即可。然后,再将转置的矩阵martix水平翻转,即以i, j为行列进入循环,使得matrix[i][j] = matrix[i][num_col - j - 1],需要注意,j的上界是num_col // 2,因为num_col // 2为轴心。

66. Plus One

  • 给定一个数组nums,如[1, 2, 3],代表了123的各位,现在对个位加一,返回结果数组,如[1, 2, 4]

  • 初始化carry进位标识符,首先对个位加一,如果结果大于10,则模10后标记carry = 1,然后遍历剩余的位数加carry,同时判断是否进位,直到遍历结束。如果遍历结束后carry = 1,则插入1到数组下标为0处。

189. Rotate Array

  • 给定一个数组nums,与一个整数k,代表将前k位数移至数组末尾,就地修改数组nums

  • 以下标i进入循环,循环执行k次,每次nums.insert(nums.pop(0)即可。

215. Kth Largest Element in an Array

  • 给定一个数组记为nums,返回第k大的元素。

  • 首先通过heapq.heapify(nums)建堆,然后通过heapq.nlargest(k, nums)[-1]返回结果即可。

76. Minimum Window Substring

  • 给定原始字符串s与目标字符串t,返回一个最小窗口字符串sub_s,该窗口字符串是最小的字符串包含了目标字符串t所有字符。

  • 首先初始化两个字典记作start_dicend_dic,它们的键值分别为字符和出现的次数,然后遍历t中的每一个字符,更新这两个字典。然后计算t的长度记为t_length。初始化下标start = 0,然后以end = 0为下标遍历send表示s的右边界,如果s[end]end_dic中,而且end_dic[s[end]] > 0,则将start_dic[s[end]]自减,同时,如果start_dic[s[end]] >= 0,则将t_length自减,如果t_length == 0,则进入以下循环:如果s[start]end_dic中,而且end_dic[s[start]] > 0,如果start_dic[s[start]] < 0start_dic[s[start]]自增,否则breakstart += 1,然后根据当前最小窗口大小min_size是否大于end - start + 1来更新最小窗口大小min_size,和结果起始下标min_start。最终,如果min_size < len(s) + 1,则返回s[min_start: min_start + min_size],否则返回空串。

链表 - Linked List

206. Reverse Linked List

  • 给定一链表,将它就地逆序。

  • 初始化前驱节点pre_node=None,通过head_node遍历链表,通过cur_node临时存储head_node,然后更新head_node = head_node.next,接着更新当前节点的后继节点为前驱节点,cur_node.next = pre_node,最后将前驱节点更新为当前节点,pre_node = cur_node,直到遍历结束,最终返回pre_node为逆序后的头结点。

141. Linked List Cycle

  • 给定一个链表,判断链表是否存在“环”

  • 分别维护快慢指针,初始化为s_node, f_node = head, head.next,以快慢指针都为真的条件进入while循环,如果快指针与慢指针地址相等,则存在环,否则更新慢指针,s_node=s_node.next,更新快指针两次,f_node=f_node.nextif f_node: f_node = f_node.next,继续循环,如果循环结束,则不存在环。

2. Add Two Numbers

  • 给定两个链表,它们从头节点到尾节点分别表示数字的最低位到最高位,求将两链表相加的结果链表。

  • 初始化进位记录标识符count=0与结果头节点head,以两链表为真的条件进入循环,将当前节点结果相加,并加count后,模10,如果进位,则将count记为1,并保存结果cur_node.next = Node(x),然后更新cur_node=cur_node.next,直到循环结束。如果仍有较长链表遍历未结束,则遍历该链表,依次将其节点与count相加后添加在结果节点的cur_node后,直到遍历结束,最后检查进位是否需要需要创建新节点,并返回结果头节点。

21. Merge Two Sorted Lists

  • 给定两个有序链表,将他们合并成新的有序链表,并返回这个链表的头节点。

  • 初始化新头节点与当前节点记为head_nodecur_node,以两链表为真的条件进入循环,比较两链表的当前值,将值小的节点添加为cur_node的后继节点,然后更新该节点为之后继,然后更新cur_node=cur_node.next,直到循环结束。循环结束后,如果仍有链表为真,则将剩余部分作为cur_node的后继,然后返回头节点。

23. Merge k Sorted Lists

  • 给定k个有序链表,将他们合并成新的有序链表,并返回这个链表的头节点。

  • 同上,略。

树和图 - Trees and Graphs

98. Validate Binary Search Tree

  • 给定一个树,判断该二叉树是否是二叉查找树

  • 将中根遍历该二叉树的结果保存,检查该数组是否有序,如果有序,则是二叉查找树。

94. Binary Tree Inorder Traversal

  • 给定一颗二叉树,输出中根遍历结果。

  • 初始化栈stack,将元组(root, False)入栈,以栈不为空进入循环,将栈顶元组出栈,结果记为cur_node, visited,如果cur_node为真时,visited为真,即已经访问了该节点,则将该节点的值cur_node.val添加到结果数组,如果visited为假,即尚未访问该节点,则依次将该节点的右节点,该节点,该节点的左节点入栈,他们的访问标记分别为False, True, False,然后继续循环。最后打印结果。

102. Binary Tree Level Order Traversal

  • 给定一颗二叉树,输出层序遍历结果。

  • 初始化层节点数组level_nodes=[root],以层节点数组不为空为条件进入循环,向结果数组添加层节点数组内所有节点的值,然后初始化临时层节点数组tmp_level_nodes,遍历当前层节点的所有节点,添加他们的左右孩子节点(需为真),然后更新level_nodes=tmp_level_nodes,直到循环结束,最后返回结果数组。

103. Binary Tree Zigzag Level Order Traversal

  • 给定一颗二叉树,输出层序遍历结果,双数层的结果逆序。

  • 同上,在更新双数层节点时逆序即可,略。

116. Populating Next Right Pointers in Each Node

  • 给定一颗满二叉树,将二叉树的每一层变成一个链表(二叉树的节点数据结构已经有next成员变量)

  • 同上,在更新level_nodes==tmp_level_nodes后,遍历之,node.next = next_level_nodes[index + 1]更新后继节点。

117. Populating Next Right Pointers in Each Node II

  • 给定一颗二叉树,将二叉树的每一层变成一个链表(二叉树的节点数据结构已经有next成员变量)

  • 同上,略。

235. Lowest Common Ancestor of a Binary Search Tree

  • 给定一颗二叉搜索树与其两个节点,返回这两个节点的最小公共祖先。

  • 利用二叉搜索树性质并递归,如果两个节点的值pval, qval都小于root.val,那么公共祖先一定在root节点的左子树中,所以递归调用当前函数,根节点,即二叉查找树为root.left。相反,如果pval, qval都大于root.val,则公共祖先一定在root节点的右子树中,执行上述操作。最终,如果qval < root.val < pval,则root为最小公共祖先。

236. Lowest Common Ancestor of a Binary Tree

  • 给定一颗二叉树与其两个节点,返回这两个节点的最小公共祖先。

  • 初始化p_path, q_path分别保存先根遍历到p, q节点的路径。路径是指使用先根遍历,遍历该二叉树,直到某个节点的值等于目标节点的值node.val==target.val,并将完成标记flag=Ture,并将其他遍历结果移出路径,如何保存路径,请参见257. Binary Tree Paths。然后遍历两个路径p_path, q_path,最后一个相同的节点,即是最小公共祖先。

105. Construct Binary Tree from Preorder and Inorder Traversal

  • 已知一颗二叉树的先根和中根遍历结果,恢复二叉树。

  • 利用递归,以中根遍历结果数组不为空的条件进入函数,将先根数组pre_vals的首个节点值root_val出队列,并求出root_val在中根遍历数组中的下标,记为root_index,易知,中根遍历数组中,该节点下标左边的值均为其左子树的值,该下标右边的值均为其右子树的值。创建节点root=TreeNode(root_val),而root.left则递归本函数,入参分别为pre_valsin_vals[: root_index],而root.right则递归本函数,入参分别为pre_valsin_vals[root_index + 1:],最后返回根节点。

200. Number of Islands

  • 描述较为复杂,概述为寻找一个0-1矩阵中“孤岛”,即1构成的块的个数。

  • 维护一个visited数组,描述了某个下标i, j是否已经访问过,以下标i, j分别代表行列遍历图,如果图中grid[i, j] == 1,则进行深度优先遍历,需注意深度优先遍历的条件,即0<=i<=row, 0<=j<=col。如果i, j已经访问过,或者grid[i, j]==0则返回0,否则将本次遍历区域加1,并将visited[i, j]=1后,继续遍历,方向为上、下、左、右。最后以所有行列i, j为入口遍历完毕后,返回累计结果。

257. Binary Tree Paths

  • 给定一颗二叉树,输出先根遍历到所有叶子节点的路径字符串。

  • 初始化临时路径path与结果路径集合paths,先根遍历二叉树,遍历的过程中,每访问一个节点,如果该节点为空,则返回,否则将其添加到临时路径path中,并检查该节点是否有左右孩子节点,如果没有,则执行一次path临时路径到结果路径的序列化,结果添加到paths中。如果有左右孩子节点,则继续对该节点的左右孩子进行先根遍历。如果访问到叶子节点,则对path执行pop操作,将该节点出栈。最后返回结果路径集合paths

695. Max Area of Island

  • 给定一个二维数组grid,其元素为01,找到最大的“孤岛”,并返回其大小。

  • 维护result变量记录结果,维护一个二维数组visitedvistied[i][j]描述了grid[i][j]是否已经被访问过,然后对以i, j为下标进入循环,对grid[i][j]进行深度优先遍历。在深度优先遍历时,维护一个res = 1变量,如果grid[i][j] == 0,则返回0,如果grid[i][j] == 1,才能继续遍历,同时,将visited[i][j] = 1,并将res += 1,然后进行方向为上、下、左、右的深度优先遍历。如果res > result,则更新result = res,最后返回result作为结果。

547. Friend Circles

  • 给定一个二维数组M,其中元素为01,表示第j个人是否是第i个人的直接朋友。如果kj的朋友,ji的朋友,则ik是间接朋友,它们形成了一个“朋友圈”,求M中朋友圈的个数。

  • 维护一个visited数组,表示是否已经检查过第i个人的朋友圈。然后以i为第i个人的下标,进入循环,如果visited[i] == 1,即已经检查过该人的朋友圈,则continue,否则,首先将visited[i] = 1,然后初始化栈stack = [i],准备深度优先遍历:当栈stack不为空,则栈尾出栈记作j,则以k为第k个人的下标,进入循环,如果visited[k] == 0M[j][k] == 1,即第k个人的朋友圈尚未检查,而且jk互为朋友,则将k入栈。当以i为下标的外部循环结束,则将res += 1,结果自增。最后返回res作为结果。

104. Maximum Depth of Binary Tree

  • 给定一颗二叉树,输出二叉树的深度。

  • 略,参考层序遍历二叉树,遍历时记录深度即可。

回溯 - Backtracking

17. Letter Combinations of a Phone Number

  • 数字2-9中,每个数字对应电话号码上的几个字母,给定一个由2-9组成的字符串,输出所有可能的字母组合。

  • 初始化结果数组result,对给定数字字符串s以及每个字符所能对应的字母,进行深度优先遍历。即,遍历数字字符串s,对每一个下标i,与其对应的数字num,查询它可能的组成字母,依次递归调用深度优先遍历函数。深度优先遍历函数有四个参数,分别是当前下标i,数字字符串s,当前组合pattern,结果数组result,直到当前下标i == len(s)时,将pattern添加到result中,并返回结果数组。

39. Combination Sum

  • 给定一个整形数组,所有元素均为正数,记作candiates,给定一个目标数记作target,在candiates找到所有整数的组合,使他们的和等于target,每个元素可以使用多次。

  • 首先排序candidates,然后设计深度优先遍历函数dfs(candidates, target, last_num, result, results)。即,target == 0,则添加result到结果数组results,如果target < candidates[0],则返回。然后遍历candidate的每一个数字记作num,对每一个num,如果它大于target,则返回。如果它小于last_num,则continue,因为这个数字应该已经被遍历过了。否则,将num添加到临时result,然后递归调用dfs(candidates, target - num, num, result, results),最后通过result.pop()当前num,全部结束后返回results

排序和搜索 - Sorting and Searching

26. Remove Duplicates from Sorted Array

  • 给定一个已经排序的数组,数组中可能有重复元素,就地移除重复元素,并返回新的数组长度。

  • 初始化有序下标j == 0,以下标i = 0开始遍历排序数组nums,如果排序数组nums在有序下标j的值不等于在下标i的值,则将j += 1,并使得nums[j] = nums[i]。如果排序数组nums在有序下标j的值等于下标i的值,则什么都不做。最后返回j + 1作为结果。

88. Merge Sorted Array

  • 给定两个排序后的数组a, b,其中a数组足够长,归并两个排序数组至a数组并返回。

  • 从后遍历数组a, b,初始化三个下标a_i == len(a) - 1b_i == len(b) - 1, m_i = len(a) + len(b) - 1,分别代表a的下标,b的下标,结果下标,以a_i, b_i均大于等于0进入循环,如果a[a_i] > b[b_i],则a[m_i] = a[a_i],然后m_i -= 1a_i -= 1,反之同理,直到循环结束。如果b_i仍大于等于0,则说明b仍有剩余,这些数字都很小,所以以b_i大于等于0为条件进入循环,依次a[m_i] = b[b_i],然后m_i -= 1,然后b_i -= 1,最后结束。

75. Sort Colors

  • 三色排序,给定一个整型数组nums,只包含0, 1, 2三种元素,以O(n)的时间就地排序,不可使用基数排序,后返回结果。

  • 初始化三个下标i == 0, j == len(nums) - 1, k == 0,分别代表左下标,右下标,当前下标。然后k < j,即当前下标小于右下标为条件进入循环,如果nums[k] == 2,则交换num[k]num[j]的值,然后j -= 1,即右下标左移。如果nums[k] == 1,则k += 1。如果nums[k] == 0,则交换num[k]nums[i]的值,然后i += 1, k += 1,直到循环结束。

153. Find Minimum in Rotated Sorted Array

  • 给定一个有序数组nums,数组在某一位被翻转,例如:如[0, 1, 2, 3, 4] -> [3, 4, 0, 1, 2],返回最小元素。

  • 初始化三个下标i == 0, j == len(nums) - 1, mid == 0,分别代表左下标,右下标,中下标。然后以i < j为条件进入循环,计算mid = (i + j) // 2,如果nums[mid] < nums[j],则说明区间有序,更新j = mid,继续循环。如果nums[mid] >= nums[j],则说明区间内存在翻转,最小元素应在翻转区间,将i = mid + 1后,继续循环。当循环结束,返回nums[i]作为结果。

33. Search in Rotated Sorted Array

  • 给定一个有序数组nums和目标数target,数组在某一位被翻转,例如:如[0, 1, 2, 3, 4] -> [3, 4, 0, 1, 2],查找target,如果存在则返回其下标,否则返回-1

  • 初始化peak_i = -1, peak_num == -inf,代表最大值和其下标。遍历数组nums,找到最大值和其下标。此时,如果target大于peak_num,则返回-1。然后进行判断,如果target >= nums[0],则在[0:peak_i + 1]区间进行二分查找,如果target < nums[0],则target在翻转区间内,则在[peak_i + 1:]区间内进行二分查找。

74. Search a 2D Matrix

  • 给定一个二维数组nums和一个目标数target,该二维数组的每个元素是严格按下标增长的。在二维数组nums查找元素target,如果存在则返回True,否则返回False

  • 初始化peak_j = 0,以nums[j][0] <= target为条件,遍历nums每行的第一个元素,记录peak_j = j,在区间行nums[j][:]进行二分查找,后返回结果。

240. Search a 2D Matrix II

  • 给定一个二维数组nums和一个目标数target,该二维数组是的每一个行是有序的,每一列是有序的。在二维数组nums查找元素target,如果存在则返回True,否则返回False

  • 初始化peak_j = 0,以nums[j][0] <= target为条件,遍历nums每行的第一个元素,记录peak_j = j,以下标i遍历0行到j行,在区间行nums[i][:]进行二分查找,后返回结果。

252. Meeting Rooms

  • 给定一个数组intervals,数组内的元素是一个整型二元组,表示了会议的开始和结束时间,如果会议时间有冲突,判断会议之间是否有冲突。

  • 将该数组按开始时间排序后结果记为intervals,然后以i为下标遍历数组,如果intervals[i].start < intervals[i-1].end,则有冲突,返回False,否则继续循环直到结束,返回True,即没有冲突。

253. Meeting Rooms II

  • 给定一个数组intervals,数组内的元素是一个整型的二元组,表示了会议的开始和结束时间,因为会议时间有可能冲突,返回最多需要的会议室数量。

  • 维护一个字典interval_rooms_map,它的键是会议开始或结束时间,它的值时此刻会议室的“名义数量”,然后遍历intervals,对interval_rooms_map[interval.start] += 1,对interval_rooms_map[interval.end] -= 1,表示每个会议interval的起始时间对会议室的“名义数量”,即如果会议开始,那么占用数需要自增,如果结束,那么占用数自减。然后,获取该字典的所有键并升序排序,其结果记为keys_sorted。然后,初始化max_room = 0, cur_room = 0,代表最大会议室数量和当前会议室数量,通过key_sortedkey遍历interval_rooms_map的值,并使得cur_room += interval_rooms_map[key],同时更新最大会议室数量max_room = max(max_room, cur_room),最后返回max_room

56. Merge Intervals

  • 给定一个数组intervals,数组内的元素是一个整型的二元组,表示了开始和结束时间,由于时间可能重叠,返回合并后的intervals数组,例如:[[1, 3], [2, 6], [8, 10]]合并后应该为[[1, 6], [8, 10]

  • 首先以interval.start排序intervals数组,然后初始化结果数组results = [intervals[0]],从下标为1开始遍历排序后的intervals数组,如果interval.start <= results[-1].end,即说明出现重叠,则results[-1].end = max(interval.end, results[-1].end)。否则,添加新合并区间results.append(interval),最后返回结果。

动态规划 - Dynamic Programming

121. Best Time to Buy and Sell Stock

  • 给定一个数组prices,数组内每个元素代表了某个股票某时刻的价格,选择一个时间买入,一个时间卖出,返回最大的收益。

  • 初始化最大收益s_max=0,最小价格p_min=-inf,遍历prices中的每个价格price,取p_min = min(price, p_min),然后计算当前买入价格收益profit = price - p_min,选择更新最大收益s_max=max(profit, s_max),最后返回s_max作为结果。

53. Maximum Subarray

  • 给定一个整型数组nums,返回最大的子数组的和。

  • 初始化dp = [0] * len(nums),以下标i遍历数组nums,则dp[i] = max(nums[i], nums[i] + dp[i - 1]),即以下标为i截止的子数组nums[:i+1],它的最大 dp[i] = max(num, num + dp[i - 1])其中dp[i]为第i个下标的最大子数组和。

70. Climbing Stairs

  • 给定一个n阶楼梯,一次可以爬1阶楼梯或者2阶楼梯,返回爬到n阶,有多少种爬法。

  • 初始化dp = [0] * (n + 1)dp[i]表示爬到第i阶,有多少种爬法,所以,可以写出递推式:dp[i] = dp[i - 1] + dp[i - 2],最后,返回dp[n - 1]作为结果。

198. House Robber

  • 给定一个数组numsnums中每个下标i对应的nums[i]代表i位置财产的价值。限定不可以同时拿取两个相邻位置的财产,返回可拿取财产的最大值。

  • 初始化dp = [0] * len(nums),则有初始情况dp[0] = nums[0]dp[1] = max(nums[0], nums[1])dp[i]代表了当财产个数为i个时,可拿取财产的最大值,所以,可以写出递推式:dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]),最后返回max(dp[-1], dp[-2])作为结果。

152. Maximum Product Subarray

  • 给定一个整型数组nums,返回最大的子数组的积。

  • 初始化dp = [0] * len(nums)dp[i]表示以nums[i]为最后一个元素的子数组的最大子数组的积。由于负数的存在,需要初始化dp_min = [0] * len(nums)dp_max = [0] * len(nums)dp_min[i]dp_max[i]分别代表以nums[i]为最后一个元素的子数组的最小数组积和最大数组积。dp_min的意义在于,由于负数的存在,如果dp_min[i - 1]是一个负数,而nums[i]同样是一个负数,则dp_min[i - 1] * nums[i]将会是正数。所以我们可以写出递推式:dp[i] = max(dp_min[i-1] * nums[i], dp_max[i-1] * nums[i], nums[i]),然后更新dp_max[i] = dp[i]dp_min[i] = min(dp_min[i-1] * nums[i], dp_max[i-1] * nums[i], nums[i]),最后返回max(dp)作为结果。

139. Word Break

  • 给定一个字符串s,给定一个字符串数组wordDic,其元素是一些单词。如果s能被wordDic中的单词组合而成,则返回True,否则返回False

  • 初始化dp = [False] * len(s) + 1dp[i]表示以s[i]结尾的子串,是否能被wordDic中的单词组合。则外循环以下标i遍历字符串s,内循环以下标j遍历ilen(s),如果dp[i]为真,即以s[i]结尾的子串可以被wordDic中的单词组合,而且子串s[i: j+1]wordDic中,那么dp[j + 1] = Ture,最后,返回dp[-1]作为结果。

62. Unique Paths

  • 给定一个二维数组的行列m, n,从位置mat[0][0]出发,到达mat[-1][-1],限定能向右或者向下移动,返回走法的总数。

  • 初始化dp = [[1 for _ in range(0, n)] for _ in range(0, m)]dp[i][j]表示从出发点mat[0][0]到该点的走法数量。则以下标i, j遍历行列,则可以写出递推式:dp[i][j] = dp[i - 1][j] + dp[i][j - 1],最后返回dp[-1][-1]作为结果。

120. Triangle

  • 给定一个数组triangletriangle中的元素均为整型数组。现自顶向下在triangle中的每行选择一个数,限定在i行选择第j个数后,在i+1行选择时只能选择j, j + 1,最终使得它们的和最小,并返回结果。

  • 初始化dp = [0] * (len(triangle) + 1)dp[i]表示“自底向上”选择数字时,第i行为止最小的和。则以i为下标,倒序遍历triangle的每一行,以j为下标遍历triangle[i]每一个元素,可以写出递推式:dp[j] = traiangle[i][j] + min(dp[j], dp[j + 1]),最后返回dp[0]作为结果。

Releases

No releases published

Packages

No packages published