332.重新安排行程
题目链接:332. 重新安排行程 - 力扣(LeetCode)
class Solution {
private Deque<String> res;//最后路径
private Map<String, Map<String, Integer>> map;//机场映射,int来判断要使用目的地几次
public List<String> findItinerary(List<List<String>> tickets) {
map = new HashMap<String, Map<String, Integer>>();
res = new LinkedList<>();
for(List<String> t : tickets){
Map<String, Integer> temp;//存放终点站,并有几个指向
if(map.containsKey(t.get(0))){
//map中已有从t起飞的对象
temp = map.get(t.get(0));//得到t对应的终点站,t对应多个终点站
temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);//加入t的终点站,在temp中找t终点站的value+1
}else{
//map中没有从t起飞的对象
temp = new TreeMap<>();//升序Map
temp.put(t.get(1), 1);
}
map.put(t.get(0), temp);
}//map获得所有映射关系
res.add("JFK");
backTracking(tickets.size());
return new ArrayList<>(res);
}
private boolean backTracking(int ticketNum){
if(res.size() == ticketNum + 1){
return true;
}
String last = res.getLast();
if(map.containsKey(last)){//防止出现null
for(Map.Entry<String, Integer> target : map.get(last).entrySet()){//由于map的val也是映射,所以遍历用entrySet
int count = target.getValue();
if(count > 0){
res.add(target.getKey());
target.setValue(count - 1);
if(backTracking(ticketNum)) return true;
res.removeLast();
target.setValue(count);
}
}
}
return false;
}
}
51. N皇后
思路:双层数组填充
char[][] chessboard = new char[n][n];
for (char[] c : chessboard) {
Arrays.fill(c, '.');
}
其实不难,难点在于数据的处理和储存
class Solution {
List<List<String>> result = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessborad = new char[n][n];
for(char[] c : chessborad){
Arrays.fill(c,'.');
}
backTracking(n,0,chessborad);
return result;
}
private void backTracking(int n, int row, char[][] chessborad){
if(row == n){
result.add(chessboradToList(chessborad));
return;
}
for(int col = 0; col < n; col++){
if(isValid(row, col, n, chessborad)){//能保证一行只有一个Q
chessborad[row][col] = 'Q';
backTracking(n,row+1,chessborad);
chessborad[row][col] = '.';
}
}
}
private List<String> chessboradToList(char[][] chessborad){
List<String> list = new ArrayList<>();
for(char[] c : chessborad){
list.add(String.copyValueOf(c));
}
return list;
}
private boolean isValid(int row, int col, int n, char[][] chessborad){
for(int i = 0; i < row; i++){//同列有没有Q
if(chessborad[i][col] == 'Q'){
return false;
}
}
for(int i = row-1,j = col-1; i >= 0 && j >= 0; i--,j--){//斜45
if(chessborad[i][j] == 'Q'){
return false;
}
}
for(int i = row-1,j = col+1; i >= 0 && j <= n-1; i--, j++){
if(chessborad[i][j] == 'Q'){
return false;
}
}
return true;
}
}
37. 解数独
题目链接: