2020秋招-刷题

02/25/2020

今天上午刷题 75M, 77M, 211M, 79M，很多都可以一遍bug free了
212H 没做出来，用的是TrieNode, 属于是知识盲区了。
Udacity: C2 52% 学到了sql 算是个重点把， 要多花时间在这个上。

請問可以抱團嗎？

魯蛇帝王 发表于 2020-2-26 11:28
請問可以抱團嗎？

哈哈可以呀 一起刷啊

02/26/2020

80M, 121E, 122E
今天上午休息了一上午， 下午晚上都放在项目讨论上去了，做的题目比较少。明天把 buy and sell stock 的专题做完。
udacity: 今天开始攻克 postgresql. 现在的确意识到SQL是backend必备知识了。这个视频讲的不错，是手把手教学 https://www.youtube.com/watch?v=qw--VYLpxG4

02/27/2020

123H, 415E, 173M
udacity: C2 complete
终于把sql给入门了.... 耗了一整个晚上。

zjy1825945 发表于 2020-2-16 13:39
02/15/2020

今天晚上参加了学校cs的networking会，没参加上contest。

N皇后问题必然不是N^2的时间复杂度啊。

WarriorZ 发表于 2020-2-29 03:55
N皇后问题必然不是N^2的时间复杂度啊。

感谢纠正啊！ 我重新看了一下代码，backtracking 用的是O(n^3)

zjy1825945 发表于 2020-2-29 05:34
感谢纠正啊！ 我重新看了一下代码，backtracking 用的是O(n^3)

虽然我不知道你代码是怎么实现的，但是N皇后是一个np-hard问题，你怎么可能写出polynomial的代码呢。

02/28/2020

253M, 252E - meeting room 题，需要重新刷
665E
867e
750M+ google follow up

WarriorZ 发表于 2020-2-29 06:44
虽然我不知道你代码是怎么实现的，但是N皇后是一个np-hard问题，你怎么可能写出polynomial的代码呢。

你好 这是我的lc 51的代码，我觉得时间复杂度是o(n^3)吧？

1. class Solution(object):
   
2.     def solveNQueens(self, n):
   
3.         """
   
4.         :type n: int
   
5.         :rtype: List[List[str]]
   
6.         """res = []
   
7.         self.dfs([-1]*n, 0, [], res)
   
8.         return res
   
9.    
   
10.     def dfs(self, array, row, path, res):
    
11.         n = len(array)
    
12.         if row == n:
    
13.             res.append(path)
    
14.             return
    
15.         for i in range(n):
    
16.             if not self.check(array, row, i): # try to set array[row] = i
    
17.                 continue
    
18.             temp = '.'*n
    
19.             self.dfs(array[:row]+[i]+array[row+1:], row+1, path+[temp[:i]+'Q'+temp[i+1:]], res)
    
20.         
    
21.     def check(self, array, index, num):
    
22.         for i in range(0, index):
    
23.             if array[i] == num or abs(array[i]-num) == index - i:
    
24.                 return False
    
25.         return True

复制代码