832. Flipping an Image

题目描述

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

1
2
3
4

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

1
2
3
4

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

• 1 <= A.length = A[0].length <= 20
• 0 <= A[i][j] <= 1

题目大意

给定一二维数组，第一步将每一行数组反转，第二步如果数值是 1 则替换为 0,否则替换为 1。

解题思路

暴力搜索，根据题目要求处理二维数组。

代码

1
2
3
4
5
6
7
8
9
10

class Solution {
    func flipAndInvertImage(_ A: [[Int]]) -> [[Int]] {
        var ans = [[Int]]()
        for a in A {
            ans.append(a.reversed().map{ $0 == 1 ? 0 : 1})
        }
        return ans
    }
}

833. Find And Replace in String

题目描述

To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y. The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y. If not, we do nothing.

For example, if we have S = “abcd” and we have some replacement operation i = 2, x = “cd”, y = “ffff”, then because “cd” starts at position 2 in the original string S, we will replace it with “ffff”.

Using another example on S = “abcd”, if we have both the replacement operation i = 0, x = “ab”, y = “eee”, as well as another replacement operation i = 2, x = “ec”, y = “ffff”, this second operation does nothing because in the original string S[2] = ‘c’, which doesn’t match x[0] = ‘e’.

All these operations occur simultaneously. It’s guaranteed that there won’t be any overlap in replacement: for example, S = “abc”, indexes = [0, 1], sources = [“ab”,”bc”] is not a valid test case.

Example 1:

1
2
3
4

Input: S = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation: "a" starts at index 0 in S, so it's replaced by "eee".
"cd" starts at index 2 in S, so it's replaced by "ffff".

Example 2:

1
2
3
4

Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation: "ab" starts at index 0 in S, so it's replaced by "eee". 
"ec" doesn't starts at index 2 in the original S, so we do nothing.

Notes:

• 0 <= indexes.length = sources.length = targets.length <= 100
• 0 < indexes[i] < S.length <= 1000
• All characters in given inputs are lowercase letters.

题目大意

根据 indexs[i] 所提供的下标，在字符串 S[indexs[i]...] 中，如果是以 sources[i] 开头，则将 sources[i] 替换为 targets[i]。

解题思路

根据 indexs 对 sources 和 targets 进行排序。
根据题目要求进行替换。

代码

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 findReplaceString(_ S: String, _ indexes: [Int], _ sources: [String], _ targets: [String]) -> String {
        var ans = ""
        var last = 0
        var replaceRules = [(Int, String, String)]()
        for ((offset: i, element: index), source) in zip(indexes.enumerated(), sources) {
            replaceRules.append((index, source, targets[i]))
        }
        replaceRules.sort{$0.0 < $1.0}
        for (i, (index, source, target)) in replaceRules.enumerated() {
            if String(S[S.index(S.startIndex, offsetBy: index)...]).hasPrefix(source) {
                ans.append(String(S[S.index(S.startIndex, offsetBy: last)..<S.index(S.startIndex, offsetBy: index)]))
                last = index + source.count
                ans.append(target)
            }
            if i == replaceRules.count - 1 {
                ans.append(String(S[S.index(S.startIndex, offsetBy: last)..<S.endIndex]))
            }
        }
        return ans
    }
}

823. Binary Trees With Factors

题目描述

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node’s value should be equal to the product of the values of it’s children.

How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.

Example 1:

1
2
3

Input: A = [2, 4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

1
2
3

Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Note:

• 1 <= A.length <= 1000.
• 2 <= A[i] <= 10 ^ 9.

题目大意

给定一数组，求最多能生成多少棵，满足左右子节点相乘等于根节点的树，结果最大为 10 ** 9 + 7

解题思路

动态规划
对 A 进行排序。
如果 m * n == a，并且 m * m < a, a % m == 0
则 a 能生成的树为 m * n 如果 m != n则再乘以 2。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    func numFactoredBinaryTrees(_ A: [Int]) -> Int {
        var dp = [Int: Int]()
        let mod = Int(pow(10.0, 9.0)) + 7
        let sortedA = A.sorted()
        for (i, a) in sortedA.enumerated() {
            var num = 0
            for m in sortedA[0..<i] {
                if m * m > a { break }
                if a % m > 0 { continue }
                let n = a / m
                num = num + dp[m]! * (dp[n] ?? 0) * (m != n ? 2 : 1) % mod
            }
            dp[a] = num + 1
        }
        return dp.reduce(0, { (res, arg1) -> Int in
            let (_, v) = arg1
            return v + res
        }) % mod
    }
}

