写于2019年5月25日
文章目录
[39. 组合总和](https://leetcode.com/problems/combination-sum/)① 题目描述② 使用回溯法
[42. 接雨水](https://leetcode.com/problems/trapping-rain-water/)① 题目描述② 暴力法（按列遍历）③ 使用堆栈
[46. 全排列](https://leetcode.com/problems/permutations/)① 题目描述② 回溯法③ 交换法（实质回溯，`Hot`）④ 带重复数字的全排列——[leetcode的47题](https://leetcode.com/problems/permutations-ii/)
39. 组合总和
① 题目描述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。说明： 所有数字（包括 target）都是正整数。 解集不能包含重复的组合。示例 1:
输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ]
示例 2:
输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]
② 使用回溯法
以示例2为例，第一次加入了2，还可以加入2，直到里面的数字总和>= target。如果等于target将其加入result中，否则直接返回。返回之后，删除最后一个2，尝试添加下一个数字3。总体感觉： 回溯，就是向前走不动了，我就撤销最后一步继续向前，直到遍历完所有的结果。注意： 向result中添加一个结果时，要new ArrayList<>(temp)，否则添加的仍然为temp所指向的内存，导致最后结果为[ [], [] ]（以示例1为例）。代码如下：
List
<List
<Integer>> result
= new ArrayList<>();
public List
<List
<Integer>> combinationSum(int[] candidates
, int target
) {
backtrace(new ArrayList<>(), 0, target
, candidates
);
return result
;
}
public void backtrace(List
<Integer> temp
, int start
, int remain
, int[] nums
) {
if (remain
< 0) {
return;
}
if (remain
== 0) {
result
.add(new ArrayList<>(temp
));
return;
}
for (int i
= start
; i
< nums
.length
; i
++) {
temp
.add(nums
[i
]);
backtrace(temp
, i
, remain
- nums
[i
], nums
);
temp
.remove(temp
.size() - 1);
}
}
42. 接雨水
① 题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
② 暴力法（按列遍历）
当前列能接水，由左边最高列、右边最高列的较小值减去当前列的高度决定（木桶原理）。如果左边最高列、右边最高列的较小值小于当前列的高度，直接置为0，否则为二者的差值。示意图如下，计算周围的列高度小于左右最高列的较小值，由于有另一较高列的支持，该行还是装Math.min(max_left, max_right) - height[i]的雨水： 代码如下：
public int trap(int[] height
) {
int size
= height
.length
;
int sum
= 0;
for (int i
= 1; i
< size
- 1; i
++) {
int max_left
= 0, max_right
= 0;
for (int j
= i
- 1; j
>= 0; j
--) {
if (max_left
< height
[j
]) {
max_left
= height
[j
];
}
}
for (int j
= i
+ 1; j
< size
; j
++) {
if (max_right
< height
[j
]) {
max_right
= height
[j
];
}
}
int min
= Math
.min(max_left
, max_right
);
sum
+= (min
- height
[i
] > 0) ? (min
- height
[i
]) : 0;
}
return sum
;
}
③ 使用堆栈
具体分析见博客，代码如下：
public int trap(int[] height
) {
int sum
= 0;
int current
= 0;
Stack
<Integer> stack
= new Stack<>();
while (current
< height
.length
) {
while (!stack
.isEmpty() && height
[current
] > height
[stack
.peek()]) {
int h
= height
[stack
.peek()];
stack
.pop();
if (stack
.isEmpty()) {
break;
}
int dis
= current
- stack
.peek() - 1;
int min
= Math
.min(height
[stack
.peek()], height
[current
]);
sum
= sum
+ dis
* (min
- h
);
}
stack
.push(current
);
current
++;
}
return sum
;
}
46. 全排列
① 题目描述
给定一个没有重复数字的序列，返回其所有可能的全排列。示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
② 回溯法
当temp中含有当前元素时，则继续下一次循环，保证添加的元素不重复。当temp构造完成，返回，删除一次temp中刚添加的元素。代码如下：
public List
<List
<Integer>> permute(int[] nums
) {
List
<List
<Integer>> result
= new ArrayList<>();
backtrace(result
, new ArrayList<>(), nums
);
return result
;
}
public void backtrace(List
<List
<Integer>> result
, List
<Integer> temp
, int[] nums
) {
if (temp
.size() == nums
.length
) {
result
.add(new ArrayList<>(temp
));
return;
}
for (int i
= 0; i
< nums
.length
; i
++) {
if (temp
.contains(nums
[i
])) {
continue;
}
temp
.add(nums
[i
]);
backtrace(result
, temp
, nums
);
temp
.remove(temp
.size() - 1);
}
}
③ 交换法（实质回溯，Hot）
代码如下：
public List
<List
<Integer>> permute(int[] nums
) {
List
<List
<Integer>> result
= new ArrayList<>();
helper(result
, nums
, 0);
return result
;
}
public void helper(List
<List
<Integer>> result
, int[] nums
, int current
) {
if (current
== nums
.length
) {
List
<Integer> temp
= new ArrayList<>();
for (int i
= 0; i
< nums
.length
; i
++) {
temp
.add(nums
[i
]);
}
result
.add(temp
);
}
for (int i
= current
; i
< nums
.length
; i
++) {
swap(nums
, i
, current
);
helper(result
, nums
, current
+ 1);
swap(nums
, i
, current
);
}
}
public void swap(int[] nums
, int i
, int j
) {
int temp
= nums
[i
];
nums
[i
] = nums
[j
];
nums
[j
] = temp
;
}
④ 带重复数字的全排列——leetcode的47题
通过hashSet存储数字，如果是重复数字则不进行全排序。
public void helper(List
<List
<Integer>> result
, int[] nums
, int current
) {
if (current
== nums
.length
) {
List
<Integer> temp
= new ArrayList<>();
for (int i
= 0; i
< nums
.length
; i
++) {
temp
.add(nums
[i
]);
}
result
.add(temp
);
}
Set
<Integer> set
=new HashSet<>();
for (int i
= current
; i
< nums
.length
; i
++) {
if(!set
.contains(nums
[i
])){
set
.add(nums
[i
]);
swap(nums
, i
, current
);
helper(result
, nums
, current
+ 1);
swap(nums
, i
, current
);
}
}
}
