Skip to content

Commit 7667e50

Browse files
JustDoItGitJustDoItGit
authored
Merge pull request algorithm004-01#7 from algorithm004-01/master
merge
2 parents d327010 + d5bca6f commit 7667e50

File tree

108 files changed

+3982
-8
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

108 files changed

+3982
-8
lines changed

‎.gitignore‎

Lines changed: 0 additions & 1 deletion
This file was deleted.

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
# 极客大学「算法训练营第四期 - 1 班」作业提交仓库
22

3+
请大家通过该链接查看讲师课件并进行下载: https://pan.baidu.com/s/1k1BHhltBkZLJw0TG-uYC7g 密码:p5op
34

45
## 仓库目录结构说明
56

‎Week 01/id_006/DequeDemo.java‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package com.mrglint.leetcode;
2+
3+
import java.util.Deque;
4+
import java.util.LinkedList;
5+
6+
/**
7+
* @author luhuancheng
8+
* @since 2019-10-20 10:34
9+
*/
10+
public class DequeDemo {
11+
public static void main(String[] args) {
12+
// 一个使用链表实现的无界双端队列
13+
Deque<String> deque = new LinkedList<>();
14+
15+
// 从头部入队
16+
deque.addFirst("a");
17+
deque.addFirst("b");
18+
deque.addFirst("c");
19+
System.out.println(deque);
20+
21+
// 从尾部入队
22+
deque.addLast("a");
23+
deque.addLast("b");
24+
deque.addLast("c");
25+
System.out.println(deque);
26+
27+
String str = deque.peek();
28+
System.out.println(str);
29+
System.out.println(deque);
30+
31+
while (deque.size() > 0) {
32+
// 从头部出队
33+
System.out.println(deque.removeFirst());
34+
}
35+
36+
System.out.println(deque);
37+
}
38+
}
39+

‎Week 01/id_006/LeetCode_189_006.java‎

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
package com.mrglint.leetcode.solution189;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* @author luhuancheng
7+
* @since 2019-10-17 13:19
8+
*/
9+
public class Solution {
10+
11+
/**
12+
暴力破解 - 写法1，时间复杂度 O(n * k)
13+
*
14+
*/
15+
public void rotate1(int[] nums, int k) {
16+
for (int i = 0; i < k; i++) {
17+
int choose = nums[nums.length - 1];
18+
int j = nums.length - 1;
19+
while (j > 0) {
20+
nums[j] = nums[j - 1];
21+
j--;
22+
}
23+
nums[j] = choose;
24+
}
25+
}
26+
27+
/**
28+
暴力破解 - 写法2，时间复杂度 O(n * k)
29+
*
30+
*/
31+
public void rotate2(int[] nums, int k) {
32+
int temp, previous;
33+
for (int i = 0; i < k; i++) {
34+
previous = nums[nums.length - 1];
35+
for (int j = 0; j < nums.length; j++) {
36+
temp = nums[j];
37+
nums[j] = previous;
38+
previous = temp;
39+
}
40+
}
41+
}
42+
43+
/**
44+
* (index + number) % array.length 可以取得index索引所在元素，往右移动number次
45+
使用额外数组， 时间复杂度O(n)
46+
*
47+
*/
48+
public void rotate3(int[] nums, int k) {
49+
int[] a = new int[nums.length];
50+
for (int i = 0; i < nums.length; i++) {
51+
a[(i + k) % nums.length] = nums[i];
52+
}
53+
54+
for (int i = 0; i < a.length; i++) {
55+
nums[i] = a[i];
56+
}
57+
58+
}
59+
60+
public void rotate4(int[] nums, int k) {
61+
k = k % nums.length;
62+
int count = 0;
63+
for (int start = 0; count < nums.length; start++) {
64+
// 下一个要被替换位置的指针
65+
int next = (start + k) % nums.length;
66+
// previous保存放入下一个替换位置的值
67+
int previous = nums[start];
68+
while (next != start) {
69+
// temp保存被替换的数组元素
70+
int temp = nums[next];
71+
nums[next] = previous;
72+
previous = temp;
73+
// 下一次替换位置
74+
next = (next + k) % nums.length;
75+
count++;
76+
}
77+
// 将最后一个值放入原点位置
78+
nums[start] = previous;
79+
count++;
80+
}
81+
}
82+
83+
public void rotate(int[] nums, int k) {
84+
// 1, 2, 3, 4, 5 -> 5, 4, 3, 2, 1 -> 4, 5, 3, 2, 1 -> 4, 5, 1, 2, 3
85+
k = k % nums.length;
86+
reverse(nums, 0, nums.length - 1);
87+
reverse(nums, 0, k - 1);
88+
reverse(nums, k, nums.length - 1);
89+
}
90+
91+
private void reverse(int[] nums, int start, int end) {
92+
while (start < end) {
93+
int temp = nums[start];
94+
nums[start] = nums[end];
95+
nums[end] = temp;
96+
start++;
97+
end--;
98+
}
99+
}
100+
}
101+

