Skip to content

Commit 2e52ac8

Browse files
YanunYanun
committed
week 02 作业
1 parent b0dbe7b commit 2e52ac8

File tree

8 files changed

+781
-2
lines changed

8 files changed

+781
-2
lines changed

‎Week 01/id_176/LeetCode_146_176.swift‎

Lines changed: 151 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,151 @@
1+
/*
2+
* @lc app=leetcode.cn id=146 lang=swift
3+
*
4+
* [146] LRU缓存机制
5+
*
6+
* https://leetcode-cn.com/problems/lru-cache/description/
7+
*
8+
* algorithms
9+
* Medium (43.82%)
10+
* Likes: 271
11+
* Dislikes: 0
12+
* Total Accepted: 20.6K
13+
* Total Submissions: 47K
14+
* Testcase Example: '["LRUCache","put","put","get","put","get","put","get","get","get"]\n' +
15+
'[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]'
16+
*
17+
* 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
18+
*
19+
* 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
20+
* 写入数据 put(key, value) -
21+
* 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
22+
*
23+
* 进阶:
24+
*
25+
* 你是否可以在 O(1) 时间复杂度内完成这两种操作？
26+
*
27+
* 示例:
28+
*
29+
* LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
30+
*
31+
* cache.put(1, 1);
32+
* cache.put(2, 2);
33+
* cache.get(1); // 返回 1
34+
* cache.put(3, 3); // 该操作会使得密钥 2 作废
35+
* cache.get(2); // 返回 -1 (未找到)
36+
* cache.put(4, 4); // 该操作会使得密钥 1 作废
37+
* cache.get(1); // 返回 -1 (未找到)
38+
* cache.get(3); // 返回 3
39+
* cache.get(4); // 返回 4
40+
*
41+
*
42+
*/
43+
44+
// @lc code=start
45+
46+
class LRUCache {
47+
48+
class DoublyLinkedList {
49+
50+
class LinkedListNode {
51+
let key: Int
52+
var value: Int
53+
var next: LinkedListNode?
54+
weak var previous: LinkedListNode?
55+
56+
init(key: Int = 0, value: Int = 0) {
57+
self.key = key
58+
self.value = value
59+
}
60+
}
61+
62+
let head = LinkedListNode()
63+
let tail = LinkedListNode()
64+
var size = 0
65+
66+
init() {
67+
head.next = tail
68+
tail.previous = head
69+
}
70+
71+
func addNode(_ node: LinkedListNode) {
72+
73+
node.previous = head
74+
node.next = head.next
75+
76+
head.next?.previous = node
77+
head.next = node
78+
79+
size += 1
80+
}
81+
82+
func removeNode(_ node: LinkedListNode) {
83+
84+
node.next?.previous = node.previous
85+
node.previous?.next = node.next
86+
87+
size -= 1
88+
}
89+
90+
func moveNodeToHead(_ node: LinkedListNode) {
91+
92+
removeNode(node)
93+
addNode(node)
94+
}
95+
96+
func popTail() -> LinkedListNode? {
97+
98+
guard size > 0, let node = tail.previous else {
99+
return nil
100+
}
101+
removeNode(node)
102+
return node
103+
}
104+
}
105+
106+
107+
let capacity: Int
108+
let list = DoublyLinkedList()
109+
var cache = [Int: DoublyLinkedList.LinkedListNode]()
110+
111+
init(_ capacity: Int) {
112+
self.capacity = capacity
113+
}
114+
115+
func get(_ key: Int) -> Int {
116+
117+
guard let node = cache[key] else {
118+
return -1
119+
}
120+
121+
list.moveNodeToHead(node)
122+
return node.value
123+
}
124+
125+
func put(_ key: Int, _ value: Int) {
126+
127+
if let node = cache[key] {
128+
node.value = value
129+
list.moveNodeToHead(node)
130+
} else {
131+
132+
let node = DoublyLinkedList.LinkedListNode(key: key, value: value)
133+
list.addNode(node)
134+
cache[key] = node
135+
136+
if list.size > capacity, let tail = list.popTail() {
137+
cache[tail.key] = nil
138+
}
139+
}
140+
}
141+
142+
}
143+
144+
/**
145+
* Your LRUCache object will be instantiated and called as such:
146+
* let obj = LRUCache(capacity)
147+
* let ret_1: Int = obj.get(key)
148+
* obj.put(key, value)
149+
*/
150+
// @lc code=end
151+

