回溯
class Solution {
/**
回溯问题套路模板
bactracing(nums, startIndex)
*/
List<List<Integer>> res = new ArrayList();
List<Integer> path = new ArrayList();
public List<List<Integer>> permute(int[] nums) {
if(nums.length == 0 || nums == null) {
return res;
}
backtracing(nums, 0);
return res;
}
public void backtracing(int[] nums, int startIndex) {
if(path.size() == nums.length) {
res.add(new ArrayList(path));
return;
}
for(int i = 0; i < nums.length; i++) {
if(!path.contains(nums[i])) {
path.add(nums[i]);
backtracing(nums, i + 1);
path.remove(path.size() - 1);
}
}
}
}
class Solution {
/**
和上一题的区别就是，少加一步判断
for循环从startIndex开始
*/
List<List<Integer>> res = new ArrayList();
List<Integer> path = new ArrayList();
public List<List<Integer>> subsets(int[] nums) {
if(nums.length == 0 || nums == null) {
return res;
}
Arrays.sort(nums);
backtracing(nums, 0);
return res;
}
public void backtracing(int[] nums, int startIndex) {
if(!res.contains(path)) {
res.add(new ArrayList(path));
}
for(int i = startIndex; i < nums.length; i++) {
if(!path.contains(nums[i])) {
path.add(nums[i]);
backtracing(nums, i + 1);
path.remove(path.size() - 1);
}
}
}
}
class Solution {
/**
先创建一个数字和字母对应的hashmap
回溯的时候，遍历两个字符串
*/
List<String> res = new ArrayList();
StringBuffer path = new StringBuffer();
HashMap<Character, String> map = new HashMap();
public List<String> letterCombinations(String digits) {
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
if(digits == null ||digits.length() == 0) {
return res;
}
backtracing(digits, 0);
return res;
}
public void backtracing(String digits, int startIndex) {
if(path.length() == digits.length()) {
res.add(path.toString());
return;
}
char digit = digits.charAt(startIndex);
String s = map.get(digit);
char[] ch = s.toCharArray();
for(char c: ch) {
path.append(c);
backtracing(digits, startIndex + 1);
path.deleteCharAt(path.length() - 1);
}
}
}
class Solution {
/**
可以被重复选取
*/
List<List<Integer>> res = new ArrayList();
List<Integer> path = new ArrayList();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backtracing(candidates, target, 0);
return res;
}
public void backtracing(int[] candidates, int target, int start) {
if(sum(path) == target) {
res.add(new ArrayList(path));
return;
}
else if(sum(path) > target) {
return;
}
// #############################################
// 其他方式?
for(int i = start; i < candidates.length; i++) {
path.add(candidates[i]);
backtracing(candidates, target, i);
path.remove(path.size() - 1);
}
}
public int sum(List<Integer> path) {
int sum = 0;
for(int i = 0; i < path.size(); i++) {
sum += path.get(i);
}
return sum;
}
}
class Solution {
/**
left和right分别表示左括号和右括号数量
*/
List<String> res = new ArrayList();
StringBuffer path = new StringBuffer();
public List<String> generateParenthesis(int n) {
backtracing(n, 0, 0);
return res;
}
public void backtracing(int n, int left, int right) {
if(path.length() == n * 2) {
res.add(path.toString());
return;
}
if(left < n) {
path.append("(");
backtracing(n, left + 1, right);
path.deleteCharAt(path.length() - 1);
}
if(right < left) {
path.append(")");
backtracing(n, left, right + 1);
path.deleteCharAt(path.length() - 1);
}
}
}
贪心算法
class Solution {
/**
0 1
dp[i]表示第i天买入 or 卖出
买入 dp[i][0] = dp[i - 1][0], dp[i - 1][1] + prices[i];
dp[i][1] = dp[i - 1][1], -prices[i]
*/
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][1] = -prices[0];
for(int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[n - 1][0];
}
}
class Solution {
/**
朴实无华的想法不太对
boolean dp[i]表示可以第i个位置是可以到达的
dp[i] = dp[i - 1] ? dp[i - 1] >= 1，dp[i] = true ?
##################################################
dp[i]表示第i个位置可以跳跃的最远距离？
dp[i] i + nums[i]
*/
public boolean canJump(int[] nums) {
int[] dp = new int[nums.length];
if(nums.length == 0 || nums == null) {
return false;
}
dp[0] = nums[0];
// 0 1 2 3 4
// 2,3,1,1,4
// 2,4,4,4,8
// 0 1 2
// 0 2 2
// 0 x
for(int i = 1; i < dp.length; i++) {
if(dp[i - 1] < i) {
return false;
}
dp[i] = Math.max(dp[i - 1], i + nums[i]);
if(dp[i] >= nums.length - 1) {
return true;
}
}
return dp[dp.length - 1] >= nums.length - 1;
}
}
class Solution {
/**
dp[i]表示跳跃到位置i的最小跳跃次数
感觉像上一题那样直接求出dp[i]
然后看变化了几次？
*/
public int jump(int[] nums) {
int jump = 0;
int maxdistance = 0;
int index = 0;
for(int i = 0; i < nums.length - 1; i++) {
maxdistance = Math.max(i + nums[i], maxdistance);
if(index == i) {
jump++;
index = maxdistance;
}
}
return jump;
}
}
class Solution {
/**
记录s中所有字母出现的最后一个位置
用int[26]记录
每次遍历更新end
end - start + 1
*/
public List<Integer> partitionLabels(String s) {
int[] lastIndex = new int[26];
List<Integer> list = new ArrayList();
for(int i = 0; i < s.length(); i++) {
lastIndex[s.charAt(i) - 'a'] = i;
}
int start = 0;
int end = 0;
for(int i = 0; i < s.length(); i++) {
end = Math.max(end, lastIndex[s.charAt(i) - 'a']);
if(end == i) {
list.add(end - start + 1);
start = end + 1;
}
}
return list;
}
}
