发表于 |

230. Kth Smallest Element in a BST

题目描述

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

题目大意

找二叉搜索树中，第 k 个小的值。

解题思路

通过辅助栈，按照中序遍历二叉树。

代码

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 kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        var tree = root
        var stack = [TreeNode?]()
        while tree != nil {
            stack.append(tree)
            tree = tree?.left
        }
        var num = 1
        while !stack.isEmpty && num <= k {
            tree = stack.removeLast()
            num += 1
            var r = tree?.right
            while r != nil {
                stack.append(r)
                r = r?.left
            }
        }
        return tree?.val ?? 0
    }
}

发表于 | 分类于 |

464. Can I Win

题目描述

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
maxChoosableInteger = 10
desiredTotal = 11
Output:
false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

题目大意

提供两个整数 maxChoosableInteger 和 desiredTotal 两个玩家轮流从 1~maxChoosableInteger,直到 总和 >= desiredTotal，确定第一个玩家是否能获胜。 1~maxChoosableInteger 不能重复选择。

解题思路

通过 visited 数组记录是否数字是否已经被访问过。
map 记录当前组合是否被访问过。
简单粗暴的 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
30
31
class Solution {
    func canIWin(_ maxChoosableInteger: Int, _ desiredTotal: Int) -> Bool {
        if desiredTotal <= maxChoosableInteger { return true }
        if (1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal { return false }
        var visited = Array(repeating: false, count: maxChoosableInteger)
        var map = [Int: Bool]()
        func dfs(target: Int) -> Bool {
            let key = (visited.reduce(0) { (res, v) -> Int in
                var next = res << 1
                if v { next |= 1 }
                return next
            })
            if let v = map[key] { return v }
            for (i, v) in visited.enumerated() {
                if !v {
                    visited[i] = true
                    if target <= i + 1 || !dfs(target: target - i - 1) {
                        map[key] = true
                        visited[i] = false
                        return true
                    }
                    visited[i] = false
                }
            }
            map[key] = false
            return false
        }
        return dfs(target: desiredTotal)
    }
}

发表于 | 分类于 |

658. Find K Closest Elements

题目描述

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

1
2
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

1
2
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

  • The value k is positive and will always be smaller than the length of the sorted array.
  • Length of the given array is positive and will not exceed 104
  • Absolute value of elements in the array and x will not exceed 104

题目大意

给定一个有序数组，在数组中找到与 x 接近的 k 个元素。

解题思路

使用二分查找找到最接近 x 的数组下标 index。
从子序列 index-k...index+k 中找到最接近 x 的 k 个元素。

代码

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 findClosestElements(_ arr: [Int], _ k: Int, _ x: Int) -> [Int] {
        func binarySearch() -> Int {
            var l = 0
            var r = arr.count - 1
            while l + 1 < r {
                let mid = (l + r) / 2
                if arr[mid] == x {
                    return mid
                }else if arr[mid] > x {
                    r = mid
                }else {
                    l = mid
                }
            }
            return r
        }
        guard arr.count > 0 else { return [] }
        if arr[0] > x { return Array(arr[0..<min(k, arr.count)]) }
        if arr.last! < x { return Array(arr[max(arr.count - k, 0)..<arr.count]) }
        let index = binarySearch()
        var l = max(0, index - k)
        var r = min(index + k, arr.count - 1)
        while r - l != k - 1 {
            if x - arr[l] > arr[r] - x {
                l += 1
            }else {
                r -= 1
            }
        }
        return Array(arr[l...r])
    }
}

发表于 | 分类于 |

795. Number of Subarrays with Bounded Maximum

题目描述

We are given an array A of positive integers, and two positive integers L and R (L <= R).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

1
2
3
4
5
6
7
Example :
Input: 
A = [2, 1, 4, 3]
L = 2
R = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Note:

  • L, R and A[i] will be an integer in the range [0, 10^9].
  • The length of A will be in the range of [1, 50000].

题目大意

求最大值 >= L、<= R的所有子序列。

解题思路

通过 > R 将数组分割成多个子序列。
再通过 < L 将数组分割计算，确保每个子序列中都存在至少一个满足 >= L && <= R。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    func numSubarrayBoundedMax(_ A: [Int], _ L: Int, _ R: Int) -> Int {
        var ans = 0
        var lastIndex = 0
        for (i, a) in (A+[R+1]).enumerated() {
            if a > R {
                let c = i - lastIndex
                var last = 0
                for (j, subA) in A[lastIndex..<i].enumerated() {
                    if subA >= L {
                        ans += (j - last + 1) * (c - j)
                        last = j + 1
                    }
                }
                lastIndex = i + 1
            }
        }
        return ans
    }
}

发表于 | 分类于 |

659. Split Array into Consecutive Subsequences

题目描述

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Example 1:

1
2
3
4
5
6
Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3
3, 4, 5

Example 2:

