剑指offer刷题week 02

第一周的题目已经刷完，开始愉快的第二周刷题之路

24. 机器人的运动范围

地上有一个 mm 行和 nn 列的方格，横纵坐标范围分别是 0∼m−10∼m−1 和 0∼n−10∼n−1。

一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。

但是不能进入行坐标和列坐标的数位之和大于 kk 的格子。

请问该机器人能够达到多少个格子？

样例1

输入：k=7, m=4, n=5

输出：20

样例2

输入：k=18, m=40, n=40

输出：1484

解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
但是，它不能进入方格（35,38），因为3+5+3+8 = 19。

注意:

0<=m<=50
0<=n<=50
0<=k<=100

一道BFS（宽搜）的经典模板题。
直接上代码

class Solution {
public:
    int getPairSum(pair<int,int> p)
    {
        int s = 0;
        while (p.first) {
            s += p.first % 10;
            p.first /= 10;
        }
        while (p.second) {
            s += p.second % 10;
            p.second /= 10;
        }
        return s;
    }
    
    int movingCount(int threshold, int rows, int cols)
    {
        int res=0;
        if(!rows||!cols)     return 0;
        vector<vector<bool>> st(rows,vector<bool>(cols,false));
        queue<pair<int,int>>q;
        q.push({0,0});
        int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
        while(q.size())
        {
            pair<int,int> p=q.front();
            q.pop();
            
            if(st[p.first][p.second]||getPairSum(p)>threshold) continue;
            res++;
            st[p.first][p.second]=true;
            
            for(int i=0;i<4;i++)
            {
                int a = p.first + dx[i] , b = p.second + dy[i];
                if(a >= 0 && a < rows && b>=0 && b < cols)
                    q.push({a,b});
            }
        }
        return res;
    }
};

---

25剪绳子

给你一根长度为 nn 绳子，请把绳子剪成 mm 段（mm、nn 都是整数，2≤n≤582≤n≤58 并且 m≥2m≥2）。

每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？

例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

样例

输入：8

输出：18

解析

这道题据说是一道小学数奥题先上结论：
结论就是把数字拆分出尽可能多的3。如果拆完之后n%3==1 就拆除两个2，如果n%3==2 就拆出一个2

证明过程是这样的
1：假设在某次拆分时ni>=5，那么 x*ni<=x*3*(ni-3)。因为我们可以将以上等式化简为为：2ni>=9,又有ni>=5 所以拆分出的结果中必不包含大于5的数字

2：对于4，可等价为2*2 故最后结果中也必不包含2

3：结果中除了边界情况（n<=3）否则结果中比不包含1
ni>=4，1*(ni-1)<=(ni-2)2*

4：2*2*2<3*3 综上，可得出之前的结论
这题感觉还是直接记这个结论比较好下来比较好

代码：

class Solution {
public:
    int maxProductAfterCutting(int len) {
      
        if(len<=3)
            return len-1;
        int res=1;
        if(len%3==1)
        {
            res*=4;
            len-=4;
        }
        else if(len%3==2)
        {
            res*=2;
            len-=2;
        }
        
        while(len)
        {
            res*=3;
            len-=3;
        }
        
        return res;
        
    }
};

---

二进制中1的个数

输入一个32位整数，输出该数二进制表示中1的个数。

注意：

• 负数在计算机中用其绝对值的补码来表示。

样例1

输入：9
输出：2
解释：9的二进制表示是1001，一共有2个1。

样例2

输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110，
一共有31个1。

解析：

先来理解一下补码（或者叫做补数）的概念

我们先随意列举一个数字 3 那么他对于10的补数就是 7
因为 10-3=7 也就是说3和7互为对于10的补数

然后我们回到计算机中的二进制

• 对于一个正数，他的补码为本身
• 对于对于负数，他的补码为按位取反并+1
• 对于有符号的类型，第一位为符号位0为正1为负 并且在c语言中，有符号整数又移会在最高位补上1，无符号整数辉仔最高位补上0
• 计算机内存中存储的是补码
  举个例子，在一个8位二进制数中

