DFS
字符串
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44class Solution {
public List<List<String>> partition(String s) {
List<List<String>> list = new ArrayList<>();
if(s == null || s.length() == 0)
return list;
boolean[][] dp = getPalindromic(s);
partitionHelper(s, 0, dp, new ArrayList<>(), list);
return list;
}
private void partitionHelper(String s, int curLen,
boolean[][] dp, List<String> l, List<List<String>> list) {
if(curLen == s.length()) {
list.add(new ArrayList<>(l));
return;
}
for(int j = curLen; j < s.length(); j++) {
if(dp[curLen][j] == true) {
l.add(s.substring(curLen, j+1));
partitionHelper(s, j+1, dp, l, list);
l.remove(l.size()-1);
}
}
}
public boolean[][] getPalindromic(String s) {
if(s == null || s.length() == 0)
return new boolean[][]{};
int len = s.length();
boolean[][] dp = new boolean[len][len];
for(int i = 0; i < len; i++) {
dp[i][i] = true;
if(i < len-1 && s.charAt(i) == s.charAt(i+1))
dp[i][i+1] = true;
}
for(int l = 3; l <= len; l++) {
for(int i = 0; i+l-1 < len; i++) {
int j = i+l-1;
dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
}
}
return dp;
}
}
排列组合
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<>();
if(candidates == null || candidates.length == 0)
return list;
backcombinationSum(candidates, 0, target, new ArrayList<>(), list);
return list;
}
private void backcombinationSum(int[] candidates, int index, int target, List<Integer> l, List<List<Integer>> list) {
if(target == 0) {
list.add(new ArrayList<>(l));
return;
}
for(int i = index; i < candidates.length; i++) {
if(candidates[i] <= target) {
l.add(candidates[i]);
backcombinationSum(candidates, i, target-candidates[i], l, list);
l.remove(l.size()-1);
}
}
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<>();
if(candidates == null || candidates.length == 0)
return list;
Arrays.sort(candidates);
backcombinationSum2(candidates, 0, target, new ArrayList<>(), list, new boolean[candidates.length]);
return list;
}
private void backcombinationSum2(int[] candidates, int index, int target,
List<Integer> l, List<List<Integer>> list, boolean[] vis) {
if(target == 0) {
list.add(new ArrayList<>(l));
return;
}
for(int i = index; i < candidates.length; i++) {
if(i != 0 && candidates[i] == candidates[i-1] && !vis[i-1])
continue;
if(candidates[i] <= target) {
l.add(candidates[i]);
vis[i] = true;
backcombinationSum2(candidates, i+1, target-candidates[i], l, list, vis);
l.remove(l.size()-1);
vis[i] = false;
}
}
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
if(nums == null || nums.length == 0)
return list;
int len = nums.length;
boolean[] vis = new boolean[len];
backpermute(nums, vis, new ArrayList<>(), list);
return list;
}
private void backpermute(int[] nums, boolean[] vis, List<Integer> l, List<List<Integer>> list) {
if(l.size() == nums.length) {
list.add(new ArrayList<>(l));
return;
}
for(int i = 0; i < nums.length; i++) {
if(vis[i] == false) {
vis[i] = true;
l.add(nums[i]);
backpermute(nums, vis, l, list);
vis[i] = false;
l.remove(l.size()-1);
}
}
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
if(nums == null || nums.length == 0)
return list;
Arrays.sort(nums);
boolean[] vis = new boolean[nums.length];
backpermuteUnique(nums, vis, new ArrayList<>(), list);
return list;
}
private void backpermuteUnique(int[] nums, boolean[] vis, List<Integer> l, List<List<Integer>> list) {
if(l.size() == nums.length) {
list.add(new ArrayList<>(l));
return;
}
for(int i = 0; i < nums.length; i++) {
if(i != 0 && nums[i] == nums[i-1] && !vis[i-1])
continue;
if(vis[i])
continue;
vis[i] = true;
l.add(nums[i]);
backpermuteUnique(nums, vis, l, list);
vis[i] = false;
l.remove(l.size()-1);
}
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> list = new ArrayList<>();
if(k > n)
return list;
combineHelper(n, k, 1, new ArrayList<>(), list);
return list;
}
private void combineHelper(int n, int k, int index, List<Integer> l, List<List<Integer>> list) {
if(l.size() == k)
list.add(new ArrayList<>(l));
for(int i = index; i <= n; i++) {
l.add(i);
combineHelper(n, k, i+1, l, list);
l.remove(l.size()-1);
}
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
backtracksubset(nums,0,list,res);
return res;
}
public void backtracksubset(int[] nums,int position,List<Integer> list,List<List<Integer>> res){
res.add(new ArrayList<>(list));
for(int i=position;i<nums.length;i++){
list.add(nums[i]);
backtracksubset(nums,i+1,list,res);
list.remove(list.size()-1);
}
}
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
if(nums == null || nums.length == 0)
return list;
Arrays.sort(nums);
backsubsetsWithDup(nums, 0, new ArrayList<>(), list, new boolean[nums.length]);
return list;
}
private void backsubsetsWithDup(int[] nums, int index, List<Integer> l, List<List<Integer>> list, boolean[] vis) {
list.add(new ArrayList<>(l));
for(int i = index; i < nums.length; i++) {
if(i != 0 && nums[i] == nums[i-1] && !vis[i-1])
continue;
if(vis[i])
continue;
l.add(nums[i]);
vis[i] = true;
backsubsetsWithDup(nums, i+1, l, list, vis);
l.remove(l.size()-1);
vis[i] = false;
}
}
}
回溯
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
Arrays.sort(nums);
int sum = Arrays.stream(nums).sum();
if(sum % k != 0)
return false;
int average = sum / k;
int len = nums.length;
if(nums[len-1] > average)
return false;
boolean[] vis = new boolean[len];
for(int i = len-1; i > 0 && nums[i] == average; i--) {
vis[i] = true;
k--;
}
if(k == 1)
return true;
return subsetHelper(nums, k, 0, 0, average, vis);
}
private boolean subsetHelper(int[] nums, int k, int index, int curSum, int target, boolean[] vis) {
if(k == 1)
return true;
if(curSum == target)
return subsetHelper(nums, k-1, 0, 0, target, vis);
for(int i = index; i < nums.length; i++) {
if(vis[i] == true)
continue;
vis[i] = true;
if(subsetHelper(nums, k, i+1, curSum+nums[i], target, vis) == true)
return true;
vis[i] = false;
}
return false;
}
}
动态规划
递归
-
1
2
3
4
5
6
7
8public int shuta(int n, int[][] nums) {
for(int i = n-2; i >= 0; i--) {
for(int j = 0; j <= i; j++) {
nums[i][j] += Math.max(nums[i+1][j], nums[i+1][j+1]);
}
}
return nums[0][0];
} -
1
2
3
4
5
6
7
8
9
10
11
12public int muniu(int year) {
if(year < 4)
return year;
int[] dp = new int[55];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for(int i = 4; i <= year; i++) {
dp[i] = dp[i-1] + dp[i-3];
}
return dp[year];
} continue…
买卖股票
-
1
2
3
4
5
6
7
8
9
10
11public int maxProfit(int[] prices) {
int max = 0, min = Integer.MAX_VALUE;
for(int i = 0; i < prices.length; i++) {
if(prices[i] < min) {
min = prices[i];
} else if(prices[i]-min > max) {
max = prices[i]-min;
}
}
return max;
} -
1
2
3
4
5
6
7
8
9public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0)
return 0;
int max = 0;
for(int i = 1; i < prices.length; i++)
if(prices[i] > prices[i-1])
max += prices[i]-prices[i-1];
return max;
} -
1
2
3
4
5
6
7
8
9
10
11public int maxProfit(int[] prices) {
int firBuy = Integer.MIN_VALUE, firShell = 0;
int senBuy = Integer.MIN_VALUE, senShell = 0;
for(int p: prices){
firBuy = Math.max(firBuy, -p);
firShell = Math.max(firShell, firBuy + p);
senBuy = Math.max(senBuy, firShell - p);
senShell = Math.max(senShell, senBuy + p);
}
return senShell;
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public int maxProfit(int k, int[] prices) {
if(k < 1 || prices.length < 1)
return 0;
int[] buy = new int[k];
int[] shell = new int[k];
Arrays.fill(buy, Integer.MIN_VALUE);
Arrays.fill(shell, 0);
for(int p: prices){
for(int i = 0; i < k; i++){
if( i == 0){
buy[i] = Math.max(buy[i], -p);
shell[i] = Math.max(shell[i], buy[i] + p);
}else{
buy[i] = Math.max(buy[i], shell[i-1] - p);
shell[i] = Math.max(shell[i], buy[i] + p);
}
}
}
return shell[k-1];
} -
1
2
3
4
5
6
7
8
9
10
11public int maxProfit(int[] prices, int fee) {
if(prices == null || prices.length < 2)
return 0;
int buy = -prices[0];
int sell = 0;
for(int i = 1; i < prices.length; i++) {
buy = Math.max(buy, sell-prices[i]);
sell = Math.max(sell, buy + prices[i] -fee);
}
return sell;
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public int maxProfit(int[] prices) {
if(prices == null || prices.length < 2)
return 0;
int len = prices.length;
int[] no = new int[len];
int[] buy = new int[len];
int[] sell = new int[len];
sell[0] = no[0] = 0;
buy[0] = -prices[0];
for(int i = 1; i < len; i++) {
no[i] = sell[i-1];
sell[i] = Math.max(sell[i-1], buy[i-1]+prices[i]);
buy[i] = Math.max(buy[i-1], no[i-1]-prices[i]);
}
return Math.max(sell[len-1], no[len-1]);
}
数字
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public String add(String num1, String num2) {
if(num1 == null || num1.length() == 0)
return num2;
if(num2 == null || num2.length() == 0)
return num1;
int i = num1.length()-1, j = num2.length()-1;
int diff = 0;
StringBuilder sb = new StringBuilder();
while(i >= 0 || j >= 0 || diff > 0) {
int n1 = i >= 0 ? Integer.valueOf(num1.charAt(i--)-'0') : 0;
int n2 = j >= 0 ? Integer.valueOf(num2.charAt(j--)-'0') : 0;
sb.append((n1+n2+diff) % 10);
diff = (n1+n2+diff) /10;
}
return sb.reverse().toString();
} -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47public String mul(String num1, String num2) {
if(num1 == null || num1.length() == 0 || num2 == null || num2.length() == 0)
return "0";
char sign1 = num1.charAt(0);
char sign2 = num2.charAt(0);
char sign = '+';
if(sign1 == '+' || sign1 == '-') {
sign = sign1;
num1 = num1.substring(1);
}
if(sign2 == '+' || sign2 == '-') {
if((sign^sign2) != 0)
sign = '-';
else
sign = '+';
num2 = num2.substring(1);
}
int len1 = num1.length();
int len2 = num2.length();
char[] chars1 = new StringBuilder(num1).reverse().toString().toCharArray();
char[] chars2 = new StringBuilder(num2).reverse().toString().toCharArray();
int[] res = new int[len1+len2];
for(int i = 0; i < len1; i++) {
for(int j = 0; j < len2; j++) {
res[i+j] += (int)(chars1[i]-'0') * (int)(chars2[j]-'0'); // +=
}
}
for(int i = 0; i < len1+len2; i++) {
if(res[i] >= 10) {
res[i+1] += res[i]/10;
res[i] %= 10;
}
}
StringBuilder sb = new StringBuilder();
int i = res.length-1;
while(i >= 0 && res[i] == 0)
i--;
while(i >= 0) {
sb.append(res[i]);
i--;
}
if(sb.length() == 0)
return "0";
if(sign == '-')
sb.insert(0, '-');
return sb.toString();
} 字符串相减
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55public String subtract(String num1, String num2) {
if(num2 == null || num2.length() == 0)
return num1;
int len1 = num1.length();
int len2 = num2.length();
// 判断正负
boolean isPositive = true;
if(len1 < len2) {
isPositive = false;
} else if(len1 == len2) {
int i = 0;
while(i < len1 && num1.charAt(i) == num2.charAt(i))
i++;
if(num1.charAt(i) < num2.charAt(i))
isPositive = false;
}
// 计算
char[] chars1 = new StringBuilder(num1).reverse().toString().toCharArray();
char[] chars2 = new StringBuilder(num2).reverse().toString().toCharArray();
int maxLen = Math.max(len1, len2);
int[] res = new int[maxLen];
for(int i = 0; i < maxLen; i++) {
int n1 = i < len1 ? chars1[i]-'0' : 0;
int n2 = i < len2 ? chars2[i]-'0' : 0;
if(isPositive)
res[i] = n1-n2;
else
res[i] = n2-n1;
}
// 进位
for(int i = 0; i < maxLen-1; i++) {
if(res[i] < 0) {
res[i] += 10;
res[i+1] -= 1;
}
}
// 计算结果
StringBuilder sb = new StringBuilder();
int i = maxLen-1;
while(i >= 0 && res[0] == 0)
i--;
while(i >= 0) {
sb.append(res[i]);
i--;
}
if(sb.length() == 0)
return "0";
if(!isPositive)
sb.insert(0, '-');
return sb.toString();
}进制转换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20private static final String str="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
public int any2ten(String num, int b) {
int res = 0;
num = new StringBuilder(num).reverse().toString();
for(int i = 0; i < num.length(); i++) {
res += str.indexOf(num.charAt(i)+"") * Math.pow(b, i);
}
return res;
}
public String ten2any(int num, int b) {
StringBuilder sb = new StringBuilder();
while(num > 0) {
int index = num % b;
num /= b;
sb.append(str.charAt(index));
}
return sb.reverse().toString();
}