1
2
3
4
5
6
Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3, 4, 5
3, 4, 5

Example 3:

1
2
Input: [1,2,3,4,4,5]
Output: False

Note:
The length of the input is in range of [1, 10000]

题目大意

将一有序数组，拆分成多个递增子序列。（每个子序列至少三个）

解题思路

一个字典 dict 记录剩余 num 的个数
另一个字典 tail 则记录当前的 num 是否可以被拼接到之前的子序列。
如果不可以则重新启动一个新的序列，但是新的序列需要满足至少有三个 num 。

代码

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 isPossible(_ nums: [Int]) -> Bool {
        var dict = [Int: Int]()
        var tail = [Int:Int]()
        for num in nums {
            dict[num] = (dict[num] ?? 0) + 1
        }
        for num in nums {
            if let c = dict[num], c == 0 {
                continue
            } else if let c = tail[num], c > 0 {
                tail[num] = c - 1
                tail[num + 1] = (tail[num + 1] ?? 0) + 1
            } else if let c1 = dict[num + 1], c1 > 0, let c2 = dict[num + 2], c2 > 0 {
                dict[num + 1] = c1 - 1
                dict[num + 2] = c2 - 1
                tail[num + 3] = (tail[num + 3] ?? 0) + 1
            } else {
                return false
            }
            dict[num]! -= 1
        }
        return true
    }
}

发表于 | 分类于 |

649. Dota2 Senate

题目描述

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

Ban one senator’s right:
A senator can make another senator lose all his rights in this and all the following rounds.
Announce the victory:
If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.
Given a string representing each senator’s party belonging. The character ‘R’ and ‘D’ represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire.

Example 1:
Input: “RD”
Output: “Radiant”
Explanation: The first senator comes from Radiant and he can just ban the next senator’s right in the round 1.
And the second senator can’t exercise any rights any more since his right has been banned.
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.
Example 2:
Input: “RDD”
Output: “Dire”
Explanation:
The first senator comes from Radiant and he can just ban the next senator’s right in the round 1.
And the second senator can’t exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator’s right in the round 1.
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote

题目大意

有两个阵营，分别是 R 和 D ，使用最佳策略对其他阵营进行禁言。求最终可以发言的阵营。

解题思路

通过模拟每一轮投票，直到只剩下一个阵营，flag为正则表示 R 占据优势，flag为负则表示D占据优势。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    func predictPartyVictory(_ senate: String) -> String {
        var senates = Array(senate)
        var flag = 0
        while Set(senates).count > 1 {
            var tmpSenates = [Character]()
            for s in senates {
                if s == "R" {
                    if flag >= 0 { tmpSenates.append("R") }
                    flag += 1
                }else {
                    if flag <= 0 { tmpSenates.append("D") }
                    flag -= 1
                }
            }
            senates = tmpSenates
        }
        return senates[0] == "D" ? "Dire" : "Radiant"
    }
}

发表于 |

Jewels and Stones

题目描述

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so “a” is considered a different type of stone from “A”.

Example 1:

1
2
Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

1
2
Input: J = "z", S = "ZZ"
Output: 0

Note:

  • S and J will consist of letters and have length at most 50.
  • The characters in J are distinct.

题目大意

求 S 中有多少个 J 中的字母，区分大小写。

解题思路

辅助字典，暴力搜索

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func numJewelsInStones(_ J: String, _ S: String) -> Int {
        var dict = [Character: Int]()
        for char in J {
            dict[char] = 1
        }
        var ans = 0
        for char in S {
            if dict[char] != nil {
                ans += 1
            }
        }
        return ans
    }
}

发表于 |

638. Shopping Offers

题目描述

In LeetCode Store, there are some kinds of items to sell. Each item has a price.

However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.

You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.

Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.

You could use any of special offers as many times as you want.

Example 1:

1
2
3
4
5
6
7
Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation: 
There are two kinds of items, A and B. Their prices are $2 and $5 respectively. 
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B. 
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.

Example 2:

1
2
3
4
5
6
7
Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation: 
The price of A is $2, and $3 for B, $4 for C. 
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C. 
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C. 
You cannot add more items, though only $9 for 2A ,2B and 1C.

Note:

  • There are at most 6 kinds of items, 100 special offers.
  • For each item, you need to buy at most 6 of them.
    You are not allowed to buy more items than you want, even if that would lower the overall price.

题目大意

给定一组商品价格 prices ,以及一些组合的优惠策略 special （包含商品数目及其对应的价格）, 以及要购买的商品数目 needs，求在最优策略下，恰好购买 needs 所需的商品（不能超过），需要的最小金额。