1 = 00000001(原码) 00000001(补码)

-1= 10000001(原码) 01111111 (补码)

2 = 00000010(原码) 00000010(补码)

我们会发现
1的补码加上-1的补码刚好等于 000000000 也就是二进制表示的我们会发现 1的补码加上-1的补码刚好等于0
2的补码加上-1的补码刚好等于 00000001 也就是二进制的1
所以我们发现，补码其实进行的就是讲所有的减法都可以用加法来操作，计算机只需要实现一个加法器便可以对加法和减法同时进行计算
原理很简单，假如我们有一个时钟，现在时间是4点（12小时制） 那么如果让4点变成3点除去往回拨一个小时还有就是往前拨11个小时 因为在表盘内所有的数字都不会超过12

然后我们回到这道题目
首先，给的数字是有正负标示的，然后根据所给样例发现，符号位的1也计算在其中那么我们定义一个无符号整形，讲原本的一个小负数变温一个大正数
这样不但保证了原本的符号位计算加入了其中，而且可以确保里面的值必然大于等于0，让我们可以while循环直接判断
上代码：

    int NumberOf1(int n) {
        
        unsigned int _n=n;
        int res=0;
        while(_n>0)
        {
            res+=_n&1;
            _n>>=1;
        }
        return res;
    }

---

数值的整数次方

实现函数double Power(double base, int exponent)，求base的 exponent次方。

不得使用库函数，同时不需要考虑大数问题。

注意：

• 不会出现底数和指数同为0的情况

样例1

输入：10 ，2

输出：100

样例2

输入：10 ，-2

输出：0.01

简单题，直接上代码

class Solution {
public:
    double Power(double base, int exponent) {
        
        double res=1;
        
        if(exponent==0)
            return 1;
            
        int n=-1;
        if(exponent<0)
            n=1;
        while(exponent!=0)
        {
            res*=base;
            exponent+=n;
        }
        if(n>0)
        {
            return (double)1/res;
        }
        else
        {
            return res;
        }
        
    }
};

放一下大佬的简洁版代码

class Solution {
public:
    double Power(double a, int b) {
        double minus = 1;
        if (b < 0) minus = -1, b = -b;

        double res = 1;
        while (b -- ) res *= a;
        if (minus == -1) res = 1 / res;

        return res;
    }
};

---

28. 在O(1)时间删除链表结点

给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。

假设链表一定存在，并且该节点一定不是尾节点。

样例

输入：链表 1->4->6->8
删掉节点：第2个节点即6（头节点为第0个>节点）

输出：新链表 1->4->8

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val=node->next->val;
        node->next=node->next->next;
    }
};

---

删除链表中重复的节点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。

样例1

输入：1->2->3->3->4->4->5

输出：1->2->5

样例2

输入：1->1->1->2->3

输出：2->3

先上代码

    ListNode* deleteDuplication(ListNode* head) {
        
        ListNode* dummy=new ListNode(0);
        dummy->next=head;
        ListNode* p=dummy;
        while(p->next)
        {
            ListNode* q=p->next;
            while(q&&p->next->val==q->val)
                q=q->next;
            if(p->next->next==q) p=p->next;
            else p->next=q;
        }
        return dummy->next;
    }

思路大概如下：
首先因为这道题目的头结点可能会被删掉，对于这种类型的为题，我们可以使用一个虚拟的头结点 来简化代码 使用新建的头结点，可以保证这个头结点不会被删掉，从而减少对头结点的特殊处理。返回时只需要将虚拟头结点的下一个元素返回即可。

然后就是具体的题解 由于题目中已经给我们拍好了序，所以我们只需要使用两个指针对其中的每个元素进行便利，分别用于记录开始的节点和结束的节点 如果两节点之间的长度大于1，则删除中间部分 如下图

ps：这一周都在搞sdk接入，形神具疲 绝望1.0

---