824. Goat Latin

题目描述

A sentence S is given, composed of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to “Goat Latin” (a made-up language similar to Pig Latin.)

The rules of Goat Latin are as follows:

If a word begins with a vowel (a, e, i, o, or u), append “ma” to the end of the word.
For example, the word ‘apple’ becomes ‘applema’.

If a word begins with a consonant (i.e. not a vowel), remove the first letter and append it to the end, then add “ma”.
For example, the word “goat” becomes “oatgma”.

Add one letter ‘a’ to the end of each word per its word index in the sentence, starting with 1.
For example, the first word gets “a” added to the end, the second word gets “aa” added to the end and so on.
Return the final sentence representing the conversion from S to Goat Latin.

Example 1:

1
2

Input: "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Example 2:

1
2

Input: "The quick brown fox jumped over the lazy dog"
Output: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

Notes:

• S contains only uppercase, lowercase and spaces. Exactly one space between each word.
• 1 <= S.length <= 150.

题目大意

以空格将字符串分成一个数组，根据如下规则生成新的字符串。

• 如果以元音字母开头，则直接在尾部加上 ma
• 否则，将第一个字母移至尾部，再在尾部加上 ma
• 第 i 个字符串，则在尾部添加 i 个 a

解题思路

根据题目要求处理字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    func toGoatLatin(_ S: String) -> String {
        var ans = ""
        let vowel = "aeiouAEIOU"
        for (i, s) in S.split(separator: " ").enumerated() {
            var v = ""
            if vowel.contains(s.first!) {
                v += s
            }else {
                v += s[s.index(s.startIndex, offsetBy: 1)...] + String(s.first!)
            }
            ans.append(v + "ma" + String(repeating: "a", count: i+1) + " ")
        }
        ans.removeLast()
        return ans
    }
}

820. Short Encoding of Words

题目描述

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is [“time”, “me”, “bell”], we can write it as S = “time#bell#” and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

1
2
3

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:

• 1 <= words.length <= 2000.
• 1 <= words[i].length <= 7.
• Each word has only lowercase letters

题目大意

给定一组单词将字符变为 word1#word2#....wordn 的字符串 S。
对于任意单词，从下标 i 到 S 中最近的一个 # 之间的，部分相等，则可以不计算此单词。

解题思路

将 words 中的单词反转之后进行排序，如果下一单词不是上一单词的前缀，则加上下一单词的字符长度和 # 字符的长度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    func minimumLengthEncoding(_ words: [String]) -> Int {
        var ans = 0
        var last = ""
        for word in (words.map{ String($0.reversed())}.sorted{$0 > $1} + [""]){
            if !last.hasPrefix(word) {
                ans += word.count + 1
            }
            last = word
        }
        return ans
    }
}

822. Card Flipping Game

题目描述

On a table are N cards, with a positive integer printed on the front and back of each card (possibly different).

We flip any number of cards, and after we choose one card.

If the number X on the back of the chosen card is not on the front of any card, then this number X is good.

What is the smallest number that is good? If no number is good, output 0.

Here, fronts[i] and backs[i] represent the number on the front and back of card i.

A flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.

Example:

1
2
3
4

Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation: If we flip the second card, the fronts are [1,3,4,4,7] and the backs are [1,2,4,1,3].
We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so 2 is good.

Note:

• 1 <= fronts.length == backs.length <= 1000.
• 1 <= fronts[i] <= 2000.
• 1 <= backs[i] <= 2000.

题目大意

每张牌的正反面都有一个数，随意翻牌，找出一个最小的数与其他牌当前的正面数值不相等。
front 代表牌正面的数值，back 代表牌背面的数值。

解题思路

如果正反面数值相同，则无论我们如何翻这张牌，正面的牌一定不符合条件。
找出正反面数值相同。将数值存在集合内。
遍历 front 和 back ，找到不在集合中存在的最小数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    func flipgame(_ fronts: [Int], _ backs: [Int]) -> Int {
        var same = Set<Int>()
        for (front, back) in zip(fronts, backs) {
            if front == back {
                same.insert(front)
            }
        }
        var ans = Int.max
        for (front, back) in zip(fronts, backs) {
            if !same.contains(front){ ans = min(ans, front) }
            if !same.contains(back) { ans = min(ans, back) }
        }
        return ans == Int.max ? 0 : ans
    }
}

819. Most Common Word

题目描述

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.

Example:

1
2
3
4
5
6
7
8
9
10

Input: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

Note:

• 1 <= paragraph.length <= 1000.
• 1 <= banned.length <= 100.
• 1 <= banned[i].length <= 10.
• The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)
• paragraph only consists of letters, spaces, or the punctuation symbols !?’,;.
• Different words in paragraph are always separated by a space.
• There are no hyphens or hyphenated words.
• Words only consist of letters, never apostrophes or other punctuation symbols.

题目大意

求除 banned 内含有的单词以外，出现频次做多的单词。

解题思路

暴力搜索，字典辅助。

代码

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 mostCommonWord(_ paragraph: String, _ banned: [String]) -> String {
        let words = paragraph.split { (c) -> Bool in
            return " [!?',;.]".contains(c)
        }
        var dict = [String: Int]()
        for word in words {
            let str = String(word).lowercased()
            dict[str] = (dict[str] ?? 0) + 1
        }
        var ans = ""
        var frequency = 0
        for (k, v) in dict {
            if !banned.contains(k) {
                ans = frequency > v ? ans : k
                frequency = max(frequency, v)
            }
        }
        return ans
    }
}

789. Escape The Ghosts

题目描述

You are playing a simplified Pacman game. You start at the point (0, 0), and your destination is (target[0], target[1]). There are several ghosts on the map, the i-th ghost starts at (ghosts[i][0], ghosts[i][1]).

Each turn, you and all ghosts simultaneously may move in one of 4 cardinal directions: north, east, west, or south, going from the previous point to a new point 1 unit of distance away.

You escape if and only if you can reach the target before any ghost reaches you (for any given moves the ghosts may take.) If you reach any square (including the target) at the same time as a ghost, it doesn’t count as an escape.

Return True if and only if it is possible to escape.

Example 1:

1
2
3
4
5
6

Input: 
ghosts = [[1, 0], [0, 3]]
target = [0, 1]
Output: true
Explanation: 
You can directly reach the destination (0, 1) at time 1, while the ghosts located at (1, 0) or (0, 3) have no way to catch up with you.

Example 2:

1
2
3
4
5
6

Input: 
ghosts = [[1, 0]]
target = [2, 0]
Output: false
Explanation: 
You need to reach the destination (2, 0), but the ghost at (1, 0) lies between you and the destination.

Example 3:

1
2
3
4
5
6

Input: 
ghosts = [[2, 0]]
target = [1, 0]
Output: false
Explanation: 
The ghost can reach the target at the same time as you.

Note:

• All points have coordinates with absolute value <= 10000.
• The number of ghosts will not exceed 100.

题目大意

玩家从原点到达目标位置 target，ghosts 表示鬼魂的位置，玩家可以向上下左右进一步，求是否能在不遇到鬼魂的情况下，到达目标位置。

解题思路

根据以起点到目标位置的 曼哈顿距离记为 min_ghost，求是否有鬼魂的曼哈顿距离小于 min_ghost, 如果有则返回 true，否则返回 false。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    func escapeGhosts(_ ghosts: [[Int]], _ target: [Int]) -> Bool {
        func manhattanDistance(lhs: [Int], rhs: [Int]) -> Int {
            return abs(lhs[0] - rhs[0]) + abs(lhs[1] - rhs[1])
        }
        
        var min_ghost = manhattanDistance(lhs: [0, 0], rhs: target)
        for point in ghosts {
            if manhattanDistance(lhs: point, rhs: target) <= min_ghost {
                return false
            }
        }
        return true
    }
}

424. Longest Repeating Character Replacement

题目描述

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string’s length and k will not exceed 104.

Example 1:

1
2
3
4
5
6
7
8

Input:
s = "ABAB", k = 2
Output:
4
Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

1
2
3
4
5
6
7
8
9

Input:
s = "AABABBA", k = 1
Output:
4
Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

题目大意

替换字符串 s 中 k 个字符，使字符串拥有最长重复字符。

解题思路

