Skip to content

Commit 10a7420

Browse files
chefyuanchefyuan
authored
Merge pull request chefyuan#34 from zztian1024/main
为数组篇&链表篇&二叉树 增加 Swift 实现
2 parents 81dde48 + 37b2a2a commit 10a7420

36 files changed

+1472
-4
lines changed

‎animation-simulation/二叉树/二叉树中序遍历（Morris）.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -102,3 +102,34 @@ class Solution {
102102
}
103103
```
104104

105+
Swift Code：
106+
107+
```swift
108+
class Solution {
109+
func inorderTraversal(_ root: TreeNode?) -> [Int] {
110+
var list:[Int] = []
111+
guard root != nil else {
112+
return list
113+
}
114+
var p1 = root, p2: TreeNode?
115+
while p1 != nil {
116+
p2 = p1!.left
117+
if p2 != nil {
118+
while p2!.right != nil && p2!.right !== p1 {
119+
p2 = p2!.right
120+
}
121+
if p2!.right == nil {
122+
p2!.right = p1
123+
p1 = p1!.left
124+
continue
125+
} else {
126+
p2!.right = nil
127+
}
128+
}
129+
list.append(p1!.val)
130+
p1 = p1!.right
131+
}
132+
return list
133+
}
134+
}
135+
```

‎animation-simulation/二叉树/二叉树中序遍历（迭代）.md

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -51,5 +51,32 @@ class Solution {
5151
}
5252
```
5353

54+
Swift Code：
55+
56+
```swift
57+
class Solution {
58+
func inorderTraversal(_ root: TreeNode?) -> [Int] {
59+
var arr:[Int] = []
60+
var cur = root
61+
var stack:[TreeNode] = []
62+
63+
while !stack.isEmpty || cur != nil {
64+
//找到当前应该遍历的那个节点
65+
while cur != nil {
66+
stack.append(cur!)
67+
cur = cur!.left
68+
}
69+
//此时指针指向空，也就是没有左子节点，则开始执行出栈操作
70+
if let temp = stack.popLast() {
71+
arr.append(temp.val)
72+
//指向右子节点
73+
cur = temp.right
74+
}
75+
}
76+
return arr
77+
}
78+
}
79+
```
80+
5481
###
5582

‎animation-simulation/二叉树/二叉树基础.md

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -406,6 +406,42 @@ public:
406406
};
407407
```
408408
409+
Swift Code：
410+
411+
```swift
412+
class Solution {
413+
func levelOrder(_ root: TreeNode?) -> [[Int]] {
414+
var res:[[Int]] = []
415+
guard root != nil else {
416+
return res
417+
}
418+
var queue:[TreeNode?] = []
419+
queue.append(root!)
420+
421+
while !queue.isEmpty {
422+
let size = queue.count
423+
var list:[Int] = []
424+
425+
for i in 0..<size {
426+
guard let node = queue.removeFirst() else {
427+
continue
428+
}
429+
if node.left != nil {
430+
queue.append(node.left)
431+
}
432+
if node.right != nil {
433+
queue.append(node.right);
434+
}
435+
list.append(node.val)
436+
}
437+
res.append(list)
438+
}
439+
440+
return res
441+
}
442+
}
443+
```
444+
409445
时间复杂度：O（n） 空间复杂度：O（n）
410446

411447
大家如果吃透了二叉树的层序遍历的话，可以顺手把下面几道题目解决掉，思路一致，甚至都不用拐弯

‎animation-simulation/二叉树/二叉树的前序遍历(Morris).md

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -103,4 +103,41 @@ class Solution {
103103
}
104104
```
105105

106+
Swift Code：
107+
108+
```swift
109+
class Solution {
110+
func preorderTraversal(_ root: TreeNode?) -> [Int] {
111+
var list:[Int] = []
112+
guard root != nil else {
113+
return list
114+
}
115+
var p1 = root, p2: TreeNode?
116+
while p1 != nil {
117+
p2 = p1!.left
118+
if p2 != nil {
119+
//找到左子树的最右叶子节点
120+
while p2!.right != nil && p2!.right !== p1 {
121+
p2 = p2!.right
122+
}
123+
//添加 right 指针，对应 right 指针为 null 的情况
124+
if p2!.right == nil {
125+
list.append(p1!.val)
126+
p2!.right = p1
127+
p1 = p1!.left
128+
continue
129+
}
130+
//对应 right 指针存在的情况，则去掉 right 指针
131+
p2!.right = nil
132+
} else {
133+
list.append(p1!.val)
134+
}
135+
//移动 p1
136+
p1 = p1!.right
137+
}
138+
return list
139+
}
140+
}
141+
```
142+
106143
好啦，今天就看到这里吧，咱们下期见！

