【LeetCode】栈和队列相关问题_取出字符串中的一个字符,分别入栈和入队列-程序员宅基地
栈和队列相关问题
栈的基础应用
20. 有效的括号
题目描述
方法1 基础栈的应用
bool isValid1(string s) {
stack<char> stack1;
for (int i = 0;i < s.size();i++)
{
if (s[i] == '{' || s[i] == '(' || s[i] == '[')
{
stack1.push(s[i]);
}
else
{
assert(s[i] == '}' || s[i] == ')' || s[i] == ']');
if (stack1.empty())return false;//判断栈不为空
char tmp = stack1.top();
stack1.pop();
switch (s[i])
{
case '}':
if (tmp != '{')return false;
case ')':
if (tmp != '(')return false;
case ']':
if (tmp != '[')return false;
}
}
}
if (!stack1.empty())//栈为空
return false;
return true;
}
方法2 将右括号入栈 加速
bool isValid(string s) {
//压入右括号而不是左括号
stack<char> stack1;
for (int i = 0;i < s.size();i++)
{
if (s[i] == '{' || s[i] == '(' || s[i] == '[')
{
switch (s[i])
{
case '{':
stack1.push('}');
break;
case '(':
stack1.push(')');
break;
case '[':
stack1.push(']');
break;
}
}
else
{
assert(s[i] == '{' || s[i] == '(' || s[i] == '[');
if (!stack1.empty()&&stack1.top()==s[i])
stack1.pop();//判断栈不为空
else return false;
//stack1.pop();
}
}
return stack1.empty();
}
150. 逆波兰表达式求值
题目描述
方法1 基础栈的应用 注意负数
bool isoper(string a)//判断是否是运算符
{
if (a.size() == 1 && (a[0] == '+' || a[0] == '-' || a[0] == '*' || a[0] == '/'))
return true;
else
return false;
}
int toint(string a)//转成int 注意i符号
{
int res=0;
int positive=1;
for (int i = 0;i < a.size();i++)
{
if (a[i] == '-')positive = -1;
else
{
res = res * 10 + int(a[i] - '0');
}
}
return positive*res;
}
int evalRPN(vector<string>& tokens) {
if (tokens.size() == 0)return 0;
stack<int> stack1;
int res = 0;
for (int i = 0;i < tokens.size();i++)
{
if (!isoper(tokens[i]))
{
int a = toint(tokens[i]);
stack1.push(a);
}
else
{
assert(stack1.size() > 1);
int rnum = stack1.top();
stack1.pop();
int lnum = stack1.top();
stack1.pop();
//int res;
switch (tokens[i][0])
{
case'+':
res = rnum + lnum;
break;
case'-':
res = lnum - rnum;
break;
case'*':
res = lnum*rnum;
break;
case'/':
res = lnum / rnum;
break;
}
stack1.push(res);
}
}
assert(stack1.size() == 1);
return stack1.top();
}
71. 简化路径
题目描述
方法1 分割时带‘/’一起分割（时间慢）
//分割结果为 所有的字符都分割 没有跳过 / a / . b形式
vector<string> splitstring(string path)
{
vector<string>ret;
int begin = 0;
int i = 0;
while (path[i] != '\0')
{
if (path[i] != '/')i++;
else
{
if (i != begin)
{
ret.push_back(path.substr(begin, i - begin));
}
ret.push_back("/");
begin = i + 1;
i++;
}
}
if (begin != i)//注意字符串最后可能没有/ 要单独处理
{
ret.push_back(path.substr(begin, i - begin));
}
return ret;
}
bool issplit(string s)//是不是分割符
{
return s.size() == 1 && s[0] == '/';
}
bool ispath1(string s)//是不是.
{
return s.size() == 1 && s[0] == '.';
}
bool ispath2(string s)//是不是..回退符
{
return s.size() == 2 && s == "..";
}
string simplifyPath(string path) {
vector<string> splitpath = splitstring(path);
stack<string>ret;
string res;
for (int i = 0;i < splitpath.size();i++)
{
if (issplit(splitpath[i]))
{
if (ret.size() == 0 || !issplit(ret.top()))
ret.push("/");
}
else if (ispath1(splitpath[i]))
{
continue;
}
else if (ispath2(splitpath[i]))
{
assert(issplit(ret.top()));
if (ret.size() == 1)
{
continue;
}
ret.pop();
ret.pop();
}
else
{
ret.push(splitpath[i]);
}
}
if (ret.size() > 1 && issplit(ret.top()))ret.pop();//size>1并且最后一个字符是/ 就弹出
vector<string> rev;//转移到vector 中
while (!ret.empty())
{
rev.push_back(ret.top());
ret.pop();
}
for (int i = rev.size() - 1;i >= 0;i--)
{
res += rev[i];
}
return res;
}
方法2 分割是跳过‘/’ 最后再加入 由于stack是逆序的 换成使用vector容器
vector<string> splitstring(string path)
{
vector<string>ret;
int begin = 0;
int i = 0;
while (path[i] != '\0')
{
if (path[i] != '/')i++;
else
{
if (i != begin)//当两个位置不同时 保证ret中的元素不为空
{
ret.push_back(path.substr(begin, i - begin));
}
//ret.push_back("/"); 跳过/符号
begin = i + 1;
i++;
}
}
if (begin != i)
{
ret.push_back(path.substr(begin, i - begin));
}
return ret;
}
bool ispath1(string s)
{
return s.size() == 1 && s[0] == '.';
}
bool ispath2(string s)
{
return s.size() == 2 && s == "..";
}
string simplifyPath1(string path) {
vector<string> splitpath = splitstring(path);
vector<string>ret;
string res;
for (int i = 0;i < splitpath.size();i++)
{
if (ispath1(splitpath[i]))//.符号 跳过
{
continue;
}
else if (ispath2(splitpath[i]))//是..符号
{
//assert(issplit(ret.top()));
if(ret.size()==0)
{
continue;
}
ret.pop_back();
}
else
{
ret.push_back(splitpath[i]);//是路径
}
}
if (ret.size() == 0)return "/";
for (int i = 0;i < ret.size();i++)
{
res += ("/" + ret[i]);
}
return res;
}
方法3 不使用分割函数 逐个字符比较 末尾补上/
string simplifyPath(string path) {
path+="/";//方便处理末尾没有/的情况
vector<string> ret;
string tmp;
string res;
for (char s : path)
{
if (s == '/')//是分割符
{
if (tmp == ".."&&!ret.empty())//回退
{
ret.pop_back();
}
else if (tmp.size() != 0 && tmp != "."&&tmp!="..")//是路径 要加上不等于..不然可能会加入..
{
ret.push_back(tmp);
}
tmp.clear();//清空
}
else
{
tmp += s;//读取非/的字符
}
}
for (int i = 0;i < ret.size();i++)//输出
{
res += ("/" + ret[i]);
}
if (ret.size() == 0)return"/";
return res;
}
栈和递归的紧密关系
144. 二叉树的前序遍历
题目描述
方法1 递归实现
void preorderTraversal1(TreeNode* root) {
if(root==NULL)
{
return;
}
cout<<root->val;//访问
preorderTraversal1(root->left)；
preorderTraversal1(root->right);
}
方法2 模拟系统栈
按照 右子树 左子树 父节点的顺序入栈
struct Command {
string s;
TreeNode* node;
Command(string s1, TreeNode* node1) :s(s1), node(node1) {
};
};
vector<int> preorderTraversal1(TreeNode* root) {
vector<int> ret;
if (root == NULL)
{
return ret;
}
stack<Command> stack1;
stack1.push("go",root);
while (!stack1.empty())
{
Command tmp = stack1.top();
stack1.pop();
if (tmp.s == "print")
{
ret.push_back(tmp.node->val);
}
else
{
assert(tmp.s == "go");
if (tmp.node->right) {
stack1.push(Command("go", tmp.node->right)); }
if (tmp.node->left) {
stack1.push(Command("go", tmp.node->left)); }
stack1.push(Command("print", tmp.node));
}
}
return ret;
}
方法3 添加空指针表示需要打印
vector<int> preorderTraversal2(TreeNode* root) {
stack<TreeNode*>stack1;
vector<int>ret;
if (root == NULL)
{
return ret;
}
stack1.push(root);
while (!stack1.empty())
{
TreeNode* tmp = stack1.top();
stack1.pop();
if (tmp != NULL)
{
if (tmp->right)stack1.push(tmp->right);
if (tmp->left)stack1.push(tmp->left);
stack1.push(tmp);
stack1.push(NULL);//添加空指针表示这个元素以及访问过
}
else//检测到空指针就输出
{
tmp = stack1.top();
stack1.pop();
ret.push_back(tmp->val);
}
}
return ret;
}
方法4 使用迭代
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*>stack1;
vector<int>ret;
if (root == NULL)
{
return ret;
}
//stack1.push(root);
//ret.push_back(root->val);
TreeNode* tmp = root;
while (!stack1.empty())
{
//TreeNode* tmp = stack1.top();
//ret.push_back(tmp->val);
while (tmp)//从左子树开始 一直入栈
{
stack1.push(tmp);
ret.push_back(tmp->val);//父节点输出
tmp = tmp->left;//左子树入栈
}
tmp = stack1.top();//回退
stack1.pop();
tmp = tmp->right;//访问右子树
}
return ret;
}
94. 二叉树的中序遍历
题目描述
方法1 递归
方法2 模拟系统栈
vector<int> inorderTraversal1(TreeNode* root) {
stack<Command> stack;
vector<int>ret;
if (root == NULL)
{
return ret;
}
stack.push(Command("go", root));
while (!stack.empty())
{
Command tmp = stack.top();
stack.pop();
if (tmp.s == "go")
{
if (tmp.node->right) {
stack.push(Command("go", tmp.node->right)); }
stack.push(Command("print", tmp.node));
if (tmp.node->left) {
stack.push(Command("go", tmp.node->left); }
}
else
{
ret.push_back(tmp.node->val);
}
}
return ret;
}
方法3 将空指针入栈表示需要输出
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> stack;
vector<int>ret;
if (root == NULL)return ret;
stack.push(root);
while (!stack.empty())
{
TreeNode* tmp = stack.top();
stack.pop();
if (tmp != NULL)
{
if (tmp->right != NULL) stack.push(tmp->right);
stack.push(tmp);
stack.push(NULL);
if (tmp->left != NULL)stack.push(tmp->left);
}
else
{
tmp = stack.top();
stack.pop();
ret.push_back(tmp->val);
}
}
return ret;
}
方法4 使用迭代 找最左子树
vector<int> inorderTraversal2(TreeNode* root) {
stack<TreeNode*> stack;
vector<int>ret;
TreeNode* tmp = root;
//stack.push(root);
while (!stack.empty()||tmp)
{
while (tmp != NULL)
{
stack.push(tmp);
tmp = tmp->left;//左子树一直入栈
//前序遍历这里输出
}
tmp = stack.top();//回退
ret.push_back(tmp->val);//输出
stack.pop();
tmp = tmp->right;//访问右子树
}
return ret;
}
145. 二叉树的后序遍历
题目描述
方法1 递归
方法2 模拟系统栈
方法3 空指针入栈表示输出
（和前面方法一样 省略）
方法4 迭代（增加pre表示前驱节点） 困难
vector<int> postorderTraversal(TreeNode* root) {
//非常难想
stack<TreeNode*>stack;
vector<int>ret;
TreeNode*tmp = root;
TreeNode*pre = NULL;
while (!stack.empty() || tmp)
{
while (tmp != NULL)
{
stack.push(tmp);//入栈
ret.push_back(tmp->val);
tmp = tmp->left;
}
tmp = stack.top();//回退
if (tmp->right == NULL || tmp->right == pre)//右子树为空或者已经访问 说明右子树访问完毕 就访问当前根节点
{
stack.pop();
ret.push_back(tmp->val);
pre = tmp;
tmp = NULL;
}
else//右子树还没有访问 就访问右子树
{
tmp = tmp->right;
}
}
return ret;
}
方法5 迭代 根 右 左 的顺序访问 再反转（特殊方法）
类似前序遍历
vector<int> postorderTraversal1(TreeNode* root) {
//根 右 左遍历再反转
stack<TreeNode*>stack;
vector<int>ret;
TreeNode*tmp = root;
while (!stack.empty || tmp)
{
while (tmp != NULL)
{
stack.push(tmp);
tmp = tmp->right;
ret.push_back(tmp->val);
}
tmp = stack.top();
stack.pop();
tmp = tmp->left;
}
reverse(ret.begin(), ret.end());
return ret;
}
341. 扁平化嵌套列表迭代器
题目描述
题目理解
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* class NestedInteger {
* public:
* // Return true if this NestedInteger holds a single integer, rather than a nested list.
* bool isInteger() const;
*
* // Return the single integer that this NestedInteger holds, if it holds a single integer
* // The result is undefined if this NestedInteger holds a nested list
* int getInteger() const;
*
* // Return the nested list that this NestedInteger holds, if it holds a nested list
* // The result is undefined if this NestedInteger holds a single integer
* const vector<NestedInteger> &getList() const;
* };
*/
//=========可以调用的函数========
class NestedInteger {
bool isInteger() const;//是否是一个整型变量
int getInteger() const;//是整型变量的话返回整型变量的值
const vector<NestedInteger> &getList() const;//是列表的话 返回列表
}
方法1 使用栈模拟 在hasNext时进行展开
class NestedIterator {
private:
stack<NestedInteger> st;
public:
NestedIterator(vector<NestedInteger> &nestedList) {
//逆序入栈
for (auto iter = nestedList.rbegin(); iter != nestedList.rend(); iter++) {
st.push(*iter);
}
}
int next() {
auto t = st.top();
st.pop();
return t.getInteger();
}
bool hasNext() {
while (!st.empty()) {
auto cur = st.top();
if (cur.isInteger()) return true;//是整型变量 就返回true
st.pop();
auto curList = cur.getList();//是列表的话 返回列表
for (auto iter = curList.rbegin(); iter != curList.rend(); iter++) {
st.push(*iter);//列表元素入栈
}
}
return false;
}
};
方法2 在构造函数全都展开
class NestedIterator {
stack<NestedInteger> st;//设置公有成员变量
public:
NestedIterator(vector<NestedInteger> &nestedList) {
for (auto iter = nestedList.rbegin();iter != nestedList.rend();iter++)
{
indata(*iter);
}
}
void indata(NestedInteger &nestedList)//递归调用该函数
{
if (nestedList.isInteger())
{
st.push(nestedList);
return;
}
else
{
vector<NestedInteger> tmplist = nestedList.getList();
for (auto iter = tmplist.rbegin();iter != tmplist.rend();iter++)
{
indata(*iter);
}
}
}
int next() {
auto ret = st.top();
st.pop();
return ret.getInteger();
}
bool hasNext() {
return !st.empty();
}
};
队列的典型应用
102. 二叉树的层序遍历
题目描述
方法1 使用队列 队列为节点和层数组成的pair
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ret;
deque<pair<TreeNode*, int>> q;
if (root == NULL)return ret;
q.push_back(make_pair(root, 0));
while (!q.empty())
{
pair<TreeNode*, int>tmp = q.front();
q.pop_front();
TreeNode* tmpnode = tmp.first;
int tmplevel = tmp.second;
if (tmplevel == ret.size())//该层第一个元素
{
ret.push_back(vector<int>());//增加新vector
}
ret[tmplevel].push_back(tmpnode->val);
if (tmpnode->left)(q.push_back(make_pair(tmpnode->left, tmplevel + 1)));
if (tmpnode->right)(q.push_back(make_pair(tmpnode->right, tmplevel + 1)));
}
reverse(ret.begin(), ret.end());
return ret;
}
方法2 每次只遍历队列尺寸大小的元素 不用记录层数
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ret;
deque<TreeNode*> q;
if (root == NULL)return ret;
q.push_back(root);
//bool odd = true;
while(!q.empty())
{
int size = q.size();
vector<int> tmpvec;//临时vector 保存该层的结果
for (int i = 0;i<size;i++)
{
TreeNode* tmp = q.front();
q.pop_front();
//TreeNode* tmpnode=tmp.first;
tmpvec.push_back(tmp->val);
// ret[tmplevel].push_back(tmpnode->val);
if (tmp->left)q.push_back(tmp->left);
if (tmp->right)q.push_back(tmp->right);
}
ret.push_back(tmpvec);
}
return ret;
}
107. 二叉树的层次遍历 II
题目描述
方法1 正常遍历之后逆序
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> ret;
deque<pair<TreeNode*, int>> q;
if (root == NULL)return ret;
q.push_back(make_pair(root, 0));
while (!q.empty())
{
pair<TreeNode*, int>tmp = q.front();
q.pop_front();
TreeNode* tmpnode = tmp.first;
int tmplevel = tmp.second;
if (tmplevel == ret.size())
{
ret.push_back(vector<int>());//增加新vector
}
ret[tmplevel].push_back(tmpnode->val);
if (tmpnode->left)(q.push_back(make_pair(tmpnode->left, tmplevel + 1)));
if (tmpnode->right)(q.push_back(make_pair(tmpnode->right, tmplevel + 1)));
}
reverse(ret.begin(), ret.end());
return ret;
}
方法2 先求出树的高度 倒着装n-depth
vector<vector<int>> levelOrderBottom(TreeNode* root) {
int n = getDep(root);
vector<vector<int>> ans(n, vector<int>());
dfs(root, 0, ans, n - 1);
return ans;
}
void dfs(TreeNode *root, int depth, vector<vector<int>>& ans, int n) {
if (root == NULL) return ;
ans[n - depth].push_back(root->val); // 倒着装 n - depth
dfs(root->left, depth + 1, ans, n);
dfs(root->right, depth + 1, ans, n);
}
int getDep(TreeNode *root) {
// 求树的高度
if (root == NULL) return 0;
return max(getDep(root->left), getDep(root->right)) + 1;
}
103. 二叉树的锯齿形层次遍历
题目描述
方法1 根据层数的奇偶性 先进先出 后进后出 （使用piar记录层数）
栈中一直是顺序储存 只不过取出的方式不一样
vector<vector<int>> zigzagLevelOrder1(TreeNode* root) {
vector<vector<int>> ret;
deque<pair<TreeNode*, int>> q;
if (root == NULL)return ret;
q.push_back(make_pair(root, 0));
bool odd = true;
while (!q.empty())
{
int size = q.size();
if (odd)
{
for (int i = 0;i<size;i++)
{
pair<TreeNode*, int>tmp = q.front();
q.pop_front();
TreeNode* tmpnode = tmp.first;
int tmplevel = tmp.second;
if (tmplevel == ret.size())
{
ret.push_back(vector<int>());
}
ret[tmplevel].push_back(tmpnode->val);
if (tmpnode->left)q.push_back(make_pair(tmpnode->left, tmplevel + 1));
if (tmpnode->right)q.push_back(make_pair(tmpnode->right, tmplevel + 1));
}
}
else
{
for (int i = 0;i<size;i++)
{
pair<TreeNode*, int>tmp = q.back();
q.pop_back();
TreeNode* tmpnode = tmp.first;
int tmplevel = tmp.second;
if (tmplevel == ret.size())
{
ret.push_back(vector<int>());
}
ret[tmplevel].push_back(tmpnode->val);
if (tmpnode->right)q.push_front(make_pair(tmpnode->right, tmplevel + 1));
if (tmpnode->left)q.push_front(make_pair(tmpnode->left, tmplevel + 1));
}
}
odd = !odd;
}
return ret;
}
方法2 每次遍历当前队列尺寸的元素 使用子vector记录临时返回值
```cpp
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;
deque<TreeNode*> q;
if (root == NULL)return ret;
q.push_back(root);
bool odd = true;
while (!q.empty())
{
int size = q.size();
vector<int> tmpvec;
if (odd)
{
for (int i = 0;i<size;i++)
{
TreeNode* tmp = q.front();
q.pop_front();
//TreeNode* tmpnode=tmp.first;
tmpvec.push_back(tmp->val);
// ret[tmplevel].push_back(tmpnode->val);
if (tmp->left)q.push_back(tmp->left);
if (tmp->right)q.push_back(tmp->right);
}
}
else
{
for (int i = 0;i<size;i++)
{
TreeNode* tmp = q.back();
q.pop_back();
//TreeNode* tmpnode=tmp.first;
tmpvec.push_back(tmp->val);
//ret[tmplevel].push_back(tmpnode->val);
if (tmp->right)q.push_front(tmp->right);
if (tmp->left)q.push_front(tmp->left);
}
}
ret.push_back(tmpvec);
odd = !odd;
}
return ret;
}
199. 二叉树的右视图
题目描述
方法1 使用广度优先搜索 记录最右边的值
vector<int> rightSideView1(TreeNode* root) {
vector<int>ret;
deque<TreeNode*> q;
if (root == NULL)
{
return ret;
}
q.push_back(root);
while (!q.empty())
{
int size = q.size();
for (int i = 0;i<size;i++)
{
TreeNode* tmp = q.front();
q.pop_front();
if (i == size - 1)//最右边的值
{
ret.push_back(tmp->val);
}
if (tmp->left)q.push_back(tmp->left);
if (tmp->right)q.push_back(tmp->right);
}
}
return ret;
}
方法2 使用深度优先搜索 先遍历右子树 当出现新的层时 就是最右边的子树
void order(TreeNode* root, int high, vector<int>&ret)
{
if (root == NULL)return;
if (high == ret.size())
{
ret.push_back(root->val);
}
order(root->right, high + 1, ret);
order(root->left, high + 1, ret);
}
vector<int> rightSideView(TreeNode* root) {
//深度优先
vector<int>ret;
order(root, 0, ret);
return ret;
}
BFS和图的最短路径
279. 完全平方数
题目描述
方法1 使用栈进行BFS
int numSquares(int n) {
deque<pair<int, int>> d;
d.push_back(make_pair(n, 0));
vector<bool> visited(n + 1);//为了避免重复添加元素 添加visted数组
for (auto i : visited)
{
i = false;
}
while (!d.empty())
{
pair<int, int>tmp = d.front();
int tmpvalue = tmp.first;
int step = tmp.second;
d.pop_front();
if (tmpvalue == 0)
{
return step;
}
for (int i = 1;tmpvalue - i*i>=0;i++)
{
if (visited[tmpvalue - i*i] == false)
{
d.push_back(make_pair(tmpvalue - i*i, step + 1));
visited[tmpvalue - i*i] = true;
}
}
}
return 0;
}
方法2 一些优化
int numSquares1(int n) {
deque<pair<int, int>> d;
d.push_back(make_pair(n, 0));
vector<bool> visited(n + 1);
for (auto i : visited)
{
i = false;
}
while (!d.empty())
{
pair<int, int>tmp = d.front();
int tmpvalue = tmp.first;
int step = tmp.second;
d.pop_front();
if (tmpvalue == 0)
{
return step;
}
for (int i = 1;;i++)
{
int res = tmpvalue - i*i;//优化 用res代替tmpvalue-i*i 减少计算 并且提前返回
if (res<0)break;
if (res == 0)return step + 1;//提前返回
if (visited[res] == false)
{
d.push_back(make_pair(res, step + 1));
visited[res] = true;
}
}
}
return 0;
}
方法3 动态规划
int numSquares(int n) {
vector<int> nres(n+1, 0x7FFFFFFF);//初始值设置为最大整数
nres[0]=0;
for(int i=0;i<n+1;i++)
{
for(int j=1;;j++)
{
int tmp=i-j*j;
if(tmp<0)break;
nres[i]=min(nres[i],nres[tmp]+1);//从小到大记录每个数的最小值
}
}
return nres[n];
}
127. 单词接龙
题目描述
方法1 BFS暴力搜索 列表中的每个字符串都进行判断（超时）
bool match(string a, string b)
{
int dif = 0;
for (int i = 0;i < a.size();i++)
{
if (dif > 1) return false;
if (a[i] != b[i])dif++;
}
if (dif == 1)return true;
return false;
}
int ladderLength1(string beginWord, string endWord, vector<string>& wordList) {
int word_size = beginWord.size();
int list_size = wordList.size();
vector<bool> visited(list_size + 1, false);
deque<pair<string, int>> q;
q.push_back(make_pair(beginWord, 0));
while (!q.empty())
{
pair<string, int>tmp = q.front();
q.pop_front();
string tmpstring = tmp.first;
int path = tmp.second;
for (int i = 0;i < list_size;i++)
{
if (tmpstring == endWord)
return path + 1;
if (!visited[i])
{
if (match(tmpstring, wordList[i]))
{
q.push_back(make_pair(wordList[i], path + 1));
visited[i] = true;
}
}
}
}
return 0;
}
方法2 vector转为set 搜索当前字符串换一个字符是否存在
按个遍历当前单词的每个字母，然后对他进行替换’a’-‘z’，如果单词替换之后，能够在我们的节点中找到下一个词，那么就将哪个词加入队列中，同时把该节点移除候选节点。
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> s;
for (auto &i : wordList) s.insert(i);
int word_size=beginWord.size();
int list_size = wordList.size();
//vector<bool> visited(list_size + 1, false);
deque<pair<string, int>> q;
q.push_back(make_pair(beginWord,0));
while (!q.empty())
{
list_size = s.size();
pair<string, int>tmp = q.front();
q.pop_front();
string tmpstring = tmp.first;
int path = tmp.second;
for (int i = 0;i < word_size;i++)
{
char ch = tmpstring[i];
for (char c = 'a';c <= 'z';c++)//更换一个字符是否存在
{
if (ch == c)continue;
tmpstring[i] = c;
if (s.find(tmpstring) != s.end())
{
if (tmpstring == endWord)
return path + 2;
q.push_back(make_pair(tmpstring, path+1));
s.erase(tmpstring);
}
tmpstring[i] = ch;
}
}
}
return 0;
}
方法3 使用vector储存每一层 而不是使用队列
int ladderLength2(string beginWord, string endWord, vector<string>& wordList) {
int word_size = wordList[0].length(), list_size = wordList.size();
// 构建 转换树，某个结点的孩子结点为一个集合，包含了所有能够进行一次转换得到的有效单词。
// 按层从beginWord开始构建多叉树，直到遇到endWord，此时的层高+1即为最短路径。
vector<set<string>> levels(list_size + 1, set<string>()); //树最高不超过字典长度
vector<int> flags(list_size, 0);// 标记数组，用于标记哪些单词已经被 选择
levels[0].insert(beginWord);
for (int i = 0; i < levels.size(); i++) {
// 尝试添加下一层的有效单词
for (auto it = levels[i].begin(); it != levels[i].end(); it++) {
// 遍历当前层的每一个单词
// 从字典中选择能够进行一次字母转换，而得到的单词
for (int k = 0; k < list_size; k++) {
if (flags[k] == 1) continue;
int l = 0, cnt = 0;
while (l < word_size && cnt <= 1) {
//判断几个字符不同
if ((*it)[l] != wordList[k][l]) cnt++;
l++;
}
if (cnt == 1) {
flags[k] = 1;
levels[i + 1].insert(wordList[k]);
// 此时，得到最小层数，直接return
if (wordList[k] == endWord)
{
return i + 2;
}
}
}
}
}
return 0;
}
126. 单词接龙 II
题目描述
方法1 太难了 我不会
优先队列相关问题
347. 前 K 个高频元素
题目描述
方法1 统计词频后排序
方法2 使用最小堆 nlogk的复杂度
vector<int> topKFrequent1(vector<int>& nums, int k) {
unordered_map<int, int> freq;
for (int i = 0;i<nums.size();i++)
{
freq[nums[i]]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > dq;
for (unordered_map<int, int>::iterator iter = freq.begin();iter != freq.end();iter++) //使用迭代器遍历
{
if (dq.size() == k)
{
if (iter->second>dq.top().first)
{
dq.pop();
dq.push(make_pair(iter->second, iter->first));
}
}
else
{
dq.push(make_pair(iter->second, iter->first));
}
}
vector<int>ret;
while (!dq.empty())
{
ret.push_back(dq.top().second);
dq.pop();
}
return ret;
}
方法2 最大堆 统计前n-k个低频元素
vector<int> topKFrequent(vector<int>& nums, int k) {
//priority_queue <int> i;
unordered_map<int, int> freq;
vector<int>ret;
if (nums.size() == k)return nums;
for (int i = 0;i<nums.size();i++)
{
freq[nums[i]]++;
}
//cout<<"sdf"<<endl;
// return nums;
priority_queue<pair<int, int>> dq;
int size = freq.size() - k;
if (size == 0)
{
for (unordered_map<int, int>::iterator iter = freq.begin();iter != freq.end();iter++)
{
ret.push_back(iter->first);
}
return ret;
}
//cout<<size<<endl;
for (unordered_map<int, int>::iterator iter = freq.begin();iter != freq.end();iter++) //使用迭代器遍历
{
// cout<<iter->first<<size<<endl;
if (dq.size() == size)
{
//cout<<iter->second<<" sdf"<<dq.top().first<<endl;
if (iter->second<dq.top().first)//比队列中的元素小 就添加队列中的最大值
{
ret.push_back(dq.top().second);
//cout<<ret[0]<<endl;
dq.pop();
dq.push(make_pair(iter->second, iter->first));
}
else
{
ret.push_back(iter->first);//不然就添加自己
}
}
else
{
dq.push(make_pair(iter->second, iter->first));
//cout<<dq.top().first<<endl;
}
}
return ret;
}
23. 合并K个排序链表
题目描述
方法1 优先队列
存入的是第几个链表和头节点的值 也有直接存入节点的
ListNode* mergeKLists(vector<ListNode*>& lists) {
//使用优先队列 //还有分治法和两两合并的方法 没写
ListNode* dummyhead = new ListNode(-1);
ListNode* tmp = dummyhead;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> >dq;
for (int i = 0;i<lists.size();i++)
{
if (lists[i] == NULL)continue;
dq.push(make_pair(lists[i]->val, i));
}
while (!dq.empty())
{
pair<int, int>tmp1 = dq.top();
dq.pop();
int tmpnum = tmp1.second;
tmp->next = lists[tmpnum];
tmp = tmp->next;
if (lists[tmpnum]->next)
{
lists[tmpnum] = lists[tmpnum]->next;
dq.push(make_pair(lists[tmpnum]->val, tmpnum));
}
}
return dummyhead->next;
}
方法2 分治法（别人写的 有空看）
class Solution {
public:
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}
ListNode* merge(vector <ListNode*> &lists, int l, int r) {
if (l == r) return lists[l];
if (l > r) return nullptr;
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
};
方法3 两两合并（别人写的 有空看）
class Solution {
public:
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *ans = nullptr;
for (size_t i = 0; i < lists.size(); ++i) {
ans = mergeTwoLists(ans, lists[i]);
}
return ans;
}
};
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
智能推荐
oracle 12c 集群安装后的检查_12c查看crs状态-程序员宅基地
文章浏览阅读1.6k次。安装配置gi、安装数据库软件、dbca建库见下：http://blog.csdn.net/kadwf123/article/details/784299611、检查集群节点及状态：[root@rac2 ~]# olsnodes -srac1 Activerac2 Activerac3 Activerac4 Active[root@rac2 ~]_12c查看crs状态
解决jupyter notebook无法找到虚拟环境的问题_jupyter没有pytorch环境-程序员宅基地
文章浏览阅读1.3w次，点赞45次，收藏99次。我个人用的是anaconda3的一个python集成环境，自带jupyter notebook，但在我打开jupyter notebook界面后，却找不到对应的虚拟环境，原来是jupyter notebook只是通用于下载anaconda时自带的环境，其他环境要想使用必须手动下载一些库：1.首先进入到自己创建的虚拟环境(pytorch是虚拟环境的名字)activate pytorch2.在该环境下下载这个库conda install ipykernelconda install nb__jupyter没有pytorch环境
国内安装scoop的保姆教程_scoop-cn-程序员宅基地
文章浏览阅读5.2k次，点赞19次，收藏28次。选择scoop纯属意外，也是无奈，因为电脑用户被锁了管理员权限，所有exe安装程序都无法安装，只可以用绿色软件，最后被我发现scoop，省去了到处下载XXX绿色版的烦恼，当然scoop里需要管理员权限的软件也跟我无缘了（譬如everything）。推荐添加dorado这个bucket镜像，里面很多中文软件，但是部分国外的软件下载地址在github，可能无法下载。以上两个是官方bucket的国内镜像，所有软件建议优先从这里下载。上面可以看到很多bucket以及软件数。如果官网登陆不了可以试一下以下方式。_scoop-cn
Element ui colorpicker在Vue中的使用_vue el-color-picker-程序员宅基地
文章浏览阅读4.5k次，点赞2次，收藏3次。首先要有一个color-picker组件 <el-color-picker v-model="headcolor"></el-color-picker>在data里面data() { return {headcolor: ’ #278add ’ //这里可以选择一个默认的颜色} }然后在你想要改变颜色的地方用v-bind绑定就好了，例如：这里的:sty..._vue el-color-picker
迅为iTOP-4412精英版之烧写内核移植后的镜像_exynos 4412 刷机-程序员宅基地
文章浏览阅读640次。基于芯片日益增长的问题，所以内核开发者们引入了新的方法，就是在内核中只保留函数，而数据则不包含，由用户（应用程序员）自己把数据按照规定的格式编写，并放在约定的地方，为了不占用过多的内存，还要求数据以根精简的方式编写。boot启动时，传参给内核，告诉内核设备树文件和kernel的位置，内核启动时根据地址去找到设备树文件，再利用专用的编译器去反编译dtb文件，将dtb还原成数据结构，以供驱动的函数去调用。firmware是三星的一个固件的设备信息，因为找不到固件，所以内核启动不成功。_exynos 4412 刷机
Linux系统配置jdk_linux配置jdk-程序员宅基地
文章浏览阅读2w次，点赞24次，收藏42次。Linux系统配置jdkLinux学习教程，Linux入门教程（超详细）_linux配置jdk
随便推点
matlab(4)：特殊符号的输入_matlab微米怎么输入-程序员宅基地
文章浏览阅读3.3k次，点赞5次，收藏19次。xlabel('\delta');ylabel('AUC');具体符号的对照表参照下图：_matlab微米怎么输入
C语言程序设计-文件(打开与关闭、顺序、二进制读写)-程序员宅基地
文章浏览阅读119次。顺序读写指的是按照文件中数据的顺序进行读取或写入。对于文本文件，可以使用fgets、fputs、fscanf、fprintf等函数进行顺序读写。在C语言中，对文件的操作通常涉及文件的打开、读写以及关闭。文件的打开使用fopen函数，而关闭则使用fclose函数。在C语言中，可以使用fread和fwrite函数进行二进制读写。 Biaoge 于2024-03-09 23:51发布 阅读量：7 ️文章类型：【 C语言程序设计 】在C语言中，用于打开文件的函数是____，用于关闭文件的函数是____。
Touchdesigner自学笔记之三_touchdesigner怎么让一个模型跟着鼠标移动-程序员宅基地
文章浏览阅读3.4k次，点赞2次，收藏13次。跟随鼠标移动的粒子以grid（SOP）为partical（SOP）的资源模板，调整后连接【Geo组合+point spirit（MAT)】，在连接【feedback组合】适当调整。影响粒子动态的节点【metaball(SOP)+force(SOP)】添加mouse in（CHOP)鼠标位置到metaball的坐标，实现鼠标影响。..._touchdesigner怎么让一个模型跟着鼠标移动
【附源码】基于java的校园停车场管理系统的设计与实现61m0e9计算机毕设SSM_基于java技术的停车场管理系统实现与设计-程序员宅基地
文章浏览阅读178次。项目运行环境配置：Jdk1.8 + Tomcat7.0 + Mysql + HBuilderX（Webstorm也行）+ Eclispe（IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持）。项目技术：Springboot + mybatis + Maven +mysql5.7或8.0+html+css+js等等组成，B/S模式 + Maven管理等等。环境需要1.运行环境：最好是java jdk 1.8，我们在这个平台上运行的。其他版本理论上也可以。_基于java技术的停车场管理系统实现与设计
Android系统播放器MediaPlayer源码分析_android多媒体播放源码分析 时序图-程序员宅基地
文章浏览阅读3.5k次。前言对于MediaPlayer播放器的源码分析内容相对来说比较多，会从Java-&amp;gt;Jni-&amp;gt;C/C++慢慢分析，后面会慢慢更新。另外，博客只作为自己学习记录的一种方式，对于其他的不过多的评论。MediaPlayerDemopublic class MainActivity extends AppCompatActivity implements SurfaceHolder.Cal..._android多媒体播放源码分析 时序图
java 数据结构与算法 ——快速排序法-程序员宅基地
文章浏览阅读2.4k次，点赞41次，收藏13次。java 数据结构与算法 ——快速排序法_快速排序法