作者：office多多 链接：https://www.nowcoder.com/discuss/374134?type=0&order=0&pos=67&page=1
-
10个堆，每堆10个苹果，其中9个堆里苹果是50g/个，一个堆里苹果是40g/个，有一杆秤只能称一次，所称重量为x,求40g苹果所在堆。
- 将堆编码为1-10；然后每堆拿出k个，最后少了k*10克，则知道是第几堆的苹果。
-
5L和6L水桶，得到三升水。
- 1、6L的水桶装满水，倒满5L的桶。 2、将5L桶里的水倒了，将6L桶里剩余的1L放入5L桶。 3、6L的桶装满水，倒满5L桶里，6L桶里还剩2L(6-4)水。 4、 将5L桶里的水倒了，将6L桶里剩余的2L水放入5L桶里。 5、将6L桶装满水，倒满5L的桶，这时6L的桶里还剩3L水。
-
两个一小时蚊香怎么得到15分钟的记时
- 同时点燃AB两只蚊香，其中A蚊香点燃两头，等A蚊香烧完后（30分钟），点燃B蚊香的另一头。
-
4分钟沙漏和7分钟沙漏怎么漏出9分钟
- 4分钟的和7分钟的同时开始，4分钟的完后又倒过来开始。7分钟的沙漏完后立马倒过来，（4分钟的沙漏还剩1分钟）。等4分钟的沙漏完后，将7分钟的又立马倒过来，等漏完就是9分钟。
-
八个球，其中有一个是其余球重量的1.5倍，有什么方案找出来
- 3次。 AB两边，一边放4个，如果A重，则把B端的去了，A端的4个分成AB端一边两个。在把轻的那端去了，重的那端的2个分成一边一个，重的那个球就找出来了。
-
桌上100个球，每次可以拿一到五个, 现在我们两个人依次拿球，你先拿，使用怎样的拿球策略，可以使你最终能拿到最后一个球？
- 第一次拿四个，后来每个你拿球的时候只要保证剩下的球是6的倍数就行了如果他拿n个球 ，你就拿6-n个球。
-
有10个石头，每人每次可以拿1-2个，轮流拿，最后一个拿的人算输，有什么必赢的方案。
- 对方先拿、保证两个人每一轮回拿满3个（对方拿一个，我拿两个、对方拿两个，我拿一个）。
-
一亿数据获取前1000个最大值 https://zhuanlan.zhihu.com/p/73233544
- 把一亿个数字的前100个 首先放入数组。 然后把最小值放在ary[0]。然后再循环100到一亿之间的。 每次循环判断当前数字是否大于ary[0]当大于时，当前数字放入ary[0] 并再次重构数组最小值进入ary[0]以此类推 。当循环完这一亿个数字后。 最大的前100个数字就出来了。
- 左神直通BAT算法笔记（基础篇）-上
- 左神直通BAT算法笔记（基础篇）-下
- 左神直通BAT算法（进阶篇）-上
- 左神直通BAT算法（进阶篇）-下
- 剑指offer解析-上（Java实现）
- 剑指offer解析-下（Java实现）
如果要求不按照原来的顺序排列
1、荷兰国旗问题解决。
如果要求按照原来的顺序排列
2、将原链表划分为三个链表，然后再连接起来。
1、 用hash表，但是空间复杂度为n。
map.put(cur,new Node(cur.value));2、不用hash表，空间复杂度为1.
将链表复制为：1->1'->2->2'->3->3'->null 1）可以设置每一个节点的复制节点 2）设置rand节点：例如，1的rand节点为3，1的复制节点为1'，那么1'应该指向3'，如何找到3'呢？令1'.next=3.next。 3）将节点和复制节点拆分。
将两个链表代表的整数相加之后的数，再成为一个新的链表。
1、使用栈结构，空间复杂度为n
用两个栈保存两个链表的值，然后弹出相加，如果有进位，用ca记录，最后成为一个链表。
Node node = null;
whlie(!s1.isEmpty() || !s2.isEmpty()){
n1 = s1.isEmpty() ? 0 : s1.pop();
n2 = s2.isEmpty() ? 0 : s2.pop();
n = n1+n2;
//*******头插法：倒着连接链表**********
pre = node
node = new Node(n%10);
node.next = pre;
ca = n/10;
}
if(ca == 1){
pre = node;
node = new Node(1);
node.next = pre;
}
return node;2、将两个链表逆序，然后相加即可。
public Node reverseList(Node head){
Node pre = null;
Node next = null;
while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}1、使用栈结构，每个k个节点入栈，然后将这个k个节点连接，注意节点之间的连接与头节点的设置。
- 每k个节点之间的栈连接
public Node resign(Stack<Node> stack,Node left,Node right){
Node cur = stack.pop();
if(left != null){
left.next = cur;
}
Node next = null;
while(!stack.isEmpty()){
next = stack.pop();
cur.next = next;
cur = next;
}
cur.next = right;
return cur;
}2、使用单链表逆序
public void resign(Node left,Node start,Node end,Node right){
Node pre = start;
Node cur = start.next;
Node next = null;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
if(left != null){
left.next = end;
}
start.next = right;
}1、使用队列收集遍历到的节点，然后再连接为双向链表。
- 双向链表连接
Node pre = head;
pre.left = null;
Node cur = null;
while(!queue.isEmpty()){
cur = queue.poll();
pre.right = cur;
cur.left = pre;
pre = cur;
}
pre.right = null;
return head;- 递归遍历模板
public void pre�(Node head){
if(head == null){
return;
}
System.out.println(head.value + " ");
pre(head.left);
pre(head.right);
}-
非递归遍历
-
前序遍历
用栈来保存信息，但是遍历的时候，是：先输出根节点信息，然后压入右节点信息，然后再压入左节点信息。
public void pre�(Node head){
if(head == null){
return;
}
Stack<Integer> stack = new Stack<>();
stack.push(head);
while(!stack.isEmpty()){
head = stack.poll();
System.out.println(head.value + " ");
if(head.right != null){
stack.push(head.right);
}
if(head.left != null){
stack.push(head.left);
}
}
System.out.println();
}- 中序遍历
中序遍历的顺序是左中右，先一直左节点遍历，并压入栈中，当做节点为空时，输出当前节点，往右节点遍历。
public void inorder(Node head){
if(head == null){
return;
}
Stack<Integer> stack = new Stack<>();
stack.push(head);
while(!stack.isEmpty() || head != null){
if(head != null){
stack.push(head);
head = head.left
} else {
head = stack.poll();
System.out.println(head.value + " ");
head = head.right;
}
}
System.out.println();
}- 后序遍历
用两个栈来实现，压入栈1的时候为先左后右，栈1弹出来就是中右左，栈2收集起来就是左右中。
根据搜索二叉树性质，最后一个元素是头节点，比后序数组最后一个元素小的数组会在数组左边，比数组最后一个元素值大的数组在数组的右边。所以，我们需要找到后续数组中，小的数组的中的最后一个元素和大的数组中的第一个元素。
搜索二叉树：中序遍历，递增。 完全二叉树：层次遍历二叉树，有右孩子没有左孩子，为false，如果当前节点并不是左右孩子都有，那么后面的节点都必须是叶子节点。
- 递归的收集左右边界信息
public void setMap(Node head,int level,int[][] map){
if(head == null){
return;
}
map[l][0] = map[l][0] == null ? h : map[l][0];
map[l][1] = h;
setMap(head.left,level+1,map);
setMap(head.right,level+1,map);
}- 递归获取树的高度
public int getHeight(Node head,int level){
if(head == null){
return level;
}
return Math.max(getHeight(head.left,level+1),getHeight(head.right,level+1));
}- 递归打印叶子节点（非左右边界节点）
public int printLeafNotInMap(Node head,int level,int[][] map){
if(head == null){
return;
}
if(head.left == null && head.right == null && head != map[level][0] && head != map[level][1]){
System.out.println(head.value + " ");
}
printLeafNotInMap(head.left,level+1,map);
printLeafNotInMap(head.right,level+1,map);
}思路： 用一个 hashmap (key是累加和sum，value是当前层level) 保存每一步的累加和sum，例如，当到第三层的第一个节点的时候，当前的累加和sum的值，如果sum在hashmap中不存在，保存到hashmap中。然后递归的遍历求每个sum，同时，求最长路径长度Math.max(level-map.get(sum-k)，max)。
这个思路也可以用到数组中的累加和问题。
这个题目是二叉树中很多题目中的套路：树形dp。
1、列出所有可能性，比如，这个题目的可能性有：左子树上的可能性、右子树的可能性、左右子树整体的可能性。 2、根据第一步的可能性，确定需要的信息，比如，这个题目，我们需要左子树的满足的最大搜索树头结点leftMaxBSTHead，左子树的最大搜索树的大小leftBSTSize，左子树的最大值max。 3、合并第二步的信息，写出信息结构。
public class ReturnType{
public Node maxBSTHead;
public int maxBSTSize;
public int min;
public int max;
public ReturnType(Ndoe maxBSTHead,int maxBSTSize,int min,int max){
this.maxBSTHead = maxBSTHead;
this.maxBSTSize - maxBSTSize;
this.min = min;
this.max = max;
}
}4、设计递归函数，以及设计base case。
平衡二叉树的左右子树高度相差不能超过1，所以，我们需要的信息有height、isBST（是否是平衡二叉树）
保存yes_X_max：X来的情况。 保存no_X_max：X不来的情况。
- 返回结构
public class ReturnType{
public int yesHeadMax;
public int noHeadMax;
}本来按层打印只需要利用queue宽度遍历即可，但是，因为这里需要换行，所以，需要添加额外的辅助变量来换行的操作。
换行需要的变量：last表示正在打印的当前行的最右节点，nlast表示下一行的最右节点。
ZigZag打印：需要用到LinkedList双端队列。
原则1：从左往右打印，头部弹出元素打印，如果有孩子，孩子尾部加入队列。
原则2：从右往左打印，尾部弹出元素打印，如果有孩子，孩子头部加入队列。
搜索二叉树的中序遍历应该为递增的，找到两个节点，过程为：第一个错误节点为第一次降序时较大的节点，第二个错误的节点是最后一次降序时较小的节点。
序列化二叉树，然后判断子串即可。
利用node的parent节点找到头结点，然后中序遍历，当前节点的后一个节点就是。
这种题目都是有一个parent节点指向父节点的，一般会有最优解，减少时间复杂度。
情况1：如果node有右子树，那么后继节点就是右子树上最左边的节点。 情况2：如果没有右子树。 1）如果是当前节点的父节点的左孩子，则当前节点就是后继节点。 2）如果是当前节点的额父节点的右孩子，则向上寻找，假设向上寻找移动到的节点为s，s的父节点为p，如果发现s是p的左孩子，那么p就是后继节点。
public Node getNextNode(Node node){
if(node == null){
return node ;
}
if(node.right != null){
//寻找右节点的最左节点
return getLeftMost(node.right);
} else {
Node parent = node.parent;
while(parent != null && parent.left != node){
node = parent;
parent = node.parent;
}
return parent;
}
}1）如果cur等于null，或者等于o1或者o2，那么返回cur。 2）如果cur的left和right都为空，那么返回null，说明没有。 3）如果cur的left和right都不为空，那么cur就是。 4）如果cur的left和right一个为空，一个不为空，返回不是空的节点即可。
利用hashmap，然后将o1节点往上遍历到节点，并把每个节点放入集合A中，然后o2往上遍历到头节点，只要遍历的节点发现在集合A中，那么这个节点就是公共祖先节点。
1）找到右子树的最左节点，如果到达最后一层，说明左子树为满二叉树，节点数为：2^(h-1)，递归右子树bs(node.right,level+1,h)，所以为：2^(h-1)+bs(node.right,level+1,h)。 2）找到右子树的最左节点，如果没有到达最后一层，说明右子树为满二叉树，所以为：2^(h-level-1)+bs(node.left,level+1,h)。
P173、P172、神级遍历方法
1、用一维数组代替二维数组，降低空间复杂度 2、需要记录的值： 必须值：一维数组的第一个值（累加值） 可能值：一维数组的上一行的前一个值（i-1）、一维数组的上一行的当前值（i） 3、初始化第一行的数据 4、有了相关值之后，从左到右，从上到下遍历。
1、一般一位变量是：更新的维度（更短的维度），同时，需要求出哪个是长字符串、短字符串
2、字符串的题目循环时：1-n
3、如果是3个方向a[i-1][j-1]、a[i-1][j]、a[i][j-1]来更新值，那么循环时，需要一个变量pre记录左上角a[i-1][j-1]的值，并且循环时，需要记录初始值（P198）
4、一般题目根据循环i、j直接将二维根据变量替换成一维的即可
5、如果需要比较当前dp[i][j]的值的大小，则需要用temp变量记录dp[i][j]的值，并且将当前值替换成temp（P232）
- 通常依赖的位置
dp[i][j]、dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]。累加：依赖某一行、某一列、行和列
- 方法
方法1：如果题目简单，通过题目直接找出依赖。 方法2：如果题目复杂，写出递归版本，然后，根据递归版本，用普通的值代入，找出依赖哪些值。
1、确定递归函数变量有哪些？ 2、解决局部问题，剩下的问题递归解决，写出递归模板。 3、写出base case。
-
换钱的最少货币数（P189） 1、
process(arr,int i,int aim)2、process(arr,i+1,aim-k*arr[i]) -
机器人到达指定位置的方法数（P192、P199） 1、
process(int N,int cur,int rest,int P)2 2.1）当前位置在1时process(N,2,rest-1,P)2.2）当前位置在N时process(N,N-1,rest-1,P)2.3）当前位置在i时process(N,cur-1,rest-1,P)+process(N,cur+1,rest-1,P)
- 求出dp数组
dp[i] = {dp[j]+1(0<=j<i,arr[j]<arr[i])}- 根据dp数组求出最长递增子序列
1、找到dp数组中最大值及最大值的index
2、从最大值开始，从右往左遍历，如果dp[index-1] == dp[index]且arr[index-1]<arr[index]这个字符满足要求，遍历完所有的字符
- 求出dp数组
dp[i][j] = dp[i-1][j]
dp[i][j] = dp[i][j-1]
dp[i][j] = dp[i-1][j-1] + 1求以上三者的最大值即可。
- 根据dp数组求出最长公共子序列
如果是来自dp[i-1][j-1]方向的，则是满足要求的字符。
- 求dp数组
如果当前两个字符串的字符相等，则dp[i][j] = dp[i-1][j-1] + 1，否则dp[i][j] = 0
- 根据dp数组求公共子串
只需要找到最大的dp中的值max，然后往前遍历max次即可，收集这些值。
dp[i][j]代表str1的字符到i的子串和str1的字符到j的子串的代价
- 如果当前字符串相等
dp[i][j] = dp[i-1][j-1]- 如果当前字符串不相等
dp[i][j] = dp[i-1][j-1] + rc//加上一个代替的代价- 字符串1和字符串2少一个的情况
dp[i][j] = dp[i-1][j] //str1删除一个字符的代价dc
dp[i][j] = dp[i][j-1] //str1插入一个字符的代价ic位置（i，j）的情况如下：
-
dp[i-1][j]代表能否被str1[0...i-2]和str2[0...j-1]交错组成，如果可以，且str1[i-1]==aim[i+j-1]，则dp[i][j]==true -
dp[i][j-1]代表能否被str1[0...i-1]和str2[0...j-2]交错组成，如果可以，且str2[j-1]==aim[i+j-1]，则dp[i][j]==true -
其他情况都是false
用hashmap保存key为数组中的值，value为当前值所在的子序列的长度len，每次遍历一个值的时候就更新，并且只需要更新子序列的开始值和结束值这两个边界即可。
思路
可以采用双指针的方法进行求解（类似滑动窗口）。
left：当值大于target时，left++; right：当值小于target时，right++；
思路
用一个map记录（sum，j），key的sum为：从arr最左边开始累加最早出现的sum值，value的j为：sum值最早出现的位置。
用map.get(sum-k)得到长度len;
思路
当cur当前累加和小于0时，清零，重新累加，用max记录最大值。
思路：只要确定在二分两侧的某一侧肯定存在你要找的内容，就可以使用二分查找，并不是一定要有序数组。
思路：记录当前位置的最大值和最小值
现在免费送给大家，在我的公众号 好好学java 回复 资料 即可获取。
有收获？希望老铁们来个三连击，给更多的人看到这篇文章
1、老铁们，关注我的原创微信公众号「好好学java」，专注于Java、数据结构和算法、微服务、中间件等技术分享，保证你看完有所收获。
2、给俺一个 star 呗，可以让更多的人看到这篇文章，顺便激励下我继续写作，嘻嘻。