‎animation-simulation/二叉树/二叉树的前序遍历(栈).md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,3 +67,32 @@ class Solution {
6767
}
6868
```
6969

70+
Swift Code：
71+
72+
```swift
73+
class Solution {
74+
75+
func preorderTraversal(_ root: TreeNode?) -> [Int] {
76+
var list:[Int] = []
77+
var stack:[TreeNode] = []
78+
79+
guard root != nil else {
80+
return list
81+
}
82+
stack.append(root!)
83+
while !stack.isEmpty {
84+
let temp = stack.popLast()
85+
if let right = temp?.right {
86+
stack.append(right)
87+
}
88+
if let left = temp?.left {
89+
stack.append(left)
90+
}
91+
//这里也可以放到前面
92+
list.append((temp?.val)!)
93+
}
94+
return list
95+
}
96+
}
97+
```
98+

‎animation-simulation/二叉树/二叉树的后续遍历 (迭代).md

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -71,6 +71,39 @@ class Solution {
7171
}
7272
```
7373

74+
Swift Code：
75+
76+
```swift
77+
class Solution {
78+
func postorderTraversal(_ root: TreeNode?) -> [Int] {
79+
var list:[Int] = []
80+
var stack:[TreeNode] = []
81+
var cur = root, preNode: TreeNode?
82+
while !stack.isEmpty || cur != nil {
83+
//和之前写的中序一致
84+
while cur != nil {
85+
stack.append(cur!)
86+
cur = cur!.left
87+
}
88+
//1.出栈，可以想一下，这一步的原因。
89+
cur = stack.popLast()
90+
//2.if 里的判断语句有什么含义？
91+
if cur!.right === nil || cur!.right === preNode {
92+
list.append(cur!.val)
93+
//更新下 preNode，也就是定位住上一个访问节点。
94+
preNode = cur
95+
cur = nil
96+
} else {
97+
//3.再次压入栈，和上面那条 1 的关系？
98+
stack.append(cur!)
99+
cur = cur!.right
100+
}
101+
}
102+
return list
103+
}
104+
}
105+
```
106+
74107
当然也可以修改下代码逻辑将 `cur = stack.pop()` 改成 `cur = stack.peek()`，下面再修改一两行代码也可以实现，这里这样写是方便动画模拟，大家可以随意发挥。
75108

76109
时间复杂度 O（n）, 空间复杂度O（n）

‎animation-simulation/二叉树/二叉树的后续遍历（Morris）.md

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -116,6 +116,62 @@ class Solution {
116116
}
117117
```
118118

119+
Swift Code：
120+
121+
```swift
122+
class Solution {
123+
var list:[Int] = []
124+
func postorderTraversal(_ root: TreeNode?) -> [Int] {
125+
guard root != nil else {
126+
return list
127+
}
128+
var p1 = root, p2: TreeNode?
129+
while p1 != nil {
130+
p2 = p1!.left
131+
if p2 != nil {
132+
while p2!.right != nil && p2!.right !== p1 {
133+
p2 = p2!.right
134+
}
135+
if p2!.right == nil {
136+
p2!.right = p1
137+
p1 = p1!.left
138+
continue
139+
} else {
140+
p2!.right = nil
141+
postMorris(p1!.left)
142+
}
143+
}
144+
p1 = p1!.right
145+
}
146+
//以根节点为起点的链表
147+
postMorris(root!)
148+
return list
149+
}
150+
151+
func postMorris(_ root: TreeNode?) {
152+
let reverseNode = reverseList(root)
153+
//从后往前遍历
154+
var cur = reverseNode
155+
while cur != nil {
156+
list.append(cur!.val)
157+
cur = cur!.right
158+
}
159+
reverseList(reverseNode)
160+
}
161+
162+
func reverseList(_ head: TreeNode?) -> TreeNode? {
163+
var cur = head, pre: TreeNode?
164+
while cur != nil {
165+
let next = cur?.right
166+
cur?.right = pre
167+
pre = cur
168+
cur = next
169+
}
170+
return pre
171+
}
172+
}
173+
```
174+
119175
时间复杂度 O（n）空间复杂度 O（1）
120176

121177
总结：后序遍历比起前序和中序稍微复杂了一些，所以我们解题的时候，需要好好注意一下，迭代法的核心是利用一个指针来定位我们上一个遍历的节点，Morris 的核心是，将某节点的右子节点，看成是一条链表，进行反向遍历。

‎animation-simulation/剑指offer/1的个数.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -200,6 +200,31 @@ class Solution {
200200
}
201201
```
202202

203+
Swift Code:
204+
205+
```swift
206+
class Solution {
207+
func countDigitOne(_ n: Int) -> Int {
208+
var high = n, low = 0, cur = 0, count = 0, num = 1
209+
while high != 0 || cur != 0 {
210+
cur = high % 10
211+
high /= 10
212+
//这里我们可以提出 high * num 因为我们发现无论为几，都含有它
213+
if cur == 0 {
214+
count += high * num
215+
} else if cur == 1 {
216+
count += high * num + 1 + low
217+
} else {
218+
count += (high + 1) * num
219+
}
220+
low = cur * num + low
221+
num *= 10
222+
}
223+
return count
224+
}
225+
}
226+
```
227+
203228
时间复杂度 : O(logn) 空间复杂度 O(1)
204229

205230

‎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+
```

0 commit comments

Comments
 (0)