• [刷题记录]牛客面试笔刷TOP101(一)

    牛客笔试算法必刷TOP101系列,每日更新中~(主要是记录自己的刷题,所以描述的可能不是很清楚

    但如果刚好能帮助到你就更好了)

    后续后头复习的时候,记得是看正解啊,别对着错的例子傻傻看了...

    目录

    1.合并有序链表2023.9.3

    2.链表是否有环2023.9.4

    3.判断链表中环的入口点

    4.链表中倒数最后K个节点2023.9.5

    5.删除链表的倒数第n个节点

    6.两个链表的第一个公共节点2023.9.6

    7.链表相加

    8.单链表的排序23.9.7

     9.判断一个链表是否为回文结构

    10.链表的奇偶(节点)重排23.9.8

    11.删除有序链表中的重复元素

    12.删除有序链表中的重复元素||23.9.9

    13.二分查找-| 23.9.10

    14.二维数组中的查找

    15寻找峰值

    16.比较版本号23.9.11

    17.二叉树的前序遍历

    18.二叉树的中序遍历

    19二叉树的后序遍历

    20.二叉树的层序遍历23.9.12

    21.按之字形顺序打印二叉树

    22.二叉树的最大深度23.9.13

    23.二叉树中和为某一值的路径(一)

    24.二叉搜索树与双向链表

    25.对称的二叉树23.9.14

    1.合并有序链表2023.9.3

    合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com)

    题意大致为:

    将两个链表中的元素按照从小到大的顺序合并成为一个链表.

    所给予的条件:

    给出的所要合并的链表都是从小到大顺序排列的.

    思路:

    创建一个新的头节点来方便组装新的链表.分别用两个指针遍历两个链表,比较两个指针所在的节点,较小的节点先一步存放到新链表中,并且相应的指针向后移动一位.

    移动后的指针所在的节点再与先前较大的未移动的节点进行比较,循环进行上面的操作.

    直到任一链表遍历完毕,再把另一没遍历完的链表剩下的节点连接到新链表的尾巴. 

    错解:

    1. public ListNode Merge (ListNode pHead1, ListNode pHead2) {
    2.         // write code here
    3.         ListNode fakeHead = new ListNode(-1);
    4.         ListNode cur = fakeHead;
    5.         while(pHead1.next != null || pHead2.next != null){//我怎么用了或呢!!!
    6.                                                    //明明是把链表都遍历一遍不要管他next
    7.             if(pHead1.val <= pHead2.val){
    8.                 cur.next = pHead1;
    9.                 cur = cur.next;
    10.                 pHead1 = pHead1.next;
    11.             }else{
    12.                 cur.next = pHead2;
    13.                 cur = cur.next;
    14.                 pHead2 = pHead2.next;
    15.             }
    16.         }
    17.         if(pHead1.next == null){//上面错,下面跟着错了.
    18.             cur.next = pHead2;
    19.         }
    20.         if(pHead2.next == null){
    21.             cur.next = pHead1;
    22.         }
    23.         return fakeHead.next;
    24.     }

    刚开始,可能脑袋真的不好使了.

    明明想的是,要把链表都遍历完整一遍,分别拿每一个节点跟另一个链表的节点进行比较.结果while循环中写的却是.next.还想不出问题在哪里真的是罪过.

    还有while循环条件中的连接符号居然用的||.

    只要有一个链表遍历完了就结束循环,所以要用&&啊啊啊!!!

    真的是出师未捷身先死,下面好好加油吧.

    正确题解:

    起码脑子里的思路是对的,就是想的跟写的对不太上...

    1. import java.util.*;
    2.  
    3. /*
    4.  * public class ListNode {
    5.  *   int val;
    6.  *   ListNode next = null;
    7.  *   public ListNode(int val) {
    8.  *     this.val = val;
    9.  *   }
    10.  * }
    11.  */
    12.  
    13.  
    14. public class Solution {
    15.     /**
    16.      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    17.      *
    18.      * 
    19.      * @param pHead1 ListNode类 
    20.      * @param pHead2 ListNode类 
    21.      * @return ListNode类
    22.      */
    23.     public ListNode Merge (ListNode pHead1, ListNode pHead2) {
    24.         // write code here
    25.         if(pHead1 == null){
    26.             return pHead2;
    27.         }
    28.         if(pHead2 == null){
    29.             return pHead1;
    30.         }
    31.         ListNode fakeHead = new ListNode(-1);
    32.         ListNode cur = fakeHead;
    33.         while(pHead1 != null && pHead2 != null){//这里之前用了||
    34.             if(pHead1.val <= pHead2.val){
    35.                 cur.next = pHead1;
    36.  
    37.                 pHead1 = pHead1.next;
    38.             }else{
    39.                 cur.next = pHead2;
    40.                 
    41.                 pHead2 = pHead2.next;
    42.             }
    43.             cur = cur.next;
    44.         }
    45.         if(pHead1 == null){
    46.             cur.next = pHead2;
    47.         }else{
    48.             cur.next = pHead1;
    49.         }
    50.         return fakeHead.next;
    51.     }
    52. }

    2.链表是否有环2023.9.4

    判断链表中是否有环_牛客题霸_牛客网 (nowcoder.com)

    题意:

    判断链表中是否有环,环所指的是:链表中节点的next存放此节点先前节点的地址.

    给予的条件:

    普通链表一个

    思路:

    这道题先前有学习过,我学到了两种解法.

    ①:用快慢指针的方法,快指针的速度是慢指针的两倍.在完全遍历完链表先前,如果快指针与慢指针相遇了,则证明此链表中含有环.反之,证明没有.(闭环追及问题)

    ②:用HashSet的方法,将链表进行遍历,把遍历到的节点的地址存放到set当中.如果链表有环则必定会有节点重复存放第二次,就可以用contains来判断有没有环.

    1. public static boolean hasCycle(ListNode head) {
    2.         ListNode fast = head;
    3.         ListNode slow = head;
    4.         //因为fast一次走两步,在while循环中就要判断能否有足够的位置够一次走两步
    5.         //首先要判断fast!=null,看是否遍历完成,如果没有再看其后面有没有节点
    6.         while(fast != null && fast.next != null){
    7.             fast = fast.next.next;
    8.             slow = slow.next;
    9.             if(slow == fast){
    10.                 return true;
    11.             }
    12.         }
    13.         return false;
    14.     }

    3.判断链表中环的入口点

    链表中环的入口结点_牛客题霸_牛客网 (nowcoder.com)

    思路:首先是要判断链表有没有环,有环才能进行后面的操作

    1. public ListNode EntryNodeOfLoop(ListNode pHead) {
    2.         ListNode fast = pHead;
    3.         ListNode slow = pHead;
    4.         boolean check = false;
    5.         //首先要判断链表有没有环
    6.         while(fast != null && fast.next != null){
    7.             fast = fast.next.next;
    8.             slow = slow.next;
    9.             if(fast == slow){
    10.                 check = true;
    11.                 break;
    12.             }
    13.         }
    14.         if(!check){
    15.             //证明没有环
    16.             return null;
    17.         }
    18.         slow = pHead;
    19.         while(slow != fast){
    20.             slow = slow.next;
    21.             fast = fast.next;
    22.         }
    23.         return fast;
    24.     }

    4.链表中倒数最后K个节点2023.9.5

    链表中倒数最后k个结点_牛客题霸_牛客网 (nowcoder.com)

    题意:

    根据给出的K,来返回链表中倒数第K个节点及其往后的所有节点.

    思路:(有误)

    这个题目以前写过了.

    用的是快慢指针的方式,倒数第一个与倒数第K个节点之间相差K-1个节点.

    所以,可以先让快指针从头节点走k-1步,再让慢指针从头节点开始,与快指针一齐一次走一步,直到快指针到达了末尾节点,此时慢指针所在的节点就是倒数第K个节点.

    将慢指针所在的节点返回即可. 

    纠正:

    其实这里的本质是,控制两端的距离,再平行的进行移动.

    快指针其实移动k个节点会好一点,

    错解:

    这里写的是移动k个节点了,跟想的时候不一样.如果是移动k个节点,看的是末尾后一个位置即空节点与倒数第K个节点的位置距离.

    例如,倒数第三个节点,与空节点相差的距离是3.即倒数第三个节点要移动3次才能到达空节点的位置.

    先判定再移动是为了能预防出现快指针走过头,走到了null,直接返回null却没有返回slow的情况

    如果链表长5,求倒数第6个节点的时候,就会出现.

    1. public ListNode FindKthToTail (ListNode pHead, int k) {
    2.         if(pHead == null){
    3.             return null;
    4.         }
    5.         // write code here
    6.         ListNode fast = pHead;
    7.         ListNode slow = pHead;
    8.         for(int i = 0; i < k; i++){
    9.             fast = fast.next;
    10.             if(fast == null){
    11.                 return null;//主要是这里的问题,
    12.                             //因为倒数的k刚好为链表的长度,而fast是从头节点1开始
    13.                             //走到空指针之后就直接返回了
    14.                             //其实应该把if判定条件放到移动指针的上面
    15.                             //而且在外面加一个判断k是否合法的条件
    16.                             //当k小于0或等于0时返回null.
    17.             }
    18.         }
    19.         while(fast != null){//fast要在尾巴节点停下来
    20.             fast = fast.next;
    21.             slow = slow.next;
    22.         }
    23.         return slow;
    24.     }

    正解:

    2023.9.7补充一下,for循环里面的if主要是为了防止越界的,证明当前fast指针指向的节点不为空,可以继续往下走.是作为条件而不是判断,所以要放在上面而不是下面.

    1. public ListNode FindKthToTail (ListNode pHead, int k) {
    2.         if(pHead == null){
    3.             return null;
    4.         }
    5.         // write code here
    6.         ListNode fast = pHead;
    7.         ListNode slow = pHead;
    8.         for(int i = 0; i < k; i++){
    9.             if(fast == null){
    10.                 return null;
    11.             }
    12.             fast = fast.next;
    13.             
    14.         }
    15.         while(fast != null){//fast要在尾巴节点停下来
    16.             fast = fast.next;
    17.             slow = slow.next;
    18.         }
    19.         return slow;
    20.     }

    5.删除链表的倒数第n个节点

    删除链表的倒数第n个节点_牛客题霸_牛客网 (nowcoder.com)

    嗨呀,这个跟上面一起写的.简单啦,我就不信我会错.

    思路(否决):

    既然是删除,肯定要找到被删除的节点的前驱与后驱.再将他们连接起来.

    找到倒数第n个节点,继续用快慢指针的方式来找.

    有一个问题,slow的位置恰好倒数第n个的位置,那么其前驱我们就不能知道了.

    所以要找倒数第n个位置的前一个,那么slow与fast之间的距离就会增加一位.变成了fast走n+1

    还想到了,可能会删除头节点这种情况,想在fast移动之后加上一个判定条件 

    思路(第二版):

    觉得上面的太麻烦了,还容易出错.因为上面的思路会存在越界的行为.

    头节点会变动的题型还是创建一个假的头节点来存放比较好.再加上一个新的指针在slow指针的前一位变动,tmp就是前驱slow是倒数第n个fast是后驱.将tmp与fast连接起来就好了

    1. public ListNode removeNthFromEnd (ListNode head, int n) {
    2.         // write code here
    3.         ListNode fast = head;
    4.         ListNode slow = head;
    5.         ListNode fakeHead = new ListNode(-1);
    6.         fakeHead.next = head;
    7.         ListNode tmp = fakeHead;
    8.         // if(n <= 0){
    9.         //     return null;
    10.         // }  写完才看到,题目保证n一定有效
    11.  
    12.         for(int i = 0; i < n; i++){
    13.             if(fast == null){//走过头了
    14.                 return null;
    15.             }
    16.             fast = fast.next;
    17.         }
    18.  
    19.         while(fast != null){
    20.             fast = fast.next;
    21.             slow = slow.next;
    22.             tmp = tmp.next;
    23.         }
    24.         
    25.         tmp.next = slow.next;
    26.         return fakeHead.next;
    27.     }

    6.两个链表的第一个公共节点2023.9.6

    两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com)

    思路:

    也是炒冷饭了.想到的是先遍历链表,分别得到他们的长度.

    用双指针的方式,对于较长的链表先走两个链表长度差的距离.

    再让两个指针分别从链表出发,一次走一步直到null,如果其中两指针相对,则证明有公共节点,

    然后还学到了第二个方法.

    对比上面的方法的优点是:不用考虑哪一个链表比较长,也不用额外写代码来得到链表的长度.虽然他们的本质都是双指针的方式.

    就像下图的一样,直接让两个指针从两个链表的头节点开始一起往下走,任一一个指针遍历完所在的链表后,来到空节点时则会跳转到另一条链表的头节点开始遍历.

    观察下面的图我们可以发现,这样就能消除链表长度导致的长度差.

    1. public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    2.         ListNode l1 = pHead1;
    3.         ListNode l2 = pHead2;
    4.  
    5.         while(l1 != l2){
    6.             if(l1 == null){
    7.                 l1 = pHead2;
    8.             }else{
    9.                 l1 = l1.next;
    10.             }
    11.  
    12.             if(l2 == null){
    13.                 l2 = pHead1;
    14.             }else{
    15.                 l2 = l2.next;
    16.             }
    17.         }
    18.         return l1;
    19.     }

    7.链表相加

    链表相加(二)_牛客题霸_牛客网 (nowcoder.com)

    思路:

    我只能想到把链表都给翻转了才进行后面的操作.

    然后创建一个新的头节点,创建新的节点.如果现在相加的节点个位溢出了就要移动到下一位去.

    先写写看吧.

    错解(愚蠢的错误):

    最后一个例子没过去,好可惜.

    努力找找看哪里错了吧...我看别人的代码好优雅噢.我的有点不堪.

    1. public ListNode addInList (ListNode head1, ListNode head2) {
    2.         // write code here
    3.         //先翻转两个链表
    4.         head1 = rever(head1);
    5.         head2 = rever(head2);
    6.         ListNode fakeHead = new ListNode(-1);
    7.         //创建两个指针来遍历链表
    8.         ListNode l1 = head1;
    9.         ListNode l2 = head2;
    10.         ListNode cur = fakeHead;//遍历新链表
    11.         //存储溢出
    12.         int count = 0;
    13.         while(l1 != null && l2 != null){
    14.             int tmp = l1.val + l2.val + count;
    15.             if(tmp >= 10){
    16.                 tmp -= 10;//溢出了,得留到下一个.
    17.                 count = 1;
    18.             }else{
    19.                 count = 0;
    20.             }
    21.             ListNode node = new ListNode(tmp);
    22.             cur.next = node;
    23.             cur = node;
    24.  
    25.             l1 = l1.next;
    26.             l2 = l2.next;
    27.         }
    28.         while(l1 != null){
    29.            int tmp = l1.val + count;
    30.            if(tmp >= 10){
    31.                 tmp -= 10;
    32.                 count = 1;
    33.            }else{
    34.                 count = 0;
    35.            }
    36.            ListNode node = new ListNode(tmp); 
    37.            cur.next = node;
    38.            cur = node;
    39.            l1 = l1.next;
    40.         }
    41.         while(l2 != null){
    42.            int tmp = l2.val + count;
    43.            if(tmp >= 10){
    44.                 tmp -= 10;
    45.                 count = 1;
    46.            }else{
    47.                 count = 0;
    48.            }
    49.            ListNode node = new ListNode(tmp); 
    50.            cur.next = node;
    51.            cur = node;
    52.            l1 = l1.next;//什么东西啊,什么东西啊.对自己无语啦.,把这里改成l2就好了
    53.         }
    54.         if(count != 0){
    55.             ListNode node = new ListNode(count);
    56.             cur.next = node;
    57.             cur = node;
    58.         }
    59.         return rever(fakeHead.next);
    60.     }
    61.  
    62.     public ListNode rever(ListNode head){
    63.         ListNode cur = head.next;
    64.         ListNode pre = head;
    65.         while(cur != null){
    66.             ListNode curNext = cur.next;
    67.             cur.next = pre;
    68.             pre = cur;
    69.             cur = curNext;
    70.         }
    71.         head.next = null;
    72.         return pre;
    73.     }

    正解:

    在错解里的代码改了.糊涂啊糊涂 

    8.单链表的排序23.9.7

    单链表的排序_牛客题霸_牛客网 (nowcoder.com)

    思路(没想到):

    一开始我只想到了把链表放到数组里面,在数组中进行排序之后再赋值到链表上.但是感觉不怎么好,又看到了题解里面说的用分治的思想,其实就是归并排序嘛.但是我内心会对递归有一定的抵触心理...但还是认真看了一遍题解,也自己动手画了一遍图.思路是清晰了,但不知道代码写得怎么样.先动手看看吧.

    1. public ListNode sortInList (ListNode head) {
    2.         // write code here
    3.         //既然是用归并排序递归的思路:
    4.         //递归首先要考虑的是其结束的条件.
    5.         //当只剩一个节点或没有节点的时候结束拆链表的递归操作
    6.         if(head == null || head.next == null){
    7.             return head;//返回当前节点
    8.         }
    9.         //先找到链表的中间点,进行拆.
    10.         //找中间点用到了快慢指针的思想,再加上一个中间点的前驱节点才能进行拆除
    11.         ListNode left = head;
    12.         ListNode mid = head.next;
    13.         ListNode right = mid.next;
    14.         while(right != null || right.next != null){
    15.             //因为要考虑链表节点个数的奇偶情况
    16.             //奇数个的时候right指针走到尾巴节点就该停下来了,再继续走两步会越界
    17.             //所以是right.next!=null的情况
    18.             //偶数个的时候right指针可以走到尾巴节点的后一个空节点
    19.             //还有就是因为right一次走两步的关系,需要判断能否还有足够的节点
    20.             left = left.next;
    21.             mid = mid.next;
    22.             right = right.next.next;
    23.         }
    24.         //走完了,此时mid来到了中间节点的位置,left是mid的前驱节点的位置
    25.         //别忘了head
    26.         //此时前半段链表就被head和left所包裹
    27.         //后半段链表就被mid与right所包裹
    28.         //就要将他们分开了
    29.         left.next = null;
    30.         //继续调用来递归
    31.         ListNode lhead = sortInList(head);//递归前半段
    32.         ListNode rhead = sortInList(mid);//递归后半段
    33.         //将他们进行排序
    34.         //写一个排序的方法
    35.         return sort(lhead,rhead);
    36.     }
    37.  
    38.     public ListNode sort(ListNode p1,ListNode p2){
    39.         //此处用双指针的方式,来分别遍历两个链表
    40.         //就跟归并排序里的一样了
    41.         //还要判断谁空了就返回另一半
    42.         if(p1 == null){
    43.             return p2;
    44.         }
    45.         if(p2 == null){
    46.             return p1;
    47.         }
    48.         //重新创建一个新的链表来存储
    49.         ListNode cur = new ListNode(-1);
    50.         while(p1 != null && p2 != null){
    51.             if(p1.val > p2.val){
    52.                 cur.next = p2;
    53.                 p2 = p2.next;
    54.             }else{
    55.                 cur.next = p1;
    56.                 p1 = p1.next;
    57.             }
    58.         }
    59.         //如果有剩余的节点没有遍历到,就直接加上去
    60.         if(p1 != null){
    61.             cur.next = p1;
    62.         }else{
    63.             cur.next = p2;
    64.         }
    65.         return cur.next;//最后返回排好序的链表
    66.     }

    正解:

    都没有什么大错误,就是有一些逻辑上的不清楚.

    也算是对递归这个心魔没那么恐惧了吧...

    1. public ListNode sortInList (ListNode head) {
    2.         // write code here
    3.         //既然是用归并排序递归的思路:
    4.         //递归首先要考虑的是其结束的条件.
    5.         //当只剩一个节点或没有节点的时候结束拆链表的递归操作
    6.         if(head == null || head.next == null){
    7.             return head;//返回当前节点
    8.         }
    9.         //先找到链表的中间点,进行拆.
    10.         //找中间点用到了快慢指针的思想,再加上一个中间点的前驱节点才能进行拆除
    11.         ListNode left = head;
    12.         ListNode mid = head.next;
    13.         ListNode right = mid.next;
    14.         while(right != null && right.next != null){//错误1:调试后发现错误了||
    15.             //因为要考虑链表节点个数的奇偶情况
    16.             //奇数个的时候right指针走到尾巴节点就该停下来了,再继续走两步会越界
    17.             //所以是right.next!=null的情况
    18.             //偶数个的时候right指针可以走到尾巴节点的后一个空节点
    19.             //还有就是因为right一次走两步的关系,需要判断能否还有足够的节点
    20.             left = left.next;
    21.             mid = mid.next;
    22.             right = right.next.next;
    23.         }
    24.         //走完了,此时mid来到了中间节点的位置,left是mid的前驱节点的位置
    25.         //别忘了head
    26.         //此时前半段链表就被head和left所包裹
    27.         //后半段链表就被mid与right所包裹
    28.         //就要将他们分开了
    29.         left.next = null;
    30.         //继续调用来递归
    31.         ListNode lhead = sortInList(head);//递归前半段
    32.         ListNode rhead = sortInList(mid);//递归后半段
    33.         //将他们进行排序
    34.         //写一个排序的方法
    35.         return sort(lhead,rhead);
    36.     }
    37.  
    38.     public ListNode sort(ListNode p1,ListNode p2){
    39.         //此处用双指针的方式,来分别遍历两个链表
    40.         //就跟归并排序里的一样了
    41.         //还要判断谁空了就返回另一半
    42.         if(p1 == null){
    43.             return p2;
    44.         }
    45.         if(p2 == null){
    46.             return p1;
    47.         }
    48.         //重新创建一个新的链表来存储
    49.         ListNode head = new ListNode(-1);//补充3:这里忘记加一个遍历的指针了
    50.         //直接用头节点去接了怪不得返回只有一个节点
    51.         ListNode cur = head;
    52.         while(p1 != null && p2 != null){
    53.             if(p1.val >= p2.val){//补充2 加一个=
    54.                 cur.next = p2;
    55.                 p2 = p2.next;
    56.             }else{
    57.                 cur.next = p1;
    58.                 p1 = p1.next;
    59.             }
    60.             cur = cur.next;//补充1
    61.         }
    62.         //如果有剩余的节点没有遍历到,就直接加上去
    63.         if(p1 != null){
    64.             cur.next = p1;
    65.         }else{
    66.             cur.next = p2;
    67.         }
    68.         return head.next;//最后返回排好序的链表
    69.     }

     9.判断一个链表是否为回文结构

    判断一个链表是否为回文结构_牛客题霸_牛客网 (nowcoder.com)

    思路:

    找到中间的节点,将后半段链表进行翻转.

    用双指针的形式,从开头与中间开始遍历节点.如果两者不一样,则证明为不是回文结构.

     错解:

    不是很明白出什么问题了,先放到idea调试看看

    主要是翻转之后与前半段的链接没有处理好.

    我想实现的是指针分别遍历,没有给他们设null,直到他们相遇或者在偶数情况下在相邻的时候结束循环.

    错的原因写在相应的注释里了,链表题还是要好好画图啊.还有记得理清一下循环结束的条件,是用||还是&&

    1. public boolean isPail (ListNode head) {
    2.         // write code here
    3.         //先用双指针的形式找到中间节点,如果是偶数个节点,就找中间靠右的节点
    4.         if(head == null || head.next == null){
    5.             return true;//如果只有一个节点或者为空则
    6.         }
    7.         ListNode slow = head;
    8.         ListNode fast = head;
    9.         boolean count = true;
    10.         while(fast != null && fast.next != null){
    11.             slow = slow.next;
    12.             fast = fast.next.next;
    13.         }
    14.         //此时slow为中间节点
    15.         //这里本质上还是多此一举了,如果是奇数个直接从中间开始翻转就好了
    16.         //这里的想法也是想把中间节点与翻转后的末尾进行连接,让两个指针能够相遇
    17.         //但是顺序错了,而且这样就会太复杂
    18.         if(fast != null){
    19.             //证明为奇数个数,中间节点向后走一个
    20.             ListNode mid = slow;
    21.             slow = slow.next;
    22.             slow.next = mid;
    23.         }
    24.         //翻转后半段
    25.         slow = reverse(slow);
    26.         while(head != slow || head.next != slow){//还要你,我最近怎么老是用错||与&&
    27.             if(head.val != slow.val){
    28.                 count = false;
    29.                 break;
    30.             }
    31.             head = head.next;
    32.             slow = slow.next;
    33.         }
    34.         return count;
    35.     }
    36.  
    37.     public ListNode reverse(ListNode head){
    38.         ListNode cur = head.next;
    39.         ListNode pre = head;
    40.         while(cur != null){
    41.             ListNode curNext = cur.next;
    42.             cur.next = pre;
    43.             pre = cur;
    44.             cur = curNext;
    45.         }
    46.         return pre;
    47.     }

    正解:

    还是得自己调试和画图才能写出来,下次加油嗷.

    1. public boolean isPail (ListNode head) {
    2.         // write code here
    3.         //先用双指针的形式找到中间节点,如果是偶数个节点,就找中间靠右的节点
    4.         if(head == null || head.next == null){
    5.             return true;//如果只有一个节点或者为空则
    6.         }
    7.         ListNode slow = head;
    8.         ListNode fast = head;
    9.         boolean count = true;
    10.         while(fast != null && fast.next != null){
    11.             slow = slow.next;
    12.             fast = fast.next.next;
    13.         }
    14.         //此时slow为中间节点
    15.         
    16.         //翻转后半段
    17.         slow = reverse(slow);//得到的slow是翻转后的了,相当于链表的末尾
    18.         
    19.         while(head != slow && head.next != slow){//中间放个&&是同时照顾到链表节点的个数为奇偶情况
    20.             if(head.val != slow.val){
    21.                 count = false;
    22.                 break;
    23.             }
    24.             head = head.next;
    25.             slow = slow.next;
    26.         }
    27.         return count;
    28.     }
    29.  
    30.     public ListNode reverse(ListNode head){
    31.         ListNode cur = head.next;
    32.         ListNode pre = head;
    33.         while(cur != null){
    34.             ListNode curNext = cur.next;
    35.             cur.next = pre;
    36.             pre = cur;
    37.             cur = curNext;
    38.         }
    39.         return pre;
    40.     }

    10.链表的奇偶(节点)重排23.9.8

    链表的奇偶重排_牛客题霸_牛客网 (nowcoder.com)

    注意是链表的节点噢

    思路(错误):

    用双指针的形式,p1指针从head开始,p2从head.next开始.

    都为一次走两步,p1遍历奇数节点,p2遍历偶数节点.

    感觉能写出来,开心呢!

    错解:

    好像死循环了...但是我看不出来

    debug后发现,主要是分开遍历分别把他们添加到新链表中会改变他们的next,导致在链表中形成环.

    1. public ListNode oddEvenList (ListNode head) {
    2.         // write code here
    3.         if(head == null || head.next == null){//只有一个节点的,直接返回
    4.             return head;
    5.         }
    6.         ListNode p1 = head;
    7.         ListNode p2 = head.next;
    8.         ListNode fakeHead = new ListNode(-1);
    9.         ListNode cur = fakeHead;
    10.         //先遍历奇数节点
    11.         while(p1 != null && p1.next != null){//debug后发现,是这里条件的问题
    12.                                             //链表个数为奇数个时p1会在最后一个节点停下来
    13.                                             //但是没有进行下面的操作,再走到下面的循环就会死循环
    14.                                              //但不是主要的问题...
    15.             cur.next = p1;
    16.             p1 = p1.next.next;
    17.             cur = cur.next;
    18.         }
    19.         while(p2 != null && p2.next != null){
    20.             cur.next = p2;
    21.             p2 = p2.next.next;
    22.             cur = cur.next;
    23.         }
    24.         cur.next = null;
    25.         return fakeHead.next;
    26.     }

    正解:

    可以一起遍历,两个指针作为相互的下一步的接口.

    p1.next = p2.next;奇数的next变成偶数的next,偶数的next是下一个奇数位

    然后p1 = p2.next来到刚刚存放的奇数位.

    p2.next = p1.next.偶数的next变成奇数的next,奇数的next是下一个偶数位.

    就这样把奇数和偶数分开遍历了一遍.并把他们都连接起来了.

    最后只要把连接好的偶数位放到奇数位的后边

    1. public ListNode oddEvenList (ListNode head) {
    2.         // write code here
    3.         if(head == null || head.next == null){//只有一个节点的,直接返回
    4.             return head;
    5.         }
    6.         ListNode p1 = head;
    7.         ListNode p2 = head.next;
    8.         //分别把奇数位与偶数位交叉串起来
    9.         ListNode p2Head = p2;
    10.         while(p2 != null && p2.next != null){//因为p2是先遍历的节点,所以以其为结束条件
    11.             p1.next = p2.next;
    12.             p1 = p2.next;
    13.             p2.next = p1.next;
    14.             p2 = p1.next;
    15.         }
    16.         //再把偶数放到奇数后面
    17.         p1.next = p2Head;
    18.         return head;
    19.     }

    11.删除有序链表中的重复元素

    删除有序链表中重复的元素-I_牛客题霸_牛客网 (nowcoder.com)

    思路:

    如果下一个节点的val是相同的就while一路next直到下一个不同样,再把他连接上.

    用双指针的方式?

    1. public ListNode deleteDuplicates (ListNode head) {
    2.         // write code here
    3.         if(head == null){
    4.             return head;
    5.         }
    6.         ListNode p1 = head;
    7.         ListNode p2 = head.next;
    8.         while(p2 != null){
    9.             if(p1.val == p2.val){
    10.                 p2 = p2.next;
    11.             }else{
    12.                 p1.next = p2;
    13.                 p1 = p1.next;
    14.                 p2 = p1.next;
    15.             }
    16.         }
    17.         return head;
    18.     }

     

    正解:

    思考了一下后,发现.

    永远是以p2为结束条件,所以跳出循环的时候p2一定为null.

    那最后不管p1的next是怎么样的,都把他给上p2即null就不会出错啦.

    1. public ListNode deleteDuplicates (ListNode head) {
    2.         // write code here
    3.         if(head == null){
    4.             return head;
    5.         }
    6.         ListNode p1 = head;
    7.         ListNode p2 = head.next;
    8.         while(p2 != null){
    9.             if(p1.val == p2.val){
    10.                 p2 = p2.next;
    11.             }else{
    12.                 p1.next = p2;
    13.                 p1 = p1.next;
    14.                 p2 = p1.next;
    15.             }
    16.         }
    17.         p1.next = p2;
    18.         return head;
    19.     }

    12.删除有序链表中的重复元素||23.9.9

    删除有序链表中重复的元素-II_牛客题霸_牛客网 (nowcoder.com)

    思路:

    只能想到用map的方法来写,计算出现的频率留下只出现一次的节点.

    双指针的方式尝试了,但是写不出来..

    正解:

    双指针的主要思路是,先看后动.

    用一个指针p2遍历链表,查看其当前val是否与下一个节点的val相同.

    如果相同就next,直到遇到下一个与其val不同的节点.

    这时,p2就会在相同节点的最后一个停下来.

    然后观察负责连接的指针p1与p2的关系.

    如果p1的下一个就是p2,那么证明两个节点为相邻的节点,p1就可以移动一步

    如果p1的下一个不是p2,那么证明刚刚p2遇到了重复的元素并进行了跳过.就需要连接p2的next节点(p2会在相同val节点的末端停下).

    最后p2继续遍历链表

    1. public ListNode deleteDuplicates (ListNode head) {
    2.         // write code here
    3.         if(head == null || head.next == null){
    4.             return head;
    5.         }
    6.         
    7.         //因为头节点可能会被删掉,所以加一个假的头节点
    8.         ListNode fakeHead = new ListNode(-1);
    9.         fakeHead.next = head;
    10.         ListNode p1 = fakeHead;
    11.         ListNode p2 = head;
    12.         while(p2 != null){
    13.             //p2遍历链表,p1用来连接
    14.             while(p2.next != null && p2.val == p2.next.val){//会在相同点的最后一个停下来
    15.                 p2 = p2.next;
    16.             }
    17.             if(p1.next == p2){
    18.                 p1 = p1.next;
    19.             }else{
    20.                 p1.next = p2.next;
    21.             }
    22.             p2 = p2.next;
    23.         }
    24.         return fakeHead.next;
    25.     }

    13.二分查找-| 23.9.10

    二分查找-I_牛客题霸_牛客网 (nowcoder.com)

    思路:

    让我回忆一下二分查找是什么...

    在升序数组中,要找到一个target.

    三个指针,left,mid,right.

    先查看mid所在的数值为多少,如果mid比target小,则证明target在右半边.left = mid + 1,mid = (left+right)/2.

    如果mid比target大,则证明target在左半边,right = mid - 1,mid = (left+right)/2.

    如果mid == target则返回mid.

    1. public int search (int[] nums, int target) {
    2.         if(nums.length == 0){
    3.             return -1;
    4.         }
    5.         int left = 0;
    6.         int right = nums.length;
    7.         int count = -1;
    8.         while(left <= right){//这里记得要给等号噢,只剩两位数的时候可能会遍历不到
    9.             int mid = (left + right) / 2;
    10.             if(nums[mid] == target){
    11.                 count = mid;
    12.                 break;
    13.             }else if(nums[mid] > target){
    14.                 right = mid - 1;
    15.             }else if(nums[mid] < target){
    16.                 left = mid + 1;
    17.             }
    18.         }
    19.         return count;
    20.     }

    14.二维数组中的查找

    二维数组中的查找_牛客题霸_牛客网 (nowcoder.com)

    思路:

    升序的二维数组...

    先从第一个数组末尾开始向左遍历

    遇到比target大的,就向左移动一位.

    遇到比target小的,就向下移动一位.

    1. public boolean Find (int target, int[][] array) {
    2.         // write code here
    3.         int y = array[0].length - 1;//得到一行的长度
    4.         int x = 0;//得到一共有多少行
    5.         int n = array.length - 1;
    6.         while(x <= n && y >= 0){
    7.             if(array[x][y] == target){
    8.                 return true;
    9.             }else if(array[x][y] > target){
    10.                 y--;
    11.             }else if(array[x][y] < target){
    12.                 x++;
    13.             }
    14.         }
    15.         return false;
    16.     }

    15寻找峰值

    寻找峰值_牛客题霸_牛客网 (nowcoder.com)

    思路:

    想直接暴力模拟,但是会越界.

    正解:

    采用二分查找的方法,其实我一开始也想到了用二分查找.但判断的是两个边界与mid的关系,而不是mid与周围元素的关系.

    这个向左收缩,right = mid 而不是mid-1

    1. public int findPeakElement (int[] nums) {
    2.         // write code here
    3.         if(nums.length == 1){
    4.             return 0;
    5.         }
    6.         int left = 0;
    7.         int right = nums.length - 1;
    8.         int mid = 0;
    9.         while(left < right){
    10.             mid = (left + right) / 2;
    11.             if(nums[mid] < nums[mid+1]){
    12.                 left = mid + 1;//如果mid的右边元素比mid大证明mid不可能是波峰
    13.                                 //区间往右边收缩
    14.             }else{
    15.                 //如果mid的左边元素比mid小,mid可能是波峰
    16.                 //所以不能-1跳过mid缩小区间了
    17.                 right = mid;
    18.             }
    19.         }
    20.         return left;//不断缩小区间,直到两边界相等时,得到的为波峰
    21.     }

    16.比较版本号23.9.11

    比较版本号_牛客题霸_牛客网 (nowcoder.com)

    思路:

    以'.'为分隔,获取数字.

    每一个"."之间的数值进行比较.

    注意的是,要比较一整个数.

    例入:0.226与0.38.因为226大于38所以前面的版本号是久一点的.

    1. public int compare (String version1, String version2) {
    2.         // write code here
    3.         int len1 = version1.length();
    4.         int len2 = version2.length();
    5.         int i = 0;
    6.         int j = 0;
    7.         while(i < len1 || j < len2){//可以不关注之间的长度差,注意不越界就行
    8.             int count1 = 0;
    9.             while(i < len1){
    10.                 char ch = version1.charAt(i);//获取下标的字符
    11.                 if(ch == '.'){//如果是"."就跳过
    12.                     i++;
    13.                     break;
    14.                 }else{//如果不是就加起来,记得*10是为了进位
    15.                     count1 = (count1 * 10) +  ch - '0'; 
    16.                     i++;
    17.                 }
    18.             }
    19.             int count2 = 0;
    20.             while(j < len2){
    21.                 char ch = version2.charAt(j);
    22.                 if(ch == '.'){
    23.                     j++;
    24.                     break;
    25.                 }else{
    26.                     count2 = (count2 * 10) + ch - '0';
    27.                     j++;
    28.                 }
    29.             }
    30.             //此处的比较是按照"."来分割的,比较两个字符串同一位置整个修订号的大小
    31.             if(count1 > count2){
    32.                 return 1;
    33.             }else if(count1 < count2){
    34.                 return -1;
    35.             }
    36.         }
    37.         return 0;
    38.     }

    17.二叉树的前序遍历

    二叉树的前序遍历_牛客题霸_牛客网 (nowcoder.com)

    思路:

    递归的思路,前序是:中序,左节点,右节点

    中序就是中间节点在前面,每次往下走一步就把当前root的val加入,然后才去遍历左再遍历右

    1. public int[] preorderTraversal (TreeNode root) {
    2.         // write code here
    3.         List list = new ArrayList<>();
    4.         preoder(list,root);
    5.         int[] ret = new int[list.size()];
    6.         for(int i = 0; i < list.size(); i++){
    7.             ret[i] = list.get(i);
    8.         }
    9.         return ret;
    10.     }
    11.  
    12.     public void preoder(List list,TreeNode root){
    13.         if(root == null){
    14.             return;
    15.         }
    16.         list.add(root.val);
    17.         preoder(list,root.left);
    18.         preoder(list,root.right);
    19.     }

    18.二叉树的中序遍历

    二叉树的中序遍历_牛客题霸_牛客网 (nowcoder.com)

    思路:

    跟前序遍历的思想差不多,中序嘛就是左节点在前面.

    就要找左节点,走走走,遍历到最左下角的左节点.便把其加入,再一步一步回头.

    1. public int[] inorderTraversal (TreeNode root) {
    2.         // write code here
    3.         List list = new ArrayList<>();
    4.         inorder(list,root);
    5.         int[] ret = new int[list.size()];
    6.         for(int i = 0; i < list.size(); i++){
    7.             ret[i] = list.get(i);
    8.         }
    9.         return ret;
    10.     }
    11.     public void inorder(List list,TreeNode root){
    12.         if(root == null){
    13.             return;
    14.         }
    15.         inorder(list,root.left);
    16.         //先遍历完左节点,再加入
    17.         list.add(root.val);
    18.         inorder(list,root.right);
    19.     }

    19二叉树的后序遍历

    二叉树的后序遍历_牛客题霸_牛客网 (nowcoder.com)

    思路:

    都差不多嘛,后序就左 右 中.

    先遍历左节点,再遍历右边的节点,最后加入

    1. public int[] postorderTraversal (TreeNode root) {
    2.         // write code here
    3.         List list = new ArrayList<>();
    4.         postorder(list,root);
    5.         int[] ret = new int[list.size()];
    6.         for(int i = 0; i < list.size(); i++){
    7.             ret[i] = list.get(i);
    8.         }
    9.         return ret;
    10.     }
    11.     public void postorder(List list, TreeNode root){
    12.         if(root == null){
    13.             return;
    14.         }
    15.         postorder(list,root.left);
    16.         postorder(list,root.right);
    17.         list.add(root.val);
    18.     }

    20.二叉树的层序遍历23.9.12

    求二叉树的层序遍历_牛客题霸_牛客网 (nowcoder.com)

    思路:

    之前学的数据结构已经忘完了..emm

    重新看了一下该怎么层序遍历.

    要额外使用一个队列来存放每一层的节点.

    1. public ArrayList> levelOrder (TreeNode root) {
    2.         // write code here
    3.         ArrayList> ret = new ArrayList<>();//存放结果返回
    4.         if (root == null) {
    5.             return ret;
    6.         }
    7.         Queue queue = new
    8.         LinkedList<>();//创建一个队列存放每一层的节点
    9.         //先手动放入头节点,作为第一层的元素
    10.         queue.offer(root);
    11.         
    12.         while (!queue.isEmpty()) { //当存放每一层元素的队列不为空时
    13.             int size = queue.size();//记录当前层元素的个数
    14.             //把队列中的一个元素拿出来
    15.             //最左节点的元素是最先放进去的,根据队列也会最先拿出来
    16.             //并放到列表中
    17.             ArrayList list = new ArrayList<>();
    18.             while (size != 0) {
    19.                 TreeNode tmp = queue.poll();
    20.                 list.add(tmp.val);
    21.                 //查看其有没有左右节点
    22.                 if (tmp.left != null) {
    23.                     queue.offer(tmp.left);
    24.                 }
    25.                 if (tmp.right != null) {
    26.                     queue.offer(tmp.right);
    27.                 }
    28.                 //每取出一个元素,size记得--
    29.                 size--;        
    30.             }
    31.             ret.add(list);
    32.         }
    33.         return ret;
    34.     }

    21.按之字形顺序打印二叉树

    按之字形顺序打印二叉树_牛客题霸_牛客网 (nowcoder.com)

    思路:

    感觉跟上面的层序遍历差不多,设置一个变量,每遍历完一层变换一下,按照此变量去考虑是否要反转list.

    1. public ArrayList> Print (TreeNode pRoot) {
    2.         // write code here
    3.         ArrayList> ret = new ArrayList<>();
    4.         if(pRoot == null){
    5.             return ret;
    6.         }
    7.         Queue queue = new LinkedList<>();
    8.         queue.offer(pRoot);
    9.         boolean count = true;
    10.         while(!queue.isEmpty()){
    11.             ArrayList list = new ArrayList<>();
    12.             int size = queue.size();
    13.             while(size != 0){
    14.                 TreeNode tmp = queue.poll();
    15.                 list.add(tmp.val);
    16.                 if(tmp.left != null){
    17.                     queue.offer(tmp.left);
    18.                 }
    19.                 if(tmp.right != null){
    20.                     queue.offer(tmp.right);
    21.                 }
    22.                 size--;
    23.             }
    24.             if(!count){
    25.                 Collections.reverse(list);//每隔一行就翻转一下
    26.             }
    27.             count = !count;
    28.             ret.add(list);
    29.         } 
    30.         return ret;
    31.     }

    22.二叉树的最大深度23.9.13

    二叉树的最大深度_牛客题霸_牛客网 (nowcoder.com)

    思路:

    层序遍历?每遍历一层就计数+1

    直接写出来啦!( •̀ ω •́ )y

    1. public int maxDepth (TreeNode root) {
    2.         // write code here
    3.         if(root == null){
    4.             return 0;
    5.         }
    6.         Queue queue = new LinkedList<>();
    7.         int count = 0;
    8.         queue.offer(root);
    9.         while(!queue.isEmpty()){
    10.             int size = queue.size();
    11.             while(size != 0){
    12.                 TreeNode tmp = queue.poll();
    13.                 if(tmp.left != null){
    14.                     queue.offer(tmp.left);
    15.                 }
    16.                 if(tmp.right != null){
    17.                     queue.offer(tmp.right);
    18.                 }
    19.                 size--;
    20.             }
    21.             count++;
    22.         }
    23.         return count;
    24.     }

    23.二叉树中和为某一值的路径(一)

    二叉树中和为某一值的路径(一)_牛客题霸_牛客网 (nowcoder.com)

    思路:

    题目要求的是,从头节点到叶子节点一路下来连续的val和为sum.

    可以使用递归的方式,先递归左节点的.每走到一个节点就把当前root的val从sum中减去.直到sum为0,且刚好为叶子节点的情况下则返回true;

    递归遍历完左节点再去遍历右节点的. 

    1. public boolean hasPathSum (TreeNode root, int sum) {
    2.         // write code here
    3.         if(root == null){
    4.             return false;
    5.         }
    6.         if(root.left == null && root.right == null && sum - root.val == 0){
    7.             return true;
    8.         }
    9.         boolean countLeft = hasPathSum(root.left,sum - root.val);
    10.         boolean countRight = hasPathSum(root.right,sum - root.val);
    11.         return countLeft || countRight;
    12.     }

    24.二叉搜索树与双向链表

    二叉搜索树与双向链表_牛客题霸_牛客网 (nowcoder.com)

    思路:

    二叉搜索树:每一个节点的值比其左节点大,但比其右节点小.

    可以观察,二叉搜索树变成双向链表后,链表的数值是递增的.

    而二叉搜索树中,数值大小为:左节点<根节点<右节点.

    是不是就很像中序遍历呢,

    所以就可以按照中序遍历的思路来完成.

    要将节点连接起来,肯定是要使用双指针.

    关注链表的头节点,为二叉搜索树的最左节点也是数值最小的节点.

     遍历左节点,

    来到中间连接左边.

    遍历右节点

    1. public class Solution {
    2.     TreeNode pre = null;
    3.     TreeNode head = null;
    4.     public TreeNode Convert(TreeNode pRootOfTree) {
    5.         //递归
    6.         if(pRootOfTree == null){
    7.             return null;
    8.         }
    9.         Convert(pRootOfTree.left);//遍历左节点
    10.         if(pre == null){//如果是最左节点,则记录一下作为头节点与前驱节点并跳过
    11.             pre = pRootOfTree;
    12.             head = pRootOfTree;
    13.         }else{
    14.             pRootOfTree.left = pre;//此时pRootOfTree为一棵树的根节点,连接左
    15.             pre.right = pRootOfTree;//前驱的右连接根节点
    16.             pre = pRootOfTree;//前驱的指针来到当前根节点,作为下一个根节点的前驱
    17.         }
    18.         Convert(pRootOfTree.right);//遍历右节点
    19.         return head;
    20.     }
    21. }

    25.对称的二叉树23.9.14

    对称的二叉树_牛客题霸_牛客网 (nowcoder.com)

    思路:
    对称,左子树的右节点与右子树 的左节点对称.

    从根节点开始,使用两个指针分别遍历左子树与右子树.

    检查左子树的左节点的值与右子树的右节点是否相同.

    左子树的右节点的值与右子树的左节点是否相同

    1. public boolean isSymmetrical (TreeNode pRoot) {
    2.         // write code here
    3.         return tree(pRoot,pRoot);//从头节点,分别用两个指针往左和右遍历
    4.     }
    5.  
    6.     public boolean tree(TreeNode root1,TreeNode root2){
    7.        if(root1 == null && root2 == null){//当两个指针同时为空结束递归
    8.             return true;
    9.        }
    10.        //当任意一指针为空,或两边数值不相等时返回false
    11.        if(root1 == null || root2 == null || root1.val != root2.val){
    12.             return false;
    13.        }
    14.         //继续遍历相对称的节点
    15.        return tree(root1.left,root2.right) && tree(root1.right,root2.left);
    16.     }

  • 相关阅读:
    货币转换
    vue3+element-plus国际化
    web前端进阶：＜6＞一个自我简介的小程序
    Serverless 数仓技术与挑战 - 张雁飞｜3306π
    HTTP 协议的基本格式和 fiddler 的用法
    .NET混合开发解决方案7 WinForm程序中通过NuGet管理器引用集成WebView2控件
    秋招准备--基础知识复习--系统编程
    【web实战-业务逻辑】评论点赞逻辑
    2022牛客多校第二场解题报告
    eclipse 源代码文件报错处理
  • 原文地址：https://blog.csdn.net/weixin_67719939/article/details/132655294