栈和队列

Dear 丶 2024-02-19 13:28 195阅读 0赞

20.[\[LeetCode\] Valid Parentheses 验证括号][LeetCode_ Valid Parentheses]

给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串，判断字符串是否有效。

有效字符串需满足：

1.  左括号必须用相同类型的右括号闭合。
2.  左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

**示例 1:**

输入: "()"
    输出: true

**示例 2:**

输入: "()[]{}"
    输出: true

这道题让我们验证输入的字符串是否为括号字符串，包括大括号，中括号和小括号。这里我们需要用一个栈，我们开始遍历输入字符串，如果当前字符为左半边括号时，则将其压入栈中，如果遇到右半边括号时，若此时栈为空，则直接返回false，如不为空，则取出栈顶元素，若为对应的左半边括号，则继续循环，反之返回false，代码如下：

![复制代码][copycode.gif]

class Solution {
    public:
        bool isValid(string s) {
            stack<char> parentheses;
            for (int i = 0; i < s.size(); ++i) {
                if (s[i] == '(' || s[i] == '[' || s[i] == '{') parentheses.push(s[i]);
                else {
                    if (parentheses.empty()) return false;
                    if (s[i] == ')' && parentheses.top() != '(') return false;
                    if (s[i] == ']' && parentheses.top() != '[') return false;
                    if (s[i] == '}' && parentheses.top() != '{') return false;
                    parentheses.pop();
                }
            }
            return parentheses.empty();
        }
    };

150.[\[LeetCode\] Evaluate Reverse Polish Notation 计算逆波兰表达式][LeetCode_ Evaluate Reverse Polish Notation]

根据[逆波兰表示法][Link 1]，求表达式的值。

有效的运算符包括 `+`, `-`, `*`, `/` 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

**说明：**

*  整数除法只保留整数部分。
 *  给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

**示例 1：**

输入: ["2", "1", "+", "3", "*"]
    输出: 9
    解释: ((2 + 1) * 3) = 9

**示例 2：**

输入: ["4", "13", "5", "/", "+"]
    输出: 6
    解释: (4 + (13 / 5)) = 6

**示例 3：**

输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
    输出: 22
    解释: 
      ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
    = ((10 * (6 / (12 * -11))) + 17) + 5
    = ((10 * (6 / -132)) + 17) + 5
    = ((10 * 0) + 17) + 5
    = (0 + 17) + 5
    = 17 + 5
    = 22

[逆波兰表达式][Link 2]就是把操作数放前面，把操作符后置的一种写法，我们通过观察可以发现，第一个出现的运算符，其前面必有两个数字，当这个运算符和之前两个数字完成运算后从原数组中删去，把得到一个新的数字插入到原来的位置，继续做相同运算，直至整个数组变为一个数字。从前往后遍历数组，遇到数字则压入栈中，遇到符号，则把栈顶的两个数字拿出来运算，把结果再压入栈中，直到遍历完整个数组，栈顶数字即为最终答案。代码如下:

class Solution {
    public:
        int evalRPN(vector<string>& tokens) {
            if (tokens.size() == 1) return stoi(tokens[0]);
            stack<int> st;
            for (int i = 0; i < tokens.size(); ++i) {
                if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") {
                    st.push(stoi(tokens[i]));
                } else {
                    int num1 = st.top(); st.pop();
                    int num2 = st.top(); st.pop();
                    if (tokens[i] == "+") st.push(num2 + num1);
                    if (tokens[i] == "-") st.push(num2 - num1);
                    if (tokens[i] == "*") st.push(num2 * num1);
                    if (tokens[i] == "/") st.push(num2 / num1);
                }
            }
            return st.top();
        }
    };

我们也可以用递归来做，由于一个有效的逆波兰表达式的末尾必定是操作符，所以我们可以从末尾开始处理，如果遇到操作符，向前两个位置调用递归函数，找出前面两个数字，然后进行操作将结果返回，如果遇到的是数字直接返回即可，参见代码如下：

解法二：

![复制代码][copycode.gif]

class Solution {
    public:
        int evalRPN(vector<string>& tokens) {
            int op = (int)tokens.size() - 1;
            return helper(tokens, op);
        }
        int helper(vector<string>& tokens, int& op) {
            string str = tokens[op];
            if (str != "+" && str != "-" && str != "*" && str != "/") return stoi(str);
            int num1 = helper(tokens, --op);
            int num2 = helper(tokens, --op);
            if (str == "+") return num2 + num1;
            if (str == "-") return num2 - num1;
            if (str == "*") return num2 * num1;
            return num2 / num1;
        }
    };

71.[\[LeetCode\] Simplify Path 简化路径][LeetCode_ Simplify Path]

给定一个文档 (Unix-style) 的完全路径，请进行路径简化。

例如，  
**path** = `"/home/"`, => `"/home"`  
**path** = `"/a/./b/../../c/"`, => `"/c"`

**边界情况:**