滑动窗口
维护有效区间 l...r，使得区间内除重复字符以外的字符不大于k。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
   func characterReplacement(_ s: String, _ k: Int) -> Int {
        var dict = Array(repeating: 0, count: 26)
        var ans = 0
        var l = 0
        var chars = Array(s.unicodeScalars)
        var maxCount = 0
        for (r, char) in chars.enumerated() {
            let ascii = Int(char.value) - 65
            dict[ascii] += 1
            maxCount = max(maxCount, dict[ascii])
            while r - l + 1 - dict[Int(chars[l].value) - 65] > k {
                dict[Int(chars[l].value) - 65] -= 1
                l += 1
            }
        }
        return min(chars.count, maxCount + k)
    }
}

831. Masking Personal Information

题目描述

We are given a personal information string S, which may represent either an email address or a phone number.

We would like to mask this personal information according to the following rules:

1. Email address:

We define a name to be a string of length ≥ 2 consisting of only lowercase letters a-z or uppercase letters A-Z.

An email address starts with a name, followed by the symbol ‘@’, followed by a name, followed by the dot ‘.’ and followed by a name.

All email addresses are guaranteed to be valid and in the format of “name1@name2.name3”.

To mask an email, all names must be converted to lowercase and all letters between the first and last letter of the first name must be replaced by 5 asterisks ‘*’.

1. Phone number:

A phone number is a string consisting of only the digits 0-9 or the characters from the set {‘+’, ‘-‘, ‘(‘, ‘)’, ‘ ‘}. You may assume a phone number contains 10 to 13 digits.

The last 10 digits make up the local number, while the digits before those make up the country code. Note that the country code is optional. We want to expose only the last 4 digits and mask all other digits.

The local number should be formatted and masked as “--1111”, where 1 represents the exposed digits.

To mask a phone number with country code like “+111 111 111 1111”, we write it in the form “+--*-1111”. The ‘+’ sign and the first ‘-‘ sign before the local number should only exist if there is a country code. For example, a 12 digit phone number mask should start with “+-“.

Note that extraneous characters like “(“, “)”, “ “, as well as extra dashes or plus signs not part of the above formatting scheme should be removed.

Return the correct “mask” of the information provided.

Example 1:

1
2
3
4
5

Input: "LeetCode@LeetCode.com"
Output: "l*****e@leetcode.com"
Explanation: All names are converted to lowercase, and the letters between the
             first and last letter of the first name is replaced by 5 asterisks.
             Therefore, "leetcode" -> "l*****e".

Example 2:

1
2
3
4

Input: "AB@qq.com"
Output: "a*****b@qq.com"
Explanation: There must be 5 asterisks between the first and last letter 
             of the first name "ab". Therefore, "ab" -> "a*****b".

Example 3:

1
2
3

Input: "1(234)567-890"
Output: "***-***-7890"
Explanation: 10 digits in the phone number, which means all digits make up the local number.

Example 4:

1
2
3

Input: "86-(10)12345678"
Output: "+**-***-***-5678"
Explanation: 12 digits, 2 digits for country code and 10 digits for local number.

Notes:

• S.length <= 40.
• Emails have length at least 8.
• Phone numbers have length at least 10.

题目大意

给定字符串，要求如下：

• 如果是邮箱地址，根据 @将字符串为 firstName 和 lastName, 保留 firstName 的第一个字符和最后一个字符，其他字符以 *****代替返回。

• 如果是电话号码，有可能是 10~13 位数字，其中十位为本地电话号码，其余的为国家号码。

  • 如果有国家号码则返回 + + 国家号码位数个 * + -***- + 号码后四位。
  • 如果没有国家号码则返回 ***-***- + 号码后四位。

解题思路

根据题目要求处理字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    func maskPII(_ S: String) -> String {
        let names = S.split(separator: "@")
        if names.count > 1 {
            let firstName = names[0]
            return String(firstName.first!).lowercased() + "*****" + String(firstName.last!).lowercased() + "@" + names[1].lowercased()
        }else {
            let phone = S.unicodeScalars.filter{ $0.value >= 48 && $0.value <= 57 }
            if phone.count == 10 {
                return "***-***-" + String(phone[phone.index(phone.endIndex, offsetBy: -4)...])
            }else {
                let country = (0..<phone.count - 10).reduce("") { (ans, _) -> String in
                    return ans + "*"
                }
                return "+" + country + "-***-***-" +  String(phone[phone.index(phone.endIndex, offsetBy: -4)...])
            }
        }
    }
}