Skip to content

Commit c14c229

Browse files
author
zhenzi
committed
为数组篇 增加 Swift 实现
1 parent 2c4afff commit c14c229

14 files changed

+702
-1
lines changed

‎animation-simulation/数组篇/leetcode1052爱生气的书店老板.md

Lines changed: 41 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -114,5 +114,45 @@ class Solution:
114114
ans = max(ans, t)
115115
return ans
116116
```
117-
118117

118+
Swift Code
119+
120+
```swift
121+
class Solution {
122+
func maxSatisfied(_ customers: [Int], _ grumpy: [Int], _ minutes: Int) -> Int {
123+
let len = customers.count
124+
var winSum = 0, rightSum = 0, leftSum = 0
125+
// 右区间的值
126+
for i in minutes..<len {
127+
if grumpy[i] == 0 {
128+
rightSum += customers[i]
129+
}
130+
}
131+
// 窗口的值
132+
for i in 0..<minutes {
133+
winSum += customers[i]
134+
}
135+
var maxCustomer = winSum + leftSum + rightSum
136+
// 窗口左边缘
137+
var left = 1, right = minutes
138+
while right < len {
139+
// 重新计算左区间的值，也可以用 customer 值和 grumpy 值相乘获得
140+
if grumpy[left - 1] == 0 {
141+
leftSum += customers[left - 1]
142+
}
143+
// 重新计算右区间值
144+
if grumpy[right] == 0 {
145+
rightSum -= customers[right]
146+
}
147+
// 窗口值
148+
winSum = winSum - customers[left - 1] + customers[right]
149+
maxCustomer = max(maxCustomer, winSum + leftSum + rightSum) // 保留最大值
150+
// 移动窗口
151+
left += 1
152+
right += 1
153+
}
154+
155+
return maxCustomer
156+
}
157+
}
158+
```

‎animation-simulation/数组篇/leetcode1438绝对值不超过限制的最长子数组.md

Lines changed: 149 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -111,3 +111,152 @@ class Solution:
111111
return maxwin
112112
```
113113

114+
Swift Code
115+
116+
Swift：数组模拟，超时（58 / 61 个通过测试用例）
117+
```swift
118+
class Solution {
119+
func longestSubarray(_ nums: [Int], _ limit: Int) -> Int {
120+
var maxQueue:[Int] = []
121+
var minQueue:[Int] = []
122+
let len = nums.count
123+
var right = 0, left = 0, maxWin = 0
124+
while right < len {
125+
while !maxQueue.isEmpty && (maxQueue.last! < nums[right]) {
126+
maxQueue.removeLast()
127+
}
128+
while !minQueue.isEmpty && (minQueue.last! > nums[right]) {
129+
minQueue.removeLast()
130+
}
131+
maxQueue.append(nums[right])
132+
minQueue.append(nums[right])
133+
while (maxQueue.first! - minQueue.first!) > limit {
134+
if maxQueue.first! == nums[left] {
135+
maxQueue.removeFirst()
136+
}
137+
if minQueue.first! == nums[left] {
138+
minQueue.removeFirst()
139+
}
140+
left += 1
141+
}
142+
maxWin = max(maxWin, right - left + 1)
143+
right += 1
144+
}
145+
return maxWin
146+
}
147+
}
148+
```
149+
150+
Swift：使用双端队列（击败了100.00%）
151+
152+
```swift
153+
class Solution {
154+
func longestSubarray(_ nums: [Int], _ limit: Int) -> Int {
155+
var maxQueue = Deque<Int>.init()
156+
var minQueue = Deque<Int>.init()
157+
let len = nums.count
158+
var right = 0, left = 0, maxWin = 0
159+
while right < len {
160+
while !maxQueue.isEmpty && (maxQueue.peekBack()! < nums[right]) {
161+
maxQueue.dequeueBack()
162+
}
163+
while !minQueue.isEmpty && (minQueue.peekBack()! > nums[right]) {
164+
minQueue.dequeueBack()
165+
}
166+
maxQueue.enqueue(nums[right])
167+
minQueue.enqueue(nums[right])
168+
while (maxQueue.peekFront()! - minQueue.peekFront()!) > limit {
169+
if maxQueue.peekFront()! == nums[left] {
170+
maxQueue.dequeue()
171+
}
172+
if minQueue.peekFront()! == nums[left] {
173+
minQueue.dequeue()
174+
}
175+
left += 1
176+
}
177+
maxWin = max(maxWin, right - left + 1)
178+
right += 1
179+
}
180+
return maxWin
181+
}
182+
183+
// 双端队列数据结构
184+
public struct Deque<T> {
185+
private var array: [T?]
186+
private var head: Int
187+
private var capacity: Int
188+
private let originalCapacity: Int
189+
190+
public init(_ capacity: Int = 10) {
191+
self.capacity = max(capacity, 1)
192+
originalCapacity = self.capacity
193+
array = [T?](repeating: nil, count: capacity)
194+
head = capacity
195+
}
196+
197+
public var isEmpty: Bool {
198+
return count == 0
199+
}
200+
201+
public var count: Int {
202+
return array.count - head
203+
}
204+
205+
public mutating func enqueue(_ element: T) {
206+
array.append(element)
207+
}
208+
209+
public mutating func enqueueFront(_ element: T) {
210+
if head == 0 {
211+
capacity *= 2
212+
let emptySpace = [T?](repeating: nil, count: capacity)
213+
array.insert(contentsOf: emptySpace, at: 0)
214+
head = capacity
215+
}
216+
217+
head -= 1
218+
array[head] = element
219+
}
220+
221+
public mutating func dequeue() -> T? {
222+
guard head < array.count, let element = array[head] else { return nil }
223+
224+
array[head] = nil
225+
head += 1
226+
227+
if capacity >= originalCapacity && head >= capacity*2 {
228+
let amountToRemove = capacity + capacity/2
229+
array.removeFirst(amountToRemove)
230+
head -= amountToRemove
231+
capacity /= 2
232+
}
233+
return element
234+
}
235+
236+
public mutating func dequeueBack() -> T? {
237+
if isEmpty {
238+
return nil
239+
} else {
240+
return array.removeLast()
241+
}
242+
}
243+
244+
public func peekFront() -> T? {
245+
if isEmpty {
246+
return nil
247+
} else {
248+
return array[head]
249+
}
250+
}
251+
252+
public func peekBack() -> T? {
253+
if isEmpty {
254+
return nil
255+
} else {
256+
return array.last!
257+
}
258+
}
259+
}
260+
}
261+
```
262+

