42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

class Solution {
public:
    int trap(vector<int>& height) {
        int leftmax=0,rightmax=0;
        int left=0,right=height.size()-1;
        int sum=0;

        while(left<right)
        {   
            leftmax=max(height[left],leftmax);
            rightmax=max(height[right],rightmax);
            if(height[left]<height[right])
            {
                sum=sum+leftmax-height[left];
                left++;
            }
            else
            {
                sum=sum+rightmax-height[right];
                right--;
            }
        }
        return sum;
    }
};
  • 维护两个指针left和right,以及两个变量leftMax和rightMax,初始时 left = 0,right= n - 1,leftMax =0,rightMax= 0
  • 当两个指针没有相遇时,进行如下操作:
  • 使用height[left]和height[right]的值更新leftMax和rightMax的值;
    如果height(left) < height(right),则必有leftMax <rightMax,下标 left处能接的雨水量等于leftMaz -height(left),将下标left处能接的雨水量加到能接的雨水总量,然后将left加1(即向右移动一位);
  • 如果height(left) ≥ height(vight),则必有leftMax ≥ rightMax,下标right处能接的雨水量等于rightMaa - height(right),将下标right处能接的雨水量加到能接的雨水总量,然后将right 减1(即向左移动一位)。
  • 当两个指针相遇时,即可得到能接的雨水总量。

124. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ,返回其 最大路径和 。

class Solution {
public:
    int ans=INT_MIN;
    int maxPathSum(TreeNode* root) {
        f(root);
        return ans;
    }

    int f(TreeNode*root)
    {
        if(!root) return 0;
        int left=max(0,f(root->left));
        int right=max(0,f(root->right));
        int cur=left+right+root->val;
         ans=max(ans,cur);

        return root->val+max(left,right);

    }
};
  • 后序遍历,自底向上

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
        {
            while(nums[i]!=i)
            {
                if(nums[i]==nums[nums[i]])
                {
                    return nums[i];
                }
                else
                    swap(nums[i],nums[nums[i]]);
            }
        }
        return -1;
    }
};
  • 从头遍历数组,若无重复元素排序后num[n]的元素一定在下标为n的位置
  • 判断当前数字nums[i]和下标i是否相等
    • 如果相等则遍历下一个
    • 如果不相等
      • 判断是否和num[nums[i]]相等,若相等则返回
      • 不相等的话则交换两个元素的位置
  • 时间复杂度O(n),空间复杂度O(1)

剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0) return false;
        int n=0;
        int m=matrix[0].size()-1;
        while(n<matrix.size()&&m>=0)
        {
            if(matrix[n][m]>target)
            {
                m--;
            }
            else if(matrix[n][m]<target)
            {
                n++;
            }
            else    return true;
        }
        return false;
    }
};
  • 从右上角开始查找

剑指 Offer 05. 替换空格

请实现一个函数,把字符串 s 中的每个空格替换成"%20"。

class Solution {
public:
    string replaceSpace(string s) {
        int spaceNum=0;
        int left=s.size()-1;
        for(auto i:s)
        {
            if(i==' ') spaceNum++;
        }
        int n=s.size()+spaceNum*2;
        s.resize(n);
        int right=s.size()-1;
        while(left>=0)
        {
            if(s[left]!=' ')
            {
                s[right]=s[left];
                left--;
                right--;
            }
            else
            {
                s[right]='0';
                s[right-1]='2';
                s[right-2]='%';
                right-=3;
                left--;
            }
        }
        return s;
    }
};
  • 双指针,从后往前遍历
  • 时间复杂度O(N),空间复杂度O(1)

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> vec;
        while(head)
        {
            vec.push_back(head->val);
            head=head->next;
        }
        reverse(vec.begin(),vec.end());
        return vec;
    }
};

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty()||inorder.empty()) return nullptr;
        TreeNode* node=new TreeNode(preorder[0]);
        for(int i=0;i<inorder.size();i++)
        {
            if(preorder[0]==inorder[i])
            {
                vector<int> leftPre(preorder.begin()+1,preorder.begin()+i+1);
                vector<int> leftIn(inorder.begin(),inorder.begin()+i);
                vector<int> rightPre(preorder.begin()+i+1,preorder.end());
                vector<int> rightIn(inorder.begin()+i+1,inorder.end());

                node->left=buildTree(leftPre, leftIn);
                node->right=buildTree(rightPre, rightIn);
            }
        }
        return node;
    }
};
  • 前序遍历的第一个元素为根节点,后序遍历的最后一个元素为根节点
  • 在中序遍历中找到根节点,根节点的左边为左子树的元素,右边为右子树的元素
  • 重复这个过程

06. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.empty()||postorder.empty()) return nullptr;
        TreeNode *node=new TreeNode(postorder[postorder.size()-1]);

        for(int i=0;i<inorder.size();i++)
        {
            if(postorder[postorder.size()-1]==inorder[i])
            {
                vector<int> leftPost(postorder.begin(),postorder.begin()+i);
                vector<int> leftIn(inorder.begin(),inorder.begin()+i);
                vector<int> rightPost(postorder.begin()+i,postorder.end()-1);
                vector<int> rightIn(inorder.begin()+i+1,inorder.end());

                node->left=buildTree(leftIn, leftPost);
                node->right=buildTree(rightIn, rightPost);
                break;
            }
        }
        return node;
    }
};

剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

class CQueue {
public:
    stack<int> sk1,sk2;
    CQueue() {

    }
    
    void appendTail(int value) {
        sk1.push(value);
    }
    
    int deleteHead() {
        int del;
        if(sk1.empty()&&sk2.empty()) return -1;	//队列无任何元素
        if(sk2.empty())
        {
            while(!sk1.empty())
            {
                sk2.push(sk1.top());
                sk1.pop();
            }
        }
        del=sk2.top();
        sk2.pop();
        return del;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue* obj = new CQueue();
 * obj->appendTail(value);
 * int param_2 = obj->deleteHead();
 */

剑指 Offer 10- I. 斐波那契数列

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

class Solution {
public:
    int fib(int n) {
        long long p=0,q=1,r=p+q;
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        for(int i=3;i<=n;i++)
        {
            p=q;
            q=r;
            r=(p+q)%1000000007;
        }
        return r;
    }
};

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的最小值为1。

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int l=0,r=numbers.size()-1;
        while(l<r)
        {
            int mid=l+((r-l)>>1);
            if(numbers[mid]>numbers[r])    l=mid+1;     //此情况mid一定在左部分,一定不可能是最小值,所以可以mid+1
            else if(numbers[mid]<numbers[r])    r=mid;  //此情况mid在右半部分,有可能mid就是最小值,
                                                                //所以不能l=mid-1,只能l=mid
            else r--;                   //相等时,说明有重复元素,l--即可
        }
        return numbers[r];
    }
};

剑指 Offer 13. 机器人的运动范围

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

class Solution {
public:
    vector<vector<bool>> visited;
    int getx(int x)
    {
        int s=0;
        while(x!=0)
        {
            s+=x%10;
            x=x/10;
        }
        return s;
    }
    int movingCount(int m, int n, int k) {
        visited=vector<vector<bool>>(m,vector<bool>(n));
        int ans=dfs(m,n,0,0,k);
        return ans;
    }

    int dfs(int m,int n,int x,int y,int k)
    {
        if(x<0||x>=m||y<0||y>=n||visited[x][y]==true) return 0;
        if(getx(x)+getx(y)>k) return 0;

        visited[x][y]=true;
        int ans= 1+dfs(m,n,x+1,y,k)+dfs(m,n,x,y+1,k);
        return ans;
    }
};
  • DFS,无需回溯

剑指 Offer 14- I. 剪绳子

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n+1);

        dp[2]=1;
        int ans;
        for(int i=3;i<=n;i++)
        {
            for(int j=1;j<i;j++)
            {
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));    
            }
        }
        return dp[n];
    }
};
  • 长度为i时,从j处剪成两段,分别为j和j-i
    • 若继续剪,则是j*dp[j-i]
    • 若不剪,则是j*(j-i)
    • 两者取最大值

剑指 Offer 15. 二进制中1的个数

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 ‘1’ 的个数

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans=0;
        while(n)
        {
            if(n&1) ans++;
            n=n>>1;
        }
        return ans;
    }
};
  • 时间复杂度O(K) K为二进制位数
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans=0;
        while(n)
        {
            n=n&(n-1);
            ans++;
        }
        return ans;
    }
};
  • 时间复杂度从O(n)

剑指 Offer 16. 数值的整数次方

实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。

class Solution {
public:
    double myPow(double x, int n) {
        long long pow=abs(n);
        double ans=1.0;
        while(pow)
        {
            if(pow&1)
            {
               ans*=x;
            }
            pow>>=1;
            x*=x;

        }
        if(n<0) ans=1/ans;
        return ans;
    }
};
  • 快速幂

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。

class Solution {
public:
    string s;
    vector<int> vec;
    vector<int> printNumbers(int n) {
        char num[]={'0','1','2','3','4','5','6','7','8','9'};
        for(int i=1;i<=n;i++)
            backtracking(n, num,i);
        return vec;
    }

    void backtracking (int n, char num[],int index)
    {
        
        if(s.size()==index)
        {
            vec.push_back(stoi(s));
            return;
        }

        for(int i=0;i<10;i++)
        {
            if(i==0&&s.size()==0) continue;		//去除首位为0的情况
            s.push_back(num[i]);
            backtracking(n, num,index);
            s.pop_back();
        }
        return ;
    }
};
  • 大数全排列
  • 回溯

剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

