剑指Offer---2021/7/22

梦里梦外; 2022-08-29 12:50 141阅读 0赞

### 目录 ###

*  剑指 Offer 31. 栈的压入、弹出序列
 *  剑指 Offer 38. 字符串的排列
 *  剑指 Offer 32 - I. 从上到下打印二叉树
 *  剑指 Offer 44. 数字序列中某一位的数字
 *  剑指 Offer 32 - III. 从上到下打印二叉树 III
 *  剑指 Offer 56 - I. 数组中数字出现的次数
 *  剑指 Offer 56 - II. 数组中数字出现的次数 II
 *  剑指 Offer 34. 二叉树中和为某一值的路径
 *  剑指 Offer 45. 把数组排成最小的数
 *  剑指 Offer 46. 把数字翻译成字符串
 *  剑指 Offer 64. 求1+2+…+n
 *  剑指 Offer 63. 股票的最大利润
 *  剑指 Offer 49. 丑数

# 剑指 Offer 31. 栈的压入、弹出序列 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
分析：  
  初始化一个指针ind指向poped的开始处，遍历pushed，首先将当前元素进栈，接着判断当前栈顶元素是否等于ind处的元素，是就进行出栈操作，并且ind右移。如果最后栈为空，则说明序列合法。  
代码：

class Solution { 
    public:
        bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { 
            stack<int> stk;
            int n = pushed.size();
            int ind = 0;
            for(int x : pushed) { 
                stk.push(x);
                while(ind < n && !stk.empty() && stk.top() == popped[ind]) { 
                    ind++;
                    stk.pop();
                }
            }
            return stk.empty();
        }
    };

# 剑指 Offer 38. 字符串的排列 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
方法一：  
  c++的next\_permutation封装了全排列，使用前需要先进行排序。  
代码：

class Solution { 
    public:
        vector<string> permutation(string s) { 
            sort(s.begin(), s.end());
            vector<string> res;
            do { 
                res.push_back(s);
            }while(next_permutation(s.begin(), s.end()));
            return res;
            //dfs
            
        }
    };

方法二：  
  回溯：背模板。  
代码：

class Solution { 
    public:
        void backtrack(string& s, int i, int n, string& temp, vector<string>& res, vector<int> visited) { 
            if(i == n) { 
                res.push_back(temp);
                return;
            }
            for(int j = 0; j < n; j++) { 
                if (visited[j] || (j > 0 && !visited[j - 1] && s[j - 1] == s[j])) { 
                    continue;  //考虑重复
                }
                visited[j] = 1;
                temp.push_back(s[j]);
                backtrack(s, i + 1, n, temp, res, visited);
                temp.pop_back();
                visited[j] = 0;
            }
        }
        
        vector<string> permutation(string s) { 
            sort(s.begin(), s.end());
            vector<string> res;
            string temp = "";
            int n = s.size();
            vector<int> visited(n, 0);
            backtrack(s, 0, n, temp, res, visited);
            return res;
        }
    };

# 剑指 Offer 32 - I. 从上到下打印二叉树 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
分析：  
  树的层次遍历。  
代码：

# 剑指 Offer 44. 数字序列中某一位的数字 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]  
方法一：  
  暴力求解：超时。  
代码：

class Solution { 
    public:
        int findNthDigit(int n) { 
            if(n == 0) { 
                return 0;
            }
            int cum = 0;
            for(int t = 1; ; t++) { 
                int res = 0;
                vector<int> temp;
                int x = t;
                while(x) { 
                    cum++;
                    temp.push_back(x % 10);
                    x /= 10;
                }
                if(cum < n) { 
                    continue;
                }else { 
                    int rem = cum - n;
                    return temp[rem];
                }
            }
            return -1;
        }
    };

方法二：  
  找规律：参考官方题解。  
代码：

class Solution { 
    public:
        int findNthDigit(int n) { 
            long long start = 1;
            int digit = 1;
            long long count = 9;
            while(n>count){ 
                n -=count;
                start *= 10;
                digit ++;
                count = start* digit* 9;  
            }
            int num = start +(n-1)/digit;
            string s = to_string(num);
            return s[(n-1)%digit] -'0';
        }
    };

