行业知识
剑指offer经典题目整理(三)
一、二进制计算
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中,一些经典题目的总结整理,本篇中将有关单链表操作的题目整理到了一起,方便以后复习理解,较为难理解的思路会有对代码的分析或者是思路部分会画图分析
上一篇:服务器散热支架怎么安装?