LeetCode---Backtracking && DP
2024-09-05 11:45:15
**322. Coin Change
思路：动态规划，构造一个数组，存入当前index最少需要多少个coin
public int coinChange(int[] coins, int amount) {
if(coins == null || coins.length == 0 || amount <= 0) return 0;
//表示Index需要多少个coin
int[] dp = new int[amount + 1];
for(int i = 1; i < amount + 1; i++){
dp[i] = Integer.MAX_VALUE;
for(int j = 0; j < coins.length; j++){
if(coins[j] <= i && dp[i - coins[j]] != Integer.MAX_VALUE){
dp[i] = Math.min(dp[i],dp[i - coins[j]] + 1);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
377. Combination Sum IV
思路：构造一个数组，存入当前index能有几种组成方式
public int combinationSum4(int[] nums, int target) {
if(nums == null || nums.length == 0) return 0;
int[] dp= new int[target + 1];
dp[0] = 1;
for(int i = 1; i < target + 1; i++){
for(int j = 0; j < nums.length; j++){
//数组中提供了什么，就将小于target元素的组成种数加起来即可
if(i >= nums[j]) dp[i] += dp[i - nums[j]];
}
}
return dp[target];
}
51. N-Queens
思路：回溯，构造一个二维数组存solution，同时也判断每一次放Queen是否满足要求
public List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<List<String>>();
char[][] ans = new char[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
ans[i][j] = '.';
}
}
getResult(res,ans,0);
return res;
}
public void getResult(List<List<String>> res,char[][] ans,int k){
int n = ans.length;
if(k == n){
res.add(construct(ans));
return;
}
//k表示列，根据每一列进行搜索，因此列肯定不相同，因此下面不用判断列
for(int i = 0; i < n; i++){
if(isValid(i,k,ans)){
ans[i][k] = 'Q';
getResult(res,ans,k + 1);
ans[i][k] = '.';
}
}
}
public boolean isValid(int x,int y,char[][] ans){
for(int i = 0; i < ans.length; i++){
for(int j = 0; j < ans[0].length; j++){
if(ans[i][j] == 'Q' && (x - i == y - j || x - i == j - y || x == i)){
return false;
}
}
}
return true;
}
public List<String> construct(char[][] ans){
List<String> res = new ArrayList<String>();
for(int i = 0; i < ans.length; i++){
String s = new String(ans[i]);
res.add(s);
}
return res;
}
**131. Palindrome Partitioning
思路：回溯，每趟从start开始，判断若是Palindrome则存入，不是则继续循环
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
getResult(res,ans,s,0);
return res;
}
public void getResult(List<List<String>> res,List<String> ans,String s,int start){
if(start == s.length()){
res.add(new ArrayList<String>(ans));
return;
}
for(int i = start; i < s.length(); i++){
if(isPalindrome(s,start,i)){
ans.add(s.substring(start,i + 1));
getResult(res,ans,s,i + 1);
ans.remove(ans.size() - 1);
}
}
}
public boolean isPalindrome(String s,int low,int high){
while(low <= high){
if(s.charAt(low) != s.charAt(high)){
return false;
}
low++;
high--;
}
return true;
}
**416. Partition Equal Subset Sum
思路：首先根据数学关系可以判断sum一定是偶数，然后判断有没有子集之和等于sum / 2
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0) return true;
int sum = 0;
for(int i : nums){
sum += i;
}
if(sum % 2 != 0) return false;
sum /= 2;
//dp[i]表示i是否是数组子集和，若dp[j - nums[i]]是，那么dp[j]一定是
boolean[] dp = new boolean[sum + 1];
dp[0] = true;
for(int i = 0; i < nums.length; i++){
for(int j = sum; j >= nums[i]; j--){
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[sum];
}
**494. Target Sum
思路：根据数学关系：若将正数组合和负数组合分别表示为P和N，则P - N = S => P - N + P + N = S + P + N => 2*P = S + sum，转化为有多少个数组子集为P，即同题416
public int findTargetSumWays(int[] nums, int S) {
//若将正数组合和负数组合分别表示为P和N，则P - N = S => P - N + P + N = S + P + N => 2*P = S + sum，转化为有多少个数组子集为P
if(nums == null || nums.length == 0) return 0;
int sum = 0;
for(int i : nums){
sum += i;
}
return sum < S || (S + sum) % 2 != 0 ? 0 : dfs(nums,(S + sum) / 2);
}
public int dfs(int[] nums,int target){
int[] dp = new int[target + 1];
dp[0] = 1;
for(int i = 0; i < nums.length; i++){
for(int j = target; j >= nums[i]; j--){
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
139. Word Break
思路：动态规划，构造数组表示从当前分割之前的字符串在dict里是否存在
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for(int i = 1; i < s.length() + 1; i++){
for(int j = 0; j < i; j++){
if(dp[j] && wordDict.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
总结
70. Climbing Stairs:动态规划，形成一个斐波那契数列，用递归会超时
77. Combinations:回溯，每趟从头开始循环
357. Count Numbers with Unique Digits:数学规律：一位为10个，两位为9*9个，三位为9*9*8个...
198. House Robber:动态规划，递归方程式：dp[i] = Math.max(nums[i] + dp[i - 2],dp[i - 1]);
343. Integer Break:数学规律：4=2*2 5<2*3...则一定按2或3来分，而6=2+2+2=3+3 3*3>2*2*2，因此按3分直到num小于4
52. N-Queens II：同N-Queens，设置一个全局变量，每次符合则加一，注意不能是static，否则每次运行都会将前面运行过的结果算进去
46. Permutations:回溯，每趟从头开始，需要判断有没有重复
60. Permutation Sequence：同Permutations，只不过会超时，需要用数学手段通过k来判断字符的具体顺序
303. Range Sum Query - Immutable:动态规划：递归方程式为dp[i] = dp[i - 1] + nums[i]
304. Range Sum Query 2D - Immutable：动态规划，先算边界，再算中间
训练
413. Arithmetic Slices:由于等差数列要求必须连续，则每次计算以当前元素结尾的等差数列有几个（比上一次多1），如果不连续则重置，将所有结果相加
213. House Robber II:方法和House Robber一样，只是要分两次求最大值，因为第一家和最后一家不能同时偷，两次调用函数时注意挪位问题
368. Largest Divisible Subset:构造一个数组dp存入当前num结尾时的序列长度，然后取得最大长度的Index，同时判断整除关系和dp[index]是否符合条件依次获得序列的每个元素
47. Permutations II：同Permutations，只是要去重
**467. Unique Substrings in Wraparound String:动态规划，同413，每次计算以当前字符结尾的连续数列有几个（比上一次多1），如果不连续则重置，将所有结果相加
提示
1.字符运算成整形->'c' - 'a' = 2 整形运算成字符 (char)('0' + 1) = '1'
2.判断字符串中是否含有字符：s.indexOf(char)，不能用s.contains()->参数为charSequence最新文章
- 订货（bzoj 2424）
- JavaScript字符串的操作-课堂笔记
- canvas游戏之贪食蛇
- Flask服务入门案例
- js中的命名规范
- Windows下cmd的替代软件——PowerCmd
- wpf RadioButton控件的一个bug，onpropertychanged后会修改旧属性的值
- 【转】char *str 和 char str[]的区别
- RHEL5.8安装Sybase 15.7_x86_64
- android编译系统的makefile文件Android.mk写法如下
- Android程序检测网络是否可用
- MyBatis 批量修改记录
- 学习Cocos2d的博客 --推荐
- Chrome 浏览器报 filed to load resource:net err cache read failure 错误：
- maven使用jstl表达式和The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar files deployed with this application解决
- python拓扑排序
- Cocos2D iOS之旅:如何写一个敲地鼠游戏(六):放置地鼠
- LeetCode之“排序”：Largest Number
- css_css 盒子水平居中 垂直居中
- java利用poi解析excel文件