- 力扣的算法题：1154
给你一个字符串 date ，按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。返回该日期是当年的第几天。
示例 1：
输入：date = “2019-01-09”
输出：9
解释：给定日期是2019年的第九天。
示例 2：
输入：date = “2019-02-10”
输出：41
class Solution {
func dayOfYear(_ date: String) -> Int {
let dateArray = date.split(separator: "-")
if dateArray.count < 3 {
return 0
}
var dayCount = 0
let year = (dateArray[0] as NSString).intValue
let month = (dateArray[1] as NSString).intValue
let day = (dateArray[2] as NSString).intValue
let thirtyOneDayArray:[Int] = [1,3,5,7,8,10,12]
let thirtyDayArray:[Int] = [4,6,9,11]
for index in thirtyOneDayArray {
if index < month {
dayCount += 31
} else {
break
}
}
if month > 2 {
if (year % 400 == 0) || (year % 4 == 0) && (year % 100 != 0) {
dayCount += 29
} else {
dayCount += 28
}
}
for index in thirtyDayArray {
if index < month {
dayCount += 30
} else {
break
}
}
dayCount += Int(day);
return dayCount;
}
}
- 力扣的：125
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。字母和数字都属于字母数字字符。给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
输入: s = “A man, a plan, a canal: Panama”
输出：true
解释：“amanaplanacanalpanama” 是回文串。
示例 2：
输入：s = “race a car”
输出：false
解释：“raceacar” 不是回文串。
示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串。
func isPalindrome(_ s: String) -> Bool {
if s.count == 0 {
return true
}
var left = 0
var right = s.count-1
//! 字符串小写，并转化为数组
let array = Array(s.lowercased())
while left <= right {
if !array[left].isLetter && !array[left].isNumber {
left+=1
continue
}
if !array[right].isLetter && !array[right].isNumber {
right-=1
continue
}
if array[left] == array[right] {
left+=1
right-=1
} else {
return false
}
}
return true
}
-
- 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
示例 2：
输入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]
func reverseString(_ s: inout [Character]) {
var left = 0;
var right = s.count-1
while left <= right {
let leftI = s[left]
let rightI = s[right]
let temp = s[right]
s[right] = s[left]
s[left] = temp
left = left + 1
right = right - 1
}
print(s)
}
-
- 有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
func isValid(_ s: String) -> Bool {
guard s.count % 2 == 0 else {
return false
}
// 存放对应关系
let mapDic:[Character:Character] = [
"(":")",
"{":"}",
"[":"]"]
var stack = [Character]()
for char in s {
if mapDic[char] != nil {
stack.append(char)
} else {
if stack.isEmpty {
return false
} else if mapDic[stack.last!] != char {
return false
} else {
stack.removeLast()
}
}
}
return stack.isEmpty
}
-
- 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
示例 1：
输入：s = “abc”, t = “ahbgdc”
输出：true
示例 2：
输入：s = “axc”, t = “ahbgdc”
输出：false
class Solution {
func isSubsequence(_ s: String, _ t: String) -> Bool {
var allString = t
var queue = Array(s);
while !queue.isEmpty {
let char = queue.removeFirst()
if let index = allString.firstIndex(of: char) {
allString = allString.substring(from: allString.index(index, offsetBy: 1))
} else {
return false
}
}
return queue.isEmpty
}
}
-
- 最长回文串
给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
在构造过程中，请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。
示例 1:
输入:s = “abccccdd”
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
示例 2:
输入:s = “a”
输出:1
示例 3：
输入:s = “aaaaaccc”
输出:7
func longestPalindrome(_ s: String) -> Int {
let sArray = Array(s)
var charDic:[Character : Int] = [:]
for char in sArray {
if var count = charDic[char] {
count = count + 1
charDic.updateValue(count, forKey: char)
} else {
charDic[char] = 1
}
}
var maxCount = 0
var hasJiShuCount = false
for (_, value) in charDic {
if value % 2 == 0 {
maxCount = maxCount + value
} else {
maxCount = maxCount + value - 1
hasJiShuCount = true
}
}
if hasJiShuCount {
maxCount = maxCount + 1
}
return maxCount
}
-
- 亲密字符串
给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。
交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。
例如，在 “abcd” 中交换下标 0 和下标 2 的元素可以生成 “cbad” 。
示例 1：
输入：s = “ab”, goal = “ba”
输出：true
解释：你可以交换 s[0] = ‘a’ 和 s[1] = ‘b’ 生成 “ba”，此时 s 和 goal 相等。
示例 2：
输入：s = “ab”, goal = “ab”
输出：false
解释：你只能交换 s[0] = ‘a’ 和 s[1] = ‘b’ 生成 “ba”，此时 s 和 goal 不相等。
示例 3：
输入：s = “aa”, goal = “aa”
输出：true
解释：你可以交换 s[0] = ‘a’ 和 s[1] = ‘a’ 生成 “aa”，此时 s 和 goal 相等。
func buddyStrings(_ s: String, _ goal: String) -> Bool {
if s.count != goal.count {
return false
}
if s == goal, Set(s).count < s.count {
return true
}
let goalArray = Array(goal)
var sArray = Array(s)
let count = sArray.count - 1
var lastNoSameIndex = 0
var hasFirstNoSameIndex = true
for i in 0...count {
if goalArray[i] != sArray[i] {
if hasFirstNoSameIndex {
lastNoSameIndex = i
hasFirstNoSameIndex = false
} else {
sArray.swapAt(lastNoSameIndex, i)
if sArray == goalArray {
return true
} else {
return false
}
}
}
}
return false
}
-
- 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
示例 2：
输入：strs = [“dog”,“racecar”,“car”]
输出：“”
解释：输入不存在公共前缀。
class Solution {
func longestCommonPrefix(_ strs: [String]) -> String {
if strs.count == 1 {
return strs.first!
}
let firstString = strs.first!
let firstArray = Array(firstString)
var prefixString = ""
for char in firstArray {
var hasPre = true
prefixString = prefixString.appending(String(char))
for string in strs {
if !string.hasPrefix(String(prefixString)) {
hasPre = false
}
}
if !hasPre {
prefixString.removeLast()
}
}
return prefixString
}
}
-
- 重新格式化电话号码
给你一个字符串形式的电话号码 number 。number 由数字、空格 ’ '、和破折号 ‘-’ 组成。
请你按下述方式重新格式化电话号码。
首先，删除 所有的空格和破折号。
其次，将数组从左到右 每 3 个一组 分块，直到 剩下 4 个或更少数字。剩下的数字将按下述规定再分块：
2 个数字：单个含 2 个数字的块。
3 个数字：单个含 3 个数字的块。
4 个数字：两个分别含 2 个数字的块。
最后用破折号将这些块连接起来。注意，重新格式化过程中 不应该 生成仅含 1 个数字的块，并且 最多 生成两个含 2 个数字的块。
返回格式化后的电话号码。
示例 1：
输入：number = “1-23-45 6”
输出：“123-456”
解释：数字是 “123456”
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 “123” 。
步骤 2：剩下 3 个数字，将它们放入单个含 3 个数字的块。第 2 个块是 “456” 。
连接这些块后得到 “123-456” 。
示例 2：
输入：number = “123 4-567”
输出：“123-45-67”
解释：数字是 “1234567”.
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 “123” 。
步骤 2：剩下 4 个数字，所以将它们分成两个含 2 个数字的块。这 2 块分别是 “45” 和 “67” 。
连接这些块后得到 “123-45-67” 。
示例 3：
输入：number = “123 4-5678”
输出：“123-456-78”
解释：数字是 “12345678” 。
步骤 1：第 1 个块 “123” 。
步骤 2：第 2 个块 “456” 。
步骤 3：剩下 2 个数字，将它们放入单个含 2 个数字的块。第 3 个块是 “78” 。
连接这些块后得到 “123-456-78” 。
class Solution {
func reformatNumber(_ number: String) -> String {
var newNumber:String = ""
for char in number {
if char.isNumber {
newNumber.append(char)
}
}
var count = newNumber.count;
var offset = 0
while count > 4 {
offset = offset + 3
newNumber.insert("-", at: newNumber.index(newNumber.startIndex, offsetBy: offset))
// 因为插入了一个 “- ”符号，所以要加1
offset = offset + 1
count = count - 3
}
if (count == 4) {
offset += 2;
newNumber.insert("-", at: newNumber.index(newNumber.startIndex, offsetBy: offset));
}
return newNumber
}
}
-
- 学生出勤记录 I
给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
‘A’：Absent，缺勤
‘L’：Late，迟到
‘P’：Present，到场
如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
按 总出勤 计，学生缺勤（‘A’）严格 少于两天。
学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（‘L’）记录。
如果学生可以获得出勤奖励，返回 true ；否则，返回 false 。
示例 1：
输入：s = “PPALLP”
输出：true
解释：学生缺勤次数少于 2 次，且不存在 3 天或以上的连续迟到记录。
示例 2：
输入：s = “PPALLL”
输出：false
解释：学生最后三天连续迟到，所以不满足出勤奖励的条件。
class Solution {
func checkRecord(_ s: String) -> Bool {
var countA = 0
var countL = 0
var lastChar = ""
for char in s {
if char == "A" {
lastChar = ""
countL = 0
countA += 1
if countA > 1 {
return false
}
} else if char == "L" {
countL += 1
if lastChar.isEmpty {
lastChar = String(char)
} else {
if countL >= 3 {
return false
}
}
} else {
lastChar = ""
countL = 0
}
}
return countL < 3
}
}
-
- 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dict:[Int:Int] = [:]
for i in 0...(nums.count-1) {
let other = target - nums[i]
if (dict[other] != nil) {
return [dict[other]!, i]
} else {
dict[nums[i]] = i
}
}
return []
}
}
643. 子数组最大平均数 I
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
示例 1：
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
示例 2：
输入：nums = [5], k = 1
输出：5.00000
class Solution {
func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
var sum = 0
var maxSum = 0
for i in 0..<nums.count {
if i < k {
sum = sum + nums[i]
maxSum = sum
} else {
sum = sum + nums[i] - nums[i-k]
maxSum = max(sum, maxSum)
}
}
return Double(maxSum) / Double(k)
}
}
463. 岛屿的周长
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 1：
输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边
示例 2：
输入：grid = [[1]]
输出：4
示例 3：
输入：grid = [[1,0]]
输出：4
class Solution {
func islandPerimeter(_ grid: [[Int]]) -> Int {
guard grid.count > 0 else {
return 0
}
let length = grid[0].count
let count = grid.count
var newGird = [[Int]]()
newGird.append([Int](repeating: 0, count: length + 2))
for i in 0..<count {
var temp = grid[i]
temp.insert(0, at: 0)
temp.insert(0, at: length + 1)
newGird.append(temp)
}
newGird.append([Int](repeating: 0, count: length + 2))
var landLength = 0
for i in 1..<newGird.count {
let lineBefore = newGird[i-1]
let lineCurrent = newGird[i]
for j in 1..<lineCurrent.count {
if lineBefore[j] != lineCurrent[j] {
landLength += 1
}
if lineCurrent[j] != lineCurrent[j-1] {
landLength += 1
}
}
}
return landLength
}
}
234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
class Solution {
func isPalindrome(_ head: ListNode?) -> Bool {
if head == nil {
return false
}
var nodeArray:[Int] = [Int]()
var temp = head
while temp != nil {
let next = temp?.val
nodeArray.append(next ?? 0)
temp = temp?.next
}
var leftI = 0
var rightI = nodeArray.count - 1
while leftI <= rightI {
if nodeArray[leftI] == nodeArray[rightI] {
leftI += 1
rightI -= 1
} else {
return false
}
}
return true
}
}
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
/**
* 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 hasCycle(_ head: ListNode?) -> Bool {
var oneNode = head?.next;
var twoNode = head?.next?.next;
while oneNode != nil && twoNode != nil {
if oneNode === twoNode {
return true
} else {
oneNode = oneNode?.next
twoNode = twoNode?.next?.next
}
}
return false
}
}
468. 验证IP地址
给定一个字符串 queryIP。如果是有效的 IPv4 地址，返回 “IPv4” ；如果是有效的 IPv6 地址，返回 “IPv6” ；如果不是上述类型的 IP 地址，返回 “Neither” 。
有效的IPv4地址 是 “x1.x2.x3.x4” 形式的IP地址。 其中 0 <= xi <= 255 且 xi 不能包含 前导零。例如: “192.168.1.1” 、 “192.168.1.0” 为有效IPv4地址， “192.168.01.1” 为无效IPv4地址; “192.168.1.00” 、 “192.168@1.1” 为无效IPv4地址。
一个有效的IPv6地址 是一个格式为“x1:x2:x3:x4:x5:x6:x7:x8” 的IP地址，其中:
1 <= xi.length <= 4
xi 是一个 十六进制字符串 ，可以包含数字、小写英文字母( ‘a’ 到 ‘f’ )和大写英文字母( ‘A’ 到 ‘F’ )。
在 xi 中允许前导零。
例如 “2001:0db8:85a3:0000:0000:8a2e:0370:7334” 和 “2001:db8:85a3:0:0:8A2E:0370:7334” 是有效的 IPv6 地址，而 “2001:0db8:85a3::8A2E:037j:7334” 和 “02001:0db8:85a3:0000:0000:8a2e:0370:7334” 是无效的 IPv6 地址。
示例 1：
输入：queryIP = “172.16.254.1”
输出：“IPv4”
解释：有效的 IPv4 地址，返回 “IPv4”
示例 2：
输入：queryIP = “2001:0db8:85a3:0:0:8A2E:0370:7334”
输出：“IPv6”
解释：有效的 IPv6 地址，返回 “IPv6”
示例 3：
输入：queryIP = “256.256.256.256”
输出：“Neither”
解释：既不是 IPv4 地址，又不是 IPv6 地址
class Solution {
func validIPAddress(_ queryIP: String) -> String {
var ipArray = queryIP.split(separator: ".", omittingEmptySubsequences: false)
if ipArray.count == 4 {
for item in ipArray {
if Int(item) == nil {
return "Neither"
}
if Int(item)! > 255 {
return "Neither"
}
if item.count > 3 {
return "Neither"
}
if item.count > 1 {
if item.hasPrefix("0"){
return "Neither"
}
}
}
return "IPv4"
}
ipArray = queryIP.split(separator: ":", omittingEmptySubsequences: false)
if ipArray.count == 8 {
for item in ipArray {
if item.count > 4 || item.count == 0 {
return "Neither"
}
for char in item where !("0" ... "9").contains(char) && !("a" ... "f").contains(char) && !("A" ... "F").contains(char) {
return "Neither"
}
}
return "IPv6"
}
return "Neither"
}
}
151. 反转字符串中的单词
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = “the sky is blue”
输出：“blue is sky the”
示例 2：
输入：s = " hello world "
输出：“world hello”
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = “a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
class Solution {
func reverseWords(_ s: String) -> String {
let sArr = s.split(separator: " ").reversed()
return sArr.joined(separator: " ")
}
}
686. 重复叠加字符串匹配
给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
注意：字符串 “abc” 重复叠加 0 次是 “”，重复叠加 1 次是 “abc”，重复叠加 2 次是 “abcabc”。
示例 1：
输入：a = “abcd”, b = “cdabcdab”
输出：3
解释：a 重复叠加三遍后为 “abcdabcdabcd”, 此时 b 是其子串。
示例 2：
输入：a = “a”, b = “aa”
输出：2
示例 3：
输入：a = “a”, b = “a”
输出：1
示例 4：
输入：a = “abc”, b = “wxyz”
输出：-1
class Solution {
func repeatedStringMatch(_ a: String, _ b: String) -> Int {
if b.isEmpty {
return 0
}
var newString = a
var count = 1
while newString.count < b.count {
newString += a
count += 1
}
for _ in 0...1 {
if newString.contains(b) {
return count
}
newString += a
count += 1
}
return -1
}
}
1764. 通过连接另一个数组的子数组得到一个数组
给你一个长度为 n 的二维整数数组 groups ，同时给你一个整数数组 nums 。
你是否可以从 nums 中选出 n 个 不相交 的子数组，使得第 i 个子数组与 groups[i] （下标从 0 开始）完全相同，且如果 i > 0 ，那么第 (i-1) 个子数组在 nums 中出现的位置在第 i 个子数组前面。（也就是说，这些子数组在 nums 中出现的顺序需要与 groups 顺序相同）
如果你可以找出这样的 n 个子数组，请你返回 true ，否则返回 false 。
如果不存在下标为 k 的元素 nums[k] 属于不止一个子数组，就称这些子数组是 不相交 的。子数组指的是原数组中连续元素组成的一个序列。
示例 1：
输入：groups = [[1,-1,-1],[3,-2,0]], nums = [1,-1,0,1,-1,-1,3,-2,0]
输出：true
解释：你可以分别在 nums 中选出第 0 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 和第 1 个子数组 [1,-1,0,1,-1,-1,3,-2,0] 。
这两个子数组是不相交的，因为它们没有任何共同的元素。
示例 2：
输入：groups = [[10,-2],[1,2,3,4]], nums = [1,2,3,4,10,-2]
输出：false
解释：选择子数组 [1,2,3,4,10,-2] 和 [1,2,3,4,10,-2] 是不正确的，因为它们出现的顺序与 groups 中顺序不同。
[10,-2] 必须出现在 [1,2,3,4] 之前。
示例 3：
输入：groups = [[1,2,3],[3,4]], nums = [7,7,1,2,3,4,7,7]
输出：false
解释：选择子数组 [7,7,1,2,3,4,7,7] 和 [7,7,1,2,3,4,7,7] 是不正确的，因为它们不是不相交子数组。
它们有一个共同的元素 nums[4] （下标从 0 开始）。
class Solution {
func canChoose(_ groups: [[Int]], _ nums: [Int]) -> Bool {
var index = 0
var longNumsCount = nums.count - 1
for groupIndex in 0..<groups.count {
let group = groups[groupIndex]
let firstNum = group.first!
if index > longNumsCount {
return false
}
for i in index...longNumsCount {
let temp = nums[i]
if temp == firstNum {
if i + group.count - 1 <= longNumsCount {
var arr:[Int] = [Int]()
let length = i + group.count
for j in i..<length {
arr.append(nums[j])
}
if arr != group {
index += 1
} else {
index = length
break
}
} else {
return false
}
} else {
if i == longNumsCount {
return false
}
}
}
}
return true
}
}
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution {
func merge(_ intervals: [[Int]]) -> [[Int]] {
var sortedIntevals = intervals.sorted{
return $0[0]<$1[0]
}
var lastArr:[Int] = [Int]()
var newArr:[[Int]] = [[Int]]()
for index in 0..<sortedIntevals.count {
let indexArr = sortedIntevals[index]
if index == 0 {
lastArr = indexArr
newArr.append(lastArr)
} else {
let lastNum = lastArr.last!
let nextFistNum = indexArr.first!
if lastNum >= nextFistNum {
let firstNum = min(lastArr.first!, indexArr.first!)
let lastNum = max(lastNum, indexArr.last!)
let mergeArr = [firstNum, lastNum]
newArr.removeLast()
newArr.append(mergeArr)
lastArr = mergeArr
} else {
newArr.append(indexArr)
lastArr = indexArr
}
}
}
return newArr
}
}
229. 多数元素 II
给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
示例 1：
输入：nums = [3,2,3]
输出：[3]
示例 2：
输入：nums = [1]
输出：[1]
示例 3：
输入：nums = [1,2]
输出：[1,2]
class Solution {
func majorityElement(_ nums: [Int]) -> [Int] {
var repeatDic:[Int:Int] = [:]
for num in nums {
repeatDic[num] = (repeatDic[num] ?? 0) + 1
}
let repeatCount = Double(nums.count) / 3.0
var repeatArr:[Int] = [Int]()
for (key, value) in repeatDic {
if Double(value) > repeatCount {
repeatArr.append(key)
}
}
return repeatArr
}
}
347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
class Solution {
func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
var repeatDic:[Int:Int] = [:]
for num in nums {
repeatDic[num] = (repeatDic[num] ?? 0) + 1
}
var valueSortedArr = repeatDic.values.sorted { a, b in
return a > b
}
var minValue = 0
for i in 0..<valueSortedArr.count {
if i < k {
minValue = valueSortedArr[i]
}
}
var keyArr:[Int] = [Int]()
for (key, value) in repeatDic {
if value >= minValue {
keyArr.append(key)
}
}
return keyArr
}
}
