Skip to content

Latest commit

 

History

History
658 lines (460 loc) · 22.2 KB

算法题目难点题目总结.md

File metadata and controls

658 lines (460 loc) · 22.2 KB

智力题

作者:office多多 链接:https://www.nowcoder.com/discuss/374134?type=0&order=0&pos=67&page=1

  1. 10个堆,每堆10个苹果,其中9个堆里苹果是50g/个,一个堆里苹果是40g/个,有一杆秤只能称一次,所称重量为x,求40g苹果所在堆。

    • 将堆编码为1-10;然后每堆拿出k个,最后少了k*10克,则知道是第几堆的苹果。
  2. 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水。
  3. 两个一小时蚊香怎么得到15分钟的记时

    • 同时点燃AB两只蚊香,其中A蚊香点燃两头,等A蚊香烧完后(30分钟),点燃B蚊香的另一头。
  4. 4分钟沙漏和7分钟沙漏怎么漏出9分钟

    • 4分钟的和7分钟的同时开始,4分钟的完后又倒过来开始。7分钟的沙漏完后立马倒过来,(4分钟的沙漏还剩1分钟)。等4分钟的沙漏完后,将7分钟的又立马倒过来,等漏完就是9分钟。
  5. 八个球,其中有一个是其余球重量的1.5倍,有什么方案找出来

    • 3次。 AB两边,一边放4个,如果A重,则把B端的去了,A端的4个分成AB端一边两个。在把轻的那端去了,重的那端的2个分成一边一个,重的那个球就找出来了。
  6. 桌上100个球,每次可以拿一到五个, 现在我们两个人依次拿球,你先拿,使用怎样的拿球策略,可以使你最终能拿到最后一个球?

    • 第一次拿四个,后来每个你拿球的时候只要保证剩下的球是6的倍数就行了如果他拿n个球 ,你就拿6-n个球。
  7. 有10个石头,每人每次可以拿1-2个,轮流拿,最后一个拿的人算输,有什么必赢的方案。

    • 对方先拿、保证两个人每一轮回拿满3个(对方拿一个,我拿两个、对方拿两个,我拿一个)。
  8. 一亿数据获取前1000个最大值 https://zhuanlan.zhihu.com/p/73233544

    • 把一亿个数字的前100个 首先放入数组。 然后把最小值放在ary[0]。然后再循环100到一亿之间的。 每次循环判断当前数字是否大于ary[0]当大于时,当前数字放入ary[0] 并再次重构数组最小值进入ary[0]以此类推 。当循环完这一亿个数字后。 最大的前100个数字就出来了。
  9. 经典智力题:飞机加油问题

左神总结

leetcode经典题目

红黑树

链表

链表思路总结

1 将单向链表按某值划分成左边小、中间相等、右边大的形式(p59)

如果要求不按照原来的顺序排列

1、荷兰国旗问题解决。

如果要求按照原来的顺序排列

2、将原链表划分为三个链表,然后再连接起来。

2 复制含有随机指针节点的链表(p64)

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)将节点和复制节点拆分。

3 两个单链表生成相加链表(p66)

将两个链表代表的整数相加之后的数,再成为一个新的链表。

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;
}

4 将单链表的每k个节点之间逆序

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;
}

5 将搜索二叉树转换为双向链表

一般链表的题目都可以使用容器(栈、队列)来辅助完成。同时,一般需要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;

二叉树

1 二叉树遍历问题(P94)

  • 递归遍历模板
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收集起来就是左右中

遍历变形题:根据后续数组重建搜索二叉树(P148)

根据搜索二叉树性质,最后一个元素是头节点,比后序数组最后一个元素小的数组会在数组左边,比数组最后一个元素值大的数组在数组的右边。所以,我们需要找到后续数组中,小的数组的中的最后一个元素和大的数组中的第一个元素。

遍历变形题:判断一颗二叉树是否为搜索二叉树和完全二叉树(P150)

搜索二叉树:中序遍历,递增。 完全二叉树:层次遍历二叉树,有右孩子没有左孩子,为false,如果当前节点并不是左右孩子都有,那么后面的节点都必须是叶子节点。

2 打印二叉树的边界节点(P100)

经验:二叉树的大多数问题都是用递归来解决的,所以,碰到二叉树的问题,一定得想递归版本!
  • 递归的收集左右边界信息
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);    
}

3 在二叉树中找到累加和为指定值的最长路径长度(P119)

思路: 用一个 hashmap (key是累加和sum,value是当前层level) 保存每一步的累加和sum,例如,当到第三层的第一个节点的时候,当前的累加和sum的值,如果sum在hashmap中不存在,保存到hashmap中。然后递归的遍历求每个sum,同时,求最长路径长度Math.max(level-map.get(sum-k),max)

这个思路也可以用到数组中的累加和问题。

4 找到二叉树中的最大搜索二叉子树(P121)

思路

这个题目是二叉树中很多题目中的套路:树形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。

树形dp题目:判断二叉树是否是平衡二叉树(P146)

平衡二叉树的左右子树高度相差不能超过1,所以,我们需要的信息有height、isBST(是否是平衡二叉树)

树形dp题目:二叉树节点的最大距离问题(P168)
树形dp题目:排队的最大快乐值(P169)

