题目序号 439、366、364、323、261、473、417、394、332

439. Ternary Expression Parser

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T and F (T and F represent True and False respectively).

Note:

The length of the given string is ≤ 10000. Each number will contain only one digit. The conditional expressions group right-to-left (as usual in most languages). The condition will always be either T or F. That is, the condition will never be a digit. The result of the expression will always evaluate to either a digit 0-9, T or F. Example 1:

Input: “T?2:3”

Output: “2”

Explanation: If true, then result is 2; otherwise result is 3. Example 2:

Input: “F?1:T?4:5”

Output: “4”

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

“(F ? 1 : (T ? 4 : 5))” “(F ? 1 : (T ? 4 : 5))”

-> “(F ? 1 : 4)” or -> “(T ? 4 : 5)” -> “4” -> “4”

Example 3:

Input: “T?T?F:5:3”

Output: “F”

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

“(T ? (T ? F : 5) : 3)” “(T ? (T ? F : 5) : 3)”

-> “(T ? F : 3)” or -> “(T ? F : 5)” -> “F” -> “F”

题目大意： 给定一个字符串表示一个任意嵌套的三目表达式，计算表达式的结果。你可以假设表达式一定有效，并且只包含数字0-9,?, :, T 和 F (T 和 F 分别表示 True 和 False)

注意：

字符串长度 ≤ 10000 每个数字只有一位 条件表达式从右向左分组 (与大多数编程语言保持一致) 条件永远是 T 或者 F。 也就是说，条件永远不会是数字 表达式的结果可以是 0-9, T 或者 F 解题思路： 栈（Stack）数据结构

循环直到栈中元素为1并且表达式为空：

取栈顶的5个元素，判断是否为一个可以解析的表达式。若是，则解析后压栈

否则从右向左将expression中的字符压入栈stack

366. Find Leaves of Binary Tree

Given a binary tree, collect a tree’s nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty. Example: Given binary tree

1

/

2 3

/

4 5

Returns [4, 5, 3], [2], [1]. Explanation: 1. Removing the leaves [4, 5, 3] would result in this tree:

1

/

2

2. Now removing the leaf [2] would result in this tree:

   1

3. Now removing the leaf [1] would result in the empty tree:

   []

Returns [4, 5, 3], [2], [1].

364. Nested List Weight Sum II

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example 1: Given the list [[1,1],2,[1,1]], return 8. (four 1’s at depth 1, one 2 at depth 2)

Example 2: Given the list [1,[4,[6]]], return 17. (one 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17)

323. Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

 0          3

 |          |

 1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

    0           4

    |           |

    1 --- 2 --- 3

   Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note:

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

这道题让我们求无向图中连通区域的个数，LeetCode中关于图Graph的题屈指可数，解法都有类似的特点，都是要先构建邻接链表Adjacency List来做。这道题的一种解法是利用DFS来做，思路是给每个节点都有个flag标记其是否被访问过，对于一个未访问过的节点，我们将结果自增1，因为这肯定是一个新的连通区域，然后我们通过邻接链表来遍历与其相邻的节点，并将他们都标记成已访问过，遍历完所有的连通节点后我们继续寻找下一个未访问过的节点，以此类推直至所有的节点都被访问过了，那么此时我们也就求出来了连通区域的个数。

..code-block:: python

def connect(self, root):

if root and root.left and root.right:

root.left.next = root.right if root.next:

root.right.next = root.next.left

self.connect(root.left) self.connect(root.right)

def connect1(self, root):

if root and root.left and root.right:

root.left.next = root.right if root.next:

root.right.next = root.next.left

self.connect(root.left) self.connect(root.right)

# BFS def connect2(self, root):

if not root:

return

queue = [root] while queue:

curr = queue.pop(0) if curr.left and curr.right:

curr.left.next = curr.right if curr.next:

curr.right.next = curr.next.left

queue.append(curr.left) queue.append(curr.right)

# DFS def connect(self, root):

if not root:

return

stack = [root] while stack:

curr = stack.pop() if curr.left and curr.right:

curr.left.next = curr.right if curr.next:

curr.right.next = curr.next.left

stack.append(curr.right) stack.append(curr.left)

