发表于 | 分类于 |

525. Contiguous Array

题目描述

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

1
2
3
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

1
2
3
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

题目大意

求数组中 0 和 1 个数一样的最长子数组。

解题思路

主要思路是将 0 换成 -1 进行相加。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    func findMaxLength(_ nums: [Int]) -> Int {
        var dict = [0: -1]
        var sum = 0
        var ml = 0
        for (i, num) in (nums.enumerated()) {
            sum += num == 0 ? -1 : 1
            if let v = dict[sum] {
                ml = max(ml, i - v)
            }else {
                dict[sum] = i
            }
        }
        return ml
    }
}

发表于 | 分类于 |

43. Multiply Strings

题目描述

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

  • The length of both num1 and num2 is < 110.
  • Both num1 and num2 contains only digits 0-9.
  • Both num1 and num2 does not contain any leading zero.
  • You must not use any built-in BigInteger library or convert the inputs to integer directly.

题目大意

大数乘法。

解题思路

模拟手算的过程，以数组 pos 储存结果，第一个字符串的第 i 位 和 第二个字符串的第 j 位相乘，一定是结果的的第 i + j 位，那么对当前结果进行取余就是 进位，即 i + j + 1 位。
最后剔除掉数组 pos 内所有前置位的 0 。

代码

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 multiply(_ num1: String, _ num2: String) -> String {
        let s1 = Array(num1.unicodeScalars.reversed())
        let s2 = Array(num2.unicodeScalars.reversed())
        var pos = Array(repeating: 0, count: num1.count + num2.count)
        for (i, char1) in s1.enumerated() {
            for (j, char2) in s2.enumerated() {
                let mult = Int((char1.value - 48) * (char2.value - 48))
                let p1 = num1.count + num2.count - i - j - 2, p2 = num1.count + num2.count - i - j - 2 + 1
                let sum = mult  + pos[p2]
                pos[p1] += sum / 10
                pos[p2] = sum % 10
            }
        }
        var index = pos.count - 1
        for (i, num) in pos.enumerated() {
            if num != 0 {
                index = i
                break
            }
        }
        let ans = pos[index..<pos.count].reduce("", { (res, num) -> String in
                    return res + "\(num)"
                })
        return ans.count == 0 ? "0" : ans
    }
}

发表于 | 分类于 |

754. Reach a Number

题目描述

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

1
2
3
4
5
Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.

Example 2:

1
2
3
4
5
6
Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step  from 1 to -1.
On the third move we step from -1 to 2.

Note:
target will be a non-zero integer in the range [-10^9, 10^9].

题目大意

向右或者向左移动 N 次， 每一次移动 N 步，求至少需要移动多少步才能终点。

解题思路

按照数学思想，先找规律。
2: 1 - 2 + 3 sum = 3, N = 2 + 1,
3: 1 + 2 sum = 3, N = 3,
4: 1 + 2 - 3 + 4 sum = 6, N = 3 + 1,
5: 1 - 2 - 3 + 4 + 5 sum = 6, N = 3 + 2,
6: 1 + 2 + 3 sum = 6, N = 3,
7: 1 + 2 + 3 - 4 + 5 sum = 10, N = 4 + 1,
8: -1 + 2 + 3 + 4 sum = 10, N = 4,
9: 1 + 2 - 3 + 4 + 5 sum = 10, N = 4 + 1,
10: 1 + 2 + 3 + 4 sum = 10, N = 5,
可得规律：if (sum - target) % 2 == 0 返回 n 即可
if n % 2 == 1 return n + 1
else return n + 2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func reachNumber(_ target: Int) -> Int {
        var sum = 0
        var n = 0
        let target = abs(target)
        while sum < target {
            sum += n
            n += 1
        }
        if (sum - target) % 2 == 0 {
            return n - 1
        }else {
            if n % 2 == 1 { return n }
            else { return n + 1 }
        }
    }
}

发表于 | 分类于 |

130. Surrounded Regions

题目描述

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example,

1
2
3
4
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

1
2
3
4
X X X X
X X X X
X X X X
X O X X

题目大意

将矩阵中，被X包围的所有O都变为X。

解题思路

