发表于 | 分类于 |

199. Binary Tree Right Side View

题目描述

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

1
2
3
4
5
6
7
8
For example:
Given the following binary tree,
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
You should return [1, 3, 4].

题目大意

给定一二叉树，求二叉树的右视图。
例如，从右边看二叉树，你应该返回结果为：[1, 3, 4]。

解题思路

层序遍历，辅助栈。
只将当前层的最右节点加入数组，通过flag参数标记当前层是否已经有节点被加入到数组内。

代码

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
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func rightSideView(_ root: TreeNode?) -> [Int] {
        guard let tree = root else { return [] }
        
        var ans = [Int]()
        var stack = [(0, tree)]
        var flag = 0
        
        while !stack.isEmpty {
            let t = stack.removeLast()
            if t.0 == flag {
                ans.append(t.1.val)
                flag = t.0 + 1
            }
            if let l = t.1.left {
                stack.append((t.0 + 1, l))
            }
            if let r = t.1.right {
                stack.append((t.0 + 1, r))
            }
        }
        return ans
    }
}

发表于 | 分类于 |

662. Maximum Width of Binary Tree

题目描述

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

1
2
3
4
5
6
7
8
9
10
11
Example 1:
Input: 
           1
         /   \
        3     2
       / \     \  
      5   3     9 
Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
1
2
3
4
5
6
7
8
9
10
11
Example 2:
Input: 
          1
         /  
        3    
       / \       
      5   3     
Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
1
2
3
4
5
6
7
8
9
10
11
Example 3:
Input: 
          1
         / \
        3   2 
       /        
      5      
Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
1
2
3
4
5
6
7
8
9
10
11
12
Example 4:
Input: 
          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).

题目大意

给定一个二叉树，求每层最左节点到最右节点距离的最大值。

解题思路

层序遍历，辅助队列，左节点的个数则为：i 2,右节点的个数则为：i 2 + 1
队列的首元素和末元素的差值 + 1即为宽度。
刚开始用的Int，但是会越界，于是改用Double.

代码

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
31
32
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func widthOfBinaryTree(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        var queue = [(0.0, root)]
        var ans = 0.0
        while !queue.isEmpty {
            let width = queue.last!.0 - queue.first!.0 + 1
            ans = max(ans, width)
            
            var tmp = [(Double, TreeNode)]()
            for (i, node) in queue {
                if let left = node.left { tmp.append((i * 2.0, left)) }
                if let right = node.right { tmp.append((i * 2.0 + 1.0, right)) }
            }
            queue = tmp
        }
        return Int(ans)
    }
}

发表于 | 分类于 |

733. Flood Fill

题目描述

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image.

To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

1
2
3
4
5
6
7
8
9
10
Example 1:
Input:
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation:
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.

Note:

The length of image and image[0] will be in the range [1, 50].
The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.
The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

题目大意

经典算法：洪水填充
(sr, sc)代表起始点，改变起始点的像素，再以起始点为中心的四个方向，像素点与起始点像素相同的点作为起始点，以此类推。

解题思路

采用BFS或者DFS

代码

DFS
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
func floodFill(_ image: [[Int]], _ sr: Int, _ sc: Int, _ newColor: Int) -> [[Int]]
{
    let dxs = [1, -1, 0, 0]
    let dys = [0, 0, 1, -1]
    let originColor = image[sr][sc]
    func floodFillWithDFS(image: inout [[Int]], x: Int, y: Int) {
        guard image[x][y] == originColor else {
            return
        }
        image[x][y] = newColor
        for (dx, dy) in zip(dxs, dys) {
            let targetX = dx + x
            let targetY = dy + y
            guard targetX >= 0, targetX < image.count,
                targetY >= 0, targetY < image[targetX].count else {
                continue
            }
            floodFillWithDFS(image: &image, x: targetX, y: targetY)
        }
    }
    guard image[sr][sc] != newColor else {
        return image
    }
    var ans = image
    floodFillWithDFS(image: &ans, x: sr, y: sc)
    return ans
}
BFS
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
func floodFill(_ image: [[Int]], _ sr: Int, _ sc: Int, _ newColor: Int) -> [[Int]] {
    var queue = [(sr, sc)]
    let color = image[sr][sc]
    let dxs = [1, -1, 0, 0]
    let dys = [0, 0, 1, -1]
    var ans = image
    ans[sr][sc] = newColor
    while !queue.isEmpty {
        let (x, y) = queue.removeLast()
        for (dx, dy) in zip(dxs, dys) {
            let targetX = dx + x
            let targetY = dy + y
            guard targetX >= 0, targetX < image.count,
                targetY >= 0, targetY < image[targetX].count else {
                continue
            }
            if color == image[targetX][targetY], 
                ans[targetX][targetY] != newColor {
                ans[targetX][targetY] = newColor
                queue.append((targetX, targetY))
            }
        }
    }
    return ans
}

