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;
}
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();
}
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();
}
//分割结果为 所有的字符都分割 没有跳过 / 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;
}
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;
}
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;
}
void preorderTraversal1(TreeNode* root) {
if(root==NULL)
{
return;
}
cout<<root->val;//访问
preorderTraversal1(root->left);
preorderTraversal1(root->right);
}
按照 右子树 左子树 父节点的顺序入栈
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
(和前面方法一样 省略)
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;
}
类似前序遍历
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;
}
/**
* // 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;//是列表的话 返回列表
}
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;
}
};
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();
}
};
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;
}
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;
}
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;
}
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;
}
栈中一直是顺序储存 只不过取出的方式不一样
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;
}
```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;
}
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;
}
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;
}
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;
}
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;
}
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];
}
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;
}
按个遍历当前单词的每个字母,然后对他进行替换’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;
}
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;
}
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;
}
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;
}
存入的是第几个链表和头节点的值 也有直接存入节点的
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;
}
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);
}
};
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;
}
};
文章浏览阅读2.9k次,点赞8次,收藏14次。测试主要做什么?这完全都体现在测试流程中,同时测试流程是面试问题中出现频率最高的,这不仅是因为测试流程很重要,而是在面试过程中这短短的半小时到一个小时的时间,通过测试流程就可以判断出应聘者是否合适,故在测试流程中包含了测试工作的核心内容,例如需求分析,测试用例的设计,测试执行,缺陷等重要的过程。..._测试过程管理中包含哪些过程
文章浏览阅读870次,点赞16次,收藏19次。1.背景介绍政府数字化政务是指政府利用数字技术、互联网、大数据、人工智能等新技术手段,对政府政务进行数字化改革,提高政府工作效率,提升政府服务质量的过程。随着人工智能(AI)和机器学习(ML)技术的快速发展,政府数字化政务中的人工智能与机器学习应用也逐渐成为政府改革的重要内容。政府数字化政务的人工智能与机器学习应用涉及多个领域,包括政策决策、政府服务、公共安全、社会治理等。在这些领域,人工...
文章浏览阅读219次,点赞2次,收藏4次。系统主要的用户为用户、管理员,他们的具体权限如下:用户:用户登录后可以对管理员上传的学习视频进行学习。用户可以选择题型进行练习。用户选择小程序提供的考研科目进行相关训练。用户可以进行水平测试,并且查看相关成绩用户可以进行错题集的整理管理员:管理员登录后可管理个人基本信息管理员登录后可管理个人基本信息管理员可以上传、发布考研的相关例题及其分析,并对题型进行管理管理员可以进行查看、搜索考研题目及错题情况。_mysql刷题软件
文章浏览阅读1.4k次。myelipse里有UML1和UML2两种方式,UML2功能更强大,但是两者生成过程差别不大1.建立Test工程,如下图,uml包存放uml类图package com.zz.domain;public class User {private int id;private String name;public int getId() {return id;}public void setId(int..._根据以下java代码画出类图
文章浏览阅读174次。需求:一个topic包含很多个表信息,需要自动根据json字符串中的字段来写入到hive不同的表对应的路径中。发送到Kafka中的数据原本最外层原本没有pkDay和project,只有data和name。因为担心data里面会空值,所以根同事商量,让他们在最外层添加了project和pkDay字段。pkDay字段用于表的自动分区,proejct和name合起来用于自动拼接hive表的名称为 ..._flume拦截器自定义开发 kafka
文章浏览阅读380次。原标题:Java Spring中同时访问多种不同数据库 多样的工作要求,可以使用不同的工作方法,只要能获得结果,就不会徒劳。开发企业应用时我们常常遇到要同时访问多种不同数据库的问题,有时是必须把数据归档到某种数据仓库中,有时是要把数据变更推送到第三方数据库中。使用Spring框架时,使用单一数据库是非常容易的,但如果要同时访问多个数据库的话事件就变得复杂多了。本文以在Spring框架下开发一个Sp..._根据输入的不同连接不同的数据库
文章浏览阅读3.6k次,点赞9次,收藏25次。本案例描述了晶振屏蔽以及开关电源变压器屏蔽对系统稳定工作的影响, 硬件设计时应考虑。_eft电路图
文章浏览阅读1.1k次。对于物料价格的更改,可以采取不同的手段:首先,我们来介绍MR21的方式。 需要说明的是,如果要对某一产品进行价格修改,必须满足的前提条件是: ■ 1、必须对价格生效的物料期间与对应会计期间进行开启; ■ 2、该产品在该物料期间未发生物料移动。执行MR21,例如更改物料1180051689的价格为20000元,系统提示“对于物料1180051689 存在一个当前或未来标准价格”,这是因为已经对该..._mr21 对于物料 zba89121 存在一个当前或未来标准价格
文章浏览阅读7.4k次,点赞3次,收藏13次。[文章导读]联想启天M420是一款商用台式电脑,预装的是win10系统,用户还是喜欢win7系统,该台式机采用的intel 8代i5 8500CPU,在安装安装win7时有很多问题,在安装win7时要在BIOS中“关闭安全启动”和“开启兼容模式”,并且安装过程中usb不能使用,要采用联想win7新机型安装,且默认采用的uefi+gpt模式,要改成legacy+mbr引导,那么联想启天M420台式电..._启天m420刷bios
文章浏览阅读2.7k次,点赞2次,收藏9次。一,为什么要冗余数据互联网数据量很大的业务场景,往往数据库需要进行水平切分来降低单库数据量。水平切分会有一个patition key,通过patition key的查询能..._保证冗余性
文章浏览阅读88次。是时候闭环Java应用了 原创 2016-08-16 张开涛 你曾经因为部署/上线而痛苦吗?你曾经因为要去运维那改配置而烦恼吗?在我接触过的一些部署/上线方式中,曾碰到过以下一些问题:1、程序代码和依赖都是人工上传到服务器,不是通过工具进行部署和发布;2、目录结构没有规范,jar启动时通过-classpath任意指定;3、fat jar,把程序代码、配置文件和依赖jar都打包到一个jar中,改配置..._那么需要把上面的defaultjavatyperesolver类打包到插件中
文章浏览阅读909次。1.得下载一个番茄插件,按alt+g才可以有函数跳转功能。2.不安装番茄插件,按F12也可以有跳转功能。3.进公司的VS工程是D:\sync\build\win路径,.sln才是打开工程的方式,一个是VS2005打开的,一个是VS2013打开的。4.公司库里的线程接口,在CmThreadManager.h 里,这个里面是我们的线程库,可以直接拿来用。CreateUserTaskThre..._番茄助手颜色