class Solution {
public:
   ListNode* deleteNode(ListNode* head, int val) {
       if(head->val==val) return head->next;
       ListNode *cur=head;
       while(head!=nullptr)
       {
           if(head->next!=nullptr && head->next->val==val)
           {
               if(head->next->next==nullptr)   //尾节点
               {
                   head->next=nullptr;
               }
               else    //非尾结点
               {
                   head->next=head->next->next;
               }
           }
           head=head->next;
       }
       return cur;
   
   }
};

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *temp=head;
        if(head==nullptr) return head;
        if(head->next==nullptr) return head;
        ListNode *left=head;
        ListNode *right=left->next;

        while(right!=nullptr)
        {
            if(left->val==right->val)
            {
                left->next=right->next;
                right=left->next;
            }
            else
            {
                left=left->next;
                right=left->next;
            }        
        }
        return temp;
    }
};

82. 删除排序链表中的重复元素 II

给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode*pre=new ListNode(-1);
        pre->next=head;
        ListNode*cur=head,*t=pre;
        while(cur!=nullptr)
        {
            while(cur->next!=nullptr&&cur->val==cur->next->val)	//如果有重复
            {
                cur=cur->next;								//则移动到最后一个无重复的节点
            }
            if(pre->next==cur)			//如果无重复,即没移动节点
            {
                pre=pre->next;			//则都往后移动一位
                cur=cur->next;
            }
            else							//移动了的话就把pre->next指向cur->next
            {									//pre不需要移动,执行完pre->next==cur,在													上面的if里就会移动了
                pre->next=cur->next;
                cur=cur->next;
            }
        }
        return t->next;
    }
};

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ,请你统计并返回该数组中和为 k 的连续子数组的个数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        mp[0]=1;
        int n=0,pre=0;
        for(auto& i:nums)
        {
            pre+=i;
            if(mp.find(pre-k)!=mp.end())
            {
                n+=mp[pre-k];
            }
            mp[pre]++;  //若k=2  nums=2,0,0,0,0时,pre一直是2,所以要mp[pre]++,而不是mp[pre]=1;
        }
        return n;
    }
};

剑指 Offer 22. 链表中倒数第k个节点

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *fast=head;
        ListNode *slow=head;
        while(k--)
        {
            fast=fast->next;
        }
        while(fast!=nullptr)
        {
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
};

剑指 Offer 24. 反转链表

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre=nullptr;

        while(head!=nullptr)
        {
            ListNode *t=head->next;
            head->next=pre;
            pre=head;
            head=t;
        }
        return pre;
    }
};

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==nullptr) return l2;
        if(l2==nullptr) return l1;
        if(l1->val<=l2->val)    
        {
            l1->next=mergeTwoLists(l1->next, l2);
            return l1;
        }
        else 
        {
            l2->next=mergeTwoLists(l1, l2->next);
            return l2;
        }
        return nullptr;
    }
};

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) { //遍历A树,调用recur
        if(B==nullptr||A==nullptr) return false;
        return recur(A,B)||isSubStructure(A->left, B)||isSubStructure(A->right, B);
    }

    bool recur(TreeNode* A, TreeNode* B)    //判断A和B是否相同
    {
        if(B==nullptr) return true;	//在前面
        if(A==nullptr||A->val!=B->val) return false;
        return recur(A->left, B->left)&&recur(A->right, B->right);
    }

};

剑指 Offer 27. 二叉树的镜像

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==nullptr) return root;
        TreeNode *t=root;
        swapNode(root);
        return t;
    }

    void swapNode(TreeNode* root)
    {
        if(root==nullptr) return;
        TreeNode *t=root->left;
        root->left=root->right;
        root->right=t;
        swapNode(root->left);
        swapNode(root->right);
    }
};

剑指 Offer 28. 对称的二叉树

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        
        return recur(root->left,root->right);
    }
    bool recur(TreeNode *root1,TreeNode *root2)
    {
        if(root1==nullptr&&root2==nullptr) return true;
        if(root1==nullptr || root2==nullptr) return false;
        if(root1->val!=root2->val) return false;
        return recur(root1->left, root2->right)&&recur(root1->right, root2->left);
    }
};

剑指 Offer 29. 顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.size()==0) return {};
        int up=0,down=matrix.size()-1,left=0,right=matrix[0].size()-1;
        vector<int> vec;
        while(1)
        {
            for(int j=left;j<=right;j++)
            {
                vec.push_back(matrix[up][j]);
            }
            if(++up>down) break;
            for(int j=up;j<=down;j++)
            {
                vec.push_back(matrix[j][right]);
            }
            if(--right<left) break;
            for(int j=right;j>=left;j--)
            {
                vec.push_back(matrix[down][j]);
            }
            if(--down<up) break;
            for(int j=down;j>=up;j--)
            {
                vec.push_back(matrix[j][left]);
            }
            if(++left>right) break;
        }
        return vec;
    }
};

Q.E.D.