刘洋
412天前
2374
举报

怕捶客的刷题打卡

迫于将来可能的失业焦虑,我将从今天开始,在这里每日打卡刷算法题。每次至少1道题,并且把思路和代码贴上来供大家批评讨论

题库从Leetcode刷起,主刷medium难度,主要语言为Python,遇到必须用内存级操作的就C++。

🐛🐛🐛!


全部回帖 (36)


刘洋
楼主
412天前

3月4日 Rotate List

定义一次旋转:把最后一个元素移到头部

输入:head (单链表list node),k (int)

输出:旋转k次之后的单链表head node

示例: - Input: 1->2->3->4->5->NULL, k = 2 - Output: 4->5->1->2->3->NULL

代码:

def rotateRight(head, k):
    if not (head and head.next):
        return head

    ptr = ListNode(head.val)
    ptr.next = head.next
    cnt = 1
    while ptr.next:
        cnt += 1
        ptr = ptr.next
    k = k % cnt
    if k == 0:
        return head

    ptr_s, ptr_f = ListNode(0), ListNode(0)
    ptr_s.next = head
    ptr_f.next = head
    for _ in range(k):
        ptr_f.next = ptr_f.next.next

    while ptr_f.next.next != None:
        ptr_s.next = ptr_s.next.next
        ptr_f.next = ptr_f.next.next
    new_head = ptr_s.next.next
    ptr_s.next.next = None
    ptr_f.next.next = head

    return new_head

注释:

此题需考虑较多边界情况:输入链表的长度为0或1时,直接返回;旋转次数k可整除链表长度时,直接返回。首先遍历链表,得到长度cnt,然后kcnt取余。随后,定义两个指向头部的快慢指针,使快指针比慢指针领先k个位置,然后快指针遍历到尾部就行了。

1
0
回复 # 1

work007
412天前

太强了!

0
0
回复 # 2

0
0
回复 # 3

刘洋
楼主
412天前
查看回复(1)

