发表于 | 分类于 |

84. Largest Rectangle in Histogram

题目描述

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]

The largest rectangle is shown in the shaded area, which has area = 10 unit.

屏幕快照 2017-12-06 下午5.54.03.png

For example,
Given heights = [2,1,5,6,2,3],
return 10.

题目大意

给定一数组代表直方图的矩形条高度，每个矩形条的宽度为1，在直方图种找到最大矩形的面积，如上图中例子所示。

解题思路

遍历矩形条高度，计算以当前矩形条为高度的最大面积（即要维持一个递增序列）
使用Stack构建递增序列，比栈顶小的值则弹出，并计算其面积，否则压栈。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func largestRectangleArea(_ heights: [Int]) -> Int {
    var stack = [Int]()
    var ans = 0
    let heights = heights + [-1]
    for (i, h) in heights.enumerated() {
        while let last = stack.last, h <= heights[last] {
            stack.removeLast()
            let w = stack.isEmpty ? i : i - stack.last! - 1
            ans = max(ans, w * heights[last])
        }
        stack.append(i)
    }
    return ans
}

发表于 | 分类于 |

337. House Robber III

题目描述

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

题目大意

小偷又找到了新的目标，这条街上的房子呈二叉树排列，同一晚上相邻的两层被偷会引发警报。

解题思路

