17. 電話號碼的字母組合
還是不會這種排列組合問題甫煞，需要多加練習(xí)
其中涉及字符串的拼接時需要用StringBuffer拼接峦睡，并且判斷字符串為空時不要判斷str==""；這無法判斷天通，
1.用s.length==0 來判斷空
2.用字符串函數(shù)s.equals("")這種方法判斷為空岔留。
力扣非常好的題解
public static List<String> letterCombinations(String digits) {
if(digits.length==0) return new ArrayList<>();
Map<String,String> map=new HashMap<>();
String[] nums={"2","3","4","5","6","7","8","9"};
String[] values={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
for(int i=0;i<nums.length;i++){
map.put(nums[i],values[i]);
} //test is ok
List<String> res=new LinkedList<>();
backtrack(new StringBuilder(),digits,res,0,map);
return res;
}
//關(guān)鍵是這部分的遞歸代碼亲雪，所有的組合代碼都是這種套路
public static void backtrack(StringBuilder combination, String nextdigit,List<String> res,int i,Map<String,String> map){
//第一個是參數(shù)時用于拼接字符的參數(shù)痕支，第二個是“23”這種字符串捺檬，res是最后的結(jié)果，i表示遞歸第幾個字符状知，map是保存的鍵值對
if(i==nextdigit.length()){
res.add(combination.toString());
return;
}
else{
//取出每一個字符
String s=String.valueOf(nextdigit.charAt(i));
String letters=map.get(s);
for(int j=0;j<letters.length();j++){ //這一步就像走迷宮的四個方向一樣，對每一種可能進行遞歸
String letter=String.valueOf(letters.charAt(j));
backtrack(new StringBuilder(combination+letter),nextdigit,res,i+1,map);
}
}
}
46. 全排列
這是一類題目都是遞歸+回溯
class Solution {
//整個過程設(shè)計的兩個知識點
List<List<Integer>> res=new ArrayList<>();
List<Integer> temp=new ArrayList<>();
boolean []visited=new boolean[100]; //暫定100
public List<List<Integer>> permute(int[] nums) {
Process(nums,0);
return res;
}
public void Process(int []nums,int i){
if(i==nums.length)
{
//這一步不知道語法孽查，可以這樣對list進行拷貝的饥悴，并且不損耗原來的temp數(shù)組便于之后的遞歸
res.add(new ArrayList<>(temp));
return;
}
for(int j=0;j<nums.length;j++) {
if (!visited[j]) {
visited[j] = true;
temp.add(nums[j]);
Process(nums, i+ 1);
//回溯，要將節(jié)點的訪問標(biāo)記復(fù)原，并且需要將list列表給復(fù)原（即移除數(shù)據(jù)）西设，即和原來的操作相反的操作就是回溯
visited[j] = false;
temp.remove(temp.size()-1); //將最后的元素移除,這一步?jīng)]寫
}
}
}
}
首先這種題也是dfs搜索問題瓣铣，但是對于這種問題有個回溯的過程在這里，我就是卡在這個回溯的流程這里沒搞明白贷揽，第一就是保存全排列的序列棠笑，這一步直接保存會影響后面的移除
res.add(temp);
temp=new ArrayList<>(); //本意是將temp暫存一個全排列序列，清空后再對其他序列進行全排列
return;
但是這里回溯時的本意是在原來的temp基礎(chǔ)上從后往前來刪除節(jié)點禽绪，現(xiàn)在直接將temp list清空這里再刪除節(jié)點直接會爆越界錯誤的蓖救。也違背了回溯的本意。所以這里就是將temp的序列進行拷貝印屁，
temp.remove(temp.size()-1); //將最后的元素移除
res.add(new ArrayList<>(temp)); //將原來的temp拷貝到新的空間中循捺，并且temp不受影響，可以回溯
注意到回溯的操作和原來的操作恰好是相反的雄人，也叫做復(fù)原狀態(tài)
比如將visit從訪問狀態(tài)標(biāo)記為未訪問狀態(tài)从橘，將加入的節(jié)點從隊列中取出。
總結(jié)：
1.不知道怎么將原來的list拷貝到新的空間中础钠；
2.不知道回溯的操作是什么恰力，我只是將狀態(tài)標(biāo)記了，但是沒有將加入的節(jié)點取出