从四边开始遍历，如果边缘有O,则继续进行广度遍历，将相连的O标记为#。
遍历矩阵，则剩下的O便为被X包围的，即修改为X；将标记为#的修改为O。

代码

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
44
45
46
47
48
49
func solve(_ board: inout [[Character]]) {
        func bfs(x: Int, y: Int) {
            guard board[x][y] == "O" else { return }
            board[x][y] = "#"
            var queue = [(x, y)]
            while !queue.isEmpty {
                let top = queue.removeLast()
                if top.0 > 0 && board[top.0 - 1][top.1] == "O" {
                    board[top.0 - 1][top.1] = "#"
                    queue.append((top.0 - 1, top.1))
                }
                if top.0 < board.count - 1 && board[top.0 + 1][top.1] == "O" {
                    board[top.0 + 1][top.1] = "#"
                    queue.append((top.0 + 1, top.1))
                }
                if top.1 > 0 && board[top.0][top.1 - 1] == "O" {
                    board[top.0][top.1 - 1] = "#"
                    queue.append((top.0, top.1 - 1))
                }
                if top.1 < board[0].count - 1 && board[top.0][top.1 + 1] == "O" {
                    board[top.0][top.1 + 1] = "#"
                    queue.append((top.0, top.1 + 1))
                }
            }
        }
        guard board.count > 2 && board[0].count > 2 else { return }
        for j in 0..<board[0].count {
            bfs(x: 0, y: j)
            bfs(x: board.count - 1, y: j)
        }
        for i in 1..<board.count - 1 {
            bfs(x: i, y: 0)
            bfs(x: i, y: board[0].count - 1)
        }
        for i in 0..<board.count {
            for j in 0..<board[i].count {
                if board[i][j] == "O" {
                    board[i][j] = "X"
                }else if board[i][j] == "#" {
                    board[i][j] = "O"
                }
            }
        }
    }

发表于 | 分类于 |

769. Max Chunks To Make Sorted

题目描述

Given an array arr that is a permutation of [0, 1, …, arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

1
2
3
4
5
6
7
Example 1:
Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.
1
2
3
4
5
6
7
Example 2:
Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

题目大意

将arr拆分n个部分，使得每个部分分别排序之后，重新组合在一起的数组呈递增序列。

解题思路

使数组呈递减序列，不满足条件的既加1：
arr[i..<arr.count].min()! > arr[0..<i].max()!

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    func maxChunksToSorted(_ arr: [Int]) -> Int {
        guard !arr.isEmpty else { return 0 }
        var ans = 1
        for i in 1..<arr.count {
            if arr[i..<arr.count].min()! > arr[0..<i].max()! {
                ans += 1
            }
        }
        return ans
    }
}

768. Max Chunks To Make Sorted II

题目描述

This question is the same as “Max Chunks to Make Sorted” except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8.

Given an array arr of integers (not necessarily distinct), we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

1
2
3
4
5
6
7
Example 1:
Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.
1
2
3
4
5
6
7
Example 2:
Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.

题目大意

这是I的变形，数组可能有重复元素。

解题思路

通过当前数组记为arr和已排序数组记为sortArr进行对比，如果之前的元素个数不相等则计数器加一。
只有当计数器为0，即代表arr和sortArr前N项元素相同，结果加一。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func maxChunksToSorted(_ arr: [Int]) -> Int {
        var ans = 0
        var dict = [Int: Int]()
        var count = 0
        for (x, y) in zip(arr, arr.sorted()) {
            dict[x] = (dict[x] ?? 0) + 1
            if dict[x] == 0 {count -= 1 }
            if dict[x] == 1 { count += 1 }
            dict[y] = (dict[y] ?? 0) - 1
            if dict[y] == -1 { count += 1 }
            if dict[y] == 0 { count -= 1 }
            if count == 0 { ans += 1 }
        }
        return ans
    }
}

发表于 | 分类于 |

592. Fraction Addition and Subtraction

题目描述

Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.

1
2
3
Example 1:
Input:"-1/2+1/2"
Output: "0/1"

Example 2:

1
2
Input:"-1/2+1/2+1/3"
Output: "1/3"

Example 3:

1
2
Input:"1/3-1/2"
Output: "-1/6"

Example 4:

1
2
Input:"5/3+1/3"
Output: "2/1"

Note:

  • The input string only contains ‘0’ to ‘9’, ‘/‘, ‘+’ and ‘-‘. So does the output.
  • Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then ‘+’ will be omitted.
  • The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
  • The number of given fractions will be in the range [1,10].
  • The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

题目大意

通过字符串完成表达式的计算。

解题思路

将”+” 和 “-“作为数字的正负号。
采用欧几里得算法求最大公约数，对分数进行约分。
利用tuple记录分子和分母。

代码

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 greatestCommonDivisor(m: Int, d: Int) -> Int {
        return m == 0 ? d : greatestCommonDivisor(m: d % m, d: m)
    }
    func fractionAddition(_ expression: String) -> String {
        var ans = (0, 1)
        var score = (0, 0)
        var symbol = 1
        var num = 0
        for (i, e) in expression.enumerated() {
            if e == "-" || e == "+" {
                symbol = e == "-" ? -1 : 1
            } else if e == "/" {
                score.0 = symbol * num
                num = 0
            } else {
                num = num * 10 + Int(String(e))!
            }
            if ((e == "-" || e == "+") && num != 0)  || i == expression.count - 1 {
                score.1 = num
                ans = (score.0 * ans.1 + score.1 * ans.0, (score.1 * ans.1))
                let gcd = greatestCommonDivisor(m: abs(ans.0), d: ans.1)
                ans = (ans.0 / gcd, ans.1 / gcd)
                num = 0
            }
        }
        return "\(ans.0)" + "/" + "\(ans.1)"
    }
}

发表于 | 分类于 |

461. Hamming Distance

题目描述

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

1
2
3
4
5
6
7
8
Input: x = 1, y = 4
Output: 2
Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

题目大意

汉明距离，两个二进制数不相等的位的个数。

解题思路

按位异或，求得不相等的位。
遍历，按位与求其个数。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    func hammingDistance(_ x: Int, _ y: Int) -> Int {
        var xor = x^y
        var count = 0
        while xor != 0 {
            xor = (xor - 1) & xor
            count += 1
        }
        return count
    }
}

477. Total Hamming Distance

题目描述

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:
Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Note:
Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

题目大意

计算数组内所有数值的汉明距离。

解题思路

由题目例子看:

1
2
3
4
>14: 1110
>4 : 0100
>2 : 0010
>

第一列的汉明距离是2，第二列的汉明距离是2，第三列的汉明距离是2，第四列的汉明距离是0。

1
2
3
4
5
>14: 1110
>10: 1010
>2 : 0010
>1 : 0001
>

第一列的汉明距离是4，第二列的汉明距离是3，第三列的汉明距离是3，第四列的汉明距离是3。
记每一列的1的个数为count，可得规律：(nums.count - count) * count

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    func totalHammingDistance(_ nums: [Int]) -> Int {
        var ans = 0
        for i in 0..<32 {
            var count = 0
            for num in nums {
                count += (num >> i & 1)
            }
            ans += (nums.count - count) * count
        }
        return ans
    }
}

发表于 | 分类于 |

725. Split Linked List in Parts

题目描述

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode’s representing the linked list parts that are formed.

Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]

1
2
3
4
5
6
7
8
9
Example 1:
Input: 
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].
1
2
3
4
5
6
Example 2:
Input: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Note:

The length of root will be in the range [0, 1000].
Each value of a node in the input will be an integer in the range [0, 999].
k will be an integer in the range [1, 50].

题目大意

给定数值k，把链条平均分配为k个链表，以数组形式返回。
记链表长度 % k为r，有以下规则：

  • 如果k > 链表长度，则返回k个元素的数组，不足的用nil补充。
  • 如果r > 0，则前r项多分配一个节点。
  • 如果r == 0，则链表平均分配节点数即可。

解题思路

先求得链表长度。
按照题目规则生成节点长度的数组，需要用nil补充的，标记为-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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.next = nil
 *     }
 * }
 */
