public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
ArrayList<Integer> values = new ArrayList<>();
backtrack(root,target,values,res);
return res;
}
// values : 记录从根节点到叶子节点的所有路径
// paths : 存储所有可能的结果
private void backtrack(TreeNode root, int target,
ArrayList<Integer> values,
ArrayList<ArrayList<Integer>> paths) {
if (root == null) {
return;
}
values.add(root.val);
if(root.left==null && root.right==null && root.val==target){
paths.add(new ArrayList<>(values));
}else{
backtrack(root.left,target-root.val,values,paths);
backtrack(root.right,target-root.val,values,paths);
}
values.remove(values.size()-1);
}//思路：典型的回溯法思想
private int m,n; //矩阵的长度、宽度
private boolean[][] visted; //标记是否访问
private int[][] d={
{0,1}, //向右
{-1,0},//向上
{0,-1},//向左
{1,0} //向下
};
private boolean inArea(int x,int y){
return (x>=0 && x<m) && (y>=0 && y<n);
}
//从board[startx][starty]开始寻找word[index...word.ength()]
private boolean searchMatrix(char[][] matrix, char[] str,int index,int startx,int starty){
if(index==str.length-1){ //递归到最后一个元素，检测是否相等
return matrix[startx][starty] == str[index];
}
if(matrix[startx][starty]==str[index]){
visted[startx][starty] = true;
for(int i=0;i<4;i++){
int newX = startx+d[i][0];
int newY = starty+d[i][1];
if(inArea(newX,newY) && !visted[newX][newY]){
if(searchMatrix(matrix,str,index+1,newX,newY)){
return true;
}
}
}
visted[startx][starty] =false;
}
return false;
}
//构建二维矩阵
private char[][] buildMatrix(char[] array, int rows, int cols){
//根据char[] matrix, rows, cols 构建二维的矩阵
char[][] matrix = new char[rows][cols];
int index=0;
for(int i=0;i<rows;i++) {
for (int j = 0; j < cols; j++) {
matrix[i][j] = array[index++];
}
}
return matrix;
}
//matirx 就是字符串矩阵;
//rows 和 cols 是其长度和宽度
public boolean hasPath(char[] array, int rows, int cols, char[] str) {
if(rows==0){
return false;
}
char[][] matrix = buildMatrix(array,rows,cols);
m = rows;
n = cols;
visted = new boolean[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(searchMatrix(matrix,str,0,i,j)){
return true;
}
}
}
return false;
}private boolean[][] visited;
private int m,n;
private int[][] d={
{-1,0},
{0,1},
{1,0},
{0,-1}
};
private boolean inArea(int x,int y){
return (x>=0 && x<m) && (y>=0 && y<n);
}
//从(startX,startY)位置在 board 中查找 word[index...n]
private boolean dfs(char[][] board,int startX,int startY,String word,int index){
if(index==word.length()-1){
return board[startX][startY]==word.charAt(index);
}
if(board[startX][startY]==word.charAt(index)){
visited[startX][startY]=true;
for(int i=0;i<4;i++){
int newX=startX+d[i][0];
int newY=startY+d[i][1];
if(inArea(newX,newY) && !visited[newX][newY]){
if(dfs(board,newX,newY,word,index+1)){
return true;
}
}
}
visited[startX][startY]=false;
}
return false;
}
public boolean exist(char[][] board, String word) {
m=board.length;
if(m==0){
return false;
}
n=board[0].length;
visited=new boolean[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(dfs(board,i,j,word,0)){
return true;
}
}
}
return false;
}
private List<List<Integer>> res;
private boolean[] visited;
public List<List<Integer>> permute(int[] nums) {
res = new ArrayList<>();
if(nums==null || nums.length==0){
return res;
}
visited = new boolean[nums.length];
List<Integer> p =new ArrayList<>();
generatePermutation(nums,0,p);
return res;
}
//p中保存一个有 index 的元素的排列
//向这个排列的末尾添加第 (index+1) 个元素，组成有(index+1) 个元素排列
private void generatePermutation(int[] nums,int index,List<Integer> p){
if(index==nums.length){
res.add(new ArrayList<>(p));
return;
}
for(int i=0;i<nums.length;i++){
if(!visited[i]){
visited[i]=true;
p.add(nums[i]);
generatePermutation(nums,index+1,p);
p.remove(p.size()-1);
visited[i]=false;
}
}
}private List<List<Integer>> res;
private boolean[] visited;
public List<List<Integer>> permuteUnique(int[] nums) {
res = new ArrayList<>();
if(nums==null || nums.length==0){
return res;
}
visited = new boolean[nums.length];
Arrays.sort(nums);
List<Integer> p = new ArrayList<>();
findUniquePermutation(nums,0,p);
return res;
}
//p 保存的是有 index 元素的排列
//向这个排列的末尾添加第 (index+1) 个元素，组成有(index+1) 个元素排列
private void findUniquePermutation(int[] nums,int index,List<Integer> p){
if(index==nums.length){
res.add(new ArrayList<>(p));
return;
}
for(int i=0;i<nums.length;i++){
if(!visited[i]){
if(i>0 && nums[i-1]==nums[i] &&
!visited[i-1]){ //注意：相邻元素相同，并且都未被访问
continue;
}
visited[i]=true;
p.add(nums[i]);
findUniquePermutation(nums,index+1,p);
p.remove(p.size()-1);
visited[i]=false;
}
}
return;
}private ArrayList<String> res;
private boolean[] visited;
public ArrayList<String> Permutation(String str) {
res = new ArrayList<>();
if(str==null || str.length()==0){
return res;
}
char[] chs = str.toCharArray();
Arrays.sort(chs); //方便后面的去重处理
visited = new boolean[str.length()];
permute(chs,0,new StringBuilder());
return res;
}
//产生排列
//p中保存一个存在index个元素的排列
//向这个排列的末尾添加第(index+1)个元素，获得包含(index+1)个元素的排列
private void permute(char[] chs,int index,StringBuilder p){
if(index==chs.length){
res.add(p.toString());
return;
}
for(int i=0;i<chs.length;i++){
//需要进行去重处理
if(i>0 && chs[i-1]==chs[i] && !visited[i-1]){
continue;
}
if(!visited[i]){
p.append(chs[i]);
visited[i] = true;
permute(chs,index+1,p);
p.deleteCharAt(p.length()-1);
visited[i] = false;
}
}
}private List<String> res;
//处理 index 位置的数据
//如果 index 位置是字母的话，则替换
private void replaceLetter(int index,StringBuilder p){
if(index==p.length()){
res.add(p.toString());
return;
}
char ch=p.charAt(index);
if(Character.isLetter(ch)){
p.setCharAt(index,Character.toUpperCase(ch));
replaceLetter(index+1,p);
p.setCharAt(index,Character.toLowerCase(ch));
replaceLetter(index+1,p);
}else{
replaceLetter(index+1,p);
}
return;
}
public List<String> letterCasePermutation(String S) {
res=new ArrayList<>();
if(S==null || S.length()==0){
return res;
}
StringBuilder p=new StringBuilder(S);
replaceLetter(0,p);
return res;
}private final String[] letterMap={
" ",//0
"",//1
"abc",//2
"def",//3
"ghi",//4
"jkl",//5
"mno",//6
"pqrs",//7
"tuv",//8
"wxyz"//9
};
private List<String> res;
//s 中保留了从 digits[0...index-1] 翻译得到的字符串
//寻找和 digits[index] 匹配的字母，获取 digits[0...index] 翻译得到的解
private void findCombination(String digits,int index,String s){
if(index==digits.length()){
res.add(s);
return;
}
char c = digits.charAt(index);
String letters = letterMap[c-'0']; // 翻译字符串
for(int i=0;i<letters.length();i++){
findCombination(digits,index+1,s+letters.charAt(i));
}
return;
}
public List<String> letterCombinations(String digits) {
res = new ArrayList<>();
if(digits==null || digits.length()==0){
return res;
}
findCombination(digits,0,"");
return res;
}//思路一：暴力解法
private List<List<Integer>> res;
//c存储已经找到的组合
//从start开始搜索新的元素
private void findCombination(int n,int k,int start,List<Integer> c){
if(k==c.size()){
res.add(new ArrayList<>(c));
return;
}
for(int i=start;i<=n;i++){
c.add(i);
findCombination(n,k,i+1,c);
c.remove(c.size()-1);
}
return;
}
public List<List<Integer>> combine(int n, int k) {
res=new ArrayList<>();
if(n<=0 || k<=0 || n<k){
return res;
}
List<Integer> c=new ArrayList<>();
findCombination(n,k,1,c);
return res;
}//思路二：优化，进行剪枝
private List<List<Integer>> res;
//c存储已经找到的组合
//从start开始搜索新的元素
private void findCombination(int n,int k,int start,List<Integer> c){
if(k==c.size()){
res.add(new ArrayList<>(c));
return;
}
//TODO:优化--剪枝
//c存储的是已经找到的组合。
//此时还剩下k-c.size()个空位，
//则 [i...n]之间的元素最少要有 k-c.size() 个，即 n-i+1 >= k-c.size()
//所以有 i <= n-(k-c.size())+1
for(int i=start;i<=n-(k-c.size())+1;i++){
c.add(i);
findCombination(n,k,i+1,c);
c.remove(c.size()-1);
}
return;
}
public List<List<Integer>> combine(int n, int k) {
res=new ArrayList<>();
if(n<=0 || k<=0 || n<k){
return res;
}
List<Integer> c=new ArrayList<>();
findCombination(n,k,1,c);
return res;
}
- 思路：
判断对角线不合法的情况：
(1)竖向：col[i] 表示第 i 列被占用
(2)对角线1：dai1[i] 表示第 i 条对角线被1占用
(3)对角线2：dai2[i]表示第i对角线被2占用
private List<List<String>> res;
//用于判断是否在同一竖线上，因为index表示行数，是变化的，所以不用判断是否在相同行
private boolean[] cols;
//判断是否在1类对角线上，相应坐标 i+j
private boolean[] dial1;
//判断是否在2类对角线上，相应坐标 i-j+n-1
private boolean[] dial2;
//在 index 行放皇后
//row 记录在 index 行能够放皇后的位置
//比如 row.get(0) = 1，就表示在棋盘的 [0,1] 位置放上皇后
private void putQueen(int n,int index,List<Integer> row){
if(index==n){
res.add(generateBoard(n,row));
return;
}
// [index,j] 放皇后
for(int j=0;j<n;j++){
if(!cols[j] && !dial1[index+j] && !dial2[index-j+n-1]){
row.add(j);
cols[j]=true;
dial1[index+j]=true;
dial2[index-j+n-1]=true;
putQueen(n,index+1,row);
dial2[index-j+n-1]=false;
dial1[index+j]=false;
cols[j]=false;
row.remove(row.size()-1);
}
}
}
//创建棋盘
private List<String> generateBoard(int n, List<Integer> row) {
List<String> res=new ArrayList<>();
if(n<=0){
return res;
}
char[][] board=new char[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
board[i][j]='.';
}
}
for(int i=0;i<row.size();i++){
board[i][row.get(i)]='Q';
}
for(int i=0;i<n;i++){
res.add(new String(board[i]));
}
return res;
}
public List<List<String>> solveNQueens(int n) {
res=new ArrayList<>();
if(n==0){
return res;
}
cols=new boolean[n];
dial1=new boolean[2*n-1];
dial2=new boolean[2*n-1];
List<Integer> row=new ArrayList<>();
putQueen(n,0,row);
return res;
}