Skip to content

Commit e2ca1b3

Browse files
author
haoyang.shi
committed
add
1 parent 25ded0d commit e2ca1b3

37 files changed

Lines changed: 2091 additions & 0 deletions

‎SUMMARY.md‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -190,3 +190,38 @@
190190
- [二叉搜索树的第K大节点](offer/BSTKthNode.md)
191191
- [滑动窗口的最大值](offer/MaxInWindows.md)
192192
- [股票的最大利润](offer/MaxProfit.md)
193+
- [LeetCode](leetcode/README.md)
194+
- [**无重复字符的最长子串**](leetcode/lengthOfLongestSubstring.md)
195+
- [最长公共前缀](leetcode/longestCommonPrefix.md)
196+
- [字符串的排列](leetcode/checkInclusion.md)
197+
- [字符串相乘](leetcode/StringMultiply.md)
198+
- [翻转字符串里的单词](leetcode/reverseWords.md)
199+
- [简化路径](leetcode/simplifyPath.md)
200+
- [复原IP地址](leetcode/restoreIpAddresses.md)
201+
- [三数之和](leetcode/threeSum.md)
202+
- [岛屿的最大面积](leetcode/maxAreaOfIsland.md)
203+
- [搜索旋转排序数组](leetcode/searchRote.md)
204+
- [最长连续递增序列](leetcode/findLengthOfLCIS.md)
205+
- [数组中的第K个最大元素](leetcode/findKthLargest.md)
206+
- [最长连续序列](leetcode/longestConsecutive.md)
207+
- [朋友圈](leetcode/findCircleNum.md)
208+
- [合并区间](leetcode/mergeRagen.md)
209+
- [接雨水](leetcode/trap.md)
210+
- [合并两个有序链表](leetcode/mergeTwoLists.md)
211+
- [反转链表](leetcode/reverseList.md)
212+
- [两数相加](leetcode/addTwoNumbers.md)
213+
- [排序链表](leetcode/sortList.md)
214+
- [环形链表 II](leetcode/detectCycle.md)
215+
- [相交链表](leetcode/getIntersectionNode.md)
216+
- [合并K个排序链表](leetcode/mergeKLists.md)
217+
- [二叉树的最近公共祖先](leetcode/lowestCommonAncestor.md)
218+
- [二叉树的锯齿形层次遍历](leetcode/zigzagLevelOrder.md)
219+
- [买卖股票的最佳时机](leetcode/maxProfit.md)
220+
- [买卖股票的最佳时机 II](leetcode/maxProfit2.md)
221+
- [最大子序和](leetcode/maxSubArray.md)
222+
- [最小栈](leetcode/MinStack.md)
223+
- [LRU缓存机制](leetcode/LRUCache.md)
224+
- [全 O(1) 的数据结构](leetcode/AllOne.md)
225+
- [x 的平方根](leetcode/mySqrt.md)
226+
- [UTF-8 编码验证](leetcode/validUtf8.md)
227+
- [第二高的薪水](leetcode/salary.md)

‎leetcode/AllOne.md‎

