Skip to content

Commit 79bfc47

Browse files
author
lianght1
committed
第一周作业
1 parent cd0ebbd commit 79bfc47

6 files changed

Lines changed: 526 additions & 1 deletion

File tree

‎Week_01/DequeDemo.java‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
import java.util.Deque;
2+
import java.util.LinkedList;
3+
import java.util.PriorityQueue;
4+
5+
/**
6+
* @author lianght1
7+
* @date 2021/1/31
8+
*/
9+
public class DequeDemo {
10+
11+
public static void main(String[] args) {
12+
Deque<String> deque = new LinkedList<>();
13+
14+
deque.addFirst("a");
15+
deque.addFirst("b");
16+
deque.addFirst("c");
17+
System.out.println(deque);
18+
19+
String str = deque.getFirst();
20+
System.out.println(str);
21+
System.out.println(deque);
22+
23+
while (deque.size() > 0) {
24+
System.out.println(deque.removeFirst());
25+
}
26+
27+
System.out.println(deque);
28+
29+
}
30+
31+
32+
33+
}

‎Week_01/MergeTwoSortedLists.java‎

Lines changed: 179 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,179 @@
1+
//题号：21
2+
//https://leetcode-cn.com/problems/merge-two-sorted-lists/
3+
//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
4+
//
5+
//
6+
//
7+
// 示例 1：
8+
//
9+
//
10+
//输入：l1 = [1,2,4], l2 = [1,3,4]
11+
//输出：[1,1,2,3,4,4]
12+
//
13+
//
14+
// 示例 2：
15+
//
16+
//
17+
//输入：l1 = [], l2 = []
18+
//输出：[]
19+
//
20+
//
21+
// 示例 3：
22+
//
23+
//
24+
//输入：l1 = [], l2 = [0]
25+
//输出：[0]
26+
//
27+
//
28+
//
29+
//
30+
// 提示：
31+
//
32+
//
33+
// 两个链表的节点数目范围是 [0, 50]
34+
// -100 <= Node.val <= 100
35+
// l1 和 l2 均按 非递减顺序 排列
36+
//
37+
// Related Topics 递归 链表
38+
// 👍 1506 👎 0
39+
40+
41+
42+
public class MergeTwoSortedLists{
43+
public static void main(String[] args) {
44+
Solution solution = new MergeTwoSortedLists().new Solution();
45+
}
46+
//leetcode submit region begin(Prohibit modification and deletion)
47+
/**
48+
* Definition for singly-linked list.
49+
* public class ListNode {
50+
* int val;
51+
* ListNode next;
52+
* ListNode() {}
53+
* ListNode(int val) { this.val = val; }
54+
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
55+
* }
56+
*/
57+
class Solution {
58+
59+
/**
60+
* 递归
61+
*/
62+
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
63+
64+
// if (l1 == null) {
65+
// return l2;
66+
// }
67+
//
68+
// if (l2 == null) {
69+
// return l1;
70+
// }
71+
//
72+
// //不要试图去人肉递归，只要记住，mergeTwoLists(x,y)这个函数给出的是排好序的
73+
// //合并链表，我们只需要将小的链表的下一个节点指向它即可。
74+
// if (l1.val <= l2.val) {
75+
// l1.next = mergeTwoLists(l1.next, l2);
76+
// return l1;
77+
// } else {
78+
// l2.next = mergeTwoLists(l1, l2.next);
79+
// return l2;
80+
// }
81+
82+
/**
83+
* 法一：递归法，时间复杂度O(n)，空间复杂度O(n)
84+
*/
85+
86+
// if (l1 == null) {
87+
// return l2;
88+
// }
89+
//
90+
// if (l2 == null) {
91+
// return l1;
92+
// }
93+
//
94+
// //不要试图去人肉递归，只要记住，mergeTwoLists(x,y)这个函数给出的是排好序的
95+
// //合并链表，我们只需要将小的链表的下一个节点指向它即可。
96+
// if (l1.val < l2.val) {
97+
// l1.next = mergeTwoLists(l1.next, l2);
98+
// return l1;
99+
// } else {
100+
// l2.next = mergeTwoLists(l1, l2.next);
101+
// return l2;
102+
// }
103+
104+
/**
105+
* 非递归，迭代法,
106+
*/
107+
108+
109+
ListNode result = new ListNode();
110+
ListNode pre = result;
111+
112+
while (l1 != null && l2 != null) {
113+
if (l1.val < l2.val) {
114+
pre.next = l1;
115+
l1 = l1.next;
116+
} else {
117+
pre.next = l2;
118+
l2 = l2.next;
119+
}
120+
121+
pre = pre.next;
122+
123+
}
124+
125+
pre.next = l1 == null ? l2 : l1;
126+
127+
return result.next;
128+
129+
}
130+
131+
/**
132+
* 非递归
133+
*/
134+
// public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
135+
//
136+
// //这个类似哑结点
137+
// ListNode result = new ListNode();
138+
//
139+
// //因为这里的pre会一直被替换为pre.next，因此需要个其他变量
140+
// //否則result会找不到一开始的位置
141+
// ListNode pre = result;
142+
//
143+
// while (l1 != null && l2 != null) {
144+
// //比较大小，直接将pre指向小的那个链表，然后将相应链表指针后移
145+
// if (l1.val <= l2.val) {
146+
// pre.next = l1;
147+
// l1 = l1.next;
148+
// } else {
149+
// pre.next = l2;
150+
// l2 = l2.next;
151+
// }
152+
// //pre里面增加了一个元素，因此要将指针后移
153+
// pre = pre.next;
154+
// }
155+
//
156+
// //这是一边链表比另一边长的时候，直接将长的部分放到pre后面即可
157+
// pre.next = l1 == null ? l2 : l1;
158+
//
159+
// return result.next;
160+
// }
161+
}
162+
//leetcode submit region end(Prohibit modification and deletion)
163+
public class ListNode {
164+
int val;
165+
MergeTwoSortedLists.ListNode next;
166+
167+
ListNode() {
168+
}
169+
170+
ListNode(int val) {
171+
this.val = val;
172+
}
173+
174+
ListNode(int val, MergeTwoSortedLists.ListNode next) {
175+
this.val = val;
176+
this.next = next;
177+
}
178+
}
179+
}