发表于 | 分类于 |

740. Delete and Earn

题目描述

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

1
2
3
4
5
6
Example 1:
Input: nums = [3, 4, 2]
Output: 6
Explanation:
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.
1
2
3
4
5
6
7
Example 2:
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation:
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.

Note:

The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].

题目大意

给定一个数组nums，可以执行如下操作：
在每次操作中，必须删除所有等于nums[i]- 1或nums[i]+ 1的元素，记录数组内剩余数字的总和
循环操作，求最大值。

解题思路

动态规划
dict[num]储存数字num的个数
maxNum表示数组内的最大值
dp表示删除不大于num的所有数字的最大值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func deleteAndEarn(_ nums: [Int]) -> Int {
    var dict = [Int: Int]()
    var maxNum = 0
    for num in nums {
        dict[num] = (dict[num] ?? 0) + 1
        maxNum = max(maxNum, num)
    }
    //为防止数组越界
    var dp = Array(repeating: 0, count: maxNum + 3)
    for num in 1...maxNum + 1 {
        dp[num] = max(dp[num - 1], (num > 2 ? dp[num - 2] : 0) + (dict[num] ?? 0) *
num)
    }
    return dp[maxNum]
}

发表于 | 分类于 |

669. Trim a Binary Search Tree

题目描述

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
Example 1:
Input: 
    1
   / \ 
  0   2 
  L = 1
  R = 2
Output: 
    1 
      \ 
       2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Example 2: 
Input:  
    3 
   / \ 
  0  4 
   \
    2
   / 
  1 
  L = 1
  R = 3
Output:  
		3 
     /  
   2    
  / 
 1

题目大意

保留二叉树内值为[L, R]之间的节点

解题思路

递归
寻找值在[L, R]之间的节点，修建其左右子树

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
     func trimBST(_ root: TreeNode?, _ L: Int, _ R: Int) -> TreeNode? {
        guard let tree = root else { return nil }
        if tree.val < L {
            return trimBST(tree.right, L, R)
        }else if tree.val > R{
            return trimBST(tree.left, L, R)
        }
        tree.left = trimBST(tree.left, L, R)
        tree.right = trimBST(tree.right, L, R)
        return tree
    }
}

发表于 | 分类于 |

653. Two Sum IV - Input is a BST

题目描述

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

1
2
3
4
5
6
7
8
9
10
11
Example 1:
Input:
   5
  / \
 3   6
/ \   \
2   4   7
Target = 9
Output: True
1
2
3
4
5
6
7
8
9
10
11
Example 2:
Input:
   5
  / \
 3   6
/ \   \
2   4   7
Target = 28
Output: False

Seen this question in a real interview before? YesNo

题目大意

在搜索二叉树内找到两个数和为target

解题思路

1、通过遍历二叉树，将二叉树转换为字典
2、遍历字典，寻找是否有两个数和为target

代码

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
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
        var dict = [Int: Int]()
        func find(tree: TreeNode?) {
            guard let t = tree else { return }
            dict[t.val] = (dict[t.val] ?? 0) + 1
            find(tree: tree?.left)
            find(tree: tree?.right)
        }
        find(tree: root)
        for (key, _) in dict {
            if key == k - key  {
                if (dict[k - key] ?? 0) >= 2 {
                    return true
                }
            }else if dict[k - key] != nil {
                return true
            }
        }
        return false
    }
}

