【算法】剑指offer-整数中1的个数&链表的倒数第k个节点

整数中1的个数

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

https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&tqId=11164&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

方法1:

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         //遍历n的二进制位判断
         //共有32位,循环32次
         for(int i = 0;i<32;i++)
         {
             if(n&(1<<i))
             {
                 count++;
             }
         }
         return count;
     }
};

使用结论:n&(n-1):去掉二进制序列中最后的一个1,将其变为0

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         while(n)
         {
             //n&(n-1) :去掉二进制序列中最后的一个1,将其变为0 
             //经历多少次,n变为0,则说明n的二进制序列中有多少个1
             n &=n-1;
             count++;
         }
         return count;
     }
};

链表的倒数第k个节点

输入一个链表,输出该链表中倒数第k个结点

https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&tqId=11167&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

方法:快慢指针,快指针先走k步,然后和慢指针一起走

注意:要防止快指针走到空的情况

==错误写法:==

下面的代码对于这两种情况分不开:

情况1: 5,{1,2,3,4,5} ->此时倒数第五个节点是1

情况2:6,{1,2,3,4,5} 此时没有倒数第六个节点不存在,返回空

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        //判断步数的合法性
        ListNode* fast = pListHead;
        ListNode* slow = pListHead;
        //快指针先走k步,要防止走到空
        while(k-- && fast)
        {
            fast = fast->next;
        }
        //如果fast走到空,说明没有倒数第k个节点,返回空
        //上面的实例中,二者都会走到这里
        //如果返回nullptr -> 情况1出错
        //如果返回slow  ->情况2出错
        if(fast == nullptr) return nullptr;

        // 否则快慢指针一起走,当fast
        while(fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

正解:

检查参数的合法性
快指针先走k步,注意防止快指针走到空
快慢指针一起走,当快指针走到空,返回slow位置的节点
最后进行判断:如果k还大于0,说明==>fast在先走k步的时候,提前走到空 -> 此时返回空指针,否则返回slow节点的位置

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        //判断链表是否为空
        if(pListHead == nullptr) return nullptr;

        ListNode* fast = pListHead;
        ListNode* slow = pListHead;
        //这里把fast和k谁放前放后都行
        while(k&&fast)
        {
            k--;
            fast = fast->next;
        }

        /*
            //或者写成下面的:
            //但是此时注意要将fast放前面 
            while(fast&&k--)
            {
                fast = fast->next;
            }

        */

        //如果fast提前走到空,此时是不进入下面的while循环的
        // 快慢指针一起走
        while(fast)
        {
            slow = slow->next;
            fast = fast->next;
        }

        //对k进行判断
        //如果k还大于0,说明==>fast在先走k步的时候,提前走到空 -> 此时返回空指针,
        //否则返回slow节点的位置
        return k > 0?nullptr:slow;
    }
};

把k--写在循环内部时:

把k--写在循环判断条件时::

关于fast放后面的放前面的区别:

写法2:优质写法,清晰明了

class Solution {
    public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        //判断链表的合法性
        if(pListHead == nullptr) return nullptr;

        ListNode* fast = pListHead;
        ListNode* slow = pListHead;
        //fast 先走K步
        while(k--)
        {
            //k的大小大于链表长度, fast提前走到空
            if(fast == nullptr)
            {
                return nullptr;
            }
            fast = fast->next;
        }
        //fast和slow一起走
        //当fast走到nullptr 此时slow就是倒数的第K个结点
        while(fast)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

#牛客求职必刷题#