Skip to content

Commit cc74cf1

Browse files
leosanqingleosanqing
committed
1. 新增部分题目
1 parent 3cd55bc commit cc74cf1

10 files changed

Lines changed: 427 additions & 15 deletions

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/list/_141_linked_list_cycle.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.leosanqing.leetcode.easy.list;
2+
3+
import com.leosanqing.leetcode.medium.list.ListNode;
4+
5+
/**
6+
* @Author: rtliu
7+
* @Date: 2020/8/4 下午4:15
8+
* @Package: com.leosanqing.leetcode.easy.list
9+
* @Description: 1
10+
*` Given a linked list, determine if it has a cycle in it.
11+
*` To represent a cycle in the given linked list,
12+
*` we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.
13+
*` If pos is -1, then there is no cycle in the linked list.
14+
*` Example 1:
15+
*` Input: head = [3,2,0,-4], pos = 1
16+
*` Output: true
17+
*` Explanation: There is a cycle in the linked list, where tail connects to the second node.
18+
*` Example 2:
19+
*` Input: head = [1,2], pos = 0
20+
*` Output: true
21+
*` Explanation: There is a cycle in the linked list, where tail connects to the first node.
22+
* @Version: 1.0
23+
*/
24+
public class _141_linked_list_cycle {
25+
/**
26+
* 设置两个指针 一个快指针 一个慢指针 ，只要出现两个指针指向的一样，那就说明有环
27+
* @param head
28+
* @return
29+
*/
30+
public boolean hasCycle(ListNode head) {
31+
ListNode fast = head;
32+
ListNode slow = head;
33+
while(fast != null && fast.next != null){
34+
slow = slow.next;
35+
fast = fast.next.next;
36+
if(fast == slow){
37+
return true;
38+
}
39+
}
40+
41+
return false;
42+
43+
}
44+
45+
}

java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/list/_120_triangle.java renamed to java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_120_triangle.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.leosanqing.leetcode.medium.list;
1+
package com.leosanqing.leetcode.medium.array;
22

33
import java.util.ArrayList;
44
import java.util.Arrays;

java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/list/_121_best_time_to_buy_and_sell_stock.java renamed to java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_121_best_time_to_buy_and_sell_stock.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.leosanqing.leetcode.medium.list;
1+
package com.leosanqing.leetcode.medium.array;
22