Lines changed: 142 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,142 @@
1+
# [全 O(1) 的数据结构](https://leetcode-cn.com/explore/interview/card/bytedance/245/data-structure/1033/)
2+
3+
## 题目
4+
5+
实现一个数据结构支持以下操作：
6+
7+
- Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
8+
- Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
9+
- GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
10+
- GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
11+
12+
挑战：以 O(1) 的时间复杂度实现所有操作。
13+
14+
## 解题思路
15+
16+
1. 设计一个 `Bucket` 保存所有值为 `value` 的 `key`
17+
2. 并且有临近 `value` 的 `Bucket` 指针
18+
19+
```
20+
class AllOne {
21+
22+
/** Initialize your data structure here. */
23+
public AllOne() {
24+
25+
}
26+
27+
private static class Bucket {
28+
private int value;
29+
private Set<String> keys = new HashSet<>();
30+
private Bucket next;
31+
private Bucket pre;
32+
33+
public Bucket(int value) {
34+
this.value = value;
35+
}
36+
37+
@Override
38+
public String toString() {
39+
return "Bucket{" +
40+
"value=" + value +
41+
", keys=" + keys +
42+
'}';
43+
}
44+
}
45+
46+
private Map<String, Bucket> data = new HashMap<>();
47+
private List<Bucket> bucketList = new ArrayList<>();
48+
49+
/**
50+
* Inserts a new key <Key> with value 1. Or increments an existing key by 1.
51+
*/
52+
public void inc(String key) {
53+
if (data.containsKey(key)) {
54+
Bucket bucket = data.get(key);
55+
bucket.keys.remove(key);
56+
57+
if (bucket.next == null) {
58+
bucket.next = new Bucket(bucket.value + 1);
59+
bucket.next.pre = bucket;
60+
bucketList.add(bucket.next);
61+
}
62+
63+
bucket.next.keys.add(key);
64+
data.put(key, bucket.next);
65+
} else {
66+
if (bucketList.size() == 0) {
67+
bucketList.add(new Bucket(1));
68+
}
69+
70+
Bucket bucket = bucketList.get(0);
71+
bucket.keys.add(key);
72+
data.put(key, bucket);
73+
}
74+
}
75+
76+
/**
77+
* Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
78+
*/
79+
public void dec(String key) {
80+
if (!data.containsKey(key)) {
81+
return;
82+
}
83+
84+
Bucket bucket = data.get(key);
85+
if (bucket.pre == null) {
86+
bucket.keys.remove(key);
87+
data.remove(key);
88+
} else {
89+
bucket.keys.remove(key);
90+
bucket.pre.keys.add(key);
91+
data.put(key, bucket.pre);
92+
}
93+
}
94+
95+
/**
96+
* Returns one of the keys with maximal value.
97+
*/
98+
public String getMaxKey() {
99+
if (bucketList.size() == 0) {
100+
return "";
101+
}
102+
103+
for (int i = bucketList.size() - 1; i >= 0; i--) {
104+
Bucket bucket = bucketList.get(i);
105+
106+
if (!bucket.keys.isEmpty()) {
107+
Iterator<String> iterator = bucket.keys.iterator();
108+
if (iterator.hasNext()) {
109+
return iterator.next();
110+
} else {
111+
return "";
112+
}
113+
}
114+
}
115+
116+
return "";
117+
}
118+
119+
/**
120+
* Returns one of the keys with Minimal value.
121+
*/
122+
public String getMinKey() {
123+
if (bucketList.size() == 0) {
124+
return "";
125+
}
126+
127+
for (Bucket bucket : bucketList) {
128+
if (!bucket.keys.isEmpty()) {
129+
Iterator<String> iterator = bucket.keys.iterator();
130+
if (iterator.hasNext()) {
131+
return iterator.next();
132+
} else {
133+
return "";
134+
}
135+
}
136+
}
137+
138+
return "";
139+
}
140+
}
141+
142+
```

‎leetcode/LRUCache.md‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
# [LRU缓存机制](https://leetcode-cn.com/explore/interview/card/bytedance/245/data-structure/1032/)
2+
3+
## 题目
4+
5+
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
6+
7+
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
8+
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
9+
10+
进阶:
11+
12+
你是否可以在 O(1) 时间复杂度内完成这两种操作？
13+
14+
```
15+
示例:
16+
17+
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
18+
19+
cache.put(1, 1);
20+
cache.put(2, 2);
21+
cache.get(1); // 返回 1
22+
cache.put(3, 3); // 该操作会使得密钥 2 作废
23+
cache.get(2); // 返回 -1 (未找到)
24+
cache.put(4, 4); // 该操作会使得密钥 1 作废
25+
cache.get(1); // 返回 -1 (未找到)
26+
cache.get(3); // 返回 3
27+
cache.get(4); // 返回 4
28+
```
29+
30+
## 解题思路
31+
32+
```
33+
class LRUCache extends LinkedHashMap<Integer, Integer>{
34+
35+
private final int capacity;
36+
37+
public LRUCache(int capacity) {
38+
super(capacity*, 0.75f, true);
39+
this.capacity = capacity;
40+
}
41+
42+
public int get(int key) {
43+
Integer integer = super.get(key);
44+
45+
return integer == null ? -1 : integer;
46+
}
47+
48+
public void put(int key, int value) {
49+
50+
super.put(key, value);
51+
}
52+
53+
@Override
54+
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
55+
return size() > this.capacity;
56+
}
57+
}
58+
```