‎Week 02/id_176/LeetCode_144_176.swift‎

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
/*
2+
* @lc app=leetcode.cn id=144 lang=swift
3+
*
4+
* [144] 二叉树的前序遍历
5+
*
6+
* https://leetcode-cn.com/problems/binary-tree-preorder-traversal/description/
7+
*
8+
* algorithms
9+
* Medium (62.09%)
10+
* Likes: 163
11+
* Dislikes: 0
12+
* Total Accepted: 46.6K
13+
* Total Submissions: 74.7K
14+
* Testcase Example: '[1,null,2,3]'
15+
*
16+
* 给定一个二叉树，返回它的 前序 遍历。
17+
*
18+
* 示例:
19+
*
20+
* 输入: [1,null,2,3]
21+
* ⁠ 1
22+
* ⁠ \
23+
* ⁠ 2
24+
* ⁠ /
25+
* ⁠ 3
26+
*
27+
* 输出: [1,2,3]
28+
*
29+
*
30+
* 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
31+
*
32+
*/
33+
34+
// @lc code=start
35+
/**
36+
* Definition for a binary tree node.
37+
* public class TreeNode {
38+
* public var val: Int
39+
* public var left: TreeNode?
40+
* public var right: TreeNode?
41+
* public init(_ val: Int) {
42+
* self.val = val
43+
* self.left = nil
44+
* self.right = nil
45+
* }
46+
* }
47+
*/
48+
class Solution {
49+
50+
// 递归
51+
// func preorderTraversal(_ root: TreeNode?) -> [Int] {
52+
// var result = [Int]()
53+
54+
// func traverse(_ root: TreeNode?) {
55+
// guard let root = root else {
56+
// return
57+
// }
58+
// result.append(root.val)
59+
// traverse(root.left)
60+
// traverse(root.right)
61+
// }
62+
63+
// traverse(root)
64+
65+
// return result
66+
// }
67+
68+
// 迭代法
69+
// func preorderTraversal(_ root: TreeNode?) -> [Int] {
70+
// var result = [Int]()
71+
72+
// var stack = [TreeNode]()
73+
// var curr = root
74+
75+
// while curr != nil || !stack.isEmpty {
76+
// while curr != nil {
77+
// result.append(curr!.val)
78+
// // if let right = curr!.right {
79+
// // stack.append(right)
80+
// // }
81+
// stack.append(curr!)
82+
// curr = curr!.left
83+
// }
84+
// // curr = stack.popLast()
85+
// curr = stack.popLast()?.right
86+
// }
87+
88+
// return result
89+
// }
90+
91+
// 迭代法
92+
func preorderTraversal(_ root: TreeNode?) -> [Int] {
93+
var result = [Int]()
94+
95+
guard let root = root else {
96+
return result
97+
}
98+
99+
var stack = [root]
100+
101+
while !stack.isEmpty {
102+
let curr = stack.popLast()!
103+
result.append(curr.val)
104+
105+
if let right = curr.right {
106+
stack.append(right)
107+
}
108+
109+
if let left = curr.left {
110+
stack.append(left)
111+
}
112+
}
113+
114+
return result
115+
}
116+
}
117+
// @lc code=end
118+

‎Week 02/id_176/LeetCode_145_176.swift‎

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
/*
2+
* @lc app=leetcode.cn id=145 lang=swift
3+
*
4+
* [145] 二叉树的后序遍历
5+
*
6+
* https://leetcode-cn.com/problems/binary-tree-postorder-traversal/description/
7+
*
8+
* algorithms
9+
* Hard (68.21%)
10+
* Likes: 175
11+
* Dislikes: 0
12+
* Total Accepted: 34.3K
13+
* Total Submissions: 50.2K
14+
* Testcase Example: '[1,null,2,3]'
15+
*
16+
* 给定一个二叉树，返回它的 后序 遍历。
17+
*
18+
* 示例:
19+
*
20+
* 输入: [1,null,2,3]
21+
* ⁠ 1
22+
* ⁠ \
23+
* ⁠ 2
24+
* ⁠ /
25+
* ⁠ 3
26+
*
27+
* 输出: [3,2,1]
28+
*
29+
* 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
30+
*
31+
*/
32+
33+
// @lc code=start
34+
/**
35+
* Definition for a binary tree node.
36+
* public class TreeNode {
37+
* public var val: Int
38+
* public var left: TreeNode?
39+
* public var right: TreeNode?
40+
* public init(_ val: Int) {
41+
* self.val = val
42+
* self.left = nil
43+
* self.right = nil
44+
* }
45+
* }
46+
*/
47+
class Solution {
48+
49+
// 递归法 1
50+
// func postorderTraversal(_ root: TreeNode?) -> [Int] {
51+
// var result = [Int]()
52+
53+
// func traverse(_ root: TreeNode?) {
54+
// guard let root = root else {
55+
// return
56+
// }
57+
// traverse(root.left)
58+
// traverse(root.right)
59+
// result.append(root.val)
60+
// }
61+
62+
// traverse(root)
63+
64+
// return result
65+
// }
66+
67+
// 递归法 2
68+
// func postorderTraversal(_ root: TreeNode?) -> [Int] {
69+
70+
// guard let root = root else {
71+
// return []
72+
// }
73+
74+
// return postorderTraversal(root.left) + postorderTraversal(root!.right) + [root.val]
75+
// }
76+
77+
// 迭代法 1
78+
// func postorderTraversal(_ root: TreeNode?) -> [Int] {
79+
// var result = [Int]()
80+
81+
// var stack = [TreeNode]()
82+
// var curr = root
83+
84+
// while curr != nil || !stack.isEmpty {
85+
// if curr != nil {
86+
// result.insert(curr!.val, at: 0)
87+
// stack.append(curr!)
88+
// curr = curr!.right
89+
// } else {
90+
// curr = stack.popLast()?.left
91+
// }
92+
93+
// }
94+
95+
// return result
96+
// }
97+
98+
// 迭代法 2
99+
func postorderTraversal(_ root: TreeNode?) -> [Int] {
100+
var result = [Int]()
101+
102+
guard let root = root else {
103+
return result
104+
}
105+
106+
var stack = [root]
107+
108+
while !stack.isEmpty {
109+
let curr = stack.popLast()!
110+
result.insert(curr.val, at: 0)
111+
112+
if let left = curr.left {
113+
stack.append(left)
114+
}
115+
116+
if let right = curr.right {
117+
stack.append(right)
118+
}
119+
}
120+
121+
return result
122+
}
123+
}
124+
// @lc code=end
125+

0 commit comments

Comments
 (0)