*  你是否考虑了 路径 = `"/../"` 的情况？  
    在这种情况下，你需返回 `"/"` 。
 *  此外，路径中也可能包含多个斜杠 `'/'` ，如 `"/home//foo/"` 。  
    在这种情况下，你可忽略多余的斜杠，返回 `"/home/foo"` 。
 *  这道题让简化给定的路径，光根据题目中给的那一个例子还真不太好总结出规律，应该再加上两个例子 path = `"/a/./b/../c/"`, => `"/a/c"和path = "/a/./b/c/", => "/a/b/c"， 这样我们就可以知道中间是"."的情况直接去掉，是".."时删掉它上面挨着的一个路径，而下面的边界条件给的一些情况中可以得知，如果是空的话返回"/"，如果有多个"/"只保留一个。那么我们可以把路径看做是由一个或多个"/"分割开的众多子字符串，把它们分别提取出来一一处理即可，代码如下：`
    
    C++ 解法一:
    
    ![复制代码][copycode.gif]
    
        class Solution {
        public:
            string simplifyPath(string path) {
                vector<string> v;
                int i = 0;
                while (i < path.size()) {
                    while (path[i] == '/' && i < path.size()) ++i;
                    if (i == path.size()) break;
                    int start = i;
                    while (path[i] != '/' && i < path.size()) ++i;
                    int end = i - 1;
                    string s = path.substr(start, end - start + 1);
                    if (s == "..") {
                        if (!v.empty()) v.pop_back(); 
                    } else if (s != ".") {
                        v.push_back(s);
                    }
                }
                if (v.empty()) return "/";
                string res;
                for (int i = 0; i < v.size(); ++i) {
                    res += '/' + v[i];
                }
                return res;
            }
        };
    
    ![复制代码][copycode.gif]
    
    还有一种解法是利用了C语言中的函数strtok来分隔字符串，但是需要把string和char\*类型相互转换，转换方法请猛戳[这里][Link 3]。除了这块不同，其余的思想和上面那种解法相同，代码如下：
    
    C 解法一:
    
    ![复制代码][copycode.gif]
    
        class Solution {
        public:
            string simplifyPath(string path) {
                vector<string> v;
                char *cstr = new char[path.length() + 1];
                strcpy(cstr, path.c_str());
                char *pch = strtok(cstr, "/");
                while (pch != NULL) {
                    string p = string(pch);
                    if (p == "..") {
                        if (!v.empty()) v.pop_back();
                    } else if (p != ".") {
                        v.push_back(p);
                    }
                    pch = strtok(NULL, "/");
                }
                if (v.empty()) return "/";
                string res;
                for (int i = 0; i < v.size(); ++i) {
                    res += '/' + v[i];
                }
                return res;
            }
        };
    
    ![复制代码][copycode.gif]
    
    C++中也有专门处理字符串的机制，我们可以使用stringstream来分隔字符串，然后对每一段分别处理，思路和上面的方法相似，参见代码如下：
    
    C++ 解法二：
    
    ![复制代码][copycode.gif]
    
        class Solution {
        public:
            string simplifyPath(string path) {
                string res, t;
                stringstream ss(path);
                vector<string> v;
                while (getline(ss, t, '/')) {
                    if (t == "" || t == ".") continue;
                    if (t == ".." && !v.empty()) v.pop_back();
                    else if (t != "..") v.push_back(t);
                }
                for (string s : v) res += "/" + s;
                return res.empty() ? "/" : res;
            }
        };

144.[\[LeetCode\] Binary Tree Preorder Traversal 二叉树的先序遍历][LeetCode_ Binary Tree Preorder Traversal]

给定一个二叉树，返回它的 *前序* 遍历。

**示例:**

输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    
    输出: [1,2,3]

**进阶:** 递归算法很简单，你可以通过迭代算法完成吗？

一般我们提到[树的遍历][Link 4]，最常见的有先序遍历，中序遍历，后序遍历和层序遍历，它们用递归实现起来都非常的简单。而题目的要求是不能使用递归求解，于是只能考虑到用非递归的方法，这就要用到stack来辅助运算。由于先序遍历的顺序是"根-左-右", 算法为：

1. 把根节点push到栈中

2. 循环检测栈是否为空，若不空，则取出栈顶元素，保存其值，然后看其右子节点是否存在，若存在则push到栈中。再看其左子节点，若存在，则push到栈中。

代码如下：

解法一：

![复制代码][copycode.gif]

class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            if (!root) return {};
            vector<int> res;
            stack<TreeNode*> s{
       {root}};
            while (!s.empty()) {
                TreeNode *t = s.top(); s.pop();
                res.push_back(t->val);
                if (t->right) s.push(t->right);
                if (t->left) s.push(t->left);
            }
            return res;
        }
    };

94.[\[LeetCode\] Binary Tree Inorder Traversal 二叉树的中序遍历][LeetCode_ Binary Tree Inorder Traversal]

给定一个二叉树，返回它的*中序* 遍历。

**示例:**

输入: [1,null,2,3]
       1
        \
         2
        /
       3
    
    输出: [1,3,2]

