发表于 | 分类于 |

830. Positions of Large Groups

题目描述

In a string S of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like S = “abbxxxxzyy” has the groups “a”, “bb”, “xxxx”, “z” and “yy”.

Call a group large if it has 3 or more characters. We would like the starting and ending positions of every large group.

The final answer should be in lexicographic order.

Example 1:

1
2
3
Input: "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the single large group with starting  3 and ending positions 6.

Example 2:

1
2
3
Input: "abc"
Output: []
Explanation: We have "a","b" and "c" but no large group.

Example 3:

1
2
Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]

Note: 1 <= S.length <= 1000

题目大意

求字符串内连续重复的字符区间。却连续重复字符数大于等于 3

解题思路

按照题目遍历字符串即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    func largeGroupPositions(_ S: String) -> [[Int]] {
        var last = S.first!
        var count = 0
        var ans = [[Int]]()
        for (i, char) in (S+"#").enumerated() {
            if last == char {
                count += 1
            }else {
                if count >= 3 {
                    ans.append([i-count, i-1])
                }
                last = char
                count = 1
            }
        }
        return ans
    }
}

发表于 | 分类于 |

829. Consecutive Numbers Sum

题目描述

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

1
2
3
Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3

Example 2:

1
2
3
Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4

Example 3:

1
2
3
Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

Note: 1 <= N <= 10 ^ 9.

题目大意

求正整数 N，有多少种方法可以把它写成连续正整数的和？

解题思路

由题目规律可得：
N / c 为 第c / 2 + c % 2个数，所以 N / c >= c / 2 + c % 2
符合下列情况时，存在连续正整数的和为 N。
若 c 为奇数，N 可以整除 c
若 c 为偶数，并且 (N / c) * c + c / 2 == N

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    func consecutiveNumbersSum(_ N: Int) -> Int {
        var ans = 0
        var c = 0
        while true {
            c += 1
            if N / c < c / 2 + c % 2 {
                break
            }
            if c % 2 == 1 && N % c == 0 {
                ans += 1
            }else if c % 2 == 0 && (N / c) * c + c / 2 == N {
                ans += 1
            }
        }
        return ans
    }
}

发表于 | 分类于 |

825. Friends Of Appropriate Ages

题目描述

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.

Person A will NOT friend request person B (B != A) if any of the following conditions are true:

  • age[B] <= 0.5 * age[A] + 7
  • age[B] > age[A]
  • age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.

Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.

How many total friend requests are made?

Example 1:

1
2
3
Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:

1
2
3
Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

1
2
3
Input: [20,30,100,110,120]
Output: 
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

题目大意

A 可以向 B请求是否可以做朋友，满足以下条件的一项，便不可做朋友：

  • age[B] <= 0.5 * age[A] + 7
  • age[B] > age[A]
  • age[B] > 100 && age[A] < 100

Notes:

  • 1 <= ages.length <= 20000.
  • 1 <= ages[i] <= 120.

解题思路

记录每个年龄的人数，记为 ageCount
记录小于等于当前年龄的人数，记为 sumCount
由于题目要求 age[B] <= 0.5 * age[A] + 7，所以需要减去 <= 0.5 * age[A] + 7 的人数。
并且需要减去自身的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    func numFriendRequests(_ ages: [Int]) -> Int {
        var ageCount = Array(repeating: 0, count: 121)
        var sumCount = Array(repeating: 0, count: 121)
        for age in ages { ageCount[age] += 1 }
        for i in 1...120 {
            sumCount[i] = sumCount[i - 1] + ageCount[i]
        }
        var ans = 0
        for i in 15...120 {
            if ageCount[i] == 0 { continue }
            let count = sumCount[i] - sumCount[i / 2 + 7]
            ans += count * ageCount[i] - ageCount[i]
        }
        return ans
    }
}

发表于 | 分类于 |

826. Most Profit Assigning Work

题目描述

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

Example 1:

1
2
3
Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100 
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] seperately.

Notes:

  • 1 <= difficulty.length = profit.length <= 10000
  • 1 <= worker.length <= 10000
  • difficulty[i], profit[i], worker[i] are in range [1, 10^5]

题目大意

difficulty 表示工作的难度，profit 表示对应工作的利润， worker 代表工人所能做的工作难度。
求工人所能带来的最大利润

解题思路

根据难度递减顺序对 difficulty 和 profit 进行排序。
并且对 worker 进行递增排序。
遍历数组，找到当前难度所能获得的最大利润。

代码

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 maxProfitAssignment(_ difficulty: [Int], _ profit: [Int], _ worker: [Int]) -> Int {
        var ans = 0
        var task = [(Int, Int)]()
        for (diff, pro) in zip(difficulty, profit) {
            task.append((diff, pro))
        }
        task.sort{ $0.0 < $1.0 }
        let workers = worker.sorted()
        var i = 0
        var maxPorfit = 0
        for w in workers {
            while i < profit.count && w >= task[i].0 {
                maxPorfit = max(maxPorfit, task[i].1)
                i += 1
            }
            ans += maxPorfit
        }
        
        return ans
    }
}

发表于 | 分类于 |

486. Predict the Winner

题目描述

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:

1
2
3
4
5
6
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return False.

Example 2:

1
2
3
4
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Note:

  • 1 <= length of the array <= 20.
  • Any scores in the given array are non-negative integers and will not exceed 10,000,000.
  • If the scores of both players are equal, then player 1 is still the winner.

题目大意

有两个玩家玩游戏，每一个玩家在数组中第一个数字和最后一个数字选择一个数字，累计最多的则获胜。求第一个玩家是否能够获胜。

解题思路

动态规划

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
     func PredictTheWinner(_ nums: [Int]) -> Bool {
        var dp = Array(repeating: Array(repeating: 0, count: nums.count), count: nums.count)
        for i in 1..<nums.count {
            for j in (0..<i).reversed() {
                dp[j][i] = max(nums[j] - dp[j + 1][i], nums[i] - dp[j][i - 1])
            }
        }
        return dp[0][nums.count - 1] >= 0
    }
}

发表于 | 分类于 |

821. Shortest Distance to a Character

题目描述

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = “loveleetcode”, C = ‘e’
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Note:

  • S string length is in [1, 10000].
  • C is a single character, and guaranteed to be in string S.
  • All letters in S and C are lowercase.

题目大意

给定字符串 S 和字符 C ，求 S 中每个字符距离 C 字符最小距离。

解题思路

正向反向遍历，求最小。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func shortestToChar(_ S: String, _ C: Character) -> [Int] {
        var ans = Array(repeating: S.count, count: S.count)
        var last = -(ans.count * 2 + 1)
        for (i, char) in S.enumerated() {
            if char == C { last = i }
            ans[i] = min(i - last, ans[i])
        }
        last = ans.count * 2 + 1
        for (i, char) in S.enumerated().reversed() {
            if char == C { last = i }
            ans[i] = min(last - i, ans[i])
        }
        return ans
    }
}

发表于 | 分类于 |

811. Subdomain Visit Count

题目描述

A website domain like “discuss.leetcode.com” consists of various subdomains. At the top level, we have “com”, at the next level, we have “leetcode.com”, and at the lowest level, “discuss.leetcode.com”. When we visit a domain like “discuss.leetcode.com”, we will also visit the parent domains “leetcode.com” and “com” implicitly.

Now, call a “count-paired domain” to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be “9001 discuss.leetcode.com”.

We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.

1
2
3
4
5
6
7
Example 1:
Input: 
["9001 discuss.leetcode.com"]
Output: 
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Explanation: 
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.
1
2
3
4
5
6
7
Example 2:
Input: 
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output: 
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
Explanation: 
We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.