# 剑指 Offer 32 - III. 从上到下打印二叉树 III #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]  
分析：  
  层序遍历，最后再按照要求对某些层进行逆序操作。  
代码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        vector<vector<int>> levelOrder(TreeNode* root) { 
            vector<vector<int>> res;
            vector<int> temp;
            if(root == NULL) { 
                return res;
            }
            queue<TreeNode*> que;
            que.push(root);
            while(!que.empty()) { 
                int n = que.size();
                for(int i = 0; i < n; i++) { 
                    TreeNode* fr = que.front();
                    if(fr->left) { 
                        que.push(fr->left);
                    }
                    if(fr->right) { 
                        que.push(fr->right);
                    }
                    que.pop();
                    temp.push_back(fr->val);
                }
                res.push_back(temp);
                temp.clear();
            }
            //对每一行进行处理
            for(int i = 0; i < res.size(); i++) { 
                if(i & 1) { 
                    reverse(res[i].begin(), res[i].end());
                }
            }
            return res;
        }
    };

# 剑指 Offer 56 - I. 数组中数字出现的次数 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]  
分析：  
  位运算：参考官方题解。  
代码：

class Solution { 
    public:
        vector<int> singleNumbers(vector<int>& nums) { 
            vector<int> res;
            int t = 0;
            for(int x : nums) { 
                t ^= x;
            }
            int div = 1;
            while((div & t) == 0) { 
                div <<= 1;
            }
            int a = 0, b = 0;
            for(int x : nums) { 
                if(x & div) { 
                    a ^= x;
                }else { 
                    b ^= x;
                }
            }
            res.push_back(a);
            res.push_back(b);
            return res;
        }
    };

# 剑指 Offer 56 - II. 数组中数字出现的次数 II #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 6]  
分析：  
  哈希表暴力求解。  
代码：

class Solution { 
    public:
        int singleNumber(vector<int>& nums) { 
            map<int, int> mp;
            for(int x : nums) { 
                mp[x]++;
            }
            map<int, int>::iterator it = mp.begin();
            for(; it != mp.end(); ++it) { 
                if(it->second == 1) { 
                    return it->first;
                }
            }
            return 0;
        }
    };

# 剑指 Offer 34. 二叉树中和为某一值的路径 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 7]  
分析：  
  dfs：背模板。  
代码：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution { 
    public:
        void dfs(vector<vector<int>>& res, vector<int>& temp, TreeNode* root, int target) { 
            if(root == NULL) { 
                return;
            }
            temp.push_back(root->val);
            target -= root->val;
            if(root->left == NULL && root->right == NULL && target == 0) { 
                res.push_back(temp);
            }
            dfs(res, temp, root->left, target);
            dfs(res, temp, root->right, target);
            temp.pop_back();
            target += root->val;
        }
        
        vector<vector<int>> pathSum(TreeNode* root, int target) { 
            vector<vector<int>> res;
            vector<int> temp;
            if(root == NULL) { 
                return res;
            }
            dfs(res, temp, root, target);
            return res;
        }
    };

# 剑指 Offer 45. 把数组排成最小的数 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 8]  
分析：  
  贪心算法：把数组中的数字按照题目所给要求进行排序，然后再链接在一起。  
代码：

class Solution { 
    public:
        static bool cmp(string x, string y) { 
            return x + y < y + x;
        }
        string minNumber(vector<int>& nums) { 
            vector<string> vec;
            for(int x : nums) { 
                stringstream ss;
                ss << x;
                string temp;
                ss >> temp;
                vec.push_back(temp);
            }
            sort(vec.begin(), vec.end(), cmp);
            string res = "";
            for(string x : vec) { 
                res += x;
            }
            return res;
        }
    };

# 剑指 Offer 46. 把数字翻译成字符串 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 9]  
分析：  
  动态规划：参考官方题解。  
代码：