发表于 | 分类于 |

654. Maximum Binary Tree

题目描述

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree.

1
2
3
4
5
6
7
8
9
10
11
Example 1:
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:
      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

Note:
The size of the given array will be in the range [1,1000].

题目大意

通过数组建立最大二叉树

解题思路

1、找到数组最大值作为根
2、挑选左半数组内的最大值作为左子树的根
3、挑选右半数组内的最大值作为右子树的根
以此类推
ps:其实就是题目描述

代码

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
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
     func constructMaximumBinaryTree(_ nums: [Int]) -> TreeNode? {
        func construct(start: Int, end: Int) -> TreeNode? {
            guard start <= end else { return nil }
            var index = start
            var max = nums[start]
            for i in start...end {
                if nums[i] > max {
                    index = i
                    max = nums[i]
                }
            }
            let node = TreeNode(max)
            node.left = construct(start: start, end: index - 1)
            node.right = construct(start: index + 1, end: end)
            return node
        }
        return construct(start: 0, end: nums.count - 1)
    }
}

发表于 | 分类于 |

5. Longest Palindromic Substring

题目描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

1
2
3
4
5
Example:
Input: "babad"
Output: "bab"

Note: “aba” is also a valid answer.

1
2
3
4
5
Example:
Input: "cbbd"
Output: "bb"

题目大意

最长的回文子字符串。

解题思路

遍历字符串，使用双指针的方式。
第一步：移动右指针找到第一个与左指针不相同的
第二步：移动左右指针，判断是否是回文数
第二步：判断是否是当前最大回文数

代码

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
31
func longestPalindrome1(_ s: String) -> String {
    let count = s.count
    guard count > 1 else {
        return s
    }
    var range = (start: Int, end: Int)(0, 0)
    var chars = Array(s)
    var i = 0
    repeat {
        var l = i - 1
        var r = i + 1
        while chars[i] == chars[r] {
            r += 1
            if r >= chars.count { break }
        }
        if l >= 0 && r < chars.count {
            while chars[l] == chars[r] {
                l -= 1
                r += 1
                if l < 0 || r >= chars.count { break }
                
            }
        }
        i += 1
        if range.end - range.start < r - 1 - (l + 1) {
            range = (l + 1, r - 1)
        }
    }while i < count - 1 && (count - 1 - i) * 2 > range.end + 1 - range.start
    
    return String(chars[range.start...range.end])
}

发表于 | 分类于 |

114. Flatten Binary Tree to Linked List

题目描述

Given a binary tree, flatten it to a linked list in-place.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
For example,
Given
         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.
Hints:
If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

题目大意

变二叉树为链表

解题思路

按照右-左-根的顺序遍历二叉树

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func flatten(_ root: TreeNode?) {
        var pre: TreeNode?
        func dfs(_ tree: TreeNode?) {
            guard let t = tree else { return }
            dfs(tree?.right)
            dfs(tree?.left)
            
            t.right = pre
            t.left = nil
            pre = t
        }
        dfs(root)
    }
}

发表于 | 分类于 |

671. Second Minimum Node In a Binary Tree

题目描述

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

1
2
3
4
5
6
7
8
9
10
Example 1:
Input: 
    2
   / \
  2   5
     / \
    5   7
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
1
2
3
4
5
6
7
8
Example 2:
Input: 
    2
   / \
  2   2
Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.

题目大意

给定一非空的特殊二叉树，每个节点都有0个或者2个节点，根节点是子节点中的较小
找到二叉树内，节点值第二小的节点，如果有返回节点值，否则返回-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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func findSecondMinimumValue(_ root: TreeNode?) -> Int {
        guard let tree = root else { return -1 }
        var ans = Int.max
        var min = tree.val
        func find(root: TreeNode?) {
            guard let tree = root else { return }
            if tree.val < ans && tree.val > min {
                ans = tree.val
            }
            find(root: tree.left)
            find(root: tree.right)
        }
        find(root: tree)
        return ans == Int.max ? -1 : ans
    }
}
0%