刷题笔记

一个渣渣的刷题思路记录

---

2018/9/18

题目：二叉树中和为某一值的路径：输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路：带记忆的遍历
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> ret;
        vector<int> trace;
        if(root)
            dfs(root,expectNumber,ret,trace);
        return ret;
    }
    void dfs(TreeNode* root,int s,vector<vector<int>> &ret,vector<int> &trace) {
        trace.push_back(root->val);
        if(!root->left&&!root->right) {
            if(s==root->val)
                ret.push_back(trace);
        }
        if(root->left)
            dfs(root->left,s-root->val,ret,trace);
        if(root->right)
            dfs(root->right,s-root->val,ret,trace);
        trace.pop_back();
    }

---

2018/9/17

题目：顺时针打印矩阵

思路：不存在的，就绕圈打印就对了，每一圈分成三段打印，打印完再改边界值
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int row=matrix.size();
        int col=matrix[0].size();
        vector<int> result;
        if(row==0||col==0)
            return result;
        int left=0,right=col-1,top=0,btm=row-1;
        while(left<=right&&top<=btm)
            {
            for(int i=left;i<=right;i++)
                result.push_back(matrix[top][i]);
            if(top<btm)
                for(int i=top+1;i<=btm;i++)
                    result.push_back(matrix[i][right]);
            if(top<btm&&left<right)
                for(int i=right-1;i>=left;i--)
                    result.push_back(matrix[btm][i]);
            if(top+1<btm&&left<right)
                for(int i=btm-1;i>=top+1;i--)
                    result.push_back(matrix[i][left]);
            left++;right--;top++;btm--;
        }
        return result;
    }

题目：二叉树的镜像：操作给定的二叉树，将其变换为源二叉树的镜像。

思路:递归，二叉树存在，将二叉树左右互换
    void Mirror(TreeNode *pRoot) {
        if(pRoot){
            TreeNode *left=pRoot->left;
            TreeNode *right=pRoot->right;
            pRoot->left=right;
            pRoot->right=left;
            Mirror(pRoot->left);
            Mirror(pRoot->right);
        }
        else
            return;
    }
看了速度最快的，也只是减少一个临时变量，所以也就这样了

题目：树的子结构：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：递归，一个判断起点值相同的树结构有无包含，一个递归找到起点值相同的树
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(!pRoot1)
            return false;
        if(!pRoot2)
            return false;
        return ( dfs(pRoot1,pRoot2)) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
    }
private:
    bool dfs(TreeNode * r1, TreeNode * r2){
        if(!r2)
            return true;
        if(!r1)
            return false;
        if(r1->val != r2->val)
            return false;
        return dfs(r1->left, r2->left) && dfs(r1->right, r2->right);
    }

---

2018/9/16

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路：递归，没啥子好说的，非递归的老是越界，debug心态都快崩了
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==NULL)
            return pHead2;
       else if(pHead2==NULL)
            return pHead1;
         
         ListNode* newhead=NULL;
        
        if(pHead1->val<pHead2->val)
                 
           {
              newhead=pHead1;
              newhead->next=Merge(pHead1->next,pHead2);
          }
           else
               {
               newhead=pHead2;
              newhead->next=Merge(pHead1,pHead2->next);
           }
       return newhead;
    }

题目：输入一个链表，反转链表后，输出新链表的表头。

链表反转，应该算是毫无难度了吧，边界条件也没有什么特别的，三个指针轻松解决
    ListNode* ReverseList(ListNode* pHead) {
        auto front = pHead,middle=pHead;
        ListNode* rear = NULL;
        while(front){
            front = middle->next;
            middle->next = rear;
            rear = middle;
            middle = front;
        }
        return rear;
    }

题目：输入一个链表，输出该链表中倒数第k个结点

思路：以前看过类似的，使用俩个指针，后一个指针指向前一个指针后的第k个点，考虑边界条件为主，例如链表长度小于k
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode *front;
        ListNode *rear=pListHead;
        for(int i=0; i<k; i++){
            if(rear!=NULL){
                rear = rear->next;
            }
            else
                return NULL;
        }
        front = pListHead;
        while(rear != NULL){
            rear = rear->next;
            front = front->next;
        }
        return front;
    }

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路：最简单的方法，将奇数和偶数分开存储，然后再合并，vector.clear清空存储的数据（内存大小依旧保留着），需要临时使用较多的内存空间，时间复杂度O（2n)，空间O（2n)
void reOrderArray(vector<int> &array) {
        vector<int> odd,even;
        for(auto a:array){
            if(a%2 ==1){
                odd.push_back(a);
            }
            else{
                even.push_back(a);
            }
        }
        array.clear();
        for(auto a:odd){
            array.push_back(a);
        }
        for(auto a:even){
            array.push_back(a);
        }
}
通过代码中的第一名是根据迭代更换的原理，类似于冒泡排序，将相近的俩个数排序，如果是奇后偶前，则互换,swap()函数
    void reOrderArray(vector<int> &array) {
        for(int i=0; i<array.size(); i++){
            for(int j=array.size()-1; j>i; j--){
                if(array[j]%2==1 && array[j-1]%2==0){
                    swap(array[j],array[j-1]);
                }
            }
        }
    }

---

2018/9/11

题目：数值的整数次方：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

首先呢，取巧方法，调用math.h的pow函数
#include <math.h>
class Solution {
public:
    double Power(double base, int exponent) {
        double i = pow(base,exponent);
        return i;
    }
};
第二种思路，递归算法，偶数呢，等于一半乘以一半，奇数就先-1，按偶数算，再乘，时间复杂度O（log n),需要注意的事情是，次幂可能是负数,一开始想法是利用函数取绝对值，看了一下第一名的代码，感觉他的更好其实
    double Power(double base, int exponent) {
        if(exponent>0)
        {
            if(exponent==1)
                return base;
            if(exponent%2==0)
                return Power(base,exponent/2)*Power(base,exponent/2);
            else
                return Power(base,exponent/2)*Power(base,exponent/2+1);
        }
        else if (exponent==0)
        {
            return 1;
        }
        else
        {
            return 1/Power(base,0-exponent);
        }
    }

