刷题链接

输出二叉树的右视图（递归，bfs）

前置知识：1.重建二叉树 2. 二叉树的层序遍历 3.结构体

class Solution {
    
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    struct TreeNode{
    
        int val;
        TreeNode *left,*right;
        TreeNode(int v) : val(v) {
    }
    };
    
    map<int,int> pos;
    vector<int> res;
    
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
    
        // write code here
        
        int n = zhongxu.size();
        for(int i = 0;i < n;i ++ ) pos[zhongxu[i]] = i;
        
        auto root = dfs(xianxu,zhongxu,0, n - 1,0, n - 1);
        
        bfs(root);
        return res;
    }
    
    TreeNode *dfs(vector<int>& pre, vector<int>& inorder,int pl,int pr,int il,int ir)
    {
    
        if(pl > pr) return NULL;
        int val = pre[pl];
        int k = pos[val];
        int len = k - il;
        TreeNode *root = new TreeNode(val);
        root->left = dfs(pre,inorder,pl + 1,pl + len,il,k - 1);
        root->right = dfs(pre,inorder,pl + len + 1,pr,k + 1,ir);
        return root;
    }
    
    void bfs(TreeNode* root)
    {
    
        queue<TreeNode*> q;
        q.push(root);
        while(q.size())
        {
    
            int n = q.size();
            vector<int> cur;
            while(n --)
            {
    
                auto t = q.front();
                q.pop();
                cur.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
                
            }
            res.push_back(cur.back());
        }
    }
};

设计getMin功能的栈（单调栈）

class Solution {
    
public:
    /**
     * return a array which include all ans for op3
     * @param op int整型vector<vector<>> operator
     * @return int整型vector
     */
    stack<int> stk,minstk; // 单调栈作最小栈
    vector<int> getMinStack(vector<vector<int> >& op) {
    
        // write code here
        vector<int> res;
        for(auto &c : op)
        {
    
            int a = c[0];
            if(a == 1)
            {
    
                int b = c[1];
                stk.push(b);
                if(minstk.empty() || b <= minstk.top()) minstk.push(b);
            }
            else if(a == 2)
            {
    
                if(minstk.top() == stk.top()) minstk.pop();
                stk.pop();
            }
            else if(a == 3)
            {
    
                res.push_back(minstk.top());
            }
        }
        return res;
    }
};

表达式求值（栈，递归）

这道题的精髓在：括号，递归处理。
题解

class Solution {
    
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    int solve(string s) {
    
        // write code here
        stack<int> nums;
        char sign = '+';
        int num = 0;
        s += '+' ; // 为了边界处理
        for(int i = 0;i < s.size();i ++ )
        {
    
            if(isdigit(s[i])){
    
                // 溢出处理
                num *= 10;
                num = num - '0' + s[i];
            }
            
            // 括号，递归处理
            if(s[i] == '(')
            {
    
                int j = i + 1;
                int count = 1;
                while(count){
    
                    if(s[j] == ')') count --;
                    else if(s[j] == '(') count ++;
                    j ++ ;
                }
                num = solve(s.substr(i + 1,j - i - 1));
                i = j - 1;
            }
            
            if(s[i] == '+' || s[i] == '-' || s[i] == '*')
            {
    
                if(sign == '+')
                {
    
                    nums.push(num);
                }
                else if(sign == '-')
                {
    
                    nums.push(-num);
                }
                else if(sign == '*')
                {
    
                    int b = nums.top();
                    nums.pop();
                    nums.push(num * b);
                }
                num = 0;
                sign = s[i];
            }
            
        }
        
        int res = 0;
        while(nums.size()) {
    
            res += nums.top();
            nums.pop();
        }
        return res;
    }
};

平衡二叉树（递归）

前置知识：递归求二叉树的高度

class Solution {
    
public:
    bool ans;
    bool IsBalanced_Solution(TreeNode* pRoot) {
    
        ans = true;
        dfs(pRoot);
        return ans;
    }
    
    int dfs(TreeNode *root)
    {
    
        if(!root) return 0;
        
        int left = dfs(root->left);
        int right = dfs(root->right);
        
        if(abs(left - right) > 1) ans = false;
        return max(left,right) + 1;
    }
};

岛屿数量（flood fill算法）

dfs求连通块

class Solution {
    
public:
    /**
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    vector<vector<bool>> st;
    int dx[4] = {
    -1,0,1,0}, dy[4] = {
    0,1,0,-1};
    int n,m;
    vector<vector<char> > g;
    int solve(vector<vector<char> >& grid) {
    
        // write code here
        g = grid;
        if(grid.empty() || grid[0].empty()) return 0;
        
        n = grid.size(), m = grid[0].size();
        st = vector<vector<bool>>(n,vector<bool>(m));
        int cnt = 0;
        for(int i = 0;i < n;i ++ )
           for(int j = 0;j < m;j ++ )
               if(g[i][j] == '1' && !st[i][j])
               {
    
                   dfs(i,j);
                   cnt ++;
               }
         return cnt;
    }
    
    void dfs(int x,int y)
    {
    
        st[x][y] = true;
        for(int i = 0;i < 4;i ++ )
        {
    
            int a = x + dx[i], b= y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m || st[a][b] || g[a][b] == '0') continue;
            dfs(a,b);
        }
    }
};

判断回文（双指针）

class Solution {
    
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param str string字符串 待判断的字符串
     * @return bool布尔型
     */
    bool judge(string str) {
    
        // write code here
        for(int i = 0, j = str.size() - 1;i < j;i ++ , j -- )
            if(str[i] != str[j]) return false;
        return true;
    }
};

二叉树的最大深度（递归）

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
    
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
    
        // write code here
        return dfs(root);
    }
    
    int dfs(TreeNode *root)
    {
    
        if(!root) return 0;
        
        int left = dfs(root->left);
        int right = dfs(root->right);
        
        return max(left,right) + 1;
    }
};

进制转换（短除法）

进制转换

class Solution {
    
public:
    /**
     * 进制转换
     * @param M int整型 给定整数
     * @param N int整型 转换到的进制
     * @return string字符串
     */
    char get(int x)
    {
    
        if(x <= 9) return x + '0';
        else return x - 10 + 'A';
    }
    
    string solve(int M, int N) {
    
        // write code here
        if(M == 0) return "0"; // 1.特判0
        
        string res;
        bool f = 0;  // 2.负数处理
        if(M < 0) f = 1,M = -M;
        while(M){
    
            res += get(M % N);
            M /= N;
        }
        if(f) res += "-";
        reverse(res.begin(),res.end());
        
        return res;
    }
};

买卖股票一次（贪心）

class Solution {
    
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
    
        // write code here
        int n = prices.size();
        int minlow = 1e9;
        int res = 0;
        for(int i = 0;i < n;i ++ )
        {
    
            res = max(res,prices[i] - minlow);
            minlow = min(minlow,prices[i]);
        }
        return res;
    }
};

只出现一次的数字III（异或，位运算）

题解

class Solution {
    
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
    
        int bit_mask = 0;
        for(auto c : data) bit_mask ^= c;
        
        int d = bit_mask & (-bit_mask);
        
        int v1 = 0;
        for(auto c : data)
            if(c & d) 
                v1 ^= c;
        *num1 = v1, *num2 = v1 ^ bit_mask; // 通过引用来返回值
    }
};