**进阶:** 递归算法很简单，你可以通过迭代算法完成吗？

二叉树的中序遍历顺序为左-根-右，可以有递归和非递归来解，其中非递归解法又分为两种，一种是使用栈来接，另一种不需要使用栈。我们先来看递归方法，十分直接，对左子结点调用递归函数，根节点访问值，右子节点再调用递归函数，代码如下：

解法一：

// Recursion
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode *root) {
            vector<int> res;
            inorder(root, res);
            return res;
        }
        void inorder(TreeNode *root, vector<int> &res) {
            if (!root) return;
            if (root->left) inorder(root->left, res);
            res.push_back(root->val);
            if (root->right) inorder(root->right, res);
        }
    };

下面我们再来看非递归使用栈的解法，也是符合本题要求使用的解法之一，需要用栈来做，思路是从根节点开始，先将根节点压入栈，然后再将其所有左子结点压入栈，然后取出栈顶节点，保存节点值，再将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右，代码如下：

解法二：

// Non-recursion
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode *root) {
            vector<int> res;
            stack<TreeNode*> s;
            TreeNode *p = root;
            while (p || !s.empty()) {
                while (p) {
                    s.push(p);
                    p = p->left;
                }
                p = s.top();
                s.pop();
                res.push_back(p->val);
                p = p->right;
            }
            return res;
        }
    };

145.[\[LeetCode\] Binary Tree Postorder Traversal 二叉树的后序遍历][LeetCode_ Binary Tree Postorder Traversal]

给定一个二叉树，返回它的 *后序* 遍历。

**示例:**

输入: [1,null,2,3]  
       1
        \
         2
        /
       3 
    
    输出: [3,2,1]

**进阶:** 递归算法很简单，你可以通过迭代算法完成吗？

经典题目，求二叉树的后序遍历的非递归方法，跟前序，中序，层序一样都需要用到栈，后续的顺序是左-右-根，所以当一个节点值被取出来时，它的左右子节点要么不存在，要么已经被访问过了。我们先将根结点压入栈，然后定义一个辅助结点head，while循环的条件是栈不为空，在循环中，首先将栈顶结点t取出来，如果栈顶结点没有左右子结点，或者其左子结点是head，或者其右子结点是head的情况下。我们将栈顶结点值加入结果res中，并将栈顶元素移出栈，然后将head指向栈顶元素；否则的话就看如果右子结点不为空，将其加入栈，再看左子结点不为空的话，就加入栈，注意这里先右后左的顺序是因为栈的后入先出的特点，可以使得左子结点先被处理。下面来看为什么是这三个条件呢，首先如果栈顶元素如果没有左右子结点的话，说明其是叶结点，而且我们的入栈顺序保证了左子结点先被处理，所以此时的结点值就可以直接加入结果res了，然后移出栈，将head指向这个叶结点，这样的话head每次就是指向前一个处理过并且加入结果res的结点，那么如果栈顶结点的左子结点或者右子结点是head的话，说明其子结点已经加入结果res了，那么就可以处理当前结点了，代码如下：

解法一：

class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            if (!root) return {};
            vector<int> res;
            stack<TreeNode*> s{
       {root}};
            TreeNode *head = root;
            while (!s.empty()) {
                TreeNode *t = s.top();
                if ((!t->left && !t->right) || t->left == head || t->right == head) {
                    res.push_back(t->val);
                    s.pop();
                    head = t;
                } else {
                    if (t->right) s.push(t->right);
                    if (t->left) s.push(t->left);
                }
            }
            return res;
        }
    };

论坛上还有一种双栈的解法，其实本质上跟解法二没什么区别，都是利用了改变先序遍历的顺序来实现后序遍历的，参见代码如下：

class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            if (!root) return {};
            vector<int> res;
            stack<TreeNode*> s1, s2;
            s1.push(root);
            while (!s1.empty()) {
                TreeNode *t = s1.top(); s1.pop();
                s2.push(t);
                if (t->left) s1.push(t->left);
                if (t->right) s1.push(t->right);
            }
            while (!s2.empty()) {
                res.push_back(s2.top()->val); s2.pop();
            }
            return res;
        }
    };

102.[\[LeetCode\] Binary Tree Level Order Traversal 二叉树层序遍历][LeetCode_ Binary Tree Level Order Traversal]

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:  
给定二叉树: `[3,9,20,null,null,15,7]`,

3
       / \
      9  20
        /  \
       15   7

返回其层次遍历结果：

[
      [3],
      [9,20],
      [15,7]
    ]

层序遍历二叉树是典型的广度优先搜索BFS的应用，但是这里稍微复杂一点的是，我们要把各个层的数分开，存到一个二维向量里面，大体思路还是基本相同的，建立一个queue，然后先把根节点放进去，这时候找根节点的左右两个子节点，这时候去掉根节点，此时queue里的元素就是下一层的所有节点，用一个for循环遍历它们，然后存到一个一维向量里，遍历完之后再把这个一维向量存到二维向量里，以此类推，可以完成层序遍历。代码如下：