递归，深度优先搜索（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
/**
 * 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 rob(_ root: TreeNode?) -> Int {
        func dfs(tree: TreeNode?) -> (Int, Int) {
            guard let t = tree else { return (0, 0) }
            let left = dfs(tree: t.left)
            let right = dfs(tree: t.right)
            let noRob = max(left.0, left.1) + max(right.0, right.1)
            let rob = t.val + left.0 + right.0
            return (noRob, rob)
        }
        let ans = dfs(tree: root)
        return max(ans.0, ans.1)
    }
}

发表于 | 分类于 |

583. Delete Operation for Two Strings

题目描述

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

1
2
3
4
5
Example 1:
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and
another step to make "eat" to "ea".

Note:
The length of given words won’t exceed 500.
Characters in given words can only be lower-case letters.

题目大意

给定两个字符串，求至少删除多少个字符才能使两个字符串相等。

解题思路

动态规划
遍历字符串，判断当前值相同和值不同时最少删除字符数。

1
2
3
4
5
if chars1[i - 1] == chars2[j - 1] {
    dp[i][j] = dp[i - 1][j - 1]
}else {
    dp[i][j] = min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 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
class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        
        guard !word1.isEmpty && !word2.isEmpty else {
            return word1.isEmpty ? word2.count : word1.count
        }
        
        var dp = Array(repeating: Array(repeating: 0, count: word2.count + 1), count: word1.count + 1)
        
        let chars1 = Array(word1)
        let chars2 = Array(word2)
        let c1 = word1.count
        let c2 = word2.count
        
        for i in 0...c1 { dp[i][0] = i }
        for i in 0...c2 { dp[0][i] = i }
        
        
        for i in 1...c1 {
            for j in 1...c2 {
                if chars1[i - 1] == chars2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1]
                }else {
                    dp[i][j] = min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1)
                }
            }
        }
        return dp[c1][c2]
    }
}

发表于 | 分类于 |

652. Find Duplicate Subtrees

题目描述

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

1
2
3
4
5
6
7
8
Example 1: 
        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

The following are two duplicate subtrees:

1
2
3
  2
 /
4

and

1
4

Therefore, you need to return above trees’ root in the form of a list.

题目大意

寻找重复子树

解题思路

采用辅助字典
利用字符串模拟树形结构，以字符串为key，当字典值为2时，则表示有相等的树，返回此树即可。

代码

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
/**
 * 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 findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
        var dict = [String: Int]()
        var ans = [TreeNode?]()
        func find(root: TreeNode?) -> String {
            guard let node = root else { return "." }
            let s = "\(node.val)\(find(root: node.left))\(find(root: node.right))"
            let v = (dict[s] ?? 0) + 1
            if v == 2 {
                ans.append(node)
            }
            dict[s] = v
            return s
        }
        find(root: root)
        return ans
    }
}

发表于 | 分类于 |

623. Add One Row to Tree

题目描述

Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.

The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N’s left subtree root and right subtree root. And N’s original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Example 1:
Input: 
A binary tree as following:
       4
     /   \
    2     6
   / \   / 
  3   1 5   
v = 1
d = 2
Output: 
       4
      / \
     1   1
    /     \
   2       6
  / \     / 
 3   1   5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Example 2:
Input: 
A binary tree as following:
      4
     /   
    2    
   / \   
  3   1    
v = 1
d = 3
Output: 
      4
     /   
    2
   / \    
  1   1
 /     \  
3       1

Note:
The given d is in range [1, maximum depth of the given tree + 1].
The given binary tree has at least one tree node.

题目大意

给定一个二叉树的根，然后是value v和depth d，你需要在给定的深度d中添加一个值为v的节点行，根节点位于深度1。

给定一深度d，二叉树root,添加规则如下:

  • 深度为d - 1的目标节点，创建两个值为v的节点，作为目标节点的左节点，记为vLeft，和右节点，记为vRight。
  • 目标节点的左子树应该是vLeft的左子树，目标节点的原右子树应该是vRight的右子树。
  • 如果depth d为1，则表示没有深度d - 1，那么创建一个值为v的节点作为root的新根，而root是新根的左子树。

    解题思路

    递归，层序遍历。
    如果d为1，则将v作为根节点返回。
    如果d为2，则将v插入下一层。

代码

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 addOneRow(_ root: TreeNode?, _ v: Int, _ d: Int) -> TreeNode? {
        guard let tree = root else { return nil }
        if d == 1 {
            let node = TreeNode(v)
            node.left = tree
            return node
        }
        if d == 2 {
            let (left, right) = (tree.left, tree.right)
            let (vLeft, vRight) = (TreeNode(v), TreeNode(v))
            vLeft.left = left
            vRight.right = right
            tree.left = vLeft
            tree.right = vRight
            return tree
        }
        addOneRow(tree.left, v, d - 1)
        addOneRow(tree.right, v, d - 1)
        return tree
    }
}

发表于 | 分类于 |

655. Print Binary Tree

题目描述

Print a binary tree in an m*n 2D string array following these rules:

  • The row number m should be equal to the height of the given binary tree.
  • The column number n should always be an odd number.
  • The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
  • Each unused space should contain an empty string “”.
  • Print the subtrees following the same rules.
1
2
3
4
5
6
7
8
Example 1:
Input:
     1
    /
   2
Output:
[["", "1", ""],
 ["2", "", ""]]
1
2
3
4
5
6
7
8
9
10
11
Example 2:
Input:
     1
    / \
   2   3
    \
     4
Output:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Example 3:
Input:
      1
     / \
    2   5
   / 
  3 
 / 
4 
Output:
[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

Note: The height of binary tree is in the range of [1, 10].

题目大意

转换二叉树为m * n的二位数组。
规则如下：

  • 行数m为二叉树的深度
  • 列数n必须是以奇数
  • 根节点的值应该放在第一行的中间。以根节点为中轴线，将二维数组分成左右两部分。左下部分输出左子树，右下部分输出右子树，并且左右子树的宽度相同。即使左子树或右子树有一个为nil，也需要为不存在的子树保留其空间。如果左右子树都不存在，则不需要保留任何空间。
  • 每个未使用的空间需要以空字符串表示。
  • 重复以上操作输出子树。

解题思路

1、需先求出树的高度。
2、根据树的高度，求出n。由题目中的例子可知规则，具体看代码实现。
3、递归遍历左右子树，采用双指针，求出节点的下标。

代码

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
38
39
40
41
42
43
/**
 * 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 printTree(_ root: TreeNode?) -> [[String]] {
        func findDepth(root: TreeNode?) -> Int {
            guard let node = root else { return 0 }
            return 1 + max(findDepth(root: node.left), findDepth(root: node.right))
        }
        
        
        guard let root = root else { return [] }
        
        let height = findDepth(root: root)
        var width = (1 << height) - 1
        var ans = Array(repeating: Array(repeating: "", count: width), count: height)
        
        
        func transform(root: TreeNode?, level: Int, l: Int, r: Int) {
            guard let node = root else { return }
            let mid = l + (r - l) / 2
            ans[level][mid] = "\(node.val)"
            transform(root: node.left, level: level + 1, l: l, r: mid - 1)
            transform(root: node.right, level: level + 1, l: mid + 1, r: r)
        }
        
        
        transform(root: root, level: 0, l: 0, r: width - 1)
        
        return ans
    }
}

发表于 | 分类于 |

748. Shortest Completing Word

题目描述

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, “P” on the licensePlate still matches “p” on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of “PP”, the word “pair” does not complete the licensePlate, but the word “supper” does.

Example 1:

1
2
3
4
5
Input: licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
Output: "steps"
Explanation: The smallest length word that contains the letters "S", "P", "S", and "T".
Note that the answer is not "step", because the letter "s" must occur in the word twice.
Also note that we ignored case for the purposes of comparing whether a letter exists in the word.

Example 2:

1
2
3
4
Input: licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
Output: "pest"
Explanation: There are 3 smallest length words that contains the letters "s".
We return the one that occurred first.

Note:
licensePlate will be a string with length in range [1, 7].
licensePlate will contain digits, spaces, or letters (uppercase or lowercase).
words will have a length in the range [10, 1000].
Every words[i] will consist of lowercase letters, and have length in range [1, 15].

题目大意

给定一个车牌licensePlate，在words中寻找包含了车牌上所有字符的元素。返回最短的匹配元素，如果有多个，则返回第一个。

解题思路

暴力搜索，辅助哈希表。

代码

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
class Solution {
    func shortestCompletingWord(_ licensePlate: String, _ words: [String]) -> String {
        var dict = [Character: Int]()
        var ans = ""
        let express = try! NSRegularExpression(pattern: "[a-z]", options: .caseInsensitive)
        
        for n in licensePlate.lowercased() {
            let s = String(n)
            //正则匹配字母
            if express.matches(in: s, options: NSRegularExpression.MatchingOptions.reportProgress, range: NSRange(location: 0, length: 1))
               .count >= 1{
                dict[n] = (dict[n] ?? 0) + 1
            }
        }
        
        for word in words {
            var tmp = dict
            
            for char in word {
                if let count = tmp[char] {
                    tmp[char] = count - 1
                    if count <= 1 {
                        tmp.removeValue(forKey: char)
                    }
                }
            }
            
            if tmp.isEmpty {
                if ans.isEmpty { ans = word }
                //判断最小匹配元素
                ans = ans.count <= word.count ? ans : word
            }
        }
        return ans
    }
}

发表于 | 分类于 |

718. Maximum Length of Repeated Subarray

题目描述

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

1
2
3
4
5
6
7
Example 1:
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

题目大意

求两个数组内的最长重复子数组。

解题思路

动态规划
遍历数组，找到A和B中数值相等的下标，分别记为i和j，则需将dp[i][j]置为1，如果i + 1和j + 1数值也相同，则此时dp[i+1][j+1]的值应为2。
故有动态规划方程式dp[i + 1][j + 1] = dp[i][j] + 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func findLength(_ A: [Int], _ B: [Int]) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: B.count + 1), count: A.count + 1)
        var ans = 0
        for i in 0..<A.count {
            for j in 0..<B.count {
                if A[i] == B[j] {
                    dp[i + 1][j + 1] = dp[i][j] + 1
                    ans = max(ans, dp[i + 1][j + 1])
                }
            }
        }
        return ans
    }
}

发表于 | 分类于 |

522. Longest Uncommon Subsequence II

题目描述

Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1.

1
2
3
Example 1:
Input: "aba", "cdc", "eae"
Output: 3

Note:

All the given strings’ lengths will not exceed 10.
The length of the given list will be in the range of [2, 50].

题目大意

给定一组字符串，求最长不公共子序列。
子序列可以通过删除一些字符而不改变其余元素顺序的新序列。
空字符串不属于任何字符串的子序列

解题思路

辅助字典，优化数组遍历。
根据字符串长度对数组进行排序，简化遍历。
再次遍历数组，判断当前字符串是否是数组内其他字符串的子字符串。

代码

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
38
39
40
class Solution {
    func findLUSlength(_ strs: [String]) -> Int {
        
        func isSubstring(s: String, t: String) -> Bool {
            var arr1 = Array(s)
            var arr2 = Array(t)
            var index1 = 0
            var index2 = 0
            while index1 < arr1.count && index2 < arr2.count {
                if arr1[index1] == arr2[index2] {
                    index1 += 1
                }
                index2 += 1
            }
            return index1 == arr1.count
        }
        
        var dict = [String: Int]()
        for str in strs {
            dict[str] = (dict[str] ?? 0) + 1
        }
        
        let sortStrs = strs.sorted{ $0.count > $1.count }
        for (i, s) in sortStrs.enumerated() {
            guard dict[s] == 1 else { continue }
            var flag = true
            
            for j in 0..<i {
                if isSubstring(s: s, t: sortStrs[j]) {
                    flag = false
                    break
                }
            }
    
            if flag { return s.count }
            
        }
        return -1
    }
}

发表于 | 分类于 |

746. Min Cost Climbing Stairs

题目描述

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

1
2
3
4
Example 1:
Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.
1
2
3
4
Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

题目大意

上楼梯，可以走一步也可以走两步，每一级台阶都是需要付出代价的，求花最少代价上楼梯。

解题思路

动态规划

代码

1
2
3
4
5
6
7
8
9
10
class Solution {
    func minCostClimbingStairs(_ cost: [Int]) -> Int {
        guard cost.count > 1 else { return cost.last ?? 0 }
        var dp = [cost[0], cost[1]]
        for i in 2..<cost.count {
            dp.append(min(dp[i - 1], dp[i - 2]) + cost[i])
        }
        return min(dp[dp.count - 1], dp[dp.count - 2])
    }
}
0%