‎leetcode/MinStack.md‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
# [最小栈](https://leetcode-cn.com/explore/interview/card/bytedance/245/data-structure/1049/)
2+
3+
4+
## 题目
5+
6+
7+
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
8+
9+
push(x) -- 将元素 x 推入栈中。
10+
pop() -- 删除栈顶的元素。
11+
top() -- 获取栈顶元素。
12+
getMin() -- 检索栈中的最小元素。
13+
14+
```
15+
示例:
16+
17+
MinStack minStack = new MinStack();
18+
minStack.push(-2);
19+
minStack.push(0);
20+
minStack.push(-3);
21+
minStack.getMin(); --> 返回 -3.
22+
minStack.pop();
23+
minStack.top(); --> 返回 0.
24+
minStack.getMin(); --> 返回 -2.
25+
```
26+
27+
## 解题思路
28+
29+
```
30+
class MinStack {
31+
32+
/** initialize your data structure here. */
33+
public MinStack() {
34+
35+
}
36+
37+
private LinkedList<Integer> stack = new LinkedList<>();
38+
private Queue<Integer> minStack = new PriorityQueue<>();
39+
40+
41+
42+
public void push(int x) {
43+
stack.offerFirst(x);
44+
minStack.offer(x);
45+
}
46+
47+
public void pop() {
48+
Integer poll = stack.pollFirst();
49+
if (poll != null) {
50+
minStack.remove(poll);
51+
}
52+
}
53+
54+
public int top() {
55+
Integer first = stack.peekFirst();
56+
return first == null ? 0 : first;
57+
}
58+
59+
public int getMin() {
60+
Integer first = minStack.peek();
61+
return first == null ? 0 : first;
62+
}
63+
}
64+
```

‎leetcode/README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
# LeetCode
2+
3+
包含头条常见的面试题

‎leetcode/StringMultiply.md‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
# [字符串相乘](https://leetcode-cn.com/explore/interview/card/bytedance/242/string/1015/)
2+
3+
## 题目
4+
5+
给定两个以字符串形式表示的非负整数 `num1` 和 `num2`，返回 `num1` 和 `num2` 的乘积，它们的乘积也表示为字符串形式。
6+
7+
```
8+
示例 1:
9+
10+
输入: num1 = "2", num2 = "3"
11+
输出: "6"
12+
```
13+
14+
- num1 和 num2 的长度小于110。
15+
- num1 和 num2 只包含数字 0-9。
16+
- num1 和 num2 均不以零开头，除非是数字 0 本身。
17+
- 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
18+
19+
## 解题思路
20+
21+
1. 对于字符串 `num2` 中的每一位数与字符串 `num1` 相乘所得的结果，不再分开计算最后相加，而是先全部累加，最后再考虑进位的影响。
22+
23+
1. 对于最终结果的第`i + j`位数，可以由 `num1` 数组的第 `i` 位数和 `num2` 数组的第 `j` 位数组成。
24+
25+
```
26+
public String multiply(String num1, String num2) {
27+
if (num1.length() == 0 || num2.length() == 0) {
28+
return ZEO;
29+
}
30+
31+
if (num1.equals(ZEO) || num2.equals(ZEO)) {
32+
return ZEO;
33+
}
34+
35+
if (num1.equals(ONE)) {
36+
return num2;
37+
}
38+
39+
if (num2.equals(ONE)) {
40+
return num1;
41+
}
42+
43+
int[] num = new int[num1.length() + num2.length() - 1];
44+
Arrays.fill(num, 0);
45+
for (int i = 0; i < num1.length(); i++) {
46+
for (int j = 0; j < num2.length(); j++) {
47+
num[i + j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
48+
}
49+
}
50+
51+
StringBuilder res = new StringBuilder();
52+
int addIn = 0;
53+
for (int i = num.length - 1; i >= 0; i--) {
54+
int t = num[i] + addIn;
55+
addIn = t / 10;
56+
res.append(t % 10);
57+
}
58+
59+
if (addIn > 0) {
60+
res.append(addIn);
61+
}
62+
return res.reverse().toString();
63+
}
64+
```

0 commit comments

Comments
 (0)