Life sucks, but you're gonna love it.

0%

Algorithm | LeetCode - July Challenge

【LeetCode】- July Challenge

0701 - Leetcode441 - Arranging coins - Easy

0702 - Leetcode107 - Binary Tree Level Order Traversal II

补充 - Leetcode104 - Binary Tree Level Order Traversal

0703 - Leetcode957 - Prison Cells After N days

0704 - Leetcode264 - Ugly Number II

补充 - Leetcode263 - Ugly Number

0705 - Leetcode461 - Hamming Distance

补充 - Leetcode477 - Total Hamming Distance - Medium

0706 - Leetcode66 - Plus One - Easy

0707 - Leetcode463 - Island Perimeter - Easy

0708 - 3Sum - Medium

0711 - Leetcode78 - Subsets - Medium

0713 - Leetcode100 - Same Tree - Easy

0714 - Leetcode1344 - Angle Between Hands of a Clock - Medium

0717 - Leetcode - Top K Frequent Elements - Medium

0718 - Leetcode210 - Course Scheduel II - Medium

[0719 - Leetcode64 - ]

0720 - Leetcode - Remove Linked List Elements - Medium

0722 - Leetcode103 - Binary Tree Zigzag Level Order Traversal - Medium

0724 - Leetcode797 - All Paths from source to Target - Medium

-=-=-=-=-=-=-=-=-==-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

0724 - Leetcode797 - All Paths From Source to Target

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, …, graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

1
2
3
4
5
6
7
8
9
Example:
Input: [[1,2], [3], [3], []]
Output: [[0,1,3],[0,2,3]]
Explanation: The graph looks like this:
0--->1
| |
v v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

解题思路:

把edge储存为 : {到达点:[上一个可能点]} 的字典格式,如果上一个可能的点存在0的话就跳出循环,否则的话就一直循环下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(object):
def allPathsSourceTarget(self, graph):
"""
:type graph: List[List[int]]
:rtype: List[List[int]]
"""
edge = defaultdict(list)
for i in range(len(graph)):
link = graph[i]
for k in link:
edge[k] += [i]

ans = []
self.dfs(edge, len(graph) - 1, [], ans)

return ans

def dfs(self, edge, lastnode, path, ans):

if lastnode == 0:
path = path + [0]
ans.append( path[::-1] )
return

for node in edge[lastnode]:
self.dfs(edge, node, path + [lastnode], ans)

0722 - Leetcode103 - Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

return its zigzag level order traversal as:

1
2
3
4
5
[
[3],
[20,9],
[15,7]
]

解题思路

BFS + 正反向输出 + flag决定

BFS输出,然后设置flag,每次都*-1 可以控制正反向输出。

0720 - Leetcode - Remove Linked List Elements

Remove all elements from a linked list of integers that have value val\.

Example:

1
2
Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

解题思路:

设置dummy node,查看next.val是否和要去掉的val相同,如果相同,定义next = next.next. 指针不动;如果不同,指针后移一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
dummy = ListNode(0)

dummy.next = head
head = dummy

while head.next:

if head.next.val == val:
if head.next.next:
head.next = head.next.next
else:
head.next = None
else:
head = head.next

return dummy.next

0718 - Leetcode210 - Course Scheduel II

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

解题思路:

  1. DFS

  2. Node in degree(入度)

    当我们把pre课程当做出发点,而现在要选的课程当做目的地

0717 - Leetcode347 - Top K Frequent Elements

0714 - Leetcode1344 - Angle Between Hands of a Clock

Given two numbers, hour and minutes. Return the smaller angle (in degrees) formed between the hour and the minute hand.

解题思路:

就直接写,然后钝角转化为 360 - 本身

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def angleClock(self, hour, minutes):
"""
:type hour: int
:type minutes: int
:rtype: float
"""
angle_h = (hour%12) * 30 + minutes * 0.5

angle_m = minutes * 6

# print(angle_h, angle_m)
if abs(angle_h - angle_m) > 180:
return 360 - abs(angle_h - angle_m)
return abs(angle_h - angle_m)