class Solution {
    func splitListToParts(_ root: ListNode?, _ k: Int) -> [ListNode?] {
        
        //求长度
        func findlength(root: ListNode?) -> Int {
            var list = root
            var length = 0
            while list != nil {
                length += 1
                list = list?.next
            }
            return length
        }
        
        
        //求每个链表的长度
        func findListLength(length: Int) -> [Int] {
            let num = length / k
            let r = length % k
            let counts: [Int]
            if r > 0 && r < length {
                counts = Array(repeating: num + 1, count: r) + Array(repeating: num, count: k - r)
            }else if r == length {
                counts = Array(repeating: 1, count: length) + Array(repeating: -1, count: k - length)
            }else {
                counts = Array(repeating: num, count: k)
            }
            return counts
        }
        
        let counts = findListLength(length: findlength(root: root))
        var list = root
        var ans = [ListNode?]()
        for count in counts {
            if count == -1 {
                ans.append(nil)
                continue
            }
            var node = list
            for _ in 0..<count - 1 {
                node = node?.next
            }
            
            ans.append(list)
            list = node?.next
            node?.next = nil
        }
        return ans
    }
}

发表于 | 分类于 |

547. Friend Circles

题目描述

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

1
2
3
4
5
6
7
8
Example 1:
Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.
1
2
3
4
5
6
7
8
Example 2:
Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:

  • N is in range [1,200].
  • M[i][i] = 1 for all students.
  • If M[i][j] = 1, then M[j][i] = 1.

题目大意

如果A和B是朋友，B和C是朋友，那么A和C是间接朋友。
给定二位数组M，如果M[i][j]表示i和j是朋友。求朋友圈的数量。

解题思路

DFS
通过visited辅助数组，判断是否访问过。

代码

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 findCircleNum(_ M: [[Int]]) -> Int {
        guard !M.isEmpty || !M[0].isEmpty else { return 0 }
        
        var ans = 0
        var visited = Array(repeating: 0, count: M[0].count)
        
        func dfs(k: Int) {
            visited[k] = 1
            for i in 0..<M.count {
                if M[k][i] == 0 || visited[i] == 1 { continue }
                dfs(k: i)
            }
        }
        
        for i in 0..<M.count {
            if visited[i] == 1 { continue }
            dfs(k: i)
            ans += 1
        }
        return ans
    }
}

发表于 | 分类于 |

712. Minimum ASCII Delete Sum for Two Strings

题目描述

Given two strings s1, s2, find the lowest ASCII sum of deleted characters to make two strings equal.

1
2
3
4
5
6
Example 1:
Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.
1
2
3
4
5
6
7
Example 2:
Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d]+101[e]+101[e] to the sum.  Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.

Note:

  • 0 < s1.length, s2.length <= 1000.
  • All elements of each string will have an ASCII value in [97, 122].

题目大意

给定两个字符串，删除其中一些字符使得两个字符相等。
删除字符ASCII和最小的。

解题思路

动态规划
使用数组dp记录s1前i项ASCII和。
遍历s2, 使用tmp记录删除字符ASCII和最小。添加规则为:

1
2
3
4
5
6
7
如果相等，则tmp 添加dp[j - 1]，
如果不相等，则有两种选择。第一种：删除s2[i - 1]ASCII再加上前i - 1项内最小的ASCII和；第二种：删除s1[j - 1]再加上前j  - 1项内最小的ASCII和
if s2[i - 1] == s1[j - 1] {
    tmp.append(dp[j - 1])
}else {
    tmp.append(min(dp[j] + Int(s2[i - 1].value), tmp[j - 1] + Int(s1[j - 1].value)))
}

代码

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
class Solution {
    func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
        var dp = [0]
        var arr1 = Array(s1.unicodeScalars)
        var arr2 = Array(s2.unicodeScalars)
        
        for char in s1.unicodeScalars {
            dp.append(dp.last! + Int(char.value))
        }
        
        for i in 1...arr2.count {
            var tmp = [dp[0] + Int(arr2[i - 1].value)]
            for j in 1...arr1.count {
                if arr2[i - 1] == arr1[j - 1] {
                    tmp.append(dp[j - 1])
                }else {
                    tmp.append(min(dp[j] + Int(arr2[i - 1].value), tmp[j - 1] + Int(arr1[j - 1].value)))
                }
            }
            dp = tmp
        }
        
        return dp.last!
    }
}
0%