剑指offer经典题目（三）

目录

动态规划入门

二进制运算 

链表相关 

---

动态规划入门

        题目1：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算 不同的结果）。OJ地址

        简单图示如下。 

        题目分析：因为青蛙每次所跳的台阶无非就是1个台阶或者2个台阶，所以当青蛙要跳上第n个台阶时，无非也就是从第n-1个台阶或者是从第n-2个台阶开始跳。基于此，如果从第n-2个台阶跳到第n个台阶，直接跳两个台阶跳到第n个台阶。如果从第n-1个台阶开始跳，直接跳1个台阶到第n个台阶。

        所以我们就可以认为，跳到第n个台阶的跳法=跳到第n-1个台阶的跳法+跳到第n-2个台阶的跳法。

        上述思想其实就是一个简单的动态规划思想，动态规划英文名称 Dynamic Programming，简称 DP。解决类似的 DP 问题无非就是3个步骤。

1. 定义状态。
2. 列状态转移方程。
3. 设置初始值。

        编码如下。

class Solution {
public:int jumpFloor(int number) {int* dp=new int[number+1];//1.设置状态，让dp这个数组的每一个元素表示跳到第几个台阶的总的方法数//2.列状态转移方程。dp[n]=dp[n-1]+dp[n-2]//3.设置初始值dp[1]=1;dp[2]=2;for(int i=3;i<=number;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[number];delete []dp;}
};

        咦，dp[i]=dp[i-1]+dp[i-2] ，怎么有点像斐波那契数列呢？没错，动态规划其实本质也就是一个斐波那契数列，因为动态规划其实类似于迭代思想。

        我们使用迭代思想解决这个问题。

class Solution {
public:int jumpFloor(int number) {int first=1;int second=2;int third=0;if(number==1) return 1;else if(number==2)return 2;else if(number>2){while(number>2){third=first+second;first=second;second=third;number--;}return third;}else {return 0;}}
};class Solution {
public:int jumpFloor(int number) {int first=1;int second=2;int third=0;if(number==1) return 1;else if(number==2)return 2;else if(number>2){while(number>2){third=first+second;first=second;second=third;number--;}return third;}else {return 0;}}
};

        其实这种传统的迭代方式和动态规划的方式的区别就是，动态规划会用一个数组去存储到每一个台阶的跳法，而传统的迭代方式不会存储每一个台阶的跳法。

        题目2： 我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？

        题目解析： 对于一个2*n的大矩形而言，最后一个2*1小矩形无非就是横着放置或者竖着放置。

        如果其最后一个2*1的小矩形是竖着放置的，那么放置最后一个矩形之前的上一个矩形的放置我们是不能确定其放置位置的；但是如果最后一个2*1的小矩形是横着放置的，那么放置最后一个小矩形之前的前一个矩形一定也是横着放置的，注意是一定。

        所以这种情况系，用2*1的小矩形去填充一个2*n的大矩形，其实就是填充2*(n-1)+2*(n-2)的大矩形的所有方法的总和。

        编码如下。

class Solution {
public:int rectCover(int number) {//描述状态int *dp=new int[number+1];dp[1]=1;dp[2]=2;for(int i=3;i<=number;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[number];}
};

二进制运算 

        题目3：输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。OJ地址 

        题目解析：这个题目比较简单，直接使用 num&num-1 即可，用一个计数器计算，计算按位与多少次的结果为0就是1的个数。无脑记住这个套路即可。 

        编码如下。

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

链表相关 

        题目4：链表中倒数最后k个结点_牛客题霸_牛客网 

        题目解析：可以使用一个前后指针，让第一个指针先走，走到第k个节点的位置，然后再让第二个指针走，当第一个指针走到最后一个节点时，第二个指针就走到了倒数第k个节点。 

        编码如下。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* FindKthToTail(ListNode* pHead, int k) {ListNode* _prev=pHead;ListNode* _next=pHead;//表示_prev指针的位置int count=1;//找到第k个节点的位置while(count<k&&_prev!=nullptr){_prev=_prev->next;count++;}//只关心找到了第k个节点的位置，且_prev不为空if(count==k&&_prev!=nullptr){while(_prev->next){_prev=_prev->next;_next=_next->next;}return _next;}return nullptr;}
};

         以上便是本期的所有内容^_^