解题思路

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
30
class Solution {
    func shoppingOffers(_ price: [Int], _ special: [[Int]], _ needs: [Int]) -> Int {
        var dict = [String: Int]()
        func dfs(needs: [Int]) -> Int {
            var key = ""
            var total = 0
            for (n, p) in zip(needs, price) {
                total += n * p
                key += "\(n)-"
            }
            if let cost = dict[key] { return cost }
            dict[key] = total
            for discounts in special {
                var finalNeeds = [Int]()
                for (d, n) in zip(discounts, needs) {
                    let surplus = n - d
                    if surplus < 0 { break }
                    finalNeeds.append(surplus)
                }
                if finalNeeds.count != needs.count { continue }
                dict[key] = min(dict[key]!, dfs(needs: finalNeeds) + discounts.last!)
            }
            return dict[key]!
        }
        return dfs(needs: needs)
    }
}

发表于 | 分类于 |

766. Toeplitz Matrix

题目描述

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1:

1
2
3
4
5
6
7
8
9
Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: True
Explanation:
1234
5123
9512
In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", 
"[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.

Example 2:

1
2
3
4
Input: matrix = [[1,2],[2,2]]
Output: False
Explanation:
The diagonal "[1, 2]" has different elements.

Note:

  • matrix will be a 2D array of integers.
  • matrix will have a number of rows and columns in range [1, 20].
  • matrix[i][j] will be integers in range [0, 99].

题目大意

求证此矩阵是否是常对角矩阵

解题思路

按照矩阵要求遍历即可。

代码

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 isToeplitzMatrix(_ matrix: [[Int]]) -> Bool {
        guard !matrix.isEmpty else { return false }
        let width = matrix.count
        let height = matrix[0].count
        for (index, row) in matrix.enumerated() {
            var i = index + 1, j = 1
            let num = row[0]
            while i < width && j < height {
                if num != matrix[i][j] { return false }
                i += 1
                j += 1
            }
        }
        for (index, column) in matrix[0].enumerated() {
            guard index > 0 else { continue }
            var i = 1, j = index + 1
            let num = column
            while i < width && j < height {
                if num != matrix[i][j] { return false }
                i += 1
                j += 1
            }
        }
        return true
    }
}

发表于 | 分类于 |

263. Ugly Number

题目描述

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

题目大意

丑陋数即由主要因子 2、3、5 相乘得到，1 为特殊的丑陋数。例如：6和8是丑陋数，而14不是，因为丑陋因子不包括 7

解题思路

通过递归，对目标数进行取余，判断是否能被整除，以此循环。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    func isUgly(_ num: Int) -> Bool {
        guard num > 0 else { return false }
        if num == 1 { return true }
        else if num % 2 == 0 { return isUgly(num / 2) }
        else if num % 3 == 0 { return isUgly(num / 3) }
        else if num % 5 == 0 { return isUgly(num / 5) }
        return num == 1
    }
}

264. Ugly Number II

题目描述

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number, and n does not exceed 1690.

题目大意

例如 1、2、3、4、5、6、8、9、10、12 。按照大小排列，求 n-th 丑陋数。

解题思路

从上述的例子可以看出 丑陋数由下列数组成
2 1, 2 2, 2 3, 2 4…..
3 1, 3 2, 3 3, 3 4…..
5 1, 5 2, 5 3, 5 4…..
就是在每一列求最小，例如第一次 2 3 5中2 是最小，则第二次就变成 4 3 5求最小，以此类推。

代码

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 nthUglyNumber(_ n: Int) -> Int {
        guard n > 6 else { return n }
        var uglyNums = Array(repeating: 0, count: n)
        uglyNums[0] = 1
        var f2 = 2, f3 = 3, f5 = 5
        var i2 = 0, i3 = 0, i5 = 0
        for i in 1..<n {
            let num = min(f2, f3, f5)
            uglyNums[i] = num
            if f2 == num {
                i2 += 1
                f2 = 2 * uglyNums[i2]
            }
            if f3 == num {
                i3 += 1
                f3 = 3 * uglyNums[i3]
            }
            if f5 == num {
                i5 += 1
                f5 = 5 * uglyNums[i5]
            }
        }
        return uglyNums.last!
    }
}

313. Super Ugly Number

题目描述

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

题目大意

实际上是 Ugly Number II 的变形，丑陋因子不固定，由 primes 参数提供。

解题思路

实现思路与 Ugly Number II 一致，只是把 2 3 5 变成了 primes数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    func nthSuperUglyNumber(_ n: Int, _ primes: [Int]) -> Int {
        var uglyNums = Array(repeating: Int.max, count: n)
        var indexs = Array(repeating: 0, count: primes.count)
        uglyNums[0] = 1
        for i in 0..<n {
            for j in 0..<primes.count {
                uglyNums[i] = min(uglyNums[i], primes[j] * uglyNums[indexs[j]])
            }
            for j in 0..<primes.count {
                while primes[j] * uglyNums[indexs[j]] <= uglyNums[i] { indexs[j] += 1 }
            }
        }
        return uglyNums.last!
    }
}
0%