1. LeetCode单周赛第320场

1.1 数组中不等三元组的数目

1.1.1 原题链接：力扣https://leetcode.cn/problems/number-of-unequal-triplets-in-array/

1.1.2 解题思路：

        暴力遍历咯。

1.1.3 代码：

class Solution {
public:int unequalTriplets(vector& nums) {int n = nums.size();int res = 0;for(int i = 0; i < n; i ++ ) for(int j = i + 1; j < n; j ++ ) for(int k = j + 1; k < n; k ++ ) if(nums[i] != nums[j] && nums[i] != nums[k] && nums[j] != nums[k]) res ++;return res;}
};

1.2 二叉搜索树最近节点查询

1.2.1 原题链接：力扣https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/

1.2.2 解题思路：

        1、先把树种的元素存到数组中；

        2、把数组中的元素排序，然后二分找满足要求的元素。

1.2.3 代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void tra(TreeNode* root, vector& t){if(root == nullptr) return;t.push_back(root->val);tra(root->left, t);tra(root->right, t);}vector> closestNodes(TreeNode* root, vector& queries) {vector> res;vector tmp;tra(root, tmp);sort(tmp.begin(), tmp.end());int n = tmp.size();for(auto& x: queries) {int a, b;int l = 0, r = n - 1;while(l < r) {int mid = l + r + 1 >> 1;if(tmp[mid] > x) r = mid - 1;else l = mid;}if(tmp[l] <= x) a = tmp[l];else a = -1;l = 0, r = n - 1;while(l < r) {int mid = l + r >> 1;if(tmp[mid] < x) l = mid + 1;else r = mid;}if(tmp[l] >= x) b = tmp[l];else b = -1;res.push_back({a, b});}return res;}
};

1.3 到达首都最少油耗

1.3.1 原题链接：力扣https://leetcode.cn/problems/minimum-fuel-cost-to-report-to-the-capital/

1.3.2 解题思路：

        以 0 为根，统计每个子树中节点的个数cur，那么每个子树需要的车的数量就是 cur / seats 向上取整。

1.3.3 代码：

#define N 100010
#define M 200010int h[N], e[M], ne[M], idx;typedef long long ll;class Solution {
public:ll ans = 0;void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}ll dfs(int u, int father, int seats) {ll cur = 1;for(int i = h[u]; i != -1; i = ne[i]){int j = e[i];if(j != father) {cur += dfs(j, u, seats);}}if(u != 0) {ans += (cur + seats - 1) / seats;  //向上取整}return cur;}long long minimumFuelCost(vector>& roads, int seats) {memset(h, -1, sizeof h);idx = 0;for(auto& road: roads) {add(road[0], road[1]);add(road[1], road[0]);}dfs(0, -1, seats);return ans; }
};

2.AcWing周赛第78场

2.1 商品种类

2.1.1 原题链接：4719. 商品种类 - AcWing题库

2.1.2 解题思路：

        使用set将产品的产地+名称存储到set中，最后返回set的大小即可。

2.1.3 代码：

#include 
#include 
#include 
#include using namespace std;int main()
{int n;cin >> n;unordered_set st;for(int i = 0; i < n; i ++ ) {string a, b;cin >> a >> b;st.insert(a + ' ' + b);}cout << st.size() << endl;return 0;
}

2.2 字符串

2.2.1 原题链接：4720. 字符串 - AcWing题库

2.2.2 解题思路：

        把字符串 s 中的字符一个一个存到答案字符串 res 中，若与 res 中的最后一个字符相同，则把字符串 res 中的最后一个字符删去，反之，则加入到 res 中。最后输出 res 即可。

2.2.3 代码：

#include 
#include 
#include using namespace std;int main()
{string s;cin >> s;string res;for(auto c: s) {if(res.size() && res.back() == c) res.pop_back();else res += c;}cout << res << endl;return 0;
}

2.3 排队

2.3.1 原题链接：4721. 排队 - AcWing题库

2.3.2 解题思路：

        1、用单调队列+二分的思路解决此问题；

        2、从后往前遍历身高，栈里存的是对应身高的下标，每次对栈内下标二分找到比自身矮的最右侧一个人的位置；

        3、对于栈内元素的维护，具有单调性，因为例如，对于寻找比 a[k] （k > i && k > j）的矮的最右侧的一位在哪，如果a[i], a[j]均小于a[k],且 i < j，那么，a[i]就没有存在必要了。

2.3.3 代码：

#include 
#include 
#include using namespace std;typedef long long ll;
const int N = 1e5 + 10;int h[N], stk[N];
int n;
int ans[N];int main()
{scanf("%d", &n);for(int i = 0; i < n; i ++ ) scanf("%d", &h[i]);int top = 0;for(int i = n - 1; i >= 0; i -- ) {if(!top || h[i] <= h[stk[top]]) ans[i] = -1;else {int l = 1, r = top;while(l < r) {int mid = l + r >> 1;if(h[stk[mid]] < h[i]) r = mid;else l = mid + 1;}ans[i] = stk[r] - i - 1;}if(!top || h[i] < h[stk[top]]) stk[++ top] = i;}for(int i = 0; i < n; i ++ ) printf("%d ", ans[i]);return 0;
}