解法一：

![复制代码][copycode.gif]

// Iterative
    class Solution {
    public:
        vector<vector<int> > levelOrder(TreeNode *root) {
            vector<vector<int> > res;
            if (root == NULL) return res;
    
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty()) {
                vector<int> oneLevel;
                int size = q.size();
                for (int i = 0; i < size; ++i) {
                    TreeNode *node = q.front();
                    q.pop();
                    oneLevel.push_back(node->val);
                    if (node->left) q.push(node->left);
                    if (node->right) q.push(node->right);
                }
                res.push_back(oneLevel);
            }
            return res;
        }
    };

下面我们来看递归的写法，核心就在于我们需要一个二维数组，和一个变量level，当level递归到上一层的个数，我们新建一个空层，继续往里面加数字，参见代码如下：

解法二：

class Solution \{  
public:  
vector<vector<int>> levelOrder(TreeNode\* root) \{  
vector<vector<int> > res;  
levelorder(root, 0, res);  
return res;  
\}  
void levelorder(TreeNode \*root, int level, vector<vector<int> > &res) \{  
if (!root) return;  
if (res.size() == level) res.push\_back(\{\});  
res\[level\].push\_back(root->val);  
if (root->left) levelorder(root->left, level + 1, res);  
if (root->right) levelorder(root->right, level + 1, res);  
\}  
\};

103[\[LeetCode\] Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历][LeetCode_ Binary Tree Zigzag Level Order Traversal]

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：  
给定二叉树 `[3,9,20,null,null,15,7]`,

3
       / \
      9  20
        /  \
       15   7

返回锯齿形层次遍历如下：

[
      [3],
      [20,9],
      [15,7]
    ]

这道二叉树的之字形层序遍历是之前那道[\[LeetCode\] Binary Tree Level Order Traversal 二叉树层序遍历][LeetCode_ Binary Tree Level Order Traversal 1]的变形，不同之处在于一行是从左到右遍历，下一行是从右往左遍历，交叉往返的之字形的层序遍历。根据其特点我们用到栈的后进先出的特点，这道题我们维护两个栈，相邻两行分别存到两个栈中，进栈的顺序也不相同，一个栈是先进左子结点然后右子节点，另一个栈是先进右子节点然后左子结点，这样出栈的顺序就是我们想要的之字形了，代码如下：

![复制代码][copycode.gif]

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
            vector<vector<int> >res;
            if (!root) return res;
            stack<TreeNode*> s1;
            stack<TreeNode*> s2;
            s1.push(root);
            vector<int> out;
            while (!s1.empty() || !s2.empty()) {
                while (!s1.empty()) {
                    TreeNode *cur = s1.top();
                    s1.pop();
                    out.push_back(cur->val);
                    if (cur->left) s2.push(cur->left);
                    if (cur->right) s2.push(cur->right);
                } 
                if (!out.empty()) res.push_back(out);
                out.clear();
                while (!s2.empty()) {
                    TreeNode *cur = s2.top();
                    s2.pop();
                    out.push_back(cur->val);
                    if (cur->right) s1.push(cur->right);
                    if (cur->left) s1.push(cur->left);
                }
                if (!out.empty()) res.push_back(out);
                out.clear();
            }
            return res;
        }
    };

107[\[LeetCode\] Binary Tree Level Order Traversal II 二叉树层序遍历之二][LeetCode_ Binary Tree Level Order Traversal II]

class Solution {
    public:
        vector<vector<int> > levelOrderBottom(TreeNode *root) {
            vector<vector<int> > res;
            if (root == NULL) return res;
    
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty()) {
                vector<int> oneLevel;
                int size = q.size();
                for (int i = 0; i < size; ++i) {
                    TreeNode *node = q.front();
                    q.pop();
                    oneLevel.push_back(node->val);
                    if (node->left) q.push(node->left);
                    if (node->right) q.push(node->right);
                }
                res.insert(res.begin(), oneLevel);
            }
            return res;
        }
    };

![复制代码][copycode.gif]

下面我们来看递归的解法，核心就在于我们需要一个二维数组，和一个变量level，当level递归到上一层的个数，我们新建一个空层，继续往里面加数字，参见代码如下：

解法二：

![复制代码][copycode.gif]

// Recurive
    class Solution {
    public:
        vector<vector<int>> levelOrderBottom(TreeNode* root) {
            vector<vector<int> > res;
            levelorder(root, 0, res);
            return vector<vector<int> > (res.rbegin(), res.rend());
        }
        void levelorder(TreeNode *root, int level, vector<vector<int> > &res) {
            if (!root) return;
            if (res.size() == level) res.push_back({});
            res[level].push_back(root->val);
            if (root->left) levelorder(root->left, level + 1, res);
            if (root->right) levelorder(root->right, level + 1, res);
        }
    };

199.[\[LeetCode\] Binary Tree Right Side View 二叉树的右侧视图][LeetCode_ Binary Tree Right Side View]

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

**示例:**

