分析  二分法求下限 进食速度的最低下限初始化为sum/h，上限初始化为max data 验证。验证中间值，如果吃完所用时间res<=h，说明这个速度太快，在左侧查找。否则，说明吃得太慢，在右侧查找。 验证当前下限，如果吃完所用时间res<=h，则说明这就是满足h要求的最低进食速度。代码 import java.util.*; import java.lang.Math; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String[]...

递归 1. 分析 不对称的条件：结点X的左右子树不对称，包括左右子树某一个为null，左右孩子的val不同，左孩子的左子树与右孩子的右子树不对称等等递归的base case是假设知道左右两个子树是否为null、根以及左右子树是否对称。 2. 代码 public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot == null){ return true; } return check(pRoot.left, pRoot.right); } public boolean check(TreeNode left, T...

【典型】树的动态规划问题 1. 分析 树形动态规划问题的前提：如果题目要求的目标是规则S，则流程一般是完成每个结点为root时的子树，在规则S下的每一个答案，最终答案一定在这些答案中。  本题中，规则是整棵树的最大搜索二叉树（maxBST）。求出每一个节点作为root的子树的maxBST，最终答案一定在其中。 1.1 第一步，可能性分析 第一种可能：maxBST来自（注意，不是 “是“）X的左子树。第二种：maxBST来自X的右子树。第三种：X为root的树本身是maxBST。这需要两个条件。   条件1，X的左子树和右子树都是maxBST。 条件2，X.val 比左子树的val都大，比右子树...

树形动态规划 1.套路 1.1 可能性分析  如果root的左子树不是平衡二叉树，则root不是。 如果root的右子树不是，则root不是。 如果root的左右子树的高度差超过1，则root不是。 如果以上三种没出现，那么root是平衡的。  1.2 建立数据结构 根据可能性分析列出每个结点所需信息：是否平衡、高度，建立数据结构 class ReturnType{ public boolean isBalanced; public int hight; public ReturnType(boolean isBalanced, int hight){ this.isBalanced = is...

1. 分情况列举 1.1 分析  有右孩，返回右子树的中序最左结点 无右孩,且它是父亲的左孩，则返回其父 无右孩，且它是其父亲的右孩，则从它父亲开始往上找, 直到某个结点，它是其父亲的左孩，返回其父亲。  1.2 代码 /* public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } } */ public class Solution { ...

1. 递归 1.1 分析  pre[0]是root,在in中找到root的位置 找到root位置后，根据其index确定左右子树的pre和in的范围, 递归图片转载自 https://blog.nowcoder.net/n/7131c90ce3214472887b0f2f6652f5a7 注意，Arrays.copyOfRange()的后两个参数确定数组边界，是左闭右包"[)"1.2 代码 import java.util.Arrays; public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [...

1. 双端队列+层次遍历 1.1 分析  之字形，要求奇偶层输出顺序相反。 双端队列基于LinkedList实现。奇数层，队头出对，孩子从队尾入队，先左后右。偶数层，队尾出队，孩子从队头入队，先右后左。  1.2 代码 import java.util.ArrayList; import java.util.LinkedList; import java.util.Deque; public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList&l...

1. 标记每层最右结点 1.1 分析 辅助队列last记录本层最右结点，nLast记录下层最右结点（入队时标记）。出队到last时本层输出完，last更新为nLast。 1.2 代码 import java.util.* public class Solution { ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer> > res = new ArrayList<>(); ArrayList<Integer>...

import java.util.Stack; class Node{ Node left; Node right; char val; public void Node(char value){ this.val = value; } } public class Solutions{ public void preOrderUnRecur(Node head){ //非递归 前序遍历 if(head == null) return; Stack<Ndoe> sk = new Stack<>(); sk.push(head); while(!sk.isEmpty())...

1. 分析  来源：《程序员代码面试指南》(第2版)左程云    单链表是否有环 如果一个有环，一个没有，则肯定不想交 如果都没有环，找到相交点，参考 如果都有环，分三种情况：  情况一，环入口一致，相交点在入口前面 情况二，环入口不一致，且loop1 loop2在环中不连通，则不相交 请款三，环入口不一致，且loop1 loop2在环中连通，则两个入口都算相交点   2. 代码 public class IntersectList(){ public Node getIntersectNode(Node head1, Node head2){ //是否相交，如果相交，返回相交的结点 if(h...

1. 先处理头结点 1.1 分析  把两个链表中较小的头作为新链表的头 依次比较两个链表未合并部分的头，较小者插入新表的尾 处理未走到尽头的链表1.2 代码 public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null) return l2; if(l2 == null) return l1; //先处理头 ListNode head = (l1.val <= l2.val)? l1:l2; ListNode tail = head; l1 = (head =...

1. 快慢指针+同速双指针 1.1 分析  先利用快慢指针判断是否有环，如果有，两者会在环中相遇。  再利用同速双指针，分别从相遇点和链表头出发，两者一定在环入口相遇。证明：快指针的路程：s1 = a + k1(b+c) + b慢指针的路程：s2 = a + k2(b+c) + b , 令k2 - k1 = k ,则 k >= 1。因为速度是慢指针的2倍, 所以s1 = 2 * s2，则，a + k1(b+c) + b =2 * （ a + k2(b+c) + b）简化，a + b = k (b + c)即 a = (k-1)(b+c) +c这说明，从头结点和相遇点出发，两只同速指针一定...

1. 辅助空间 1.1 分析 两次遍历链表。第一次遍历，将重复的值存入set。第二次遍历，如果set中存在，则在链表中删除。 1.2 代码 import java.util.HashSet; public class Solution { public ListNode deleteDuplication(ListNode pHead) { if(pHead==null) return null; //将重复结点存入set HashSet<Integer> set = new HashSet<>(); ListNode pre = pHead; ListNode cur...

1. 分析 分组，组内计数 count(emp_no) As t > 15 2. 代码 SELECT emp_no, COUNT(emp_no) AS t FROM salaries GROUP BY emp_no HAVING t > 15;