作者:office多多 链接:https://www.nowcoder.com/discuss/374134?type=0&order=0&pos=67&page=1
10个堆,每堆10个苹果,其中9个堆里苹果是50g/个,一个堆里苹果是40g/个,有一杆秤只能称一次,所称重量为x,求40g苹果所在堆。
5L和6L水桶,得到三升水。
两个一小时蚊香怎么得到15分钟的记时
4分钟沙漏和7分钟沙漏怎么漏出9分钟
八个球,其中有一个是其余球重量的1.5倍,有什么方案找出来
桌上100个球,每次可以拿一到五个, 现在我们两个人依次拿球,你先拿,使用怎样的拿球策略,可以使你最终能拿到最后一个球?
有10个石头,每人每次可以拿1-2个,轮流拿,最后一个拿的人算输,有什么必赢的方案。
一亿数据获取前1000个最大值 https://zhuanlan.zhihu.com/p/73233544
如果要求不按照原来的顺序排列
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个节点连接,注意节点之间的连接与头节点的设置。
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;
}
容器(栈、队列)
来辅助完成。同时,一般需要cur、pre
节点辅助连接。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[i] = {dp[j]+1(0<=j<i,arr[j]<arr[i])}
1、找到dp数组中最大值及最大值的index
2、从最大值开始,从右往左遍历,如果dp[index-1] == dp[index]
且arr[index-1]<arr[index]
这个字符满足要求,遍历完所有的字符
dp[i][j] = dp[i-1][j]
dp[i][j] = dp[i][j-1]
dp[i][j] = dp[i-1][j-1] + 1
求以上三者的最大值即可。
如果是来自dp[i-1][j-1]方向的,则是满足要求的字符。
如果当前两个字符串的字符相等,则dp[i][j] = dp[i-1][j-1] + 1
,否则dp[i][j] = 0
只需要找到最大的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//加上一个代替的代价
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++;
未排序
数组中累加和为指定值的最长子数组系列问题(P384)思路
用一个map记录(sum,j),key的sum为:从arr最左边开始累加最早出现的sum值,value的j为:sum值最早出现的位置。
用map.get(sum-k)
得到长度len;
思路
当cur当前累加和小于0时,清零,重新累加,用max记录最大值。
思路:只要确定在二分两侧的某一侧肯定存在你要找的内容,就可以使用二分查找,并不是一定要有序数组。
思路:记录当前位置的最大值和最小值
现在免费送给大家,在我的公众号 好好学java 回复 资料 即可获取。
有收获?希望老铁们来个三连击,给更多的人看到这篇文章
1、老铁们,关注我的原创微信公众号「好好学java」,专注于Java、数据结构和算法、微服务、中间件等技术分享,保证你看完有所收获。
2、给俺一个 star 呗,可以让更多的人看到这篇文章,顺便激励下我继续写作,嘻嘻。
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。