‎Week 01/id_006/LeetCode_1_006.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.mrglint.leetcode.solution1;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* @author luhuancheng
8+
* @since 2019/9/5 9:33 下午
9+
*/
10+
public class Solution {
11+
12+
public int[] twoSum(int[] nums, int target) {
13+
Map<Integer, Integer> m = new HashMap<>();
14+
for (int i = 0; i < nums.length; i++) {
15+
int anotherNumber = target - nums[i];
16+
if (m.containsKey(anotherNumber)) {
17+
// 先返回前一个数的索引
18+
return new int[]{m.get(anotherNumber), i};
19+
} else {
20+
m.put(nums[i], i);
21+
}
22+
}
23+
throw new IllegalArgumentException("no such result");
24+
}
25+
}
26+

‎Week 01/id_006/LeetCode_21_006.java‎

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
package com.mrglint.leetcode.solution21;
2+
3+
import com.mrglint.leetcode.ListNode;
4+
5+
/**
6+
* @author luhuancheng
7+
* @since 2019-10-18 22:25
8+
*/
9+
public class Solution {
10+
11+
// 啰嗦写法
12+
public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
13+
if (l2 == null) {
14+
return l1;
15+
}
16+
if (l1 == null) {
17+
return l2;
18+
}
19+
ListNode head;
20+
ListNode returnHead;
21+
if (l1.val < l2.val) {
22+
head = l1;
23+
l1 = l1.next;
24+
} else {
25+
head = l2;
26+
l2 = l2.next;
27+
}
28+
returnHead = head;
29+
while (l1 != null && l2 != null) {
30+
if (l1.val < l2.val) {
31+
head.next = l1;
32+
l1 = l1.next;
33+
} else {
34+
head.next = l2;
35+
l2 = l2.next;
36+
}
37+
head = head.next;
38+
}
39+
40+
if (l1 != null) {
41+
head.next = l1;
42+
}
43+
if (l2 != null) {
44+
head.next = l2;
45+
}
46+
47+
return returnHead;
48+
49+
}
50+
51+
/**
52+
* 递归解法
53+
* 时间复杂度为O(m+n) m,n分别为两个链表长度
54+
*/
55+
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
56+
if (l1 == null) {
57+
return l2;
58+
} else if (l2 == null) {
59+
return l1;
60+
} else if (l1.val < l2.val) {
61+
l1.next = mergeTwoLists2(l1.next, l2);
62+
return l1;
63+
}else {
64+
l2.next = mergeTwoLists2(l2.next, l1);
65+
return l2;
66+
}
67+
}
68+
69+
/**
70+
* 迭代解法
71+
* @param l1
72+
* @param l2
73+
* @return
74+
*/
75+
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
76+
ListNode prehead = new ListNode(-1);
77+
ListNode prev = prehead;
78+
while (l1 != null && l2 != null) {
79+
if (l1.val < l2.val) {
80+
prev.next = l1;
81+
l1 = l1.next;
82+
} else {
83+
prev.next = l2;
84+
l2 = l2.next;
85+
}
86+
prev = prev.next;
87+
}
88+
prev.next = l1 == null ? l2 : l1;
89+
return prehead.next;
90+
}
91+
}
92+

‎Week 01/id_006/LeetCode_26_006.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
/**
2+
* https://leetcode.com/problems/remove-duplicates-from-sorted-array/
3+
* @author luhuancheng
4+
* @since 2019-10-16 13:45
5+
*/
6+
public class Solution {
7+
8+
public int removeDuplicates(int[] nums) {
9+
if (nums.length == 0) {
10+
return 0;
11+
}
12+
int i = 0;
13+
for (int j = 1; j < nums.length; j++) {
14+
if (nums[i] != nums[j]) {
15+
nums[++i] = nums[j];
16+
}
17+
}
18+
return i + 1;
19+
}
20+
}

‎Week 01/id_006/LeetCode_283_006.java‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.mrglint.leetcode.solution283;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* https://leetcode.com/problems/move-zeroes/
7+
* @author luhuancheng
8+
* @since 2019-10-16 06:55
9+
*/
10+
public class Solution {
11+
12+
public void moveZeroes1(int[] nums) {
13+
// 指向非0位置
14+
int j = 0;
15+
for (int i = 0; i < nums.length; i++) {
16+
if (nums[i] != 0) {
17+
nums[j] = nums[i];
18+
if (i != j) {
19+
nums[i] = 0;
20+
}
21+
j++;
22+
}
23+
}
24+
}
25+
26+
public void moveZeroes(int[] nums) {
27+
int notZeroIndex = 0;
28+
for (int i = 0; i < nums.length; i++) {
29+
if (nums[i] != 0) {
30+
int temp = nums[notZeroIndex];
31+
nums[notZeroIndex] = nums[i];
32+
nums[i] = temp;
33+
notZeroIndex++;
34+
}
35+
}
36+
}
37+
38+
public static void main(String[] args) {
39+
Solution solution = new Solution();
40+
int[] a = new int[]{1, 0, 1, 2};
41+
solution.moveZeroes(a);
42+
System.out.println(Arrays.toString(a));
43+
}
44+
45+
}
46+

0 commit comments

Comments
 (0)