输入: [1,2,3,null,5,null,4]
    输出: [1, 3, 4]
    解释:
    
       1            <---
     /   \
    2     3         <---
     \     \
      5     4       <---

这道题要求我们打印出二叉树每一行最右边的一个数字，实际上是求二叉树层序遍历的一种变形，我们只需要保存每一层最右边的数字即可，可以参考我之前的博客[ Binary Tree Level Order Traversal 二叉树层序遍历][LeetCode_ Binary Tree Level Order Traversal 1]，这道题只要在之前那道题上稍加修改即可得到结果，还是需要用到数据结构队列queue，遍历每层的节点时，把下一层的节点都存入到queue中，每当开始新一层节点的遍历之前，先把新一层最后一个节点值存到结果中，代码如下：

![复制代码][copycode.gif]

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> rightSideView(TreeNode *root) {
            vector<int> res;
            if (!root) return res;
            queue<TreeNode*> q;
            q.push(root);
            while (!q.empty()) {
                res.push_back(q.back()->val);
                int size = q.size();
                for (int i = 0; i < size; ++i) {
                    TreeNode *node = q.front();
                    q.pop();
                    if (node->left) q.push(node->left);
                    if (node->right) q.push(node->right);
                }
            }
            return res;
        }
    };

279[\[LeetCode\] Perfect Squares 完全平方数][LeetCode_ Perfect Squares]

先来看第一种很高效的方法，根据四平方和定理，任意一个正整数均可表示为4个整数的平方和，其实是可以表示为4个以内的平方数之和，那么就是说返回结果只有1,2,3或4其中的一个，首先我们将数字化简一下，由于一个数如果含有因子4，那么我们可以把4都去掉，并不影响结果，比如2和8,3和12等等，返回的结果都相同，读者可自行举更多的栗子。还有一个可以化简的地方就是，如果一个数除以8余7的话，那么肯定是由4个完全平方数组成，这里就不证明了，因为我也不会证明，读者可自行举例验证。那么做完两步后，一个很大的数有可能就会变得很小了，大大减少了运算时间，下面我们就来尝试的将其拆为两个平方数之和，如果拆成功了那么就会返回1或2，因为其中一个平方数可能为0. (注：由于输入的n是正整数，所以不存在两个平方数均为0的情况)。注意下面的!!a + !!b这个表达式，可能很多人不太理解这个的意思，其实很简单，感叹号!表示逻辑取反，那么一个正整数逻辑取反为0，再取反为1，所以用两个感叹号!!的作用就是看a和b是否为正整数，都为正整数的话返回2，只有一个是正整数的话返回1，参见代码如下：

解法一：

class Solution {
    public:
        int numSquares(int n) {
            while (n % 4 == 0) n /= 4;
            if (n % 8 == 7) return 4;
            for (int a = 0; a * a <= n; ++a) {
                int b = sqrt(n - a * a);
                if (a * a + b * b == n) {
                    return !!a + !!b;
                }
            }
            return 3;
        }
    };

这道题远不止这一种解法，我们还可以用动态规划Dynamic Programming来做，我们建立一个长度为n+1的一维dp数组，将第一个值初始化为0，其余值都初始化为INT\_MAX, i从0循环到n，j从1循环到i+j\*j <= n的位置，然后每次更新dp\[i+j\*j\]的值，动态更新dp数组，其中dp\[i\]表示正整数i能少能由多个完全平方数组成，那么我们求n，就是返回dp\[n\]即可，也就是dp数组的最后一个数字，参见代码如下：

解法二：

// DP
    class Solution {
    public:
        int numSquares(int n) {
            vector<int> dp(n + 1, INT_MAX);
            dp[0] = 0;
            for (int i = 0; i <= n; ++i) {
                for (int j = 1; i + j * j <= n; ++j) {
                    dp[i + j * j] = min(dp[i + j * j], dp[i] + 1);
                }
            }
            return dp.back();
        }
    };

下面再来看一种DP解法，这种解法跟上面有些不同，上面那种解法是初始化了整个长度为n+1的dp数字，但是初始化的顺序不定的，而这个种方法只初始化了第一个值为0，那么在循环里计算，每次增加一个dp数组的长度，里面那个for循环一次循环结束就算好下一个数由几个完全平方数组成，直到增加到第n+1个，返回即可，想更直观的看这两种DP方法的区别，建议每次循环后都打印出dp数字的值来观察其更新的顺序，参见代码如下：

解法三：

// DP
    class Solution {
    public:
        int numSquares(int n) {
            vector<int> dp(1, 0);
            while (dp.size() <= n) {
                int m = dp.size(), val = INT_MAX;
                for (int i = 1; i * i <= m; ++i) {
                    val = min(val, dp[m - i * i] + 1);
                }
                dp.push_back(val);
            }
            return dp.back();
        }
    };

最后我们来介绍一种递归Recursion的解法，这种方法的好处是写法简洁，但是运算效率不敢恭维。我们的目的是遍历所有比n小的完全平方数，然后对n与完全平方数的差值递归调用函数，目的是不断更新最终结果，知道找到最小的那个，参见代码如下：

