学习笔记
#本周作业 1、二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
递归解法：
class Solution {
private TreeNode ans;
public Solution() {
this.ans = null;
}
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return false;
boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);
if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root.val == p.val || root.val == q.val);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root, p, q);
return this.ans;
}
}
2-组合
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (k <= 0 || n < k) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(n, k, 1, path, res);
return res;
}
private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i <= n; i++) {
path.addLast(i);
System.out.println("递归之前 => " + path);
dfs(n, k, i + 1, path, res);
path.removeLast();
System.out.println("递归之后 => " + path);
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 5;
int k = 3;
List<List<Integer>> res = solution.combine(n, k);
System.out.println(res);
}
}
剪枝优化后：
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (k <= 0 || n < k) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(n, k, 1, path, res);
return res;
}
private void dfs(int n, int k, int index, Deque<Integer> path, List<List<Integer>> res) {
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
// 只有这里 i <= n - (k - path.size()) + 1 与参考代码 1 不同
for (int i = index; i <= n - (k - path.size()) + 1; i++) {
path.addLast(i);
dfs(n, k, i + 1, path, res);
path.removeLast();
}
}
}
#学习笔记 树的面试题解法，一般都是递归：
- 节点定义；
- 重复性（自相似性）
递归：
- 本质是循环
- 通过函数体来进行的循环
注意点：
- 抵制人肉递归
- 找最近重复性
- 数学归纳法
#每日一题 1、验证二叉搜索树
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
private boolean isValidBST(TreeNode node, Integer min, Integer max) {
if (node == null) {
return true;
}
if (min != null && node.val <= min) {
return false;
}
if (max != null && node.val >= max) {
return false;
}
return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
}
2.最长公共前缀
反向思维，把字符串a与当前的str匹配，若str中不包含以a这个前缀，则不断减少a的长度，直到str中包含a这个前缀为止。
注意：
1.当a为""时，说明无公共前缀，可以直接返回。
2.str.startsWith(a)，若str以a为前缀，则返回true，否找返回false.
class Solution {
public String longestCommonPrefix(String[] strs) {
String a = "";
try {
a = strs[0];
for (String str : strs) {
// 若a已经减为""，则说明无公共前缀，直接返回
if (a == "") return a;
// 若a在当前str中匹配不上，则减少字符串a的长度，再次尝试匹配
while (!str.startsWith(a)) {
a = a.substring(0,a.length() - 1);
}
}
return a;
} catch (Exception e) {
return a;
}
}
}
3、n皇后问题
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (char[] i : board){
Arrays.fill(i,'.');
}
backtrack(board,0);
return res;
}
// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
void backtrack(char[][] board, int row){
if (row == board.length){
res.add(array2List(board));
return;
}
for (int j = 0;j<board.length;j++){
if (!check(board,row,j)){
continue;
}
board[row][j] = 'Q';
backtrack(board,row+1);
board[row][j] = '.';
}
}
List<String> array2List(char[][] board){
List<String> res = new LinkedList<>();
for (char[] i : board){
StringBuffer sb = new StringBuffer();
for (char j : i){
sb.append(j);
}
res.add(sb.toString());
}
return res;
}
boolean check(char[][] board,int row,int col){
int n = board.length;
// 检查列是否有皇后互相冲突
for (int i = 0; i < n; i++) {
if (board[i][col] == 'Q')
return false;
}
// 检查右上方是否有皇后互相冲突
for (int i = row - 1, j = col + 1;
i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q')
return false;
}
// 检查左上方是否有皇后互相冲突
for (int i = row - 1, j = col - 1;
i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q')
return false;
}
return true;
}
}