发表于 | 分类于 |

804. Unique Morse Code Words

题目描述

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: “a” maps to “.-“, “b” maps to “-…”, “c” maps to “-.-.”, and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[“.-“,”-…”,”-.-.”,”-..”,”.”,”..-.”,”–.”,”….”,”..”,”.—“,”-.-“,”.-..”,”–”,”-.”,”—“,”.–.”,”–.-“,”.-.”,”…”,”-“,”..-“,”…-“,”.–”,”-..-“,”-.–”,”–..”]
Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, “cab” can be written as “-.-.-….-“, (which is the concatenation “-.-.” + “-…” + “.-“). We’ll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.

Example:

1
2
3
4
5
6
7
8
9
10
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation: 
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."
There are 2 different transformations, "--...-." and "--...--.".

Note:

  • The length of words will be at most 100.
  • Each words[i] will have length in range [1, 12].
  • words[i] will only consist of lowercase letters.

题目大意

根据摩斯电码，生成对应的摩斯密码，返回不同摩斯密码的个数。

解题思路

Set

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func uniqueMorseRepresentations(_ words: [String]) -> Int {
        var morseCode = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---",
                         "-.-",".-..","--","-.","---",".--.","--.-",".-.","...",
                         "-","..-","...-",".--","-..-","-.--","--.."]
        var unique = Set<String>()
        for word in words {
            var str = ""
            for char in word.unicodeScalars {
                str.append(morseCode[Int(char.value - 97)])
            }
            unique.insert(str)
        }
        return unique.count
    }
}

发表于 | 分类于 |

[797. All Paths From Source to Target

](https://leetcode.com/problems/all-paths-from-source-to-target/description/)

题目描述

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.

Note:

  • The number of nodes in the graph will be in the range [2, 15].
  • You can print different paths in any order, but you should keep the order of nodes inside one path.

题目大意

给定有向无环图，求顶点 0 到 N - 1 的所有路径

解题思路

DFS

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] {
        var ans = [[Int]]()
        
        func dfs(list: [Int], path: [Int]) {
            for p in list {
                var new = path
                new.append(p)
                if p == graph.count - 1 {
                    ans.append(new)
                }else {
                    dfs(list: graph[p], path: new)
                }
            }
        }
        dfs(list: graph[0], path: [0])
        return ans
    }
}

发表于 | 分类于 |

791. Custom Sort String

题目描述

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :
Input:
S = “cba”
T = “abcd”
Output: “cbad”
Explanation:
“a”, “b”, “c” appear in S, so the order of “a”, “b”, “c” should be “c”, “b”, and “a”.
Since “d” does not appear in S, it can be at any position in T. “dcba”, “cdba”, “cbda” are also valid outputs.

Note:

S has length at most 26, and no character is repeated in S.
T has length at most 200.
S and T consist of lowercase letters only.

题目大意

根据 S 给定的字母顺序，对 T 进行排序，S 中不存在的字母按照原有顺序排列在尾部。

解题思路

选择排序思路。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func customSortString(_ S: String, _ T: String) -> String {
        var sArr = Array(S)
        var tArr = Array(T)
        var index = 0
        for i in 0..<sArr.count {
            for j in index..<tArr.count {
                if tArr[j] == sArr[i] {
                    tArr[j] = tArr[index]
                    tArr[index] = sArr[i]
                    index += 1
                }
            }
        }
        return String(tArr)
    }
}

发表于 | 分类于 |

807. Max Increase to Keep City Skyline

题目描述

In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.

At the end, the “skyline” when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city’s skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.

What is the maximum total sum that the height of the buildings can be increased?

Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation:
The grid is:
[ [3, 0, 8, 4],
[2, 4, 5, 7],
[9, 2, 6, 3],
[0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]

Notes:

  • 1 < grid.length = grid[0].length <= 50.
  • All heights grid[i][j] are in the range [0, 100].
  • All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

题目大意

二维数组表示一组建筑的高度
横向和纵向的最高的高度定为天际线
将建筑的高度提高到不影响天际线的最大高度
求高度提升的总和

解题思路

分别求出每一行、每一列的最大高度，并且以 maxRow 、 maxColumn数组储存。
根据 maxRow 和 maxColumn 求每一个建筑物能够提升的最大高度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    func maxIncreaseKeepingSkyline(_ grid: [[Int]]) -> Int {
        var maxRow = grid.map{ return $0.max()! }
        var maxColumn = [Int]()
        for i in 0..<grid[0].count {
            var maxLine = -1
            for j in 0..<grid.count {
                maxLine = max(maxLine, grid[j][i])
            }
            maxColumn.append(maxLine)
        }
        var ans = 0
        for i in 0..<grid.count {
            for j in 0..<grid[i].count {
                ans += min(maxRow[i], maxColumn[j]) - grid[i][j]
            }
        }
        return ans
    }
}

发表于 | 分类于 |

809. Expressive Words

题目描述

Sometimes people repeat letters to represent extra feeling, such as “hello” -> “heeellooo”, “hi” -> “hiiii”. Here, we have groups, of adjacent letters that are all the same character, and adjacent characters to the group are different. A group is extended if that group is length 3 or more, so “e” and “o” would be extended in the first example, and “i” would be extended in the second example. As another example, the groups of “abbcccaaaa” would be “a”, “bb”, “ccc”, and “aaaa”; and “ccc” and “aaaa” are the extended groups of that string.

For some given string S, a query word is stretchy if it can be made to be equal to S by extending some groups. Formally, we are allowed to repeatedly choose a group (as defined above) of characters c, and add some number of the same character c to it so that the length of the group is 3 or more. Note that we cannot extend a group of size one like “h” to a group of size two like “hh” - all extensions must leave the group extended - ie., at least 3 characters long.

Given a list of query words, return the number of words that are stretchy.

Example:
Input:
S = “heeellooo”
words = [“hello”, “hi”, “helo”]
Output: 1
Explanation:
We can extend “e” and “o” in the word “hello” to get “heeellooo”.
We can’t extend “helo” to get “heeellooo” because the group “ll” is not extended.
Notes:

0 <= len(S) <= 100.
0 <= len(words) <= 100.
0 <= len(words[i]) <= 100.
S and all words in words consist only of lowercase letters

题目大意

给定一字符串 S，是否能从 words 中的字符串进行扩展得到 S ，返回可扩展的字符串个数。
扩展规则为：连续相同的多个字符，可以扩展为不小于3个字符。

解题思路

根据规则计算 S 和 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
class Solution {
    func expressiveWords(_ S: String, _ words: [String]) -> Int {
        func charCount(str: String) -> [(Character, Int)] {
            var ans = [(Character, Int)]()
            var lastChar: Character = Character("1")
            var count = 0
            for char in str {
                if lastChar == char {
                    count += 1
                }else {
                    if count > 0 { ans.append((char, count)) }
                    lastChar = char
                    count = 1
                }
            }
            if count > 0 { ans.append((lastChar, count)) }
            return ans
        }
        func checkWord(st: [(Character, Int)], wt: [(Character, Int)]) -> Int {
            guard st.count == wt.count else { return 0 }
            for (v1, v2) in zip(st, wt) {
                if v1.0 != v2.0 { return 0 }
                if v1.1 < v2.1 { return 0 }
                if v1.1 != v2.1 && v1.1 < 3 { return 0 }
            }
            return 1
        }
        let st = charCount(str: S)
        return words.reduce(0) { (res, word) -> Int in
            return res + checkWord(st: st, wt: charCount(str: word))
        }
    }
}

发表于 | 分类于 |

814. Binary Tree Pruning

题目描述

We are given the head node root of a binary tree, where additionally every node’s value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Example 1:

1
2
3
4
5
6
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]
 
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Example 2:

1
2
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Example 3:

1
2
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Note:

The binary tree will have at most 100 nodes.
The value of each node will only be 0 or 1.

题目大意

给定以二叉树，每个节点值为 0 或者 1。
删除每个不包含 1 的子树。

解题思路

遍历二叉树，如果根节点值为 1 或者 左子树不为空 或者 右子树不为空，返回 根节点，否则返回nil。

代码

1
2
3
4
5
6
7
8
class Solution {
    func pruneTree(_ root: TreeNode?) -> TreeNode? {
        guard let tree = root else { return nil }
        tree.left = pruneTree(tree.left)
        tree.right = pruneTree(tree.right)
        return (tree.val == 1 || root?.left != nil || root?.right != nil) ? tree : nil
    }
}

发表于 | 分类于 |

783. Minimum Distance Between BST Nodes

题目描述

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.

Example :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.
The given tree [4,2,6,1,3,null,null] is represented by the following diagram:
          4
        /   \
      2      6
     / \    
    1   3  
while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

Note:

  • The size of the BST will be between 2 and 100.
  • The BST is always valid, each node’s value is an integer, and each node’s value is different.

题目大意

给定一个二叉搜索树，返回树中任意两个不同节点的最小差值。

解题思路

中序遍历树，计算最小差值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    func minDiffInBST(_ root: TreeNode?) -> Int {
        var pre = -1
        var dist = Int.max
        func minDiff(root: TreeNode?) {
            guard let tree = root else { return }
            if let left = tree.left {
                minDiff(root: left)
            }
            if pre >= 0 {
                dist = min(dist, tree.val - pre)
            }
            pre = tree.val
            if let right = tree.right {
                minDiff(root: right)
            }
        }
        minDiff(root: root)
        return dist
    }
}

发表于 | 分类于 |

698. Partition to K Equal Sum Subsets

题目描述

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

1
2
3
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

题目大意

将数组平均分成 k 个子序列，每个子序列和相同。

解题思路

递归遍历数组，用 visited 标记访问过的元素。

代码

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
class Solution {
    func canPartitionKSubsets(_ nums: [Int], _ k: Int) -> Bool {
        let sum = nums.reduce(0, +)
        var visted = Array(repeating: false, count: nums.count)
        guard nums.count > k, sum % k == 0 else { return false }
        let target = sum / k
        
        func divide(k: Int, currentSum: Int, currentNum: Int, start: Int) -> Bool {
            if k == 1 { return true }
            if currentSum == target && currentNum > 0 {
                return divide(k: k - 1, currentSum: 0, currentNum: 0, start: 0)
            }
            for i in start..<nums.count {
                if !visted[i] {
                    if nums[i] + currentSum > target { continue }
                    visted[i] = true
                    if divide(k: k, currentSum: currentSum + nums[i], currentNum: currentNum + 1, start: i + 1) {
                        return true
                    }
                    visted[i] = false
                }
            }
            return false
        }
        
        return divide(k: k, currentSum: 0, currentNum: 0, start: 0)
    }
}

发表于 | 分类于 |

752. Open the Lock

题目描述

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. The wheels can rotate freely and wrap around: for example we can turn ‘9’ to be ‘0’, or ‘0’ to be ‘9’. Each move consists of turning one wheel one slot.

The lock initially starts at ‘0000’, a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

Example 1:

1
2
3
4
5
6
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

1
2
3
4
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

1
2
3
4
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Example 4:

1
2
Input: deadends = ["0000"], target = "8888"
Output: -1

Note:

  • The length of deadends will be in the range [1, 500].
  • target will not be in the list deadends.
  • Every string in deadends and the string target will be a string of 4 digits from the 10,000 possibilities ‘0000’ to ‘9999’.

题目大意

密码锁解锁，从 0000 开始，移动每个齿轮，直到匹配到目标数字组合，求需要移动的步数。
其中 deadends 表示不能够访问的数字组合； 0 可以转到 9, 9 也可以转到 0。

解题思路

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
26
27
28
29
30
31
32
class Solution {
    func openLock(_ deadends: [String], _ target: String) -> Int {
        if deadends.contains("0000") { return -1 }
        var queue = ["0000"]
        var visited = Set(deadends + queue)
        var step = 1
        while !queue.isEmpty {
            var temp = [String]()
            for status in queue {
                let chars = status.utf8
                for (i, char) in chars.enumerated() {
                    let pre = String(chars.prefix(i))!
                    let suf = String(chars.suffix(4-i-1))!
                    for j in [1, 9] {   //需要即能正向转动齿轮，亦可反向转动齿轮。
                        let e = (Int(char) - 48 + j) % 10
                        let str = pre  + "\(e)" + suf
                        if target == str { return step }
                        if !visited.contains(str) {
                            visited.insert(str)
                            temp.append(str)
                        }
                    }
                }
            }
            queue = temp
            step += 1
        }
        return -1
    }
}

发表于 | 分类于 |

744. Find Smallest Letter Greater Than Target

题目描述

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = ‘z’ and letters = [‘a’, ‘b’], the answer is ‘a’.

Examples:
Input:
letters = [“c”, “f”, “j”]
target = “a”
Output: “c”

Input:
letters = [“c”, “f”, “j”]
target = “c”
Output: “f”

Input:
letters = [“c”, “f”, “j”]
target = “d”
Output: “f”

Input:
letters = [“c”, “f”, “j”]
target = “g”
Output: “j”

Input:
letters = [“c”, “f”, “j”]
target = “j”
Output: “c”

Input:
letters = [“c”, “f”, “j”]
target = “k”
Output: “c”
Note:
letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

题目大意

letters 是有序数组，找到 letters 中第一个大于 target 的值，如果不存在，则返回最小值。

解题思路

二分查找。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    func nextGreatestLetter(_ letters: [Character], _ target: Character) -> Character {
        var l = 0, r = letters.count - 1
        while l < r - 1 {
            let m = l + (r - l) / 2
            if letters[m] <= target {
                l = m + 1
            }else {
                r = m
            }
        }
        if letters[l] > target { return letters[l] }
        if letters[r] > target { return letters[r] }
        return letters[0]
    }
}
0%