class Solution { 
    public:
        int translateNum(int num) { 
            string src = to_string(num);
            int p = 0, q = 0, r = 1;
            for (int i = 0; i < src.size(); ++i) { 
                p = q; 
                q = r; 
                r = 0;
                r += q;
                if (i == 0) { 
                    continue;
                }
                auto pre = src.substr(i - 1, 2);
                if (pre <= "25" && pre >= "10") { 
                    r += p;
                }
            }
            return r;
        }
    };

# 剑指 Offer 64. 求1+2+…+n #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 10]  
分析：  
  联想到求阶乘，可以使用递归。  
代码：

class Solution { 
    public:
        int sumNums(int n) { 
            if(n == 0) { 
                return 0;
            }else { 
                return n + sumNums(n - 1);
            }
        }
    };

# 剑指 Offer 63. 股票的最大利润 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 11]  
方法一：  
  暴力求解：对买入和卖出的时间进行枚举，超时。  
代码：

class Solution { 
    public:
        int maxProfit(vector<int>& prices) { 
            //暴力求解
            int res = 0;
            int n = prices.size();
            for(int i = 0; i < n; i++) { 
                for(int j = i + 1; j < n; j++) { 
                    if(prices[j] > prices[i]) { 
                        res = max(res, prices[j] - prices[i]);
                    }
                }
            }
            return res;
        }
    };

方法二：  
  用一个变量记录一个历史最低价格 minprice，我们可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices\[i\] - minprice。一直更新minprice，最终得到的就是最优解。  
代码：

class Solution { 
    public:
        int maxProfit(vector<int>& prices) { 
            int inf = 1e9;
            int minprice = inf, maxprofit = 0;
            for (int price: prices) { 
                maxprofit = max(maxprofit, price - minprice);
                minprice = min(price, minprice);
            }
            return maxprofit;
        }
    };

# 剑指 Offer 49. 丑数 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 12]  
方法一：  
  暴力求解：超时。  
代码：

class Solution { 
    public:
        bool check(int n) { 
            while(n > 1) { 
                for(int i = 2; i <= n; i++) { 
                    if(n % i == 0) { 
                        if(i != 2 && i != 3 && i != 5) { 
                            return false;
                        }
                        n /= i;
                        break;
                    }
                }
            }
            return true;
        }
        int nthUglyNumber(int n) { 
            if(n == 1) { 
                return 1;
            }
            int cum = 1;
            for(int i = 2; ; i++) { 
                if(check(i)) { 
                    cum++;
                    if(cum == n) { 
                        return i;
                    }
                }
            }
            return 0;
        }
    };

方法二：  
  如果一个数x是丑数，则2x、3x以及5x都是丑数。  
代码：

class Solution { 
    public:
        int nthUglyNumber(int n) { 
            priority_queue<long long, vector<long long>, greater<long long>> que;
            que.push(1);
            int fac[] = { 2, 3, 5};
            set<long long> st;
            st.insert(1);
            long long res = 0;
            for(int i = 1; i <= n; i++) { 
                res = que.top();
                que.pop();
                for(int i = 0; i < 3; i++) { 
                    long long temp = (long long)res * fac[i];
                    if(st.count(temp) == 0) { 
                        st.insert(temp);
                        que.push(temp);
                    }
                }
            }
            return res;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20220829/d4933644d2a443c08b64ffb8f73a1478.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20220829/8b584e3bb6e948f6ada81b7317f6fcf6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20220829/0a2e347cc4a1403c92a0cad3b3541dd1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]: /images/20220829/748ebc93b026484c959b0b1f65b61916.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]: /images/20220829/887ed683aebb4886a24c1cc6bf7212ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]: /images/20220829/9355fcdd3e764e37ae90789dedf498aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 6]: /images/20220829/f01a802899c1421bbfb8f70413691bf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 7]: /images/20220829/57a4f6db157a4f3096ccc654e6db2851.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 8]: /images/20220829/8f335af8353241a79a46ef8e2a9f522a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 9]: /images/20220829/660c0913e7484ccbbf0481a1552351c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 10]: /images/20220829/01e0898ba6544e3faa7298388b816859.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 11]: /images/20220829/a0438923ef6a410bae95df3fbfb192ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 12]: /images/20220829/5983b678656f4d6a9d051c375f80e0d4.png