1128. 等价多米诺骨牌对的数量
算法思路:
这题是要求出给出的一堆数对中,统计有多少对数对符合要求
形式上,dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a == c 且 b == d ,或是 a == d 且 b == c。
因此 [1, 2]和[2, 1]可以认为是等价的的,判断两者相同可以通过较小的数*10 + 较大的数的值来进行比较,由于题目规定数值是一位数,所以这样相加不会出现重合。
class Solution {
public:
int numEquivDominoPairs(vector<vector<int>>& dominoes) {
// table用于保存,【较小的数*10 + 较大的数】有多少个,由于数值规定为一位数,所以不会超过100
vector<int> table(100) ;
int ans = 0 ;
for (int i = 0;i < dominoes.size();i++) {
if (dominoes[i][0] > dominoes[i][1]) {
// 当该表达式第一次出现时,table中对应数值为0, ans = 0,此时凑不成一对
// 第二次出现时,table中对应数值为1,ans = 0 + 1,此时可以凑成一对
// 第三次出现时,table中对应数值为2,ans = 0 + 1 + 2,此时可以凑成三对
// 第四次书显示,table中对应数值为3,ans = 0 + 1 + 2 + 3 = 6,此时可以凑成六对
// 以此类推
// 这是组合数C(n,2) 在 n 个元素中选2个,公式为0 + 1 + 2 + …… + n - 1 = n(n - 1) / 2
ans += table[dominoes[i][1] * 10 + dominoes[i][0]] ;
table[dominoes[i][1] * 10 + dominoes[i][0]] ++ ;
} else {
ans += table[dominoes[i][0] * 10 + dominoes[i][1]] ;
table[dominoes[i][0] * 10 + dominoes[i][1]] ++ ;
}
}
return ans ;
}
};
394. 字符串解码
算法思路:
首先使用栈得到每个'['字符对应的']'的位置,用unordered_map进行存储
然后使用深度优先搜索对每个方括号内的内容进行递归,并根据给的数字返回字符串。
class Solution {
public:
string ans ;
// 无序map,用于存储每个[对应的]的位置
unordered_map<int, int> find_right ;
// dfs
// l r 分别对应[ 和 ]
// count 表示方括号的内容要重复多少遍
string dfs(int count, int l, int r, string& s) {
// 创建返回的字符串,为空
string temp = "" ;
// 从l + 1 至 r - 1,这是方括号内的内容,进行遍历
for (int i = l + 1;i < r;i++) {
// 如果当前字符不是[],且不为数字字符,则为普通字符,直接添加到字符串后面即可
if (s[i] != '[' && s[i] != ']' && (s[i] < '0' || s[i] > '9')) {
temp.append(1, s[i]) ;
} else if (s[i] >= '0' && s[i] <= '9') {
// 说明当前字符时数字,数字不知一位,所以往后继续找同为数字的一位
int k = i + 1 ;
for (;k < s.size();k++) {
if (s[k] < '0' || s[k] > '9') {
// 当前寻找到的非数字字符,往前退一位
k -- ;
break ;
}
}
// 使用substr函数将字符串中找到的数字截取,并使用atoi将该字符串转换成整数
int count_next = atoi(s.substr(i, k - i + 1).c_str()) ;
// dfs往下搜索
temp.append(dfs(count_next, k + 1, find_right[k + 1], s)) ;
// 搜索完毕,i跳跃到]字符的后一位
i = find_right[k + 1] ;
}
}
string tt = temp ;
for (int i = 0;i < count - 1;i++) {
temp.append(tt) ;
}
return temp ;
}
string decodeString(string s) {
ans = "" ;
stack<int> st ;
// 根据栈获得每个[对应的]
for (int i = 0;i < s.size();i++) {
if (s[i] == '[') {
st.push(i) ;
}
if (s[i] == ']') {
find_right[st.top()] = i ;
st.pop() ;
}
}
// 以下和dfs函数中的遍历一样
for (int i = 0;i < s.size();i++) {
if (s[i] != '[' && s[i] != ']' && (s[i] < '0' || s[i] > '9')) {
ans.append(1, s[i]) ;
} else if (s[i] >= '0' && s[i] <= '9') {
int k = i + 1 ;
for (;k < s.size();k++) {
if (s[k] < '0' || s[k] > '9') {
k -- ;
break ;
}
}
int count_next = atoi(s.substr(i, k - i + 1).c_str()) ;
ans.append(dfs(count_next, k + 1, find_right[k +c++ 1], s)) ;
i = find_right[k + 1] ;
}
}
return ans ;
}
};
106. 从中序与后序遍历序列构造二叉树
算法思路:
后序遍历的顺序是:左节点 -> 右节点 -> 根节点 因此后序遍历的最后一个元素一定是当前二叉树的根节点,然后根据根节点找到该元素在中序遍历中的位置,中序遍历的顺序是:左节点 -> 根节点 -> 右节点 所以在根节点左边的一定是左子树的节点,右边的一定是右子树的节点,明确了左右子树元素的个数后,进行递归调用就可以构造二叉树了。
class Solution {
public:
unordered_map<int, int> hashtable ;
TreeNode* helper(vector<int>& inorder, vector<int>& postorder, int postorder_left, int postorder_right, int inorder_left, int inorder_right) {
if (postorder_left > postorder_right) return nullptr ;
// 后序遍历的最后一个元素一定是根节点
int tree_root = postorder[postorder_right] ;
int inorder_tree_root = hashtable[tree_root] ;
TreeNode* root = new TreeNode(tree_root) ;
// 计算右子树的节点数
int right_num = inorder_right - inorder_tree_root ;
root->left = helper(inorder, postorder, postorder_left , postorder_right - right_num - 1, inorder_left, inorder_tree_root - 1) ;
root->right = helper(inorder, postorder, postorder_right - right_num, postorder_right - 1, inorder_tree_root + 1, inorder_right) ;
return root ;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int n = inorder.size() ;
for (int i = 0;i < n;i++) {
hashtable[inorder[i]] = i ;
}
return helper(inorder, postorder, 0, n-1, 0, n-1) ;
}
};
207. 课程表
算法思路
这是拓扑排序问题,就是判断这个图是不是有向无环图,求出这个图的一个拓扑排序后,判断拓扑排序的数目是否和节点数相等,若不相等说明图中有环
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
// 预处理获得每个节点的入度
// [0, 1] 就是 1 -> 0
vector<int> indegree(numCourses, 0) ;
for (int i = 0;i < prerequisites.size();i++) {
indegree[prerequisites[i][0]] ++ ;
}
queue<int> q ;
// 将入度为0的节点添加到队列中
for (int i = 0;i < indegree.size();i++) {
if (indegree[i] == 0) {
q.push(i) ;
}
// BFS
vector<int> res ;
while (! q.empty()) {
int node = q.front() ;
q.pop() ;
res.push_back(node) ;
for (int i = 0;i < prerequisites.size();i++) {
if (prerequisites[i][1] == node) {
indegree[prerequisites[i][0]] -- ;
if (indegree[prerequisites[i][0]] == 0) {
q.push(prerequisites[i][0]) ;
}
}
}
}
return res.size() == numCourses ;
}
};
129. 求根到叶子节点数字之和
算法思路
使用回溯法,每次遍历到一个节点,判断是否是叶子节点,如果是叶子节点,将该节点值添加到数组中,然后计算数组组合起来的数字,并将数字加到总和中,然后回溯,将该节点抛弃,并return。如果不是叶子节点,先将该节点值添加到数组中,判断是否有左右子树,有的话继续递归。左右子树递归求解完后,将该节点值从数组抛弃。
class Solution {
public:
int ans ;
void helper(vector<int>& sum, TreeNode* node) {
if (node->left == nullptr && node->right == nullptr) {
sum.push_back(node->val) ;
int sum_t = 0;
for (int i = 0;i < sum.size();i++) {
sum_t = sum_t * 10 + sum[i] ;
}
ans += sum_t;
sum.pop_back() ;
return ;
}
sum.push_back(node->val) ;
if (node->left != nullptr) helper(sum, node->left) ;
if (node->right != nullptr) helper(sum, node->right) ;
sum.pop_back() ;
}
int sumNumbers(TreeNode* root) {
ans = 0 ;
if (root == nullptr) {
return ans ;
}
vector<int> sum ;
helper(sum, root) ;
return ans ;
}
};