解法四：

// Recrusion
    class Solution {
    public:
        int numSquares(int n) {
            int res = n, num = 2;
            while (num * num <= n) {
                int a = n / (num * num), b = n % (num * num);
                res = min(res, a + numSquares(b));
                ++num;
            }
            return res;
        }
    };

PS：解法二三四的运算效率真的不高，强推解法一，高效又易懂，如果想强行优化后三个算法，可以将解法一的前两个if判断加到后三个的算法的开头，能很大的提高运算效率。

127.[\[LeetCode\] Word Ladder 词语阶梯][LeetCode_ Word Ladder]

给定两个单词（*beginWord* 和 *endWord*）和一个字典，找到从 *beginWord* 到 *endWord*的最短转换序列的长度。转换需遵循如下规则：

1.  每次转换只能改变一个字母。
2.  转换过程中的中间单词必须是字典中的单词。

**说明:**

*  如果不存在这样的转换序列，返回 0。
 *  所有单词具有相同的长度。
 *  所有单词只由小写字母组成。
 *  字典中不存在重复的单词。
 *  你可以假设 *beginWord* 和 *endWord* 是非空的，且二者不相同。

**示例 1:**

输入:
    beginWord = "hit",
    endWord = "cog",
    wordList = ["hot","dot","dog","lot","log","cog"]
    
    输出: 5
    
    解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
         返回它的长度 5。

这道词句阶梯的问题给了我们一个单词字典，里面有一系列很相似的单词，然后给了一个起始单词和一个结束单词，每次变换只能改变一个单词，并且中间过程的单词都必须是单词字典中的单词，让我们求出最短的变化序列的长度。这道题还是挺有难度的，我当然是看了别人的解法才写出来的，这没啥的，从不会到完全掌握才是成长嘛～

当拿到题就懵逼的我们如何才能找到一个科学的探索解题的路径呢，那就是先别去管代码实现，如果让我们肉身解题该怎么做呢？让你将 'hit' 变为 'cog'，那么我们发现这两个单词没有一个相同的字母，所以我们就尝试呗，博主会先将第一个 'h' 换成 'c'，看看 'cit' 在不在字典中，发现不在，那么把第二个 'i' 换成 'o'，看看 'hot' 在不在，发现在，完美！然后尝试 'cot' 或者 'hog'，发现都不在，那么就比较麻烦了，我们没法快速的达到目标单词，需要一些中间状态，但我们怎么知道中间状态是什么。简单粗暴的方法就是brute force，遍历所有的情况，我们将起始单词的每一个字母都用26个字母来替换，比如起始单词 'hit' 就要替换为 'ait', 'bit', 'cit', .... 'yit', 'zit'，将每个替换成的单词都在字典中查找一下，如果有的话，那么说明可能是潜在的路径，要保存下来。那么现在就有个问题，比如我们换到了 'hot' 的时候，此时发现在字典中存在，那么下一步我们是继续试接下来的 'hpt', 'hqt', 'hrt'... 还是直接从 'hot' 的首字母开始换 'aot', 'bot', 'cot' ... 这实际上就是BFS和DFS的区别，到底是广度优先，还是深度优先。讲到这里，不知道你有没有觉得这个跟什么很像？对了，跟迷宫遍历很像啊，你想啊，迷宫中每个点有上下左右四个方向可以走，而这里有26个字母，就是二十六个方向可以走，本质上没有啥区别啊！如果熟悉迷宫遍历的童鞋们应该知道，应该用BFS来求最短路径的长度，这也不难理解啊，DFS相当于一条路走到黑啊，你走的那条道不一定是最短的啊。而BFS相当于一个小圈慢慢的一层一层扩大，相当于往湖里扔个石头，一圈一圈扩大的水波纹那种感觉，当水波纹碰到湖上的树叶时，那么此时水圈的半径就是圆心到树叶的最短距离。脑海中有没有浮现出这个生动的场景呢？

明确了要用BFS，我们可以开始解题了，为了提到字典的查找效率，我们使用HashSet保存所有的单词。然后我们需要一个HashMap，来建立某条路径结尾单词和该路径长度之间的映射，并把起始单词映射为1。既然是BFS，我们需要一个队列queue，把起始单词排入队列中，开始队列的循环，取出队首词，然后对其每个位置上的字符，用26个字母进行替换，如果此时和结尾单词相同了，就可以返回取出词在哈希表中的值加一。如果替换词在字典中存在但在哈希表中不存在，则将替换词排入队列中，并在哈希表中的值映射为之前取出词加一。如果循环完成则返回0，参见代码如下：

解法一：

![复制代码][copycode.gif]