‎animation-simulation/数组篇/leetcode1两数之和.md

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -76,6 +76,32 @@ class Solution:
7676
return rearr
7777
```
7878

79+
Swift Code:
80+
81+
```swift
82+
class Solution {
83+
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
84+
let count = nums.count
85+
if count < 2 {
86+
return [0]
87+
}
88+
89+
var rearr: [Int] = []
90+
// 查询元素
91+
for i in 0..<count {
92+
for j in i+1..<count {
93+
// 发现符合条件情况
94+
if nums[i] + nums[j] == target {
95+
rearr.append(i)
96+
rearr.append(j)
97+
}
98+
}
99+
}
100+
return rearr
101+
}
102+
}
103+
```
104+
79105
**哈希表**
80106

81107
**解析**
@@ -159,3 +185,20 @@ class Solution:
159185
return [0]
160186
```
161187

188+
Swift Code:
189+
190+
```swift
191+
class Solution {
192+
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
193+
var m:[Int:Int] = [:]
194+
for i in 0..<nums.count {
195+
let n = nums[i]
196+
if let k = m[target - n] { // 如果存在则返回
197+
return [k, i]
198+
}
199+
m[n] = i // 不存在则存入
200+
}
201+
return [0]
202+
}
203+
}
204+
```

‎animation-simulation/数组篇/leetcode219数组中重复元素2.md

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -78,6 +78,32 @@ class Solution:
7878
return False
7979
```
8080

81+
Swift Code
82+
83+
```swift
84+
class Solution {
85+
func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
86+
if nums.count == 0 {
87+
return false
88+
}
89+
var dict:[Int:Int] = [:]
90+
for i in 0..<nums.count {
91+
// 如果含有
92+
if let v = dict[nums[i]] {
93+
// 判断是否小于K，如果小于等于则直接返回
94+
let abs = abs(i - v)
95+
if abs <= k {
96+
return true
97+
}
98+
}
99+
// 更新索引，此时有两种情况，不存在，或者存在时，将后出现的索引保存
100+
dict[nums[i]] = i
101+
}
102+
return false
103+
}
104+
}
105+
```
106+
81107
**HashSet**
82108

83109
**解析**
@@ -140,3 +166,28 @@ class Solution:
140166
s.remove(nums[i - k])
141167
return False
142168
```
169+
170+
Swift Code
171+
172+
```swift
173+
class Solution {
174+
func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
175+
if nums.count == 0 {
176+
return false
177+
}
178+
var set:Set<Int> = []
179+
for i in 0..<nums.count {
180+
// 含有该元素，返回true
181+
if set.contains(nums[i]) {
182+
return true
183+
}
184+
// 添加新元素
185+
set.insert(nums[i])
186+
if set.count > k {
187+
set.remove(nums[i - k])
188+
}
189+
}
190+
return false
191+
}
192+
}
193+
```

‎animation-simulation/数组篇/leetcode27移除元素.md

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -164,3 +164,23 @@ public:
164164
};
165165
```
166166
167+
Swift Code
168+
169+
```swift
170+
class Solution {
171+
func removeElement(_ nums: inout [Int], _ val: Int) -> Int {
172+
if nums.count == 0 {
173+
return 0
174+
}
175+
var i = 0
176+
for j in 0..<nums.count {
177+
if nums[j] != val {
178+
nums[i] = nums[j]
179+
i += 1
180+
}
181+
182+
}
183+
return i
184+
}
185+
}
186+
```

0 commit comments

Comments
 (0)