Skip to content

Commit 3cd55bc

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

File tree

6 files changed

+371
-0
lines changed

6 files changed

+371
-0
lines changed

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/hard/list/_123_best_time_to_buy_and_sell_stockIII.java‎

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package com.leosanqing.leetcode.hard.list;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/8/3 上午10:57
6+
* @Package: com.leosanqing.leetcode.hard.list
7+
* @Description: 1
8+
* ` Say you have an array for which the ith element is the price of a given stock on day i.
9+
* ` Design an algorithm to find the maximum profit.
10+
* ` You may complete at most two transactions.
11+
* ` Note: You may not engage in multiple transactions at the same time
12+
* ` (i.e., you must sell the stock before you buy again).
13+
* ` Example 1:
14+
* ` Input: [3,3,5,0,0,3,1,4]
15+
* ` Output: 6
16+
* ` Explanation:
17+
* ` Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
18+
* ` Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
19+
* ` Example 2:
20+
* ` Input: [1,2,3,4,5]
21+
* ` Output: 4
22+
* ` Explanation:
23+
* ` Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
24+
* ` Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
25+
* ` engaging multiple transactions at the same time. You must sell before buying again.
26+
* ` Example 3:
27+
* ` Input: [7,6,4,3,1]
28+
* ` Output: 0
29+
* ` Explanation:
30+
* ` In this case, no transaction is done, i.e. max profit = 0.
31+
* @Version: 1.0
32+
*/
33+
public class _123_best_time_to_buy_and_sell_stockIII {
34+
public static void main(String[] args) {
35+
36+
maxProfit(new int[]{1, 2, 3, 4, 5});
37+
}
38+
39+
public static int maxProfit(int[] prices) {
40+
if (prices == null || prices.length < 2) {
41+
return 0;
42+
}
43+
int totalK = 2;
44+
int[][] dp = new int[totalK + 1][prices.length];
45+
for (int k = 1; k <= totalK; k++) {
46+
//profit = 0 when k = 0
47+
for (int i = 1; i < prices.length; i++) {
48+
//buy on day 0, sell on day i
49+
int maxProfitSellOnDayI = Math.max(0, prices[i] - prices[0]);
50+
//buy on day j, sell on day i
51+
for (int j = 1; j < i; j++) {
52+
maxProfitSellOnDayI = Math.max(maxProfitSellOnDayI, dp[k - 1][j - 1] + prices[i] - prices[j]);
53+
}
54+
//sell on day i OR not
55+
dp[k][i] = Math.max(dp[k][i - 1], maxProfitSellOnDayI);
56+
}
57+
}
58+
return dp[totalK][prices.length - 1];
59+
60+
}
61+
}

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

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
package com.leosanqing.leetcode.medium.list;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
/**
8+
* @Author: rtliu
9+
* @Date: 2020/8/3 上午9:29
10+
* @Package: com.leosanqing.leetcode.medium.list
11+
* @Description: 1
12+
* ` Given a triangle, find the minimum path sum from top to bottom.
13+
* ` Each step you may move to adjacent numbers on the row below.
14+
* ` For example, given the following triangle
15+
* `
16+
* ` 给定一个三角形，找到从上到下的最小路径总和。
17+
* ` 您可以将每一步移至下面一行中的相邻数字。
18+
* ` 例如，给定以下三角形
19+
* ` [
20+
* ` [2],
21+
* ` [3,4],
22+
* ` [6,5,7],
23+
* ` [4,1,8,3]
24+
* ` ]
25+
* ` The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
26+
* @Version: 1.0
27+
*/
28+
public class _120_triangle {
29+
public static void main(String[] args) {
30+
int[][] list = {
31+
{2},
32+
{3, 4},
33+
{6, 5, 7},
34+
{4, 1, 8, 3}
35+
};
36+
37+
List<List<Integer>> lists = new ArrayList<>();
38+
lists.add(Arrays.asList(2));
39+
lists.add(Arrays.asList(3, 4));
40+
lists.add(Arrays.asList(6, 5, 7));
41+
lists.add(Arrays.asList(4, 1, 8, 3));
42+
System.out.println(minimumTotal(lists));
43+
}
44+
45+
/**
46+
* 动态规划
47+
* @param triangle
48+
* @return
49+
*/
50+
public static int minimumTotal(List<List<Integer>> triangle) {
51+
52+
int[] ints = new int[triangle.size()];
53+
int min = Integer.MAX_VALUE;
54+
for (List<Integer> list : triangle) {
55+
// 从右到左，如果从左到右，ints[n-1]会被之前的修改覆盖
56+
for (int j = list.size() - 1; j >= 0; j--) {
57+
if (j == 0) {
58+
ints[0] += list.get(0);
59+
} else if (j == list.size() - 1) {
60+
ints[j] = list.get(j) + ints[j - 1];
61+
} else {
62+
ints[j] = list.get(j) + Math.min(ints[j - 1], ints[j]);
63+
}
64+
}
65+
}
66+
for (int anInt : ints) {
67+
if (min > anInt) {
68+
min = anInt;
69+
}
70+
}
71+
72+
return min;
73+
74+
}
75+
76+
77+
}

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

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package com.leosanqing.leetcode.medium.list;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/8/3 上午10:07
6+
* @Package: com.leosanqing.leetcode.medium.list
7+
* @Description: `
8+
* ` Say you have an array for which the ith element is the price of a given stock on day i.
9+
* ` If you were only permitted to complete at most one transaction
10+
* ` (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
11+
* ` Note that you cannot sell a stock before you buy one.
12+
* `
13+
* ` 假设您有一个数组，第i个元素是第i天给定股票的价格。
14+
* ` 如果您只被允许最多完成一笔交易
15+
* ` （即，买入并卖出一股股票），设计一种算法以找到最大的利润。
16+
* ` 请注意，您不能在买股票之前卖出股票。
17+
* `
18+
* ` Example 1:
19+
* ` Input: [7,1,5,3,6,4]
20+
* ` Output: 5
21+
* ` Explanation:
22+
* ` Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
23+
* ` Not 7-1 = 6, as selling price needs to be larger than buying price.
24+
* ` Example 2:
25+
* ` Input: [7,6,4,3,1]
26+
* ` Output: 0
27+
* ` Explanation:
28+
* ` In this case, no transaction is done, i.e. max profit = 0.
29+
* @Version: 1.0
30+
*/
31+
public class _121_best_time_to_buy_and_sell_stock {
32+
public static void main(String[] args) {
33+
System.out.println(maxProfit(new int[]{7,1,5,3,6,4}));
34+
}
35+
public static int maxProfit(int[] prices) {
36+
if(prices == null || prices.length < 2){
37+
return 0;
38+
}
39+
int buy = prices[0];
40+
int profit = 0;
41+
for (int i = 1; i < prices.length; i++) {
42+
if (buy < prices[i]) {
43+
profit = Math.max(prices[i] - buy,profit);
44+
} else {
45+
buy = prices[i];
46+
}
47+
}
48+
49+
return profit;
50+
}
51+
52+
53+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/list/_122_best_time_to_buy_and_sell_stockII.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.list;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/8/3 上午10:23
6+
* @Package: com.leosanqing.leetcode.medium.list
7+
* @Description: 1
8+
* ` Say you have an array prices for which the ith element is the price of a given stock on day i.
9+
* ` Design an algorithm to find the maximum profit.
10+
* ` You may complete as many transactions as you like
11+
* ` (i.e., buy one and sell one share of the stock multiple times).
12+
* ` Note: You may not engage in multiple transactions at the same time
13+
* ` (i.e., you must sell the stock before you buy again).
14+
* ` Example 1:
15+
* ` Input: [7,1,5,3,6,4]
16+
* ` Output: 7
17+
* ` Explanation:
18+
* ` Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
19+
* ` Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
20+
* ` Example 2:
21+
* ` Input: [1,2,3,4,5]
22+
* ` Output: 4
23+
* ` Explanation:
24+
* ` Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
25+
* ` Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
26+
* ` engaging multiple transactions at the same time. You must sell before buying again.
27+
* ` Example 3:
28+
* ` Input: [7,6,4,3,1]
29+
* ` Output: 0
30+
* ` Explanation: In this case, no transaction is done, i.e. max profit = 0.
31+
* @Version: 1.0
32+
*/
33+
public class _122_best_time_to_buy_and_sell_stockII {
34+
public static void main(String[] args) {
35+
int[] ints = {7, 6, 4, 3, 1};
36+
maxProfit(ints);
37+
}
38+
39+
public static int maxProfit(int[] prices) {
40+
if (prices == null || prices.length < 2) {
41+
return 0;
42+
}
43+
int profit = 0;
44+
int buy = prices[0];
45+
for (int i = 1; i < prices.length; i++) {
46+
if (prices[i] > prices[i - 1]) {
47+
if (i == prices.length - 1) {
48+
profit += prices[i] - buy;
49+
}
50+
continue;
51+
}
52+
profit += prices[i - 1] - buy;
53+
buy = prices[i];
54+
}
55+
56+
return profit;
57+
}
58+
}

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

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.leosanqing.leetcode.medium.list;
2+
3+
/**
4+
* @Author: rtliu
5+
* @Date: 2020/8/3 下午5:29
6+
* @Package: com.leosanqing.leetcode.medium.list
7+
* @Description: 1
8+
*` Given a non-empty array of integers,
9+
*` every element appears three times except for one,
10+
*` which appears exactly once. Find that single one.
11+
*` Note: Your algorithm should have a linear runtime complexity.
12+
*` Could you implement it without using extra memory?
13+
*` Example 1:
14+
*` Input: [2,2,3,2]
15+
*` Output: 3
16+
*` Example 2:
17+
*` Input: [0,1,0,1,0,1,99]
18+
*` Output: 99
19+
*`
20+
* @Version: 1.0
21+
*/
22+
public class _137_single_numberII {
23+
public static void main(String[] args) {
24+
int[] ints = {2,2,3,2};
25+
System.out.println(singleNumber(ints));
26+
}
27+
28+
public static int singleNumber(int[] nums) {
29+
int ans = 0;
30+
for(int i = 0; i < 32; i++) {
31+
int sum = 0;
32+
for (int num : nums) {
33+
if (((num >> i) & 1) == 1) {
34+
sum++;
35+
sum %= 3;
36+
}
37+
}
38+
if(sum != 0) {
39+
ans |= sum << i;
40+
}
41+
}
42+
return ans;
43+
}
44+
45+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/medium/tree/_129_sum_root_to_leaf_numbers.java‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
package com.leosanqing.leetcode.medium.tree;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* @Author: rtliu
8+
* @Date: 2020/8/3 上午11:26
9+
* @Package: com.leosanqing.leetcode.medium.tree
10+
* @Description: 1
11+
* ` Given a binary tree containing digits from 0-9 only,
12+
* ` each root-to-leaf path could represent a number.
13+
* ` An example is the root-to-leaf path 1->2->3 which represents the number 123.
14+
* ` Find the total sum of all root-to-leaf numbers.
15+
* ` Note: A leaf is a node with no children.
16+
* ` Example:
17+
* ` Input: [1,2,3]
18+
* ` 1
19+
* ` / \
20+
* ` 2 3
21+
* ` Output: 25
22+
* ` Explanation:
23+
* ` The root-to-leaf path 1->2 represents the number 12.
24+
* ` The root-to-leaf path 1->3 represents the number 13.
25+
* ` Therefore, sum = 12 + 13 = 25.
26+
* ` Example 2:
27+
* ` Input: [4,9,0,5,1]
28+
* ` 4
29+
* ` / \
30+
* ` 9 0
31+
* ` / \
32+
* ` 5 1
33+
* ` Output: 1026
34+
* ` Explanation:
35+
* ` The root-to-leaf path 4->9->5 represents the number 495.
36+
* ` The root-to-leaf path 4->9->1 represents the number 491.
37+
* ` The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026.
38+
* @Version: 1.0
39+
*/
40+
public class _129_sum_root_to_leaf_numbers {
41+
42+
public static void main(String[] args) {
43+
TreeNode treeNode = new TreeNode(1);
44+
treeNode.right = new TreeNode(3);
45+
treeNode.left = new TreeNode(2);
46+
treeNode.left.left = new TreeNode(4);
47+
treeNode.left.right = new TreeNode(5);
48+
49+
sumNumbers(treeNode);
50+
}
51+
52+
public static int sumNumbers(TreeNode root) {
53+
List<Integer> list = new ArrayList<>();
54+
backTrace(root, 0, list);
55+
int sum = 0;
56+
for (Integer integer : list) {
57+
sum += integer;
58+
}
59+
return sum;
60+
}
61+
62+
63+
private static void backTrace(TreeNode root, int val, List<Integer> list) {
64+
if(root == null){
65+
return;
66+
}
67+
val = val * 10 +root.val;
68+
69+
if(root.left == null && root.right == null){
70+
71+
list.add(val);
72+
return;
73+
}
74+
backTrace(root.left, val, list);
75+
backTrace(root.right, val, list);
76+
}
77+
}

0 commit comments

Comments
 (0)