剑指offer总结·

素颜马尾好姑娘i 2022-05-26 03:47 157阅读 0赞

--------------------

\- 需要注意函数的参数以及返回值：一般不需要修改的参数应该传递的是引用 并且需要加上const 修饰表示不会在函数当中修改这个参数

*  STL vector最好在知道数组的大小的时候在声明数组的时候就直接指定数组的长度，这样可以减少在动态增加数组的大小的时候扩充数组大小带来的开销，降低时间。
 *  一般使用前缀式进行自加自减等操作，因为i++会产生一个临时对象保存更改前的i的值用于使用然后再进行自加，在大对象的时候会带来较大的开销。最好采用++i直接先加再用。

--------------------

## 二叉树的镜像 ##

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    class Solution {
    public:
        void Mirror(TreeNode *pRoot) {
            if(!pRoot) return;
            TreeNode* temp = pRoot->left;
            pRoot->left = helper(pRoot->right);
            pRoot->right = helper(temp);
        }
    
        TreeNode* helper(TreeNode* root) {
            if(!root) return nullptr;
            TreeNode* temp = root->left;
            root->left = helper(root->right);
            root->right = helper(temp);
            return root;
        }
    };

*  注意：需要先保存右边的子树再去处理左子树 否则会使用的是改变过后的子树将使得结果出错。

class Solution {
       //非递归版本 使用栈
    public:
        void MirrorIteratively(TreeNode* pRoot)
        {
            if(pRoot == NULL)
                return;
            stack<TreeNode*> stackTreeNode;
            stackTreeNode.push(pRoot);
            while(!stackTreeNode.empty())
            {
       //每一层一层的交换结点的左右子树
                TreeNode *pNode = stackTreeNode.top();
                stackTreeNode.pop();
                TreeNode *pTemp = pNode->left;
                pNode->left = pNode->right;
                pNode->right = pTemp;
                if(pNode->left)
                    stackTreeNode.push(pNode->left);
                if(pNode->right)
                    stackTreeNode.push(pNode->right);
            }
        }
    };

--------------------

## 变态跳台阶 ##

//递归版本
    class Solution {
    public:
        int jumpFloorII(int number) {
            int res = 0;
            if(number<=1)
                return 1;
            for(int i=1;i<=number;++i) {
                res += jumpFloorII(number - i);
            }
            return res;
        }
    };

class Solution {
       //改进版本 采用记忆化搜索
    public:
        int jumpFloorII(int number) {
            if(number<=1)
                return 1;
            int res = 0;
            vector<int> dp(number+1,0);
            dp[0] = dp[1] = 1;
            res += helper(number,dp);
            return res;
        }
    
        int helper(int number,vector<int>& dp) {
            if(dp[number])//如果计算过就直接返回
                return dp[number];
            int res = 0;
            for(int i=1;i<=number;++i) {
                res += helper(number-i,dp);
            }
            return res; 
        }
    };

class Solution {
       //dp版本
    public:
        int jumpFloorII(int number) {
            if(number<=1)
                return 1;
            vector<int> dp(number+1,0);
            dp[0] = dp[1] = 1;
            for(int i=2;i<=number;++i) {
                dp[i] = 1;
                for(int j=1;j<i;++j)
                    dp[i] += dp[j];
            }
            return dp[number];
        }
    };

//f(n)=f(n-1)+f(n-2)+....+f(1)+1,而f(n-1)=f(n-2)+....+f(1)+1,
    //两个式子相减，得到f(n) = 2f(n-1),很明显可以得到f(n)=2^(n-1)。
    class Solution {
    public:
        int jumpFloorII(int number) {
            if(number<=1)
                return 1;
            vector<int> dp(number+1,0);
            dp[0] = dp[1] = 1;
            for(int i=2;i<=number;++i) {
                    dp[i] = 2 * dp[i-1];
            }
            return dp[number];
        }
    };