Notes:

  • The length of cpdomains will not exceed 100.
  • The length of each domain name will not exceed 100.
  • Each address will have either 1 or 2 “.” characters.
  • The input count in any count-paired domain will not exceed 10000.
  • The answer output can be returned in any order.

题目大意

给定一组网站及其访问的次数，返回网站对应的所有子域名的访问次数。

解题思路

Hash Table

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
     func subdomainVisits(_ cpdomains: [String]) -> [String] {
        var dict = [String: Int]()
        for cpdomain in cpdomains {
            let countPaired = cpdomain.split(separator: " ")
            let count = Int(countPaired[0])!
            let domains = countPaired[1].split(separator: ".")
            var str = ""
            for name in domains.reversed() {
                str = name + str
                dict[str] = (dict[str] ?? 0) + count
                str = "." + str
            }
        }
        var ans = [String]()
        for (k, v) in dict {
            ans.append("\(v) " + k)
        }
        return ans
    }
}

发表于 | 分类于 |

812. Largest Triangle Area

题目描述

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.

Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation:
The five points are show in the figure below. The red triangle is the largest.

Notes:

  • 3 <= points.length <= 50.
  • No points will be duplicated.
  • -50 <= points[i][j] <= 50.
  • Answers within 10^-6 of the true value will be accepted as correct.

题目大意

给定一组坐标，求围成的三角形的最大面积。

解题思路

暴力搜索，最主要是要知道根据 Shoelace formula 求三角形面积。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    func largestTriangleArea(_ points: [[Int]]) -> Double {
        func triangleArea(p1: [Int], p2: [Int], p3: [Int]) -> Double {
            return 0.5 * abs(Double(p1[0] * (p2[1] - p3[1])
                + p2[0] * (p3[1] - p1[1])
                + p3[0] * (p1[1] - p2[1])))
        }
        var ans = 0.0
        for i in 0..<points.count {
            for j in i+1..<points.count {
                for k in j+1..<points.count {
                   ans = max(ans, triangleArea(p1: points[i], p2: points[j], p3: points[k]))
                }
            }
        }
        return ans
    }
}

发表于 | 分类于 |

781. Rabbits in Forest

题目描述

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.
Input: answers = [10, 10, 10]
Output: 11
Input: answers = []
Output: 0

Note:

  • answers will have length at most 1000.
  • Each answers[i] will be an integer in the range [0, 999].

题目大意

每个兔子都有一些颜色， answers 代表兔子告诉你有多少只兔子和自己颜色相同。求总共有多少只兔子。

解题思路

利用字典储存相同颜色兔子的群落，还可以容纳多少只兔子。
若可以容纳兔子大于 0，则群落数 - 1
否则令 ans，重新计算群落数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    func numRabbits(_ answers: [Int]) -> Int {
        var dict = [Int: Int]()
        var ans = 0
        for answer in answers {
            if let v = dict[answer + 1], v > 0 {
                dict[answer + 1] = v - 1
            }else {
                ans += answer + 1
                dict[answer + 1] = answer
            }
        }
        return ans
    }
}

发表于 | 分类于 |

817. Linked List Components

题目描述

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

1
2
3
4
5
6
Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

1
2
3
4
5
6
Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note:

  • If N is the length of the linked list given by head, 1 <= N <= 10000.
  • The value of each node in the linked list will be in the range [0, N - 1].
  • 1 <= G.length <= 10000.
  • G is a subset of all values in the linked list.

题目大意

求链表中的连通分量个数。

解题思路

当 g 中不包含链表中的节点时，则代表一个连通分量。
移除已检索过的节点值，减少 contains 的复杂度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    func numComponents(_ head: ListNode?, _ G: [Int]) -> Int {
        var pre = head
        var g = Set(G)
        var ans = 0
        var flag = false
        while let node = pre {
            if !g.contains(node.val) {
                ans += flag ? 1 : 0
                flag = false
            }else {
                g.remove(node.val)
                flag = true
            }
            pre = pre?.next
        }
        return flag ? ans + 1 : ans
    }
}
0%