class Solution {
    public:
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            unordered_set<string> wordSet(wordList.begin(), wordList.end());
            unordered_map<string, int> pathCnt{
       {
       {beginWord, 1}}};
            queue<string> q{
       {beginWord}};
            while (!q.empty()) {
                string word = q.front(); q.pop();
                for (int i = 0; i < word.size(); ++i) {
                    string newWord = word;
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        newWord[i] = ch;
                        if (wordSet.count(newWord) && newWord == endWord) return pathCnt[word] + 1;
                        if (wordSet.count(newWord) && !pathCnt.count(newWord)) {
                            q.push(newWord);
                            pathCnt[newWord] = pathCnt[word] + 1;
                        }   
                    }
                }
            }
            return 0;
        }
    };

![复制代码][copycode.gif]

其实我们并不需要上面解法中的HashMap，由于BFS的遍历机制就是一层一层的扩大的，那么我们只要记住层数就行，然后在while循环中使用一个小trick，加一个for循环，表示遍历完当前队列中的个数后，层数就自增1，这样的话我们就省去了HashMap，而仅仅用一个变量res来记录层数即可，参见代码如下：

解法二：

![复制代码][copycode.gif]

class Solution {
    public:
        int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
            unordered_set<string> wordSet(wordList.begin(), wordList.end());
            queue<string> q{
       {beginWord}};
            int res = 0;
            while (!q.empty()) {
                for (int k = q.size(); k > 0; --k) {
                    string word = q.front(); q.pop();
                    if (word == endWord) return res + 1;
                    for (int i = 0; i < word.size(); ++i) {
                        string newWord = word;
                        for (char ch = 'a'; ch <= 'z'; ++ch) {
                            newWord[i] = ch;
                            if (wordSet.count(newWord) && newWord != word) {
                                q.push(newWord);
                                wordSet.erase(newWord);
                            }   
                        }
                    }
                }
                ++res;
            }
            return 0;
        }
    };

126.[\[LeetCode\] Word Ladder II 词语阶梯之二][LeetCode_ Word Ladder II]

给定两个单词（*beginWord* 和 *endWord*）和一个字典 *wordList*，找出所有从 *beginWord* 到 *endWord* 的最短转换序列。转换需遵循如下规则：

1.  每次转换只能改变一个字母。
2.  转换过程中的中间单词必须是字典中的单词。

**说明:**

*  如果不存在这样的转换序列，返回一个空列表。
 *  所有单词具有相同的长度。
 *  所有单词只由小写字母组成。
 *  字典中不存在重复的单词。
 *  你可以假设 *beginWord* 和 *endWord* 是非空的，且二者不相同。

**示例 1:**

输入:
    beginWord = "hit",
    endWord = "cog",
    wordList = ["hot","dot","dog","lot","log","cog"]
    
    输出:
    [
      ["hit","hot","dot","dog","cog"],
      ["hit","hot","lot","log","cog"]
    ]

**示例 2:**

输入:
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot","dot","dog","lot","log"]
    
    输出: []
    
    解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

个人感觉这道题是相当有难度的一道题，它比之前那道 [Word Ladder][] 要复杂很多，全场第四低的通过率12.9%正说明了这道题的难度，我也是研究了网上别人的解法很久才看懂，然后照葫芦画瓢的写了出来，下面这种解法的核心思想是BFS，大概思路如下：我们的目的是找出所有的路径，我们建立一个路径集paths，用以保存所有路径，然后是起始路径p，在p中先把起始单词放进去。然后定义两个整型变量level，和minLevel，其中level是记录循环中当前路径的长度，minLevel是记录最短路径的长度，这样的好处是，如果某条路径的长度超过了已有的最短路径的长度，那么舍弃，这样会提高运行速度，相当于一种剪枝。还要定义一个set变量words，用来记录已经循环过的路径中的词，然后就是BFS的核心了，循环路径集paths里的内容，取出队首路径，如果该路径长度大于level，说明字典中的有些词已经存入路径了，如果在路径中重复出现，则肯定不是最短路径，所以我们需要在字典中将这些词删去，然后将words清空，对循环对剪枝处理。然后我们取出当前路径的最后一个词，对每个字母进行替换并在字典中查找是否存在替换后的新词，这个过程在之前那道 [Word Ladder][] 里面也有。如果替换后的新词在字典中存在，将其加入words中，并在原有路径的基础上加上这个新词生成一条新路径，如果这个新词就是结束词，则此新路径为一条完整的路径，加入结果中，并更新minLevel，若不是结束词，解将新路径加入路径集中继续循环。写了这么多，不知道你看晕了没有，还是看代码吧，这个最有效：

![复制代码][copycode.gif]

class Solution {
    public:
        vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
            vector<vector<string>> res;
            unordered_set<string> dict(wordList.begin(), wordList.end());
            vector<string> p{beginWord};
            queue<vector<string>> paths;
            paths.push(p);
            int level = 1, minLevel = INT_MAX;
            unordered_set<string> words;
            while (!paths.empty()) {
                auto t = paths.front(); paths.pop();
                if (t.size() > level) {
                    for (string w : words) dict.erase(w);
                    words.clear();
                    level = t.size();
                    if (level > minLevel) break;
                }
                string last = t.back();
                for (int i = 0; i < last.size(); ++i) {
                    string newLast = last;
                    for (char ch = 'a'; ch <= 'z'; ++ch) {
                        newLast[i] = ch;
                        if (!dict.count(newLast)) continue;
                        words.insert(newLast);
                        vector<string> nextPath = t;
                        nextPath.push_back(newLast);
                        if (newLast == endWord) {
                            res.push_back(nextPath);
                            minLevel = level;
                        } else paths.push(nextPath);
                    }
                }
            }
            return res;
        }
    };