‎Week_01/MoveZeroes.java‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
//题号：283
2+
//https://leetcode-cn.com/problems/move-zeroes/
3+
//给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
4+
//
5+
// 示例:
6+
//
7+
// 输入: [0,1,0,3,12]
8+
//输出: [1,3,12,0,0]
9+
//
10+
// 说明:
11+
//
12+
//
13+
// 必须在原数组上操作，不能拷贝额外的数组。
14+
// 尽量减少操作次数。
15+
//
16+
// Related Topics 数组 双指针
17+
// 👍 935 👎 0
18+
19+
20+
public class MoveZeroes{
21+
public static void main(String[] args) {
22+
Solution solution = new MoveZeroes().new Solution();
23+
solution.moveZeroes(new int[]{1,0, 3, 0, 12});
24+
}
25+
//leetcode submit region begin(Prohibit modification and deletion)
26+
class Solution {
27+
public void moveZeroes(int[] nums) {
28+
29+
30+
/**
31+
* 法一：两次循环
32+
*/
33+
34+
35+
// if (nums == null) {
36+
// return;
37+
// }
38+
//
39+
// int j = 0;
40+
// for (int i = 0; i < nums.length; i++) {
41+
// if (nums[i]!=0) {
42+
// nums[j++] = nums[i];
43+
// }
44+
// }
45+
//
46+
// //前面有j个非0的，因为下标从0开始，因此其实位置刚好是j
47+
// for (int i = j; i < nums.length; i++) {
48+
// nums[i] = 0;
49+
// }
50+
51+
52+
/**
53+
* 法二：双指针
54+
*/
55+
56+
57+
if (nums == null) {
58+
return;
59+
}
60+
61+
//因为非0数据要保持原先位置，因此需要用非0的与0替换
62+
int j = 0;
63+
for (int i = 0; i < nums.length; i++) {
64+
//因为i,j起点一样，当nums[i]不等于0，j会加1，因此j一定是在0的位置
65+
if (nums[i] != 0) {
66+
//只有不同位置才需要交换
67+
if (i != j) {
68+
int temp = nums[i];
69+
nums[i] = nums[j];
70+
nums[j] = temp;
71+
}
72+
j++;
73+
}
74+
}
75+
}
76+
}
77+
//leetcode submit region end(Prohibit modification and deletion)
78+
79+
}

0 commit comments

Comments
 (0)