33
/**
44
* @Author: rtliu

java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/list/_122_best_time_to_buy_and_sell_stockII.java renamed to java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_122_best_time_to_buy_and_sell_stockII.java

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package com.leosanqing.leetcode.medium.list;
1+
package com.leosanqing.leetcode.medium.array;
22

33
/**
44
* @Author: rtliu
@@ -43,12 +43,15 @@ public static int maxProfit(int[] prices) {
4343
int profit = 0;
4444
int buy = prices[0];
4545
for (int i = 1; i < prices.length; i++) {
46+
// 只要 后面的大于前面的就继续往后，
4647
if (prices[i] > prices[i - 1]) {
48+
// 如果是最后一个 如[1,2,3,4,5]，当他到5的时候，就要卖出了 不然就是0
4749
if (i == prices.length - 1) {
4850
profit += prices[i] - buy;
4951
}
5052
continue;
5153
}
54+
// 不然就 计算前面的利润 如 [1,2,5,3] 当我们 到 3 的时候，我们就要计算 5-1 的利润
5255
profit += prices[i - 1] - buy;
5356
buy = prices[i];
5457
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_134_gas_station.java‎

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
package com.leosanqing.leetcode.medium.array;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/8/4 上午9:38
6+
* @Package: com.leosanqing.leetcode.medium.array
7+
* @Description: 1
8+
* ` There are N gas stations along a circular route,
9+
* ` where the amount of gas at station i is gas[i].
10+
* ` You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its
11+
* next station (i+1).
12+
* ` You begin the journey with an empty tank at one of the gas stations.
13+
* ` Return the starting gas station's index
14+
* ` if you can travel around the circuit once in the clockwise direction, otherwise return -1.
15+
* `
16+
* ` Note:
17+
* ` If there exists a solution, it is guaranteed to be unique.
18+
* ` Both input arrays are non-empty and have the same length.
19+
* ` Each element in the input arrays is a non-negative integer.
20+
* `
21+
* ` 沿循环路线有N个加油站，
22+
* ` 其中，第i个站点的天然气量为gas [i]。
23+
* ` 您有一辆带无限油箱的汽车，从第i站到下一个（i + 1）的行车成本为[i]。
24+
* ` 您可以从其中一个加油站的空罐开始旅程。
25+
* ` 返回起始加油站的索引
26+
* ` 如果您可以沿顺时针方向绕过电路一次，否则返回-1。
27+
* ` 注意：
28+
* ` 如果存在解决方案，则保证是唯一的。
29+
* ` 两个输入数组都是非空的，并且具有相同的长度。
30+
* ` 输入数组中的每个元素都是非负整数。
31+
* ` Example 1:
32+
* ` Input:
33+
* ` gas = [1,2,3,4,5]
34+
* ` cost = [3,4,5,1,2]
35+
* ` Output: 3
36+
* ` Explanation:
37+
* ` Start at station 3 (index 3) and fill up with 4 unit of gas.
38+
* ` Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0.
39+
* ` Your tank = 8 - 2 + 1 = 7 Travel to station 1.
40+
* ` Your tank = 7 - 3 + 2 = 6 Travel to station 2.
41+
* ` Your tank = 6 - 4 + 3 = 5 Travel to station 3.
42+
* ` The cost is 5. Your gas is just enough to travel back to station 3.
43+
* ` Therefore, return 3 as the starting index.
44+
* ` Example 2:
45+
* ` Input:
46+
* ` gas = [2,3,4]
47+
* ` cost = [3,4,3]
48+
* ` Output: -1
49+
* ` Explanation:
50+
* ` You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
51+
* ` Let's start at station 2 and fill up with 4 unit of gas.
52+
* ` Your tank = 0 + 4 = 4 Travel to station 0.
53+
* ` Your tank = 4 - 3 + 2 = 3 Travel to station 1.
54+
* ` Your tank = 3 - 3 + 3 = 3 You cannot travel back to station 2, as it requires 4 unit of gas but you
55+
* only have 3.
56+
* ` Therefore, you can't travel around the circuit once no matter where you start.
57+
* @Version: 1.0
58+
*/
59+
public class _134_gas_station {
60+
61+
public static void main(String[] args) {
62+
63+
int[] gas = {1, 2, 3, 4, 5};
64+
int[] cost = {3, 4, 5, 1, 2};
65+
System.out.println(canCompleteCircuit(gas, cost));
66+
}
67+
68+
public static int canCompleteCircuit(int[] gas, int[] cost) {
69+
int total = 0;
70+
71+
for (int i = 0; i < gas.length; i++) {
72+
total += gas[i] - cost[i];
73+
}
74+
if (total < 0) {
75+
return -1;
76+
}
77+
78+
for (int i = 0; i < gas.length; i++) {
79+
if (canDoIt(gas, cost, i)) {
80+
return i;
81+
}
82+
}
83+
return -1;
84+
}
85+
86+
private static boolean canDoIt(int[] gas, int[] cost, int start) {
87+
int g = 0;
88+
for (int j = 0; j < gas.length; j++) {
89+
int position = (j + start) % gas.length;
90+
g += gas[position] - cost[position];
91+
if (g < 0) {
92+
return false;
93+
}
94+
}
95+
return true;
96+
}
97+
98+
99+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/array/_138_copy_list_with_random_pointer.java‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package com.leosanqing.leetcode.medium.array;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* @Author: rtliu
8+
* @Date: 2020/8/4 上午11:30
9+
* @Package: com.leosanqing.leetcode.medium.array
10+
* @Description: https://leetcode.com/problems/copy-list-with-random-pointer/
11+
* @Version: 1.0
12+
*/
13+
public class _138_copy_list_with_random_pointer {
14+
public RandomListNode copyRandomList(RandomListNode head) {
15+
16+
if (head == null) {
17+
return null;
18+
}
19+
Map<RandomListNode, RandomListNode> map = new HashMap<>();
20+
21+
22+
23+
RandomListNode node = head;
24+
while(node !=null){
25+
map.put(node,new RandomListNode(node.val));
26+
node = node.next;
27+
}
28+
29+
node = head;
30+
31+
while(node != null){
32+
map.get(node).next = map.get(node.next);
33+
map.get(node).random = map.get(node.random);
34+
node = node.next;
35+
}
36+
37+
return map.get(head);
38+
}
39+
}
40+
41+
42+
class RandomListNode {
43+
int val;
44+
RandomListNode next;
45+
RandomListNode random;
46+
47+
public RandomListNode(int val) {
48+
this.val = val;
49+
this.next = null;
50+
this.random = null;
51+
}
52+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/list/ListNode.java‎

Lines changed: 12 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -4,18 +4,18 @@
44
* @author zhuerchong
55
*/
66
public class ListNode {
7-
public int val;
8-
public ListNode next;
7+
public int val;
8+
public ListNode next;
99

10-
public ListNode() {
11-
}
10+
public ListNode() {
11+
}
1212

13-
public ListNode(int val) {
14-
this.val = val;
15-
}
13+
public ListNode(int val) {
14+
this.val = val;
15+
}
1616

17-
public ListNode(int val, ListNode next) {
18-
this.val = val;
19-
this.next = next;
20-
}
21-
}
17+
public ListNode(int val, ListNode next) {
18+
this.val = val;
19+
this.next = next;
20+
}
21+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/list/_142_linked_list_cycleII.java‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package com.leosanqing.leetcode.medium.list;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/8/4 下午4:50
6+
* @Package: com.leosanqing.leetcode.medium.list
7+
* @Description: 1
8+
*` Given a linked list, return the node where the cycle begins.
9+
*` If there is no cycle, return null.
10+
*` To represent a cycle in the given linked list,
11+
*` we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.
12+
*` If pos is -1, then there is no cycle in the linked list.
13+
*` Note: Do not modify the linked list.
14+
*` Example 1:
15+
*` Input: head = [3,2,0,-4], pos = 1
16+
*` Output: tail connects to node index 1
17+
*` Explanation:
18+
*` There is a cycle in the linked list, where tail connects to the second node.
19+
*` Example 2:
20+
*` Input: head = [1,2], pos = 0
21+
*` Output: tail connects to node index 0
22+
*` Explanation:
23+
*` There is a cycle in the linked list, where tail connects to the first node.
24+
* @Version: 1.0
25+
*/
26+
public class _142_linked_list_cycleII {
27+
public ListNode detectCycle(ListNode head) {
28+
ListNode slow = head;
29+
ListNode fast = head;
30+
31+
while (fast!=null && fast.next!=null){
32+
fast = fast.next.next;
33+
slow = slow.next;
34+
35+
if (fast == slow){
36+
ListNode slow2 = head;
37+
while (slow2 != slow){
38+
slow = slow.next;
39+
slow2 = slow2.next;
40+
}
41+
return slow;
42+
}
43+
}
44+
return null;
45+
}
46+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/string/_131_palindrome_partitioning.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package com.leosanqing.leetcode.medium.string;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* @Author: rtliu
8+
* @Date: 2020/8/3 下午5:43
9+
* @Package: com.leosanqing.leetcode.medium.string
10+
* @Description: 1
11+
* ` Given a string s, partition s such that every substring of the partition is a palindrome.
12+
* ` Return all possible palindrome partitioning of s.
13+
* ` Example:
14+
* ` Input: "aab"
15+
* ` Output:
16+
* ` [
17+
* ` ["aa","b"],
18+
* ` ["a","a","b"]
19+
* ` ]
20+
* @Version: 1.0
21+
*/
22+
public class _131_palindrome_partitioning {
23+
public static void main(String[] args) {
24+
partition("aab");
25+
}
26+
public static List<List<String>> partition(String s) {
27+
28+
List<List<String>> answer = new ArrayList<>();
29+
for (int i = 1; i < s.length(); i++) {
30+
backTrace(answer,new ArrayList<>(), s, 0, i);
31+
}
32+
return answer;
33+
}
34+
35+
private static void backTrace(List<List<String>> answer, List<String> list, String s, int position, int length) {
36+
if (position >= s.length()) {
37+
answer.add(new ArrayList<>(list));
38+
return;
39+
}
40+
41+
42+
String substring = s.substring(position, position + length);
43+
if (isPalindrome(substring)) {
44+
list.add(substring);
45+
return;
46+
}
47+
backTrace(answer, list, s, position + length, length);
48+
}
49+
50+
private static boolean isPalindrome(String s) {
51+
for (int i = 0; i < s.length() / 2; i++) {
52+
if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
53+
return false;
54+
}
55+
}
56+
return true;
57+
}
58+
}

0 commit comments

Comments
 (0)