排列专题：
首先基本功就是全排列，全排列又分，含重复元素和不含重复元素。
解决全排列的方法又分为SWAP法，和VISITED数组法。
SWAP法的核心就是，先针对队列里第一个元素，每个全换一遍。然后把剩下的队列当做子问题递归。这样我们就需要维护一个POS指针。下一个递归从POS开始。
VISITED数组法，就是用一个数组记录哪些元素已经使用了。然后每一层递归I都从0-n,随后根据VISITED数组判断是否CONTINUE；
https://leetcode.com/problems/permutations-ii/description/
SWAP法
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
help(nums,0,new ArrayList<>());
return res;
}
private void help(int[] A,int pos,List<Integer> cur) {
if(pos == A.length){
res.add(new ArrayList<>(cur));
}
for(int i = pos; i < A.length; i++){
swap(A,i,pos);
cur.add(A[pos]);
help(A,pos+1,cur);
cur.remove(cur.size()-1);
swap(A,i,pos);
}
}
private void swap(int[] A,int i,int j){
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
VISITED数组
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
seen = new boolean[nums.length];
help(nums,new ArrayList<>());
return res;
}
boolean[] seen;
private void help(int[] A,List<Integer> cur) {
if(cur.size() == A.length){
res.add(new ArrayList<>(cur));
}
for(int i = 0; i < A.length; i++){
if(seen[i]) continue;
seen[i] = true;
cur.add(A[i]);
help(A,cur);
cur.remove(cur.size()-1);
seen[i] = false;
}
}
下面我们讨论，有重复元素的全排列。
如果用上面的SWAP法，那么即使排序了，也会因为SWAP，后面元素的顺序不再有序。那么递归不变量就变了。也就是子问题不再有序，需要重新排序。或者我们需要额外一个SET数组来去除重复。
先讲一下如果一个数组是有序的，我们就可以根据I>pos, A[i]==A[i-1] 来防止产生重复的解。也就是多个一样的数，我们只取第一个。
但是数组无序这种做法就失效了。
所以，我们要开一个SET数组，把已经用过的值存进去，如果下次遇到重复的就CONTINUE；
swap法
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
help(nums,0,new ArrayList<>());
return res;
}
private void help(int[] A,int pos,List<Integer> cur) {
if(pos == A.length){
res.add(new ArrayList<>(cur));
}
Set<Integer> s = new HashSet<>();
for(int i = pos; i < A.length; i++){
if(s.contains(A[i])) continue;
swap(A,i,pos);
cur.add(A[pos]);
s.add(A[pos]);
help(A,pos+1,cur);
cur.remove(cur.size()-1);
swap(A,i,pos);
}
}
private void swap(int[] A,int i,int j){
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
visted法
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
seen = new boolean[nums.length];
help(nums,new ArrayList<>());
return res;
}
boolean[] seen;
private void help(int[] A,List<Integer> cur) {
if(cur.size() == A.length){
res.add(new ArrayList<>(cur));
}
for(int i = 0; i < A.length; i++){
if(seen[i]) continue;
seen[i] = true;
cur.add(A[i]);
help(A,cur);
cur.remove(cur.size()-1);
seen[i] = false;
}
}
下一个排列
https://www.lintcode.com/zh-cn/problem/next-permutation/#
这道题我们需要先观察。
比如1234,下一个排列是1243. 我们可以想到把最后面有序的一对，交换一下即可。
随后思考。4312-》4321WORK；
那如果最后一对是逆序的如
1243，这时我们该怎么处理。
答案是1324。它是怎么来的呢？我们需要在2 后面的数里 找到最小的，但是要比2大的，和2交换下。就是1342，然后对2位置后面所有的数按从小到大的顺序排序。
所以我们就可以通过不断在后方扩大窗口，并且从最后一个数开始试，找到第一个i 和 J 使得NUMS[I] < NUMS[J] ，然后交换。 然后排序。我们可以明确I之后的数一定是从大到小的。所以最小的一定是从后往前来的。
public int[] nextPermutation(int[] nums) {
int l = nums.length;
for(int i = l-1;i>=0;i--){
for(int j=l-1;j>i;j--){
if(nums[i]<nums[j]){
swap(nums,i,j);
Arrays.sort(nums,i+1,l);
return nums;
}
}
}
Arrays.sort(nums);
return nums;
}
private void swap(int[] A,int i,int j){
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
上一个排列
https://www.lintcode.com/zh-cn/problem/previous-permutation/
4321, 上一个是4312.我们不难发现，需要再最后去找第一个逆序大小的PAIR。
如果是顺序的。2134，上一个是1432.我们需要找到第一个逆序对，然后交换，然后把剩余的数按倒序排。
public List<Integer> previousPermuation(List<Integer> nums) {
int l = nums.size();
for(int i = l-1;i>=0;i--){
for(int j=l-1;j>i;j--){
if(nums.get(i)>nums.get(j)){
swap(nums,i,j);
Collections.sort(nums.subList(i+1,l),Collections.reverseOrder());
return nums;
}
}
}
Collections.sort(nums,Collections.reverseOrder());
return nums;
}
private void swap(List<Integer> A,int i,int j){
int tmp = A.get(i);
A.set(i,A.get(j));
A.set(j,tmp);
}
197. 排列序号
https://www.lintcode.com/zh-cn/problem/permutation-index/
这道题，主要就是要看，当前这个位置，右边有多少个数比它小。我们需要构造一个阶乘数组，和一个右边多少个比它小的数组。
随后解就是遍历每一个位置。用右边N个比它小的N*阶乘（右边长度）
public long permutationIndex(int[] A) {
int l = A.length;
long[] f = new long[l+1];
f[1] = 1;
for(int i = 2; i<=l; i++){
f[i] = f[i-1]*i;
}
int[] smallC = new int[l];
for(int i = l - 1; i > 0; i--){
for(int j = 0;j<i;j++){
if(A[j]>A[i]) smallC[j]++;
}
}
long res = 0;
for(int i=0;i<l;i++){
res+=smallC[i]*f[l-i-1];
}
return res+1;
}
198. Permutation Index II
https://www.lintcode.com/en/problem/permutation-index-ii/
有了前一题的基础，我们只需要去除那些重复的解的序号。我们假设有2个2.
那么在排列里。会有2a，2b. 2b,2a. 这2个是重复的，所以我们需要去除21
如果有3个2. 同理需要去除32*1； 如果有2个2,2个3. 我们需要去除（2连在一起）2 * 2（3连在一起）。
那么我们就用一个HASHMAP来记录重复，然后从后往前生成解。
public long permutationIndexII(int[] A) {
int l = A.length;
long res = 0;
long f = 1,smallC=1,multi = 1;
Map<Integer,Integer> c = new HashMap<>();
for(int i = l - 1; i >= 0; i--){
if(c.containsKey(A[i])){
c.put(A[i],c.get(A[i])+1);
multi *= c.get(A[i]);
}else{
c.put(A[i],1);
}
smallC = 0;
for(int j = i+1; j < l; j++){
if(A[i]>A[j]) smallC++;
}
res += f*smallC/multi;
f = f*(l-i);
}
return res+1;
}
组合篇
135. 数字组合
https://www.lintcode.com/zh-cn/problem/combination-sum/#
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(candidates,target,0,new ArrayList<>());
return res;
}
private void dfs(int[] A,int t,int pos,List<Integer>cur) {
if(t == 0) res.add(new ArrayList<>(cur));
for (int i = pos; i < A.length; i++) {
if(A[i]>t) break;
cur.add(A[i]);
dfs(A,t-A[i],i,cur);
cur.remove(cur.size()-1);
}
}
153. 数字组合 II
https://www.lintcode.com/zh-cn/problem/combination-sum-ii/#
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(candidates,target,0,new ArrayList<>());
return res;
}
private void dfs(int[] A,int t,int pos,List<Integer>cur) {
if(t == 0) res.add(new ArrayList<>(cur));
for (int i = pos; i < A.length; i++) {
if(A[i]>t) break;
if(i>pos && A[i]==A[i-1]) continue;
cur.add(A[i]);
dfs(A,t-A[i],i+1,cur);
cur.remove(cur.size()-1);
}
}
491. Increasing Subsequences
https://leetcode.com/problems/increasing-subsequences/description/
这道题就是选或者不选。然后遍历所有可能性。一旦一个解长度大于2，就加入到解集。其次，递归的循环里都需要去重，这里因为不能给原数组排序。我们需要一个SET，记入曾经出现过的数，如果又出现了，就跳过这个数来去重。
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
int l = nums.length;
Set<Integer> s = new HashSet<>();
for (int i = 0; i < l; i++) {
if(s.contains(nums[i])) continue;
s.add(nums[i]);
List<Integer> cur = new ArrayList<>();
cur.add(nums[i]);
dfs(i+1,nums,cur);
cur.remove(cur.size()-1);
}
return res;
}
private void dfs(int pos, int[] nums, List<Integer> cur){
if(cur.size()>=2) res.add(new ArrayList<>(cur));
Set<Integer> s = new HashSet<>();
for(int i=pos;i<nums.length;i++){
if(s.contains(nums[i])) continue;
s.add(nums[i]);
if(nums[i]>=cur.get(cur.size()-1)){
cur.add(nums[i]);
dfs(i+1,nums,cur);
cur.remove(cur.size()-1);
}
}
}
LeetCode
332. Reconstruct Itinerary
https://leetcode.com/problems/reconstruct-itinerary/description/
首先构造一个USED MAP，每个票的次数。随后把临街点都初始好。随后开始从JFK 按字典序 进行DFS 加回溯。
List<String> res = new ArrayList<>();
int l;
public List<String> findItinerary(String[][] tickets) {
l = tickets.length;
Map<String,Set<String>> neis = new HashMap<>();
for(String[] t : tickets){
used.put(t[0]+"->"+t[1],used.getOrDefault(t[0]+"->"+t[1],0)+1);
if(neis.containsKey(t[0])){
neis.get(t[0]).add(t[1]);
}else{
TreeSet<String> s = new TreeSet<>();
s.add(t[1]);
neis.put(t[0],s);
}
}
res.add("JFK");
dfs("JFK",neis);
return res;
}
Map<String,Integer> used = new HashMap<>();
private boolean dfs(String cur,Map<String,Set<String>> neis){
if(res.size()==l+1) return true;
for(String nei : neis.getOrDefault(cur,new TreeSet<>())){
String key = cur+"->"+nei;
if(used.get(key) == 0) continue;
res.add(nei);
used.put(key,used.get(key)-1);
if(dfs(nei,neis)) return true;
used.put(key,used.get(key)+1);
res.remove(res.size()-1);
}
return false;
}
210. Course Schedule II
https://leetcode.com/problems/course-schedule-ii/description/
dfs 拓扑排序，需要一个VISTED SET。然后一直遍历到最深。那么最深的那个元素放在解集的底部。同时加入到VISITED。一个元素所有邻居 都遍历过了，就可以加入到解集。随后放进VISITED里。
int[] ans;
boolean[] used;
int p;
boolean hasCyc = false;
List<Set<Integer>> gra;
public int[] findOrder(int numCourses, int[][] prerequisites) {
used = new boolean[numCourses];
ans = new int[numCourses];
p = numCourses-1;
gra = new ArrayList<>();
for(int i = 0; i < numCourses; i++){
gra.add(new HashSet<>());
}
for(int[] p : prerequisites){
gra.get(p[1]).add(p[0]);
}
for(int i = 0; i < numCourses; i++){
if(used[i]) continue;
dfs(i,new boolean[numCourses]);
}
if(hasCyc) return new int[0];
return ans;
}
private void dfs(int i,boolean[] hasCycle){
hasCycle[i] = true;
used[i] = true;
for(int nei : gra.get(i)){
if(hasCycle[nei]){
hasCyc=true;
return;
}
if(used[nei]) continue;
dfs(nei,hasCycle);
hasCycle[nei] = false;
}
ans[p--] = i;
}
- Minesweeper
https://leetcode.com/problems/minesweeper/description/
dfs模拟题
int[][] steps = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}};
public char[][] updateBoard(char[][] board, int[] click) {
int h = board.length;
int l = board[0].length;
int y = click[0];
int x = click[1];
char c = board[y][x];
if(c == 'M'){
board[y][x] = 'X';
return board;
}else{
int m = 0;
for(int[] step : steps){
int ny = y+step[0];
int nx = x+step[1];
if(nx<0 || ny<0 || ny==h || nx==l ) continue;
if(board[ny][nx] == 'M') m++;
}
if(m == 0){
board[y][x] = 'B';
for(int[] step : steps){
int ny = y+step[0];
int nx = x+step[1];
if(nx<0 || ny<0 || ny==h || nx==l ) continue;
if(board[ny][nx] == 'E')
updateBoard(board,new int[]{ny,nx});
}
return board;
}else{
board[y][x] = (char)(m+'0');
return board;
}
}
}
337. House Robber III
https://leetcode.com/problems/house-robber-iii/description/
这道题想起来，就是要么用第一个，然后下面一层的肯定就不能用。要么不用这一个。下面一层的随意，可用可不用。这2个CASE里面取大的。
先给一个传统的递归写法，但是超时了，我加了记忆化搜索过了。
public int rob(TreeNode root) {
return Math.max(dfs(root,true),dfs(root,false));
}
Map<String,Integer> m = new HashMap<>();
private int dfs(TreeNode r,boolean used){
if(r == null) return 0;
if(m.containsKey(r+""+used)) return m.get(r+""+used);
int l2 = dfs(r.left,false);
int r2 = dfs(r.right,false);
int res = 0;
if(used){
res = r.val+l2+r2;
}else{
res = Math.max(dfs(r.left,true),l2)+
Math.max(dfs(r.right,true),r2);
}
m.put(r+""+used,res);
return res;
}
然后我们可以反向生成解集，然后每一次递归都要求返回2个值，第一个位置放着用的解，第二个位置放着不用的解。这样性能会提升更多。
public int rob(TreeNode root) {
int[] res = dfs(root);
return Math.max(res[0],res[1]);
}
private int[] dfs(TreeNode r){
if(r == null) return new int[]{0,0};
int[] l2 = dfs(r.left);
int[] r2 = dfs(r.right);
return new int[]{r.val+l2[1]+r2[1], Math.max(l2[0],l2[1])+Math.max(r2[0],r2[1])};
}
494. Target Sum
https://leetcode.com/problems/target-sum/description/
记忆化搜索DFS
Map<Integer,Integer> dp = new HashMap<>();
public int findTargetSumWays(int[] nums, int S) {
if(nums.length==0) return 0;
return dfs(nums,1,S-nums[0])+dfs(nums,1,S+nums[0]);
}
private int dfs(int[] nums,int i,int s){
if(i == nums.length){
if(s==0) return 1;
return 0;
}
int key = (s<<5)+i;
if(dp.containsKey(key)) return dp.get(key);
int ans = dfs(nums,i+1,s-nums[i])+dfs(nums,i+1,s+nums[i]);
dp.put(key,ans);
return ans;
}
785. Is Graph Bipartite?
https://leetcode.com/problems/is-graph-bipartite/description/
先随机选取一个点，DFS，一个染红，一个染蓝。然后看有没有冲突。没冲突返回TRUE，有冲突返回FALSE。
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] colors = new int[n];
for(int i = 0; i < n; i++){
if(colors[i]!=0) continue;
if(!dfs(i,graph,-1,colors)) return false;
}
return true;
}
private boolean dfs(int i,int[][] graph,int colored,int[] colors) {
colors[i] = colored;
for(int j=0; j<graph[i].length; j++){
int nei = graph[i][j];
if(colors[nei]==0){
if(!dfs(nei,graph,-colored,colors)) return false;
}else if(colors[nei] == colored) return false;
}
return true;
}
756. Pyramid Transition Matrix
https://leetcode.com/problems/pyramid-transition-matrix/description/
模拟题，
第一步，构造图，前2个字符为KEY，set<char> 为VALUE；
第二步，遍历bottom,生成所有可能的上一层的BOTTOM
第三步，DFS，针对每一种可能的bottom,继续生成所有可能的上一层的BOTTOM，如果BOTTOM的LENGTH 为1就RETURN TRUE；
第四步，每一种可能的BOTTOM，dfs后都RETURN FALSE，就return FALSE
第5步，写生成所有可能的BOTTOM 的代码，也是一个DFS。每个集合里选一个字母，构建所有解集。
public boolean pyramidTransition(String bottom, List<String> allowed) {
Map<String,Set<Character>> gra = new HashMap<>();
for(String s : allowed){
String key = s.substring(0,2);
char val = s.charAt(2);
if(gra.containsKey(key)) gra.get(key).add(val);
else{
Set<Character> cur = new HashSet<>();
cur.add(val);
gra.put(key,cur);
}
}
List<Set<Character>> pre = new ArrayList<>();
for(int i=2;i<=bottom.length();i++){
String key = bottom.substring(i-2,i);
if(gra.get(key) == null) return false;
pre.add(gra.get(key));
}
return dfs(convert(pre),gra);
}
private boolean dfs(List<String> pre, Map<String,Set<Character>> gra){
if(pre.get(0).length()==1) return true;
for(String cur : pre){
List<Set<Character>> pre2 = new ArrayList<>();
int i=2;
for(;i<=cur.length();i++){
String key = cur.substring(i-2,i);
if(gra.get(key) == null){
break;
}
pre2.add(gra.get(key));
}
if(i!=cur.length()+1) continue;
if(dfs(convert(pre2),gra)) return true;
}
return false;
}
private List<String> convert(List<Set<Character>> pre){
List<String> res = new ArrayList<>();
dfs2(0,pre,"",res);
return res;
}
private void dfs2(int i,List<Set<Character>> pre,String cur,List<String> res){
if(i == pre.size()) res.add(cur);
else{
for(char c : pre.get(i)){
dfs2(i+1,pre,cur+c,res);
}
}
}
638. Shopping Offers
https://leetcode.com/problems/shopping-offers/description/
dfs暴力搜索所有解。
如果这张优惠券可以用，先用了之后，再DFS剩余的NEEDS。然后不用这张优惠券，去看用下一张会不会更便宜。
public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
return help(price,special,needs);
}
private int help(List<Integer> price, List<List<Integer>> special, List<Integer> needs){
int min = dot(price,needs);
if(min == 0) return 0;
for(List<Integer> spe : special){
int i=0;
List<Integer> needs2 = new ArrayList<>(needs);
for(;i<spe.size()-1;i++){
if(needs2.get(i)<spe.get(i)) break;
needs2.set(i,needs2.get(i)-spe.get(i));
}
if(i == spe.size()-1){
min = Math.min(min,spe.get(i)+help(price,special,needs2));
}
}
return min;
}
private int dot(List<Integer> price,List<Integer> needs){
int res = 0;
for(int i=0;i<price.size();i++) {
res += price.get(i)*needs.get(i);
}
return res;
}
698. Partition to K Equal Sum Subsets
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/
这道题,和之前做过的一道题很像。就是构建每一个要构成解集的大小的数组。然后遍历每一个数字，使得所有的解集为0.
DFS来做。如果完不成，就RETURN FALSE
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int num : nums){
sum += num;
}
if(sum % k != 0) return false;
int avg = sum/k;
Arrays.sort(nums);
int l = nums.length;
if(nums[l-1]>avg){
return false;
}
while(nums[l-1] == avg){
l--;
k--;
}
int[] ans = new int[k];
Arrays.fill(ans,avg);
return dfs(nums,ans,l-1);
}
private boolean dfs(int[] n,int[] ans,int pos){
if(pos<0) return true;
for(int j=0;j<ans.length;j++){
if(n[pos]<=ans[j]){
ans[j]-=n[pos];
if(dfs(n,ans,pos-1)){
return true;
}
ans[j]+=n[pos];
}
}
return false;
}
473. Matchsticks to Square
https://leetcode.com/problems/matchsticks-to-square/description/
做法和上一题一样
int avg;
boolean[] used;
public boolean makesquare(int[] nums) {
int sum = 0;
int i = 0;
int l = nums.length;
if(l < 3) return false;
used = new boolean[l];
for(int num : nums){
sum += num;
}
if(sum%4!=0) return false;
avg = sum/4;
Arrays.sort(nums);
return dfs(nums,new int[]{avg,avg,avg,avg},l-1);
}
private boolean dfs(int[] ns,int[] egs,int pos){
if(pos == -1){
return egs[0]+egs[1]+egs[2]+egs[3] == 0;
}
for(int i=0;i<4;i++){
if(ns[pos]<=egs[i]){
egs[i] = egs[i]-ns[pos];
if(dfs(ns,egs,pos-1)) return true;
egs[i] = egs[i]+ns[pos];
}
}
return false;
}
909. Android解锁模式
https://www.lintcode.com/problem/android-unlock-patterns/
暴力DFS，枚举所有走法。
dir2 为跳跃走法，要求中间跳跃的点是被用过的。
public int numberOfPatterns(int m, int n) {
M = m;
N = n;
dfs(0,0,1);
int k = res;
res = 0;
dfs(0,1,1);
int k2 = res;
res = 0;
dfs(1,1,1);
int k3 = res;
return 4*k+4*k2+k3;
}
int M;
int N;
int[][] dir = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1},
{1,2},{1,-2},{-1,2},{-1,-2},{-2,-1},{-2,1},{2,-1},{2,1}
};
int[][] dir2 = {{0,2},{-2,0},{2,0},{0,-2},{2,2},{-2,-2},{2,-2},{-2,2}};
boolean[][] seen = new boolean[3][3];
int res = 0;
private boolean out(int y,int x){
return (y<0 || x<0 || y>2 || x>2 );
}
private void dfs(int y,int x,int k){
if(out(y,x) || seen[y][x] || k>N) return ;
if(k>=M) res++;
seen[y][x] = true;
for(int[] d : dir){
int ny = y+d[0];
int nx = x+d[1];
dfs(ny,nx,k+1);
}
for(int[] d : dir2){
int ny = y+d[0];
int nx = x+d[1];
int midy = y+d[0]/2;
int midx = x+d[1]/2;
if(!out(midy,midx) && seen[midy][midx])
dfs(ny,nx,k+1);
}
seen[y][x] = false;
}