别捧杀了,不如竞猜一下能坚持几天(

1
0
回复 # 4

work007
411天前
查看对话

刘洋:

别捧杀了,不如竞猜一下能坚持几天(

一天!每一天!

0
0
回复 # 5

刘洋
楼主
411天前

3月5日 138. Copy List with Random Pointer

经典linked list题。每一个节点不仅指向链表下一个节点,还指向随机的一个节点。数据结构定义如下:

class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

要求函数对输入链表进行深拷贝(deep copy),并返回拷贝list的头节点。

代码实现如下:

def copyRandomList(head: 'Node') -> 'Node':
    if not head:
        return

    tmp = head
    while tmp:
        nxt = tmp.next
        tmp.next = Node(tmp.val)
        tmp.next.next = nxt
        tmp = tmp.next.next

    tmp = head
    while tmp:
        if tmp.random:
            tmp.next.random = tmp.random.next
        tmp = tmp.next.next

    tmp = head.next
    while tmp.next:
        tmp.next = tmp.next.next
        tmp = tmp.next

    return head.next

此题的核心是理解并实现对象的深拷贝。Trivial解法是先遍历一次链表,并赋值给N个新节点。然后根据每个节点的random节点,每次都遍历一次链表。时间复杂度为O(N^2)。

后来看了一波discussion,里面最常用的解法是在每一个节点后插入一个重复节点(1 pass),然后用重复节点储存原节点的random节点(2 pass),最后删除原节点(3pass)。这种解法的时间复杂度为O(N),extra space complexity为O(1),差不多是最优解了。还有用hash table或dict实现的,会有O(N)的额外空间复杂度。

1
0
回复 # 6

刘洋
楼主
411天前
0
0
回复 # 7

圆圆圆
410天前

监督刘工

0
0
回复 # 8

刘洋
楼主
410天前

3月6日 46. Permutations

经典题:输出列表元素的全排列

既然是经典题,不妨写得花哨一点,七行代码如下:

def permute(nums: List[int]) -> List[List[int]]:
    if len(nums) == 1: return [nums]
    perms = []
    for i, num in enumerate(nums):
        nums_cp = list(nums)
        nums_cp.pop(i)
        perms += map(lambda x: [num] + x, self.permute(nums_cp))
    return perms

笔记:排列题当然用递归,列表的排列问题可以分解为[单个元素]与列表剩余元素排列相加的问题。这里先遍历链表,每一次都向结果列表perms里添加当前元素与剩余元素排列的结果。最后秀一下排行(

Runtime: 32 ms, faster than 95.50% of Python3 online submissions for Permutations. Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Permutations.

1
0
回复 # 9

刘洋
楼主
409天前

3月7日 48. Rotate Image

输入一个二维数组,返回顺时针旋转90°后的结果。要求in-place。(可以当成对一张图片的旋转操作)

直接上代码:

def rotate(matrix) -> None:
    n_row = len(matrix)
    if n_row < 2:
        return
    n_col = len(matrix[0])

    for i in range(n_row//2):
        for j in range(i, n_col-i-1):
            tmp = [matrix[i][j]]
            for _ in range(4):
                i, j = j, n_col - i - 1
                tmp.append(matrix[i][j])
                matrix[i][j] = tmp[0]
                tmp.pop(0)

笔记:此题主要是弄清楚矩阵transform的数学关系式。容易得到,位于[row, col]的entry将会被旋转到位置[col, n-row-1]。然后,可以把矩阵分成如图四等份,从第一部分开始操作,循环四次。

|1|1|1|2|
|4|1|2|2|
|4|4|3|2|
|4|3|3|3|

为了实现in-place转换,我在这里使用了一个queue结构,用于暂时储存entry值。

一遍通过,Runtime faster than 98.12%, memory Usage less than 100.00%.

0
0
回复 # 10

刘洋
楼主
408天前

3月8日 14. Longest Common Prefix

今天在赶ART4004作业,所以只做了easy难度的(

输出字符串列表中所有字符的最长公共前缀

代码如下

def longestCommonPrefix(strs) -> str:
    if not strs:
        return ''

    prefix = ''
    zipped = list(zip(*strs))
    for i in range(len(zipped)):
        if all(char == zipped[i][0] for char in zipped[i]):
            prefix += zipped[i][0]
        else:
            break

    return prefix

这题很简单就不做笔记了。。主要是用了个zip()函数。

Runtime faster than 96.91%. Memory Usage less than 100.00%.

0
0
回复 # 11

刘洋
楼主
407天前
查看回复(1)

3月9日 101. Symmetric Tree

判断一棵二叉树是否对称

丑陋的代码如下:

def isSymmetric(root: TreeNode) -> bool:
    return twoTreesSymmetric(root.left, root.right)

def twoTreesSymmetric(root_1: TreeNode, root_2: TreeNode) -> bool:
    if not (root_1 or root_2):
        return True
    if (root_1 and not root_2) or (not root_1 and root_2):
        return False
    if root_1.val != root_2.val:
        return False

    if (not root_1.left and not root_1.right and not root_2.left and not root_2.right):
        return True if root_1.val == root_2.val else False
    else:
        return twoTreesSymmetric(root_1.left, root_2.right) and twoTreesSymmetric(root_1.right, root_2.left)

此题边缘情况很多,所以accepted rate略低,交了好几次。而且代码写得也很丑陋。。基本思路是比较节点的左子树和右子树是否对称,所以用到一个helper函数,用来比较左子树的左子树和右子树的右子树左子树的右子树和右子树的左子树是否对称。(跟绕口令似的...

更草的是这个题我在面试的时候做过。以后多练练Binary Tree题。

Runtime faster than 70.14% . Memory Usage less than 100.00%.

0
0
回复 # 12

刘洋
楼主
407天前
查看对话

刘洋:

3月9日 101. Symmetric Tree

判断一棵二叉树是否对称

丑陋的代码如下:

def 

第一个函数要判断一下空根节点。。忘了加上去

0
0
回复 # 13

刘洋
楼主
406天前

3月10日 49. Group Anagrams

将字符串列表中的“同分异构体”分组并返回

例如:["eat", "tea", "tan", "ate", "nat"] => [["ate","eat","tea"], ["nat","tan"]]

今日这道题非常搞心态,自创的方法也一直通过不了最后一个test case,但还是把问题代码贴上来

alpha2prime = {
    'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e': 11, 'f': 13, 'g': 17, 'h': 19,
    'i': 23, 'j': 29, 'k': 31, 'l': 37, 'm': 41, 'n': 43, 'o': 47, 'p': 53,
    'q': 59, 'r': 61, 's': 67, 't': 71, 'u': 73, 'v': 79, 'w': 83, 'x': 89,
    'y': 91, 'z': 101,
}

def groupAnagrams(strs):
    if len(strs) == 0:
        return [[]]

    anagram_dict = {} 

    for string in strs:
        hash_val = 1
        for char in string:
            hash_val *= alpha2prime[char]
        anagram_dict[hash_val] = anagram_dict.get(hash_val, []) + [string]

    return [anagram_dict[key] for key, _ in anagram_dict.items()]

我的基本思路是维护一个hash table(在这里是Python dictionary),值是字符串的hash值。为了保证正确性,hash function需要满足以下条件:

  1. 对于同分异构字符串,需要返回相同的结果。
  2. 对于非同分异构字符串,不能发生collision。

按照我个人对hashing的理解,一般来说,a good hash function(可验证性+正确性+运算快)是用来对付顺序容器的。例如针对字符串,hash(s)=s[0]+s[1]⋅p+s[2]⋅p^2+...+s[n−1]⋅p^(n−1). 然而对于无序对象,这种hashing显然不正确。所以Python会存在"xxx object is not hashable"的异常类型。

为了保证无序结构hashing的正确性,就必须保证

  1. 各元素的运算顺序不影响结果,也就是“交换律”。这里我采用的是乘法。
  2. 不collide。所以,每一个字母对应一个素数prime number,可以保证结果唯一性。

于是代码就这么写出来了。但生活给我了巨大的教训

  1. 数学上正确的东西,在实际中可能并不会按理想中那样work。因为,计算机有overflow啊!!!于是,最后一个test case我挂了。我猜测这个case是leetcode后来加的(因为是第101个),含有很长的单词,目的就是为了防止我这种暴力素数相乘人士偷鸡。
  2. 我的实现里直接把alphabet to prime的mapping写成了值。这一点是非常不值得学习的,相当于用脑力代替算法(

这道题比较好想、效率又比较高的解则是用一个length=26的字符串,标记a~z每一个字符在每一个字符串里的occurrence。明天把正确代码补上。。

0
0
回复 # 14

刘洋
楼主
405天前

3月11日 56. Merge Intervals

合并多个区间

例如:输入[[1,3],[2,6],[8,10]],返回[[1,6],[8,10]].

代码:

def merge(intervals):
    if not intervals:
        return []

    intervals.sort()
    foo = []
    for i in range(len(intervals)):
        interval = intervals[i]
        if i == 0 or interval[0] > foo[-1]:
            foo += interval

        elif interval[1] > foo[-1]:
            foo.pop()
            foo.append(interval[1])

    return [(foo[i], foo[i+1]) for i in range(0, len(foo), 2)]

给昨天补打的卡,晚了半小时。。此方法O(NlogN),非最优解。用了一个stack结构。

Runtime faster than 99.03% . Memory Usage less than 6.52%. 内存用这么多,奇耻大辱啊(

0
0
回复 # 15

刘洋
楼主
404天前

3月12日 刷了两道

62. Unique Paths 这题我一看不是高中数学吗。。于是一分钟写了个组合数求解

def uniquePaths(m: int, n: int) -> int:
    import math
    f = math.factorial
    return int(f(m+n-2) / f(m-1) / f(n-1))

结果去讨论区一看,tm都在用dp。。还有加缓存的

本着奥卡姆剃刀原则,这个最简单的不想改了

64. Minimum Path Sum

输出从左上角到右下角的最短路径长度。

这题和上一道题差不多,用最基础的dp可以解决

def minPathSum(grid) -> int:
    if not grid:
        return 0

    m = len(grid)
    n = len(grid[0])
    dp = [[0 for i in range(n)] for j in range(m)]

    for i in range(n):
        dp[0][i] = dp[0][i-1] + grid[0][i]
    for j in range(1, m):
        dp[j][0] = dp[j-1][0] + grid[j][0]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[m-1][n-1]

Runtime faster than 90.48%. Memory Usage less than 78.95%.

今日迷惑:两道明显是easy难度的题为什么会被标为medium?

0
0
回复 # 16

刘洋
楼主
403天前

3月12日 两道easy

70. Climbing Stairs

一次可以爬一个台阶,也可以爬两个。输出爬N个台阶一共有多少种方法。

def climbStairs(n: int) -> int:
    if n < 2:
        return n
    dp = [0 for _ in range(n+1)]
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

本质是斐波那契数列,但直接递归的时间复杂度是O(2^N),用动归或memorization就能降到O(N).

104. Maximum Depth of Binary Tree

输出非平衡二叉树的深度

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    if not root.left:
        return 1 + maxDepth(root.right)
    if not root.right:
        return 1 + maxDepth(root.left)
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

边缘情况都考虑到就不会出错。

1
0
回复 # 17

刘洋
楼主
401天前

3月15日 75. Sort Colors

对只含三种数字的列表排序,要求in-place。建议时间复杂度O(N),且只能迭代一次列表
def sortColors(nums) -> None:
    red, white, blue = 0, 0, len(nums)-1
    while white <= blue:
        if nums[white] == 1:    # white
            white += 1
        elif nums[white] < 1:   # red
            nums[red], nums[white] = nums[white], nums[red]
            white +=1
            red += 1
        else:                   # blue
            nums[white], nums[blue] = nums[blue], nums[white]
            blue -= 1

笔记:一般看到含大量重复元素的排列问题,会想到空间换时间,用一个数组记录每个元素的occurrences,从而实现O(N)。但这样做需要2 pass

题目建议1 pass完成,就有点难想了。后来查了一波wiki,发现这类问题叫Dutch national flag problem(荷兰国旗🇳🇱问题),因为就像荷兰国旗一样是有序的三种颜色。(所以为什么不叫法国国旗问题)此问题由Dijkstra提出,可以用快速排序中partition的变种,实现多重复元素列表的1 pass排序。

具体思路为,使用三个指针。第一个指针左边全部是red,第一个和第二个指针之间全部是white,第二个和第三个之间全部是unsorted,第三个之后全部是blue。所以,我们需要让第二个和第三个指针逐渐靠近直到交叉,以得到3个partitions。关键在于保持第一个和第三个指针都指向red区域的边缘元素。

0
0
回复 # 18

刘洋
楼主
400天前

今天赶了一天作业,人要死了,🐦🐦🐦

0
0
回复 # 19

刘洋
楼主
398天前

3月18日 78. Subsets
连续鸽了两天,再🐦真的不行辽

输出一个数字列表的所有子集

写了一种递归实现

def subsets(nums):
    result = []
    if not nums:
        return result

    _susbets(nums, 0, result)
    return result

def _susbets(nums, start, result):
    if start == len(nums)-1:
        result += [[], [nums[start]]]
    else:
        _susbets(nums, start+1, result)
        result += [[nums[start]]+x for x in result]

这个题用BFS(广度优先)和DFS(深度优先)都可以做,我在这里用的是DFS。从抽象的视角来看,全子集的问题是对二叉树的遍历问题。考虑数组[1, 2, 3],我们可以构建一棵抽象的binary tree:根结点是第一个元素1,它的左子树代表“不选择1来构建子集”,右子树代表“选择1来构建子集”。此时,左子树的值为_subsets([2, 3])而右子树为[ [1]+ x for x in result],这里的result是我们从左子树得到的子集列表。算法运行的时候,直接深入到最左叶子节点,拿到[ [] ],然后到右叶子结点,添加为[[], [3]]。后面推出栈过程省略。

Challenge: 用循环方法解决此题

思路相似,注意初始化一个含空集的列表来模拟递归到栈底(base case)的情况。

def subsets(nums):
    ret = [[]]
    for num in nums:
        ret += [x+[num] for x in res]
    return ret
0
0
回复 # 20


    请登录参与讨论 :)