第三种，累乘，完全没技术含量，注意边界条件即可，例如负数，0

题目：二进制中1的个数：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路：不清楚，二进制的应该是使用位运算解决问题的，但对此不熟悉，所以是看了别人的代码，才理清的思路，用&进行位运算，1&1=1,1&0=0,0&0=0，负数在计算机中是补码存在的，所以也就不用区分了，代码也是很清晰了    
 int  NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            ++count;
            n = (n - 1) & n;
        }
        return count;
     }

---

2018/9/10

题目：报数杀人
海盗船1000人围成一圈（编号1到1000）,报数如果是三的倍数就扔进海里（一直报不要停eg.998 999(dead) 1000 1001/原来的1号 1002(dead)/原来的2号 ...），最后一个人为几号

思路：是朋友问的一道面试题目，想法大概就是每轮剩下活着的人，再进行新的一轮淘汰，递归算法如下（更优的算法并不懂，后面懂了再改吧
#include <iostream>
#include <vector>
using namespace std;

int find(vector<int> test,int num){
	int length = test.size();
	vector<int> test2;
	for(int i=0; i<length; i++){
		if(num == 3){
			num = 1;
		}
		else{
			test2.push_back(test[i]);
			num++;	
		}		
	}
	if(test2.size() == 1){
		cout << test2[0] << endl;	
		return test2[0];
	}
	return find(test2,num);
}

int main(){
	vector<int> test;
	for(int i=1; i<=10; i++){
		test.push_back(i);
	}
	int num = 1;
	int result = find(test,num);
	cout << result << endl;
}

题目：跳台阶：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。思路：第一印象是使用递归实现，每次进入函数有俩种选择，跳1或跳2，再调用自身，当级数为0时，返回跳法数+1，但很可惜，牛客会提示说时间空间不符合要求，所以没办法使用递归简单实现了

只能换思路了，仔细想了一下，也很简单的（找规律），当阶数大于3的时候，很容易就明白说，到这层阶梯的方法是只有俩种，一种是从n-1层跳上去，一种是n-2层跳，也就是跳法总数f(n)=f(n-1)+f(n-2)，而f(1)=1，f(2)=2，接下去的迭代上去就可以了，也就可以知道f(0)=1，f(-1)=0（虽然后面的没什么必要，但开心就好）
class Solution {
public:
    int jumpFloor(int number) {
            int f1=0,f2=1,f3=0;
        while(number--){
            f3 = f2+f1;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
};

 

题目：变态跳台阶：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。（真是只有活力的青蛙）

思路：完全放弃递归想法，由上面那题，思考规律吧，总感觉是数学题其实，跟上面那道类似其实，只不过需要加的变多了而已，就变成了f(n)=f(n-1)+f(n-2)+......+f(1)+f(0)，就是最后一步都是一次跳完的，所以呢，f(n)=，推导过程就不给了，反正随便猜都可以猜到的其实
class Solution {
public:
    int jumpFloorII(int number) {
        int sum=1;
        while(--number){
            sum = sum*2;
        }
        return sum;
    }
};

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

思路：乍一看好像很厉害，特么的不就是青蛙跳那道题么，代码都不用改，思路就是，竖=1，横=2，其他参考青蛙跳思路。

---

2018/8/9 刷题笔记

二叉树重建问题

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：由于前序遍历的第一个点是根结点，而中序遍历以根结点作为左右子树的分界，故以此为切入点，每次得到该树的根节点，以及左右子树的先序遍历中序遍历的结果，将俩个vector分割为四个vector   
 TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int length = pre.size();
        if(length==0){
            return NULL;
        }
        TreeNode *tree = new TreeNode(pre[0]);
        vector<int> left_pre,left_vin,right_pre,right_vin;
        int gen=0;
        while(vin[gen]!=pre[0]){
            gen++;
        }
        for(int i=0; i<gen; i++){
            left_vin.push_back(vin[i]);
            left_pre.push_back(pre[i+1]);
        }
        for(int i=gen+1; i<length; i++){
            right_vin.push_back(vin[i]);
            right_pre.push_back(pre[i]);
        }
        tree->left=reConstructBinaryTree(left_pre,left_vin);
        tree->right=reConstructBinaryTree(right_pre,right_vin);
        return tree;
    }

题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

思路：栈是先进后出，队列是先进先出，所以将一个栈反转过来，顺序就同队列一样了，一个栈只做存储数据，另一个栈做输出中转，也就是输出时将栈反转，输出队头，再将栈反转回来，保留存储顺序
class Solution
{
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        while(!stack1.empty()){
            stack2.push(stack1.top());
            stack1.pop();
        }
        int top = stack2.top();
        stack2.pop();
        while(!stack2.empty()){
            stack1.push(stack2.top());
            stack2.pop();
        }
        return top;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路：将数据进行遍历排序，思路简单明了，具体做法使用sort算法，也可自行实现
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        sort(rotateArray.begin(),rotateArray.end()); 
        return rotateArray[0];
    }
};

题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

思路：首先我真的不是那个知道这个数列的大家之一，虽然猜到了是哪一个，百度了一下才确定的，至于算法就很简单了
class Solution {
public:
    int Fibonacci(int n) {
        if(n == 0){
            return n;
        }
        int sum=0,a=0,b=1;
        for(int m=0; m<n; m++){
            sum = a+b;
            a = b;
            b = sum;
        }
        return a;
    }
};