1 frankguodongchen

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 9w+

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

LeetCode 332. Reconstruct Itinerary

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

2020-07-25 23:11:24

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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。