frankguodongchen-CSDN博客

原创 LeetCode 621. Task Scheduler

LeetCoee 621因为在相同task之间有cooldown的时间，那么最多的task需要尽量想办法分开，把其他的task放进cooldown的时间里来。如果其他的task可以完全填满这些cooldown的空格，那么最大时间其实就是所有task的时间，因为没有任何的浪费。比如cooldown时间是2，有AAA，BB，CC，DD，那么可以做成ABCDABCDA，使用BCD任务填充完需要cooldown的时间（超过也没有关系）。如果不能填充完，那么我们就要计算这些cooldown需要的额外时间。还有一

2020-08-02 03:04:04 122

原创 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

LeetCode 309考虑三种状态的转换，买入，卖出，cooldown，买入之后可以保持不动继续保持买入的状态，卖出之后进入cooldown，在cooldown也可以保持不变。cooldown之后可以买入。根据这个状态转换我们可以有这样的公式buy【i】 = min（之前买的 buy【i-1】，cooldown之后买的 price【i】 - cooldown【i-1】）sell【i】= price【i】-buy【i-1】（卖出股票）cooldown【i】 = max（sell【i-1】卖出之后进入

2020-08-02 03:03:37 128

原创 LeetCode 140. Word Break II

LeetCode 140可以使用dfs的方法来查找，不断的match prefix的部分，如果成功，那么递归继续，直到能match到字符串结束，如果不成功，那么就增加prefix的部分继续match。增加一个优化就是，先考虑是否有足够长的字符串可以用于match，如果不够，可以快速结束。 def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: wordLets = set(''.join(

2020-08-02 03:03:03 145

原创 LeetCode 70. Climbing Stairs

LeetCode 70考虑当前的第i个台阶，那么到达i的方法有两种，从i-1或者从i-2，那么这个问题可以转换为递归来做，加上memo，那么可以减少重复计算。使用动态规划相对来说也比较容易，有dp【i】=dp【i-1】+dp【i-2】的公式。class Solution: def climbStairs(self, n: int) -> int: dp = [0] * (n+1) dp[0] = 1 dp[1] = 1 f

2020-08-02 03:02:45 82

原创 LeetCode 479 largest-palindrome-product

LeetCode 479这个题目除了BruteForce的方法，我没有想出好的解法。最后求助于其他人的解法了，看到一个数学解法比较有意思，转成了python： def largestPalindromeMath(self, n: int) -> int: '''假设确实存在 P = X * Y, X，Y都是接近10^n的数，那么记 X = 10^n...

2020-08-01 02:33:05 90

原创 LeetCode 258. Add Digits

LeetCode 258直接的办法是通过一个loop不断的加到个位数位置。但是考虑结果的范围只可能是1-9 （除了0本身之外）。把1到20的数列出来试一下，可以知道其实是1到9之后开始循环。 def addDigits(self, num: int) -> int: if num == 0: return 0 r = num % 9 if r == 0: return 9 return r ..

2020-07-27 00:50:34 91

原创 LeetCode 142. Linked List Cycle II

LeetCode 142这个问题的算法和这个一样（ Floyd’s Tortoise and Hare 算法）https://blog.csdn.net/frankguodongchen/article/details/107479459 def detectCycle(self, head: ListNode) -> ListNode: if head == None: return None slow = head.next fast

2020-07-27 00:46:52 81

原创 LeetCode 797. All Paths From Source to Target

LeetCode 797要求的是所有的path，所以简单的dfs就可以实现。 def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: if len(graph) == 0: return [] result = [] currentPath = [0] end = len(graph)-1 def d

2020-07-27 00:46:22 161

原创 LeetCode 79. Word Search

LeetCode 79从数组的每个位置进行比较第一个字母，如果相同，尝试进行一次dfs的搜索。 def exist(self, board: List[List[str]], word: str) -> bool: m = len(board) n = len(board[0]) def dfs(board, i, j, word, index, visited) -> bool: if index >=

2020-07-27 00:46:00 49

原创 LeetCode 203. Remove Linked List Elements

LeetCode 203这个删除本身其实比较容易，只是想介绍一下哨兵的用法，加上一个哨兵之，我们不需要特殊处理head被删除的情况。 def removeElements(self, head: ListNode, val: int) -> ListNode: sentryNode = ListNode() sentryNode.next = head p1 = sentryNode p2 = head whi

2020-07-27 00:45:44 71

原创 LeetCode 210. Course Schedule II

LeetCode 210使用拓扑排序，先修没有依赖的课，去掉这个课之后，再找已经没有依赖的课。如果最后还剩下课，那就是无法完成的。 def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: result = [] graph = collections.defaultdict(list) graph2 = collections.defa

2020-07-27 00:45:19 71

原创 LeetCode 347. Top K Frequent Elements

LeetCode 347可以建立一个dictionary，数值做为key，数量作为value，然后根据value来排序，得到top k个。 def topKFrequent(self, nums: List[int], k: int) -> List[int]: dic = collections.defaultdict(pair) for num in nums: if num not in dic:

2020-07-27 00:45:05 73

原创 LeetCode 1344. Angle Between Hands of a Clock

LeetCode 1344这个题目主要还是数学问题，如果按照12点是0度，一圈是60分钟=360度，所以每分钟是6度。小时指针每个小时是30度，到那时还要加上分钟的偏移 30度/60*分钟数。超过360度的话，取一下模。然后就是算一下夹角，取小的一边。 def angleClock(self, hour: int, minutes: int) -> float: minuteAngle = minutes * 6 hour

2020-07-27 00:44:49 106

原创 LeetCode 430. Flatten a Multilevel Doubly Linked List

LeetCode 430如果我们能把children全部flatten掉，那么其实就是要把chiildren faltten掉之后的list插入到当前节点的后面。children的flatten我们可以使用递归来实现。 def flatten(self, head: 'Node') -> 'Node': curr = head while curr != None: if curr.child != None:

2020-07-27 00:44:29 84

原创 LeetCode 662. Maximum Width of Binary Tree

LeetCode 662按照层遍历，给每个node一个position的数组，每个left child是parent *2， right child是parent *2 + 1，进入一个新的level的时候记住最左边node的position，然后用遍历这层找到最大的width。 def widthOfBinaryTree(self, root: TreeNode) -> int: lastLevel, numAtMostLeft, max_width = 1, 1, 0

2020-07-27 00:44:02 80

原创 LeetCode 153. Find Minimum in Rotated Sorted Array

LeetCode 153研究一下rotated之后数组的特点，可以分成两段，前一段升序，后一段也是升序，只是后一段的升序小于前一段。如果拿第一个数做为标记数字，采用二分法，在中间找一个数，比第一个数大的话，那么最小的应该在后半段，如果小的话，那么应该是在前半段（包括自己）。 def findMin(self, nums: List[int]) -> int: if len(nums) == 0: raise Exception("not valid input")

2020-07-26 07:55:53 62

原创 LeetCode 15. 3Sum

LeetCode 153sum的问题，如果先确定一个数，那么我们就可以转为2sum的问题。根据这个思路，我们先排序数组，然后确定一个数，然后就在剩下的数组中寻找2sum的答案。要注意的一点是，如果有相同的数已经处理过了，我们可以跳过 def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() n = len(nums) result = [] for

2020-07-26 07:48:39 60

原创 LeetCode 463. Island Perimeter

LeetCode 463第一个想法是可以通过dfs找到所有的block，然后加上他们的边数（邻居是0或者在最边上），应该也是可以做的。再考虑这个问题，其实还是可以简化的，因为只有一个island，每个block其实有4个边，如果和他相邻的block也是island的话，他们会有一个共享的边，都是要去掉的（-2）。转换为我们看有多少相邻的属于island的block，我们也不需要dfs，只要遍历整个数组就行。 def islandPerimeter(self, grid: List[List[in

2020-07-26 07:48:18 56

原创 LeetCode 332. Reconstruct Itinerary

LeetCode 332因为给的这个题目是确保有解的，这样的话，从起点开始肯定是可以到达每个点，并且肯定只有一个终点。通过DFS的方式，我们可以找到这个终点，一旦不能再去其他的地方，我们可以把终点加入到我们的path里面进去，同时从图上去掉终点。回退到进入终点的点，看是否还能去其他地方，如果不能，也可以加入到这个path。如果中间点还可以去其他的地方，那么在加入path的时候，需要插入到去终点之前的位置。 def findItinerary(self, tickets: List[List[str

2020-07-25 23:11:24 51

原创 LeetCode 264. Ugly Number II

LeetCode 264这个有点类似于merge sort，基于已经得到的ugly number，分别*2， *3，*5 可以得到新的ugly number，然后我们需要在他们中找到最小的加入进来。 def nthUglyNumber(self, n: int) -> int: dp = [] dp.append(1) p2, p3, p5 = 0, 0, 0 for i in range(1, n):

2020-07-25 23:10:11 103 1

原创 LeetCode 62. Unique Paths

LeetCode 62如果我们用一个二维数组来表示每个i，j位置可能的paths个数，那么对于dp【i】【j】，应该有dp【i】【j】=dp【i-1】【j】+dp【i】【j-1】（只能从左边或者上边进入当前格子）再简化为使用一维数组，我们从第一行开始计算下一行，把当前行的结果都update的到这个数组上。那么就有dp【i】=dp【i-1】（左边的结果）+dp【i】（上一行的结果） def uniquePaths(self, m: int, n: int) -> int:

2020-07-25 23:09:49 40

原创 LeetCode 279. Perfect Squares

LeetCode 279先看怎么拆解一个数(n)到perfect square的和, 可以考虑减去(i)的平方,然后再继续拆解n-ii 的数. 按照这个想法,拆解可以通过递归或者dp来做.在知道了所有的拆解方法之后,我们可以统计最小的可能.如果我们用dp[n]的数组来记录n的最小拆解数,那么我们可以得到dp[n+1] = min(1 + dp[n+1 - xx] for x in rang(x, sqrt(n+1)))转化为代码: def numSquares(self, n: int) -

2020-07-25 23:09:26 50

原创 LeetCode 129. Sum Root to Leaf Numbers

LeetCode 129这个题目只需要按层遍历, 利用一个queue,把当前层放入queue,同时计算出当前的数值加入到结果就可以了.class Solution: def sumNumbers(self, root: TreeNode) -> int: q = [(0, root)] result = 0 while q: pv, cnode = q.pop(0) if cnode.left

2020-07-25 23:08:50 52

原创 LeetCode 103. Binary Tree Zigzag Level Order Traversal

LeetCode 103在普通的层遍历上面，加上一个控制，如果完成一层遍历之后，根据情况确定是否要反转一下当前层遍历的结果，加入最终结果 def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]: if root == None: return [] q = [root] totalCountInLevel = 1 leftToRight = True

2020-07-25 07:42:38 90

原创 LeetCode 287. Find the Duplicate Number

LeetCode 287最简单的想法就是先排序，然后遍历去检查。 def findDuplicate2(self, nums: List[int]) -> int: nums.sort() for x in range(1, len(nums)): if nums[x] == nums[x-1]: return nums[x]但是题目里面给出了两个限制：You must not modify th

2020-07-21 04:54:11 130

原创 LeetCode 222. Count Complete Tree Nodes

LeetCode 222最简单的方法就是遍历整个Tree，我们就知道数的节点的个数。但是这样明显没有充分利用给的条件，并且需要遍历整个数，在complete tree的情况下不是最好的方法。我们知道如果是full complete tree，那么节点的个数是2的n次方减1 （n是高度）。利用这个条件，我们转换问题成，如果是full complete tree就利用这个方式做，如果不是那么就计算左子树和右子树的节点数。 def countNodes(self, root: TreeNode) -&

2020-07-20 01:32:19 89

原创 LeetCode 260. Single Number III

LeetCode 260如果所有的数都是成对出现的，那么所有的数xor之后的结果就是0. 里面有两个数是不同的，那么我们知道结果不是0，暂时记作（ones）。如果说我们的结果是a和b的话，那么就有a xor b = ones。所以只要找到其中的一个，我们就能得到另外一个。在ones中找到其中的一个1的bit，对于这个bit，我们知道a和b是不一样的，通过这个bit，我们可以把数分成两个group，一个和a的这个bit是一样的，一个是和b的这个bit是一样。分别在这个两个group内做xor，我们就能得到

2020-07-20 01:24:18 61

原创 LeetCode 137. Single Number II

LeetCode 137除了其中的一个之外每个数都是出现了3次，那么对于其中的一个bit，如果是相加应该是3*【重复数的bit和】+唯一数的bit值。所以我们直到mod

2020-07-20 01:06:15 43

原创 LeetCode 174. Dungeon Game

LeetCode 174这个题目使用动态规划，从数组右下角开始向左上角解决会比较容易。使用一个二位数组来记录在每个位置上需要的生命值，最小是1（如果是0，那么就挂了）。为了方便处理，我们多给这个二维数组加一条边（m+1 * n+1）。在找到公主之后剩下的生命值最小是1.每次我们可以从左边过来，或者上边过来，反过来算的时候，那么即使从右边或者下边过来小的这个，min（dp【i+1】【j】， dp【i】【j+1】），这些是他们需要进入下一个的生命值，对于当前的伤害或者加强，也是需要减掉的，所以这个min（

2020-07-19 11:11:13 77

原创 LeetCode 60. Permutation Sequence

LeetCode 60分析一下这个例子：“123”， “132”， “213”，“231”， “312”， “321”。第一位置有n中可能，确定第一个位置的数字之后，后面可以有（n-1）！种可能，那么要求第k个permutation，我们可以先除（n-1）！得到第一位的数是什么。然后通过类似的方法，我们可以除（n-2)! 得到第二位数是什么。class Solution: def getPermutation(self, n: int, k: int) -> str:

2020-07-19 10:42:57 66

原创 LeetCode 130. Surrounded Regions

LeetCode 130这个题目使用逆向思维会更加容易做，考虑那些是不能全部被X包围的，然后把这些排除掉。要不被X包围必然是和边界上的一个O有连接，那么我们从边界上的O出发，做DFS或者BFS，把所有的这些O找出来，其他的都是可以被X包围的。 def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead.

2020-07-19 06:29:32 51

原创 LeetCode 787. Cheapest Flights Within K Stops

LeetCode 787第一个思路是通过BFS，搜索最多k个stop的范围，然后找到最便宜的结果。 def findCheapestPrice2(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int: fmap = collections.defaultdict(list) for s, d, p in flights: fmap[s].ap

2020-07-19 06:16:38 127

原创 LeetCode 368. Largest Divisible Subset

LeetCode 368第一个思路是把所有的subset都求出来，然后取里面最大的长度。先把所有的数排序，遍历数，把这个书加入到能被整除的集合中去，由于我们是从小到大排的，如果能被最后一个整除的话，那么就能被前面的整除。 def largestDivisibleSubsetTimeout(self, nums: List[int]) -> List[int]: if len(nums) == 0: return [] rl = [] nums.

2020-07-19 06:03:51 96

原创 LeetCode 380. Insert Delete GetRandom O(1)

LeetCode 380为了能够random的以O（1）取到一个数，基本的想法是要存在一个数组中，这样产生一个随机数之后，我们可以一O（1）读取这个数。同时要能一O（1）插入和删除，那么们需要快速直到这个数的位置，那么我们需要把这个数的位置记录在一个hash表中。在每次插入和删除之后需要调整这个hash表。如果hash表存的是位置的值，如果我们删除中间的数会造成其他的数的位置有变化，但是删除队尾的数就没有这个问题，这里我们可以做一个交换，把要删除的数交换到队尾，然后再进行操作。class Randomi

2020-07-19 05:31:43 63

原创 LeetCode 75. Sort Colors

LeetCode 75因为只有三种颜色，并且需要inplace来做修改，我们直到排序之后一定是【x个0，y个1，z个2】这样的结果，我们可以遍历数组，把等于0的交换到最前面去，把等于2的交换到最后面去。 def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ r0 =

2020-07-19 05:24:13 81 1

原创 LeetCode 392. Is Subsequence

LeetCode 392这个题目比较简单，使用两个指针（pattern字串的指针和目标字串的指针），如果相等那么同时移动，如果不等，只要移动目标字串的指针，继续比较，一直到pattern字串指针为空位置算是匹配成功；否则匹配失败。 def isSubsequence(self, s: str, t: str) -> bool: if len(s) > len(t): return False si = 0 ti = 0 w

2020-07-19 05:15:05 52

原创 LeetCode 518. Coin Change 2

LeetCode 518求换零钱可能的次数，记作f(amount), 假如使用了一枚某一种coin，那么可能的次数是f（amount- coin的面值）。我们可以用dfs的方法，一直搜索直到最后剩余为0，如果剩余不能为0，那么这个不能算一种方法。另外面值超过amount的coin也无法使用，我们可以sort 一下coins，快速的排除掉大于amount的那些coins。另外我们可以使用memo记录下来已经计算过的可能性。 def change(self, amount: int, coins: L

2020-07-19 04:28:29 60

空空如也

空空如也