/*问题 1
输入：s = "3[a]2[bc]"
输出："aaabcbc"
*/
void reserve(string& s) {
int len = s.size();
int i = 0, j = len - 1;
while (i < j) {
swap(s[i++], s[j--]);
}
}
string decodeString(string s) {
int len = s.size();
if (len <= 2) return s; // 3[] [] ab a
string ret;
stack st;
int num = 0;
for (int i = 0; i < len; ++i) {
if (s[i] != ']') {
st.push(s[i]);
}
else {
string dst;
string str;
string num_str;
char top ;
char n = st.top();
while (!st.empty()) {// 读取字符串 如 cb
top = st.top();
if (top == '[') break;
str.append(1, top);
st.pop();
}
st.pop(); // '[' 出栈
// 读取整数 如 21
while (!st.empty()) {
n = st.top();
if (n < '0' || n > '9') break;
num_str.append(1, n);
st.pop();
}
// 数字和字符串 翻转
reserve(str); reserve(num_str);
num = atoi(num_str.c_str());
for (int x = 0; x < num; ++x) {// num = 2 str=bc
dst = dst + str;// acc accacc
}// str = bcbc
int lenth = dst.size();
for (int x = 0; x < lenth; ++x) {// 在一次入栈
st.push(dst[x]);
}
}
}
while (!st.empty()) {
ret.append(1, st.top());
st.pop();
}
reserve(ret);
return ret;
}
/*问题 2
给你一个二叉树的根节点 root ， 检查它是否轴对称
*/
bool isS(TreeNode* left, TreeNode* right) {
if (!left && !right) return true;
if (!left || !right || left->val != right->val) {
return false;
}
return isS(left->right, right->left) && isS(left->left, right->right);
}
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return isS(root->left, root->right);
}
/*问题 3
* 给定一个二叉树，判断它是否是高度平衡的二叉树。
*/
int height(TreeNode* root) {
if (!root) return 0;
return max(height(root->left), height(root->right)) + 1;
}
bool isBalanced(TreeNode* root) {
if (!root) return true;
// 先判断子树是否是
int l_height = height(root->left);
int r_height = height(root->right);
if (abs(l_height - r_height) > 1) return false;
return isBalanced(root->left) && isBalanced(root->right);
}
/*问题 4
* 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
*/
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr;
invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);
return root;
}
/*问题5
手撕完全二叉树
通过1 2 3 4 5 6 构造一颗完全二叉树非数组形式
*/
void dfs(const vector& arr, int start, int len, TreeNode* node) {
if (start == len / 2) {
return;
}
else {
if (start * 2 + 1 < len) node->left = new TreeNode(arr[start * 2 + 1]);
if (start * 2 + 2 < len) node->right = new TreeNode(arr[start * 2 + 2]);
if(node->left) dfs(arr, start * 2 + 1, len, node->left);
if(node->right) dfs(arr, start * 2 + 2, len, node->right);
}
}
Tree* create_tree(const vector& arr) {
int len = arr.size();
if (len == 0) return nullptr;
if (len == 1) return new TreeNode(arr[0]);
TreeNode* node = new TreeNode(arr[0]);
dfs(arr, 0, len, node);
return node;
}
/*问题6
树的Z字形打印 递归方式
*/
void dfs(Tree* root, int flg) {
if (!root) return;
if (flg % 2 == 0) {// 顺序
if (root->left) cout << root->left->val << " ";
if (root->right) cout << root->right->val << " ";
}
else {// 逆序
if (root->right) cout << root->right->val << " ";
if (root->left) cout << root->left->val << " ";
}
dfs(root->left, flg + 1);
dfs(root->right, flg + 1);
}
void z_print(Tree* root) {
if (!root) return;
cout << root->val << " ";
dfs(root, 1);
}
/*问题7
有1,2,5,10个零钱，要组成N元，总共有多少种组合方式。
*/
void dfs(const vector& arr, int start, int val, set& s) {
if (start > arr.size()) {
return;
}
else {
if(start != 0)s.insert(val);
for (int i = start; i < arr.size(); ++i) {
dfs(arr, i+1, val + arr[i], s);
}
}
}
int zuhe(const vector& arr) {
int len = arr.size();
if (len == 0) return 0;
set s;
dfs(arr, 0, 0, s);
return s.size();
}
/*问题8
打印根节点到所有叶子节点的路径
*/
vector> all_path;
void dfs(Tree* root, vector path) {
if (!root->left && !root->right) {
path.emplace_back(root->val);
all_path.emplace_back(path);
return;
}
else {
path.emplace_back(root->val);
if (root->left) dfs(root->left, path);
if (root->right) dfs(root->right, path);
}
}
int findPath(Tree* root) {
if (!root) {
return 0;
}
vector path;
dfs(root, path);
return all_path.size();
}
/*问题9 【左右子树高度相加】
求二叉树中两个节点的最远距离
*/
int heigh(Tree* root) {
if (!root) return 0;
return max(heigh(root->left), heigh(root->right)) + 1;
}
int max_distance(Tree* root) {
if (!root) {
return 0;
}
return heigh(root->right) + heigh(root->left);
}
/*问题10
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
*/
int dx[] = {-1, 1, 0, 0}; //上下左右
int dy[] = { 0, 0,-1, 1};
bool dfs(vector>& map, int x, int y, const string& targ, int start) {
// map 走过的地方标记为'1'
if (start >= targ.size()) return true;
if (map[x][y] != targ[start]) {
return false;
}
else {
char ch = map[x][y];
map[x][y] = '1';
for (int i = 0; i < 4; ++i) {// 四个方向
int t_x = x + dx[i];
int t_y = y + dy[i];
if (t_x < 0 || t_x >= map.size() || t_y < 0 || t_y >= map[0].size() || map[t_x][t_y] == '1') {
continue;
}
if (dfs(map, t_x, t_y, targ, start + 1)) {
map[x][y] = ch;
return true;
}
}
map[x][y] = ch;
return false;
}
}
bool findPath(vector>& map, const string& targ) {
int rows = map.size();
int len = targ.size();
if (rows == 0) return false;
if (len == 0) return true;
int cols = map[0].size();
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if(dfs(map, i, j, targ, 0)) return true;
}
}
return false;
}
/*问题11
给定一个树的根节点，求树上和根节点 距离为k的个数。
*/
int k_tree_num(Tree* root, int k) {
if (!root || k < 0) return 0;
else if (k == 0) {
return 1;
}
else {
return k_tree_num(root->left, k-1) + k_tree_num(root->right, k-1);
}
}
/*问题12
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
求 1 到 25的所有路径
*/
struct pos {
int row;
int col;
pos(int x, int y) :row(x), col(y) {};
pos() {};
};
int num = 0;
void dfs(const vector>& map, vector> flag, pos start, int rows, int cols) {// 从什么地方开始找
flag[start.row][start.col] = 1;
if (map[start.row][start.col] == map[rows - 1][cols - 1]) {
++num;
}
else {
if (start.row - 1 >= 0 && flag[start.row - 1][start.col] != 1) {// 上
pos new_pos(start.row - 1, start.col);
dfs(map, flag, new_pos, rows, cols);
}
if (start.col + 1 < cols && flag[start.row][start.col + 1] != 1) { //右
pos new_pos(start.row, start.col + 1);
dfs(map, flag, new_pos, rows, cols);
}
if (start.row + 1 < rows && flag[start.row + 1][start.col] != 1) {// 下
pos new_pos(start.row + 1, start.col);
dfs(map, flag, new_pos, rows, cols);
}
if (start.col - 1 >= 0 && flag[start.row][start.col - 1] != 1) {// 左
pos new_pos(start.row, start.col-1);
dfs(map, flag, new_pos, rows, cols);
}
}
}
int pathNums(const vector>& map) {
int rows = map.size();
if (rows == 0) return 0;
int cols = map[0].size();
if (cols == 0) return 0;
vector> flag(rows, vector(cols, 0));
pos start(0, 0);
dfs(map, flag, start, rows, cols);
return num;
}
/*问题13
n皇后问题
*/
void update_queenFlag(int row, int colunm, vector>& queenFlag) {
static int dr[] = { -1, -1, -1, 0, 1, 1, 1, 0};
static int dc[] = { -1, 0, 1, 1, 1, 0,-1,-1};
queenFlag[row][colunm] = 1;
int num = queenFlag.size();
for (int i = 1; i < num; ++i) {// 从皇后位置向1到n-1延申
for (int j = 0; j < 8; ++j) {// 8个方向
int x = row + i * dr[j];
int y = colunm + i * dc[j];
if (x >= 0 && x < num && y >= 0 && y < num) {
queenFlag[x][y] = 1;
}
}
}
}
vector>> totalmap;
stack>> st_flag;
stack>> st_map;
void dfs(int k, int n) {//k表示已经成功安插了k个，n 表示n皇后
if (k == n) {
totalmap.emplace_back(st_map.top());
return;
}
else {
vector> flag;
vector> map;
for (int i = 0; i < n; ++i) {// 找到一个不为1 的位置安插皇后
flag = st_flag.top();
map = st_map.top();
if (flag[k][i] == 0) {
map[k][i] = 1;
update_queenFlag(k, i, flag);
++k;
st_flag.push(flag);
st_map.push(map);
dfs(k, n);
st_map.pop();
st_flag.pop();
--k;
}
}
}
}
int nQueen(int n)
{
vector> map(n, vector(n, 0));
vector> flag(n, vector(n, 0));
int rows = map.size();
int cols = map[0].size();
st_flag.push(flag);
st_map.push(map);
dfs(0, n);
return 0;
}
/*问题14
18:52 给出时间的左右组合 18:55
*/
vector total_times;
void save(const string& src, string dst) {
if (dst == src) return;
int len = dst.size();
if (len == 1 && dst[len-1]-'0' > 2) {
return;
}
else if (len == 2 && dst[0] - '0' == 2 && dst[1] - '0' > 3) {
return;
}
else if (len == 3 && dst[len - 1] - '0' > 5) {
return;
}
else if (len == 4) {
total_times.emplace_back(dst);
}
else {
int len = src.size();
for (int i = 0; i < len; ++i) {
if (src[i] == ':') continue;
dst.push_back(src[i]);
save(src, dst);
dst.pop_back();
}
}
}
void save_time(const string& src) {
int len = src.size();
if (len == 0) return;
for (int i = 0; i < len; ++i) {
if (src[i] == ':') continue;
save(src, src.substr(i, 1));
}
return;
}
/*问题15
输入：[100,10,20,70,60,10,50],80
返回值：[[10,10,60],[10,20,50],[10,70],[20,60]] 找出和为目标值的组合
说明：给定的候选数集是[100,10,20,70,60,10,50]，目标数是80
*/
vector d;
vector> z;
set> s;
void dfs(vector& candidates, int x, int t, int step) {// 临时的和，目标， 开始位置
if (x > t || x < 0) return;
if (x == t) { s.insert(d); }
else {
int i;
for (i = step; i < candidates.size(); i++) {
d.push_back(candidates[i]);
dfs(candidates, x + candidates[i], t, i + 1);
d.pop_back();
}
}
}
/*问题16
请写一个整数计算器，支持加减乘三种运算和括号。
数据范围： 1000≤∣s∣≤100，保证计算结果始终在整型范围内
输入："(2*(3-4))*5"
返回值：-10
*/
char compare(char ch1, char ch2) {
switch (ch1)
{
case '+':
switch (ch2)
{
case '-':
case '+':
case '=':
case ')':
return '>';
default:
return '<';
}
case '-':
switch (ch2)
{
case '-':
case '+':
case '=':
case ')':
return '>';
default:
return '<';
}
case '*':
switch (ch2)
{
case '(':
return '<';
default:
return '>';
}
case '/':
switch (ch2)
{
case '(':
return '<';
default:
return '>';
}
case '(': //
switch (ch2)
{
case ')': // ')' 不会入栈
return '=';
default:
return '<';
}
default:
return '';
}
}
int cal(int num1, int num2, char ch) {
switch (ch)
{
case '+':
return num1 + num2;
case '-':
return num1 - num2;
case '*':
return num1 * num2;
case '/':
return num1 / num2;
default:
return 0;
}
}
int solve(string s) {
s.push_back('=');
int len = s.size();
if (len == 0) return 0;
int ret = 0;
// write code here
stack st_num; // 存储数字
stack< len ) {
// 符号优先级 ( '> st_chr; // 存储运算符
int i = 0;
while ( i <= '9') {
int num = 0;
// 需要整数提出来
// "100+100"
int start = i;
int end = start + 1;
while (s[end] >' * / '>' + - '>' = 自身大于自身
if (s[i] >= '0' && s[i] <= '9') ++end;
stringstream ss;
ss << s.substr(start, end - start);
ss >= '0' && s[end] <' 入栈， '>> num;
st_num.push(num);
i += end - start;
}
else {// 运算符
// 先算括号 '<': {
st_chr.push(s[i++]);
break;
}
case '>' 计算, '='出栈
if (st_chr.empty()) {
st_chr.push(s[i++]);
continue;
}
char ch = st_chr.top();
char opt = compare(ch, s[i]);
switch (opt)
{
case '': {
int num2 = st_num.top(); st_num.pop();
int num1 = st_num.top(); st_num.pop();
int num3 = cal(num1, num2, ch);
st_num.push(num3);
st_chr.pop(); // i 不用 ++ 后续继续判断
break;
}
case '=': {// '(' ')'
st_chr.pop();
i++;
break;
}
}
}
if (st_chr.empty() && s[i] == '=') break;
}
return st_num.top();
}
/*问题16
请根据二叉树的前序遍历，中序遍历恢复二叉树
如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：
*/
void createTree(vector& xianxu, int x_start, int len,
vector< z_start + len; ++i) {
if (zhongxu[i] == root) {
index = i; break;
}
}
// 左子树
createTree(xianxu, x_start + 1, index - z_start, zhongxu, z_start, tree->& zhongxu, int z_start, TreeNode* &tree) {
int index = 0;
if (len == 0) return;
// 先找到根节点 下标
int root = xianxu[x_start];
tree = new TreeNode(root);
if (len == 1) return;
for (int i = z_start; i left);
// 右子树
createTree(xianxu, x_start + 1 + index - z_start, len - (index - z_start) - 1, zhongxu, index + 1, tree->right);
}
/*问题17
给一个整数n, 返回 1..n 能组成的 搜索二叉树 的 组合
*/
vector dfs(int l, int r) {
if (l > r) {
return { nullptr };
}
else {
vector<= r; ++i) {
vector ret;
int l_len = 0;
int r_len = 0;
for (int i = l; i lefts = dfs(l, i-1);
vector< l_len; ++j) {
for (int k = 0; k < r_len; ++k) {
TreeNode* root = new TreeNode(i, lefts[j], rights[k]);
ret.emplace_back(root);
}
}
}
return ret;
}
}
rights = dfs(i+1, r);
l_len = lefts.size();
r_len = rights.size();
for (int j = 0; j
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）