小工具知识网

当前位置: 首页 > 行业知识 > 剑指offer经典题目整理(三)

行业知识

剑指offer经典题目整理(三)

2026-11-17 08:13:48 来源:互联网转载

一、二进制计算

1.链接

二进制��1的个数_牛客题霸_牛客网 (nowcoder.com)

2.描述

输入一个整数 n ,输出该数32位二进制表示中1的个数。其中负数用补码表示。

3.思路

思路一:常规思路

常规思路是,我们知道,一个整数n是32bit位的,只需要拿一个1与32个bit位都按位与一次,同为1的则让count++(count用来计数),很简单就可以写出代码,但是考虑到每一次检测一个整数都需要去将32位都检查一边,如果碰到1很少的情况,则效率相对比较低

思路二:取巧

因此,有第二种更好的方式则是让 n = n&(n-1) ,每一次执行完都会让n在二进制中少一个1,因此每执行一次计数一次,当n为0时,则count就是1的数量

原理是每次n-1,都需要向最靠近右边的一个1去借位,而被借位的1前面位置不变,后面位置都是0,因此按位与运算后,相当于把最靠近右边的一个1给消去了

4.参考代码

思路一:常规思路

class Solution {public:    int NumberOf1(int n)     {        int count = 0;        for(int i = 0;i>i)&1) == 1)            {                count++;            }        }        return count;    }};

思路二:取巧

class Solution {public:    int NumberOf1(int n)     {        int count = 0;        while(n)        {            n = n&(n-1);            count++;        }        return count;    }};

二、链表:求倒数第k个节点(快慢指针)

1.链接

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

2.描述

给你一个单链表,要求你返回倒数第k个节点的指针,要考虑k大于链表本身长度的情况

3.思路

快慢指针,很经典的一个题目,让一个指针fast先走k步,然后再两个指针一起走,直到快的指针指向nullptr,则此时另一种指针slow指向的位置就是倒数第k个节点的位置,当然再考虑部分特殊情况,例如k大于链表长度时要特殊处理,又或者测试用例给空链表时,直接返回空

4.参考代码

class Solution {public:    ListNode* FindKthToTail(ListNode* pHead, int k)     {        ListNode* fast = pHead;        ListNode* slow = pHead;        if(pHead == nullptr)        {            return nullptr;        }         while(fast && k)        {            fast = fast->next;            k--;        }        if(k!=0)//当k超出链表长度,k此时才不等于0        {            return nullptr;        }        //两个指针一起走        while(fast != nullptr)        {            fast = fast->next;            slow = slow->next;        }        return slow;    }};

三、反转单链表

1.链接

反转链表_牛客题霸_牛客网 (nowcoder.com)

2.描述

将一个单链表反转,然后输入新的表头

3.思路

思路一:逐一头插到新的头节点中

以头插的方式,将单链表中的每个节点逐一头插到新的头结点中,个人觉得,带哨兵位头结点的话,会更好理解一点

思路二:三指针一起走实现反转

三个指针同时往后走,边走边反转指针,pre指针和mid指针用来反转节点之间的指针方向,after指针用来记录下一个节点的位置,当然要注意很多细节上的问题,例如只有一个或者两个链表时该怎么办,结束条件等等

当只有一个时,我们不需要反转,直接返回

第一个指针需要指向空,所以,我们可以让pre开始时就指向空,而mid指向第一个节点,after指向第二个节点

当after指向空时,则通过画图可以知道,此时只有mid指向的节点和pre指向的节点之间指针没有反转,因此直接将mid的next指向pre即可完成整个链表的反转

4.参考代码

思路一:逐一头插到新的头节点中

class Solution {public:    ListNode* ReverseList(ListNode* head)     {        ListNode* newhead = nullptr;        ListNode* cur = head;        while(cur)        {            ListNode* cnext = cur->next;            cur->next = newhead;            newhead = cur;            cur = cnext;        }        return newhead;    }};

思路二:三指针一起走实现反转

class Solution {public:    ListNode* ReverseList(ListNode* head)     {        if(head == nullptr || head->next == nullptr)//只有一个节点或者空链表则不需要反转        {            return head;        }        ListNode* pre = nullptr;        ListNode* mid = head;        ListNode* after = head->next;        while(after)        {            mid->next = pre;            pre = mid;            mid = after;            after = after->next;        }        mid->next = pre;        return mid;    }};

四、合并单链表

1.链接

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

2.描述

输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。

3.思路

思路一:直接遍历比大小,然后取较小的尾插

用两个指针去遍历两个但链表进行比较,较小的节点尾插到新的头节点上,这里可以设立一个哨兵位的头结点,方便操作,然后就是考虑其中一个链表未插入完的情况

思路二:递归思路

我们发现,我们每次的操作,就是需要找到两个头节点中,比较小的一个,并且进行链接,每次找到一个节点后,节点就少一个,符合递归的思想,大事化小,因此尝试用递归的思路去解决

首先,当其中一个头结点为空,则直接返回另一个头结点,也就是结束条件,然后就是每次都需要找到两个头结点中较小的一个,然后将这个头结点拿出来进行链接,让较小的链表的头结点更新到下一个,此时,我们每次递归得到的就是两个链表头节点中较小的,递归的结束条件也设置好了,此时就可以放心的递归链接了

4.参考代码

思路一:直接遍历比大小

class Solution {public:    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)     {        ListNode* cur1 = pHead1;        ListNode* cur2 = pHead2;        ListNode* newHead = new ListNode(0);        ListNode* tail = newHead;        while(cur1 && cur2)        {            if(cur1->val val)            {                tail->next = cur1;                tail = tail->next;                cur1 = cur1->next;            }            else             {                tail->next = cur2;                tail = tail->next;                cur2 = cur2->next;            }        }        if(cur1)        {            tail->next = cur1;        }        if(cur2)        {            tail->next = cur2;        }        return newHead->next;    }};

思路二:递归思路

class Solution {public:    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)     {        if(pHead1 == nullptr)        {            return pHead2;        }        if(pHead2 == nullptr)        {            return pHead1;        }        ListNode* newhead = nullptr;        if(pHead1->val val)        {            newhead = pHead1;            pHead1 = pHead1->next;        }        else         {            newhead = pHead2;            pHead2 = pHead2->next;        }        newhead->next = Merge(pHead1,pHead2);        return newhead;    }};

总结

本篇文章主要是对剑指offer中,一些经典题目的总结整理,本篇中将有关单链表操作的题目整理到了一起,方便以后复习理解,较为难理解的思路会有对代码的分析或者是思路部分会画图分析

上一篇:服务器散热支架怎么安装?

下一篇:DNF角色命名宝典,秘籍大揭秘,符号创意指南!