保存yes_X_max:X来的情况。 保存no_X_max:X不来的情况。

  • 返回结构
public class ReturnType{
    public int yesHeadMax;
    public int noHeadMax;
}

5 二叉树的按层打印与ZigZag打印(P132)

本来按层打印只需要利用queue宽度遍历即可,但是,因为这里需要换行,所以,需要添加额外的辅助变量来换行的操作。

换行需要的变量:last表示正在打印的当前行的最右节点,nlast表示下一行的最右节点。

ZigZag打印:需要用到LinkedList双端队列。

原则1:从左往右打印,头部弹出元素打印,如果有孩子,孩子尾部加入队列。

原则2:从右往左打印,尾部弹出元素打印,如果有孩子,孩子头部加入队列。

6 调整搜索二叉树中两个错误的节点(P137)

搜索二叉树的中序遍历应该为递增的,找到两个节点,过程为:第一个错误节点为第一次降序时较大的节点,第二个错误的节点是最后一次降序时较小的节点。

7 判断t1树中是否有与t2树拓扑结构完全相同的子树(P144)

序列化二叉树,然后判断子串即可。

8 在二叉树中找到一个节点的后继节点(P153)

最简单方法

利用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;
    }
}

变形题:在二叉树中找到两个节点的最近公共祖先(P155)

方法1:利用后序遍历,递归方法。

1)如果cur等于null,或者等于o1或者o2,那么返回cur。 2)如果cur的left和right都为空,那么返回null,说明没有。 3)如果cur的left和right都不为空,那么cur就是。 4)如果cur的left和right一个为空,一个不为空,返回不是空的节点即可。

方法2:用hashmap给每个节点设置父节点。

利用hashmap,然后将o1节点往上遍历到节点,并把每个节点放入集合A中,然后o2往上遍历到头节点,只要遍历的节点发现在集合A中,那么这个节点就是公共祖先节点。

9 统计完全二叉树的节点数(P176)

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、神级遍历方法

动态规划

背包九讲

动态规划思路总结

ACM动态规划总结

leetcode动态规划总结(不错)

1 动态规划空间压缩解题思路(P232、P188)

思路

1、用一维数组代替二维数组,降低空间复杂度 2、需要记录的值: 必须值:一维数组的第一个值(累加值) 可能值:一维数组的上一行的前一个值(i-1)、一维数组的上一行的当前值(i) 3、初始化第一行的数据 4、有了相关值之后,从左到右,从上到下遍历。

tips(P185、P198、P203、P232、P235)

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)

2 动态规划解题思路

1)找到base case
2)找到依赖的位置有哪些
  • 通常依赖的位置
dp[i][j]、dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]。

累加:依赖某一行、某一列、行和列

  • 方法

方法1:如果题目简单,通过题目直接找出依赖。 方法2:如果题目复杂,写出递归版本,然后,根据递归版本,用普通的值代入,找出依赖哪些值。

3 递归方法解题思路(P204、P238、P240、P245、P249)

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)

4 字符串动态规划总结

最长递增子序列(P210)
  • 求出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]这个字符满足要求,遍历完所有的字符

最长公共子序列问题(P220)
  • 求出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]方向的,则是满足要求的字符。

最长公共子串(p223)
  • 求dp数组

如果当前两个字符串的字符相等,则dp[i][j] = dp[i-1][j-1] + 1,否则dp[i][j] = 0

  • 根据dp数组求公共子串

只需要找到最大的dp中的值max,然后往前遍历max次即可,收集这些值。

最小编辑代价(P230)

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
字符串交错组成(P233)

位置(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

数组中最长连续序列(P248,不需要用动态规划)

用hashmap保存key为数组中的值,value为当前值所在的子序列的长度len,每次遍历一个值的时候就更新,并且只需要更新子序列的开始值和结束值这两个边界即可。

递归

二分查找

数组

无序(正数)、有序数组求target数组(P380、P382、)

思路

可以采用双指针的方法进行求解(类似滑动窗口)。

left:当值大于target时,left++; right:当值小于target时,right++;

未排序数组中累加和为指定值的最长子数组系列问题(P384)

思路

用一个map记录(sum,j),key的sum为:从arr最左边开始累加最早出现的sum值,value的j为:sum值最早出现的位置。

map.get(sum-k)得到长度len;

子数组最大累加和(子矩阵最大累加和)(P397、P398)

思路

当cur当前累加和小于0时,清零,重新累加,用max记录最大值。

二分查找系列

在数组中找到局部最小的位置(P401)

思路:只要确定在二分两侧的某一侧肯定存在你要找的内容,就可以使用二分查找,并不是一定要有序数组

数组中的最大累乘积(P402)

思路:记录当前位置的最大值和最小值

Tip:本来有很多我准备的资料的,但是都是外链,或者不合适的分享方式,所以大家去公众号回复【资料】好了。

现在免费送给大家,在我的公众号 好好学java 回复 资料 即可获取。

有收获?希望老铁们来个三连击,给更多的人看到这篇文章

1、老铁们,关注我的原创微信公众号「好好学java」,专注于Java、数据结构和算法、微服务、中间件等技术分享,保证你看完有所收获。

2、给俺一个 star 呗,可以让更多的人看到这篇文章,顺便激励下我继续写作,嘻嘻。