# BFS with queue def connect(self, root):

if not root:

return

queue, nextLevel = [root], [] # queue records the previous level while queue:

curr = queue.pop(0) if curr.left:

nextLevel.append(curr.left)

if curr.right:

nextLevel.append(curr.right)

if queue:

curr.next = queue[0]

if not queue and nextLevel:

queue, nextLevel = nextLevel, queue

261. Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree? According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.” Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

这道题给了我们一个无向图，让我们来判断其是否为一棵树，我们知道如果是树的话，所有的节点必须是连接的，也就是说必须是连通图，而且不能有环，所以我们的焦点就变成了验证是否是连通图和是否含有环。我们首先用DFS来做，根据pair来建立一个图的结构，用邻接链表来表示，还需要一个一位数组v来记录某个节点是否被访问过，然后我们用DFS来搜索节点0，遍历的思想是，当DFS到某个节点，先看当前节点是否被访问过，如果已经被访问过，说明环存在，直接返回false，如果未被访问过，我们现在将其状态标记为已访问过，然后我们到邻接链表里去找跟其相邻的节点继续递归遍历，注意我们还需要一个变量pre来记录上一个节点，以免回到上一个节点，这样遍历结束后，我们就把和节点0相邻的节点都标记为true，然后我们在看v里面是否还有没被访问过的节点，如果有，则说明图不是完全连通的，返回false，反之返回true，参见代码如下：

def validTree(self, n, edges):
    dic = {i: set() for i in xrange(n)}
    for i, j in edges:
        dic[i].add(j)
        dic[j].add(i)
    visited = set()
    queue = collections.deque([dic.keys()[0]])
    while queue:
        node = queue.popleft()
        if node in visited:
            return False
        visited.add(node)
        for neighbour in dic[node]:
            queue.append(neighbour)
            dic[neighbour].remove(node)
        dic.pop(node)
    return not dic


class Solution:
# @param {integer} n
# @param {integer[][]} edges
# @return {boolean}
def validTree(self, n, edges):
    graph = {i:set() for i in xrange(n)}
    for p, q in edges:
        graph[p].add(q)
        graph[q].add(p)
    while len(graph) > 0:
        leaves = list()
        for node, neighbors in graph.iteritems():
            if len(neighbors) <= 1:
                leaves.append(node)
        if len(leaves) == 0:
            return False # a cycle exists
        for n in leaves:
            if len(graph[n]) == 0:
                # must be one connected component
                return len(graph) == 1
            nei = graph[n].pop()
            graph[nei].remove(n)
            del graph[n]
    return True


def validTree(self, n, edges):
    dic = {i: set() for i in xrange(n)}
    for i, j in edges:
        dic[i].add(j)
        dic[j].add(i)
    stack = [dic.keys()[0]]
    visited = set()
    while stack:
        node = stack.pop()
        if node in visited:
            return False
        visited.add(node)
        for neighbour in dic[node]:
            stack.append(neighbour)
            dic[neighbour].remove(node)
        dic.pop(node)
    return not dic


def validTree(self, n, edges):
    nums = [-1] * n
    for edge in edges:
        if not self.union(nums, edge[0], edge[1]):
            return False
    return len(edges) == n-1

def union(self, nums, x, y):
    xx = self.find(nums, x)
    yy = self.find(nums, y)
    if xx == yy:  # cycle detected
        return False
    nums[xx] = yy
    return True

def find(self, nums, i):
    if nums[i] == -1:
        return i
    return self.find(nums, nums[i])

473. Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:

Input: [1,1,2,2,2] Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: [3,3,3,3,4] Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

Note:

The length sum of the given matchsticks is in the range of 0 to 10^9. The length of the given matchstick array will not exceed 15.

417. Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

The order of returned grid coordinates does not matter. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

Pacific ~ ~ ~ ~ ~

~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 *

• • • • • Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

394. Decode String

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = “3[a]2[bc]”, return “aaabcbc”. s = “3[a2[c]]”, return “accaccacc”. s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.

332. Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”]. All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary.

Example 1: tickets = [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] Return [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”].

Example 2: tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]] Return [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]. Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]. But it is larger in lexical order.