347.[\[LeetCode\] Top K Frequent Elements 前K个高频元素][LeetCode_ Top K Frequent Elements _K]

给定一个非空的整数数组，返回其中出现频率前 ***k*** 高的元素。

**示例 1:**

输入: nums = [1,1,1,2,2,3], k = 2
    输出: [1,2]

**示例 2:**

输入: nums = [1], k = 1
    输出: [1]

**说明：**

*  你可以假设给定的 *k* 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 *  你的算法的时间复杂度**必须**优于 O(*n* log *n*) , *n* 是数组的大小。

这道题给了我们一个数组，让我们统计前k个高频的数字，那么对于这类的统计数字的问题，首先应该考虑用HashMap来做，建立数字和其出现次数的映射，然后再按照出现次数进行排序。我们可以用堆排序来做，使用一个最大堆来按照映射次数从大到小排列，在C++中使用priority\_queue来实现，默认是最大堆，参见代码如下：

解法一：

![复制代码][copycode.gif]

class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> m;
            priority_queue<pair<int, int>> q;
            vector<int> res;
            for (auto a : nums) ++m[a];
            for (auto it : m) q.push({it.second, it.first});
            for (int i = 0; i < k; ++i) {
                res.push_back(q.top().second); q.pop();
            }
            return res;
        }
    };

![复制代码][copycode.gif]

当然，既然可以使用最大堆，还有一种可以自动排序的数据结构TreeMap，也是可以的，这里就不写了，因为跟上面的写法基本没啥区别，就是换了一个数据结构。

我们还可以使用桶排序，在建立好数字和其出现次数的映射后，我们按照其出现次数将数字放到对应的位置中去，这样我们从桶的后面向前面遍历，最先得到的就是出现次数最多的数字，我们找到k个后返回即可，参见代码如下：

解法二：

![复制代码][copycode.gif]

class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> m;
            vector<vector<int>> bucket(nums.size() + 1);
            vector<int> res;
            for (auto a : nums) ++m[a];
            for (auto it : m) {
                bucket[it.second].push_back(it.first);
            }
            for (int i = nums.size(); i >= 0; --i) {
                for (int j = 0; j < bucket[i].size(); ++j) {
                    res.push_back(bucket[i][j]);
                    if (res.size() == k) return res;
                }
            }
            return res;
        }
    };

![复制代码][copycode.gif]

[LeetCode_ Valid Parentheses]: https://www.cnblogs.com/grandyang/p/4424587.html
[copycode.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/6c434b22ef5c4bb7934b94d6e171742b.png
[LeetCode_ Evaluate Reverse Polish Notation]: https://www.cnblogs.com/grandyang/p/4247718.html
[Link 1]: https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437
[Link 2]: http://zh.wikipedia.org/wiki/%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E7%A4%BA%E6%B3%95
[LeetCode_ Simplify Path]: https://www.cnblogs.com/grandyang/p/4347125.html
[Link 3]: http://www.cnblogs.com/grandyang/p/4312273.html
[LeetCode_ Binary Tree Preorder Traversal]: https://www.cnblogs.com/grandyang/p/4146981.html
[Link 4]: http://zh.wikipedia.org/wiki/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86
[LeetCode_ Binary Tree Inorder Traversal]: https://www.cnblogs.com/grandyang/p/4297300.html
[LeetCode_ Binary Tree Postorder Traversal]: https://www.cnblogs.com/grandyang/p/4251757.html
[LeetCode_ Binary Tree Level Order Traversal]: https://www.cnblogs.com/grandyang/p/4051321.html
[LeetCode_ Binary Tree Zigzag Level Order Traversal]: https://www.cnblogs.com/grandyang/p/4297009.html
[LeetCode_ Binary Tree Level Order Traversal 1]: http://www.cnblogs.com/grandyang/p/4051321.html
[LeetCode_ Binary Tree Level Order Traversal II]: https://www.cnblogs.com/grandyang/p/4051326.html
[LeetCode_ Binary Tree Right Side View]: https://www.cnblogs.com/grandyang/p/4392254.html
[LeetCode_ Perfect Squares]: https://www.cnblogs.com/grandyang/p/4800552.html
[LeetCode_ Word Ladder]: https://www.cnblogs.com/grandyang/p/4539768.html
[LeetCode_ Word Ladder II]: https://www.cnblogs.com/grandyang/p/4548184.html
[Word Ladder]: http://www.cnblogs.com/grandyang/p/4539768.html
[LeetCode_ Top K Frequent Elements _K]: https://www.cnblogs.com/grandyang/p/5454125.html