0713 - Leetcode100 - Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

解题思路:

Recursive - 分别判断每个节点是否相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
return self.checkNode(p, q)

def checkNode(self, node1, node2):


if not node1 and not node2:
return True

if not node1 or not node2 or node1.val != node2.val:
return False

return self.checkNode(node1.left, node2.left) and self.checkNode(node1.right, node2.right)

0711 - Leetcode78 - Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解题思路:

用recursive吧,因为不希望出现重复项,所以新加进来的数可以视为前一个subset 加上 一个新的数字,而这个新的数字是subdet最后一位数字往后的。所以可以用resurcive。

比如说

  • [] 是初始解,那么[] +[1], [] + [2], []+[3] 就是第一层解
  • [1] + [2], [1]+[3] 就要继续下去。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ans = []
sub = []
ans.append(sub)
self.newsub(sub, nums, 0, ans)

return ans


def newsub(self, sub, nums, i, ans):

while i < len(nums):
ans.append(sub + [nums[i]])
self.newsub(sub + [nums[i]], nums, i+1, ans)
i += 1
return

0708 - 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

解题思路:

先排序,再固定指针 i ,然后从这个指针向右的序列确定两个指针 left, right, 寻找nums[i] = -(nums[left]+nums[right])。

如果左右两指针相加大于 -(nums[left]+nums[right]),right -= 1, 否则 left+=1.如果相等就把者三个数的list放在ans中。

注意!!!

这个题直接这样写会超时,所以要考虑很多特殊的情况。

  1. if nums[i] > 0, break 当最小值都大于零,右边的nums[left]和nums[right]肯定都大于零,就不可能存在三个数相加为0的情况;

  2. 判断是否有重复: if nums[left - 1] > i and nums[left - 1] == nums[left]: 这时候left可以直接+1忽略

    同理,可以跳过重复的右指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
ans = []
for i in range(len(nums)):
left = i + 1
right = len(nums) - 1

if i > 0 and nums[i] == nums[i-1]: continue

while left < right:
if left - 1 > i and nums[left] == nums[left-1]:
left += 1
continue
if right+1 < len(nums) and nums[right] == nums[right+1]:
right -= 1
continue

if nums[left] + nums[right] == -nums[i]:
ans.append([nums[i], nums[left], nums[right]])
left += 1

elif nums[left] + nums[right] > -nums[i]:
right -= 1
else:
left += 1
return ans

0707 - Leetcode463 - Island Perimeter

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

1
2
3
4
5
6
7
Input:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

Output: 16

解题思路:

很简单,遍历grid中的每一项,如果是1,那么他就会有4条边,然后减去临边也为1的数量,然后就可以得到小岛的周长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def islandPerimeter(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
row = len(grid)
col = len(grid[0])
count1 = 0
edge = 0
for i in range(row):
for j in range(col):
if grid[i][j] == 1:
count1 += 1
edge = edge + (self.countLand(grid, i+1, j) +self.countLand(grid, i-1, j)+self.countLand(grid, i, j+1)+self.countLand(grid, i, j-1))


return 4*count1 - edge


def countLand(self, grid, i, j):
land = 0
if i >= 0 and i < len(grid) and j >= 0 and j < len(grid[0]):
land += grid[i][j]
return land

补充 - Leetcode695 - Max Area of Island

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

解题思路:

  1. DFS。寻找最大岛屿面积,遍历每一个点,然后从每一个点延伸开始寻找它周围的是1的点,遍历过的点改标记为0.

    之前有一个题,也是遍历每一个点,然后遍历的时候改为-1,之后遍历完又换回来。这种是 解跟解之间独立的,比如是某条路径(我实在找不到那道题了),还要换回来因为可能此路不通,我们还要走下一条路。但是这种求面积的,包括数岛屿个数的题,我们在换了标记之后表示我们已经count了这个grid[i][j]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def maxAreaOfIsland(self, grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    max_area = 0

    for i in range(len(grid)):
    for j in range(len(grid[0])):
    max_area = max(max_area, self.dfs(grid, i, j))

    return max_area


    def dfs(self, grid, i, j):

    if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
    return 0

    grid[i][j] = 0

    return self.dfs(grid, i+1, j) + self.dfs(grid, i-1, j) + self.dfs(grid, i, j+1) + self.dfs(grid, i, j-1) + 1

0706 - Leetcode66 - Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

1
2
3
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

解题思路:

  1. 硬做。这道题就是在问给出的list如果代表的是一个数字,那么这个数字加上1之后,得到的list会是什么样子。给出的例子都很简单,简直是迷惑人。因为有几种特殊的情况,一种是最后一位为9的时候,它加上1之后要进位的,另一种情况是最高位同样为9的时候,它加上一是要变多一位的。所以单纯对list里面的数字进行加1处理远远不够。 我一开始想的就是把给的list转化为数字,然后+1,然后再拆解成list。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def plusOne(self, digits):
    """
    :type digits: List[int]
    :rtype: List[int]
    """
    num = 0
    i = 0
    while i < len(digits):
    num = 10*num + digits[i]
    i += 1
    num = num+1
    plus = []
    while num > 0:
    plus.append(num % 10)
    num //= 10

    return plus[::-1]
  2. recursion

    迭代去做考虑的因素就不需要分开考虑究竟最高位是不是9,那我们返回的值就是当我们所处的这一位是9的话,就把这个数字改换为0,然后对前面的数字进行+1处理。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def plusOne(self, digits):
    """
    :type digits: List[int]
    :rtype: List[int]
    """
    if len(digits) == 0:
    return [1]
    if digits[-1] < 9:
    digits[-1] += 1
    return digits
    elif digits[-1] == 9:
    return self.plusOne(digits[:-1]) + [0]

0705 - Leetcode461 - Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

1
2
3
4
5
6
7
8
Input: x = 1, y = 4

Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

解题思路:

我一开始是想着移位运算有没有取最后一位然后取异或的,但是没想起来该怎么写。于是就用了最原始的求数字二进制的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def hammingDistance(self, x, y):
"""
:type x: int
:type y: int
:rtype: int
"""
count = 0
while True:
if x == 0 and y == 0:
break

count += (x%2) ^ (y%2)

x = x // 2
y = y // 2

return count

后面查了一下确实有直接算二进制的:

bin(x) 可以返回x的二进制表示形式,但是返回的值是一个string

int(x, 16) 可以将16进制下的字符串类型x转化为一个十进制的int形式的数字

补充 - Leetcode477 - Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

1
2
3
4
5
6
7
Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

解题思路:

  1. 和上面一题不同,这道题如果每两对都要计算一下hamming distance再相加的话,就会造成很多重复的计算。所以我是直接想用数学方法写的,没有用到算法的技巧。

    假设我们的 list 中一共有 N 个数字,因为我们要求这些数字的二进制表示下的位数的差异,所以我们需要把这些数字都用0 1表示。那么对于这N个数字而言,拿出每两个数字然后逐位进行比较就相当于,对于每一位而言,我们把这N个0或1的数字拿出来,然后看看能有几个不一样。所以用到了排列组合的思想。

    对于每一位而言,N个数字一共会有个 $2 \choose N$ 种结果,$ {2 \choose N } = {N-2 \choose N} = (N-1)*N$, 而在这一位上面,我们只有两种选择,要么0 要么1,所以我们再利用一个count list来统计一下每一位1的个数count[i]。最后对于每一位而言,两两数字不同的可能性就有 ${2 \choose N} - {2 \choose count[i]} - {2 \choose N-count[i]}$.

    扫了一眼讨论区,哦,我好蠢,两两不同的可能性就是 $count[i] \times (N - count[i])$。大部分也是通过数学计算来解决这个问题的。

    又学了一招 "{0:b}".format(num) 可以把num转化为二进制字符串

    print("bin: {0:b}, oct: {0:o}, hex: {0:x}".format(12))

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def totalHammingDistance(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    count = [0] * 32
    for num in nums:
    i = 0
    while num != 0:
    count[i] += num % 2
    num /= 2
    i += 1
    N = len(nums)
    total_ham = 0

    for i in range(len(count)):
    if count[i] > 0:
    total_ham += N * (N - 1)/2 - count[i]*(count[i]-1)/2 - (N - count[i])*(N - count[i] - 1)/2

    return total_ham

0704 - Leetcode264 - Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

1
2
3
Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

解题思路:

  1. 最小堆帮助排序:主要还是明确Ugly Number的定义吧,指的就是factor只有2,3,5的数字。那么就意味着我所有的数字只能是ugly number的乘积。所以就从1开始,之后所有的数字都是ugly number里面的数字 2 3 *5.

    一开始想用动态规划,但这里存在一个排序的问题,第一个数字乘 2 3 5和第二个数字乘2 3 5,哪个应该放在哪个后面。但后来想到用min heap这个结构,会把最小的放在上面,每次我们pop出来最小的数字放在我们的sorted ugly number lsit中,然后再把它乘以2 3 5的数字放进我们的min heap中,就行了。如果pop出来的数字已经在我们的sorted ugly number里面了,那我们就跳过这个数字。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def nthUglyNumber(self, n):
    """
    :type n: int
    :rtype: int
    """
    sorted_ugly = []
    heap = [1]
    heapq.heapify(heap)

    while len(sorted_ugly) < n:
    next_ugly = heapq.heappop(heap)
    if next_ugly not in sorted_ugly:
    sorted_ugly.append(next_ugly)
    heapq.heappush(heap, next_ugly*2)
    heapq.heappush(heap, next_ugly*3)
    heapq.heappush(heap, next_ugly*5)
    return sorted_ugly[-1]
  2. 动态规划

    把2 3 5需要乘的数字表示为指针,然后依次升高,进行排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def nthUglyNumber(self, n):
    """
    :type n: int
    :rtype: int
    """
    dp = [1]
    pointer2 = 0
    pointer3 = 0
    pointer5 = 0
    while len(dp) < n:
    dp = dp + [min(dp[pointer2]*2, dp[pointer3]*3, dp[pointer5]*5)]

    if dp[-1] == dp[pointer2]*2:
    pointer2 += 1
    if dp[-1] == dp[pointer3]*3:
    pointer3 += 1
    if dp[-1] == dp[pointer5]*5:
    pointer5 += 1

    return dp[-1]

补充 - Leetcode263 - Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

1
2
3
Input: 6
Output: true
Explanation: 6 = 2 × 3

解题思路:

更直接一点,只用循环除以2 3 5 就可以了。注意小于0的数字和 =0 的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""

if num == 1: return True
if num == 0: return False

while num != 1:

if num % 2 == 0:
num = num //2
elif num%3 == 0:
num = num//3
elif num%5 == 0:
num = num//5
else:
return False
return True

0703 - Leetcode957 - Prison Cells After N days

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

  • If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
  • Otherwise, it becomes vacant.

(Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

解题思路:

  1. 规律总结,我是总结规律来的。因为如果写一个方程然后运行N次感觉时间复杂度会比较高。总结规律之后,14变换为一轮回,然后求余数就可以了。但是这个应该是有更底层的解释,为什么14个一个轮回。还有看到的规律是,几次之后,后面的模式和前面相比是前半部分和后半部分调换了位置。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    # Time: O(1), Space: O(1)
    def prisonAfterNDays(self, cells, N):
    """
    :type cells: List[int]
    :type N: int
    :rtype: List[int]
    """
    if N == 0: return cells
    temp = [0]*8
    for i in range(1, len(cells) - 1):
    temp[i] = 1 - cells[i-1] ^ cells[i+1]

    cells = temp

    re = (N - 1) % 14
    while re > 0:
    temp = [0]*8
    for i in range(1, len(cells) - 1):
    temp[i] = 1 - cells[i-1] ^ cells[i+1]
    cells[1:8] = temp[1:8]
    re -= 1
    return cells

  2. 常规做法:将pattern保存在dictionary中,然后看几个一循环。(因为有的时候可能循环周期不同

    需要注意的是保存在字典里的数字是我们接下来要找的余数,余数是从 0 到 T-1(T为周期),所以N在计算的时候需要做-1.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    # Time: O(1) Space: O(1)

    def prisonAfterNDays(self, cells, N):
    """
    :type cells: List[int]
    :type N: int
    :rtype: List[int]
    """
    pattern_dict = {}
    # cells = self.nextPattern(cells)
    n = 0
    while True:
    n += 1
    cells = self.nextPattern(cells)
    if cells in pattern_dict.values():
    break
    else:
    pattern_dict[n-1] = cells
    T = n - 1

    return pattern_dict[(N-1) % T]

0702 - Leetcode107 - Binary Tree Level Order Traversal II (104同理)

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

return its bottom-up level order traversal as:

1
2
3
4
5
[
[15,7],
[9,20],
[3]
]

解题思路:

普通的BFS每层拿出,遍历,再将每层的left right放入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root: return []

queue = [root]
ans = []
while len(queue) > 0:
nodes = []
while len(queue) > 0:
nodes.append(queue.pop(0))
# print(nodes)
tmp = [n.val for n in nodes]
ans.append(tmp)

for n in nodes:
if n.left:
queue.append(n.left)
if n.right:
queue.append(n.right)
return ans[::-1]

上述如果返回的是 ans 那就是不bottom up的 level traverse 遍历二叉树

1
2
3
4
5
6
# 学到了deque 读(deck)

from collections import deque

deque.pop()
deque.popleft() # 和append组合相当于queue的FIFO

0701 - Leetcode441 - Arranging coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

1
2
3
4
5
6
7
8
n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

解题思路:

  1. 看到这道题首先想到的是斐波那契数列,因而想到了用动态规划来写。这道题不是斐波那切数列啊!就是看到这个排列想到了。如果用动态规划写的话:

    • dp[i] 表示的就是当第i行排满之后,总共需要几个coin
    • 状态转移方程 dp[i] = dp[i-1] + i
    • 实质上也是等差数列求和:求一个 int(k) 使得 $\frac{k(k+1)}{2} <= n$, 得出的解是 $k = \frac{-1+\sqrt{1+8n}}{2} = \sqrt{2n + 0.25} - 0.5$
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # Time: O(sqrt(n)) Space: O(sqrt(n))
    # 这样写会TLE
    def arrangeCoins(self, n):
    """
    :type n: int
    :rtype: int
    """

    if n == 0: return 0
    dp = []
    dp = dp+[0]
    count = 1
    while n >= dp[-1]:
    dp = dp + [count + dp[-1]]
    count += 1

    return count - 2
  2. 写的时候直接用n减去每次的循环序号(i.e. 第一次减去1,第二次减去2)当n小于0的时候就跳出循环,返回循环的次数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # Time: O(sqrt(n))(?是这样吗) Space: O(1)

    def arrangeCoins(self, n):
    """
    :type n: int
    :rtype: int
    """
    if n == 0: return 0
    if n <= 2: return 1

    count = 0
    while n >= 0:
    count += 1
    n -= count

    return count - 1
  3. 看了别人写的之后还有Binary Search. 二叉树的时候更新左右两个端点总是会忽略的一个问题是,如果你要保左端点,那在算中值的时候需要+1,这样才能保证不陷入死循环。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def arrangeCoins(self, n):
    """
    :type n: int
    :rtype: int
    """
    left = 0
    right = n
    while left < right:
    # print(left, right)
    mid = (left + right + 1)/2

    if mid*(mid+1)/2 < n:
    left = mid
    if mid*(mid+1)/2 > n:
    right = mid - 1

    if mid*(mid+1)/2 == n:
    return mid

    return left