- 元音拼写检查器
在给定单词列表 wordlist 的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。
对于完全匹配，将原始单词加入哈希集合；
对于忽略大小写的情况下的匹配，将单词转成小写，然后将转成小写之后的单词和原始单词存入大小写哈希表；
对于忽略元音的情况下的匹配，将单词中的所有元音使用点号替换，然后将替换元音之后的单词和原始单词存入元音哈希表。
class Solution {
private:
string LowerWord(const string& str)
{
string res = "";
for (char c : str)
{
if (c>= 'A' && c <= 'Z')
{
res += tolower(c);
}
else
{
res += c;
}
}
return res;
}
string MatchWord(const string& str)
{
string res = "";
for (char c : str)
{
if (c== 'a'|| c== 'e' || c== 'i' || c== 'o' || c== 'u')
{
res += '*';
}
else
{
res += c;
}
}
return res;
}
public:
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
unordered_set<string> s1;
unordered_map<string, string> s2;
unordered_map<string, string> s3;
for (const string& word : wordlist)
{
if (s1.count(word) == 0)
{
s1.insert(word);
}
auto word1 = LowerWord(word);
if (s2.count(word1) == 0)
{
s2[word1] = word;
}
auto word2 = MatchWord(word1);
if (s3.count(word2) == 0)
{
// cout << "insert match " << word2 << " " << word << endl;
s3[word2] = word;
}
}
vector<string> res(queries.size(), "");
for (int i = 0; i < queries.size(); ++i)
{
if (s1.find(queries[i]) != s1.end())
{
res[i] = queries[i];
continue;
}
auto word1 = LowerWord(queries[i]);
if (s2.find(word1) != s2.end())
{
res[i] = s2[word1];
continue;
}
auto word2 = MatchWord(word1);
if (s3.find(word2) != s3.end())
{
res[i] = s3[word2];
continue;
}
}
return res;
}
};
- 连续差相同的数字
返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。请注意，除了 数字 0 本身之外，答案中的每个数字都 不能 有前导零。例如，01 有一个前导零，所以是无效的；但 0 是有效的。你可以按 任何顺序 返回答案。
毫无意义的一道题，遍历就对了
class Solution {
public:
vector<int> ans;
//now 当前选出的数，left剩余的数字
void func(int now, int left, int k){
if(left == 0){
ans.push_back(now);
return ;
}
//如now为2 k为3 便没有符合的数
if(now % 10 - k >= 0) {
func(now * 10 + now %10 - k, left - 1, k);
}
//k=0时，now % 10 - k 和now % 10 + k是一样的，答案会重复
if(k != 0 && now % 10 + k < 10){
func(now * 10 + now %10 + k, left - 1, k);
}
}
vector<int> numsSameConsecDiff(int n, int k) {
for(int i = 1; i<= 9; i++){
func(i, n - 1, k);
}
return ans;
}
};
- 监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。
若在 root 处安放摄像头，则孩子 一定也会被监控到。此时，只需要保证两棵孩子的子树被覆盖。
否则， 如果root 处不安放摄像头，则除了覆盖root 的两棵子树之外，孩子left,right 之一必须要安装摄像头，从而保证 root 会被监控到。
状态 a：root 必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目。
状态 b：覆盖整棵树需要的摄像头数目，无论root 是否放置摄像头。
状态 c：覆盖两棵子树需要的摄像头数目，无论节点 root 本身是否被监控到
/**
* 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) {}
* };
*/
struct Status {
int a, b, c;
};
class Solution {
public:
Status dfs(TreeNode* root) {
if (!root) {
return {INT_MAX / 2, 0, 0};
}
auto [la, lb, lc] = dfs(root->left);
auto [ra, rb, rc] = dfs(root->right);
int a = lc + rc + 1;
int b = min(a, min(la + rb, ra + lb));
int c = min(a, lb + rb);
return {a, b, c};
}
int minCameraCover(TreeNode* root) {
auto [a, b, c] = dfs(root);
return b;
}
};
- 煎饼排序
给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。
设一个元素的下标是index，我们可以通过两次煎饼排序将它放到尾部：
第一步选择 k =index + 1，然后反转子数组arr[0…k?1]，此时该元素已经被放到首部。
第二步选择 k=n，其中 n 是数组arr 的长度，然后反转整个数组，此时该元素已经被放到尾部。
通过以上两步操作，我们可以将当前数组的最大值放到尾部，然后将去掉尾部元素的数组作为新的处理对象，重复以上操作，直到处理对象的长度等于一，此时原数组已经完成排序，且需要的总操作数是 2×(n?1)，符合题目要求。
class Solution {
public:
vector<int> pancakeSort(vector<int>& arr) {
vector<int> ret;
for (int n = arr.size(); n > 1; n--) {
int index = max_element(arr.begin(), arr.begin() + n) - arr.begin();
if (index == n - 1) {
continue;
}
reverse(arr.begin(), arr.begin() + index + 1);
reverse(arr.begin(), arr.begin() + n);
ret.push_back(index + 1);
ret.push_back(n);
}
return ret;
}
};
- 强整数
给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。如果某一整数可以表示为 xi + yj ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。你可以按 任何顺序 返回答案。在你的回答中，每个值 最多 出现一次。
很无聊的题目
class Solution {
public:
vector<int> powerfulIntegers(int x, int y, int bound) {
unordered_set<int> s;
for (int i = 0; ; ++i)
{
int currX = pow(x, i);
if (currX >= bound)
{
break;
}
for (int j = 0; ; ++j)
{
int currY = pow(y, j);
if (currX + currY > bound)
{
break;
}
s.insert(currX + currY);
if (y == 1)
{
break;
}
}
if (x == 1)
{
break;
}
}
return vector<int>(s.begin(), s.end());
}
};
- 翻转二叉树以匹配先序遍历
给你一棵二叉树的根节点 root ，树中有 n 个节点，每个节点都有一个不同于其他节点且处于 1 到 n 之间的值。如果可以，则返回 翻转的 所有节点的值的列表。你可以按任何顺序返回答案。如果不能，则返回列表 [-1]。
按情况讨论即可
/**
* 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:
int i = 0; //记录当前访问的结点的索引
vector<int> res;
bool DFS(TreeNode* root, vector<int>& voyage) {
//如果树为空，肯定匹配
if (!root) {
return true;
}
if (root->val!=voyage[i]) { //如果访问的结点和数组中对应值不相等，肯定不匹配
return false;
}
i++; //索引++
//如果当前结点匹配，那就要去判断左右子树是否匹配(先左后右)
if (DFS(root->left, voyage) && DFS(root->right, voyage)) {
return true;
}
//翻转左右子树，再去判断左右子树是否匹配(先右后左)
if (DFS(root->right, voyage) && DFS(root->left, voyage)) {
res.push_back(root->val); //翻转之后如果匹配，把翻转的结点放入结果数组
return true;
}
//翻转后还不匹配，那就是不匹配；
return false;
}
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
//匹配成功，返回res
if(DFS(root, voyage)) {
return res;
}
//匹配失败，返回-1
res.erase(res.begin(),res.end());
res.push_back(-1);
return res;
}
};
- 相等的有理数
给定两个字符串 s 和 t ，每个字符串代表一个非负有理数，只有当它们表示相同的数字时才返回 true 。字符串中可以使用括号来表示有理数的重复部分。
将小数转化为分数后再比较
#define x first
#define y second
class Solution {
public:
typedef unsigned long long ULL;
typedef pair<ULL, ULL> PLL;
ULL gcd(ULL a, ULL b){
return b ? gcd(b, a%b) : a;
}
PLL simple(PLL a){//化简分数
ULL t = gcd(a.x,a.y);
return {a.x/t, a.y/t};
}
PLL add(PLL a, PLL b){//两个分数相加
a = simple(a),b = simple(b);
ULL down = a.y*b.y;
ULL up = a.x*b.y + b.x*a.y;
return simple({up,down});
}
PLL convert(string &s){//将小数转为分数
PLL a = {0,1}, b = {0,1}, c = {0, 0};//整数部分 不循环小数部分 循环小数部分
int i = 0;
//例如25.01(52)
while(i < s.size() && s[i]!='.') a.x = a.x*10 + s[i]-'0', i++; // 分解出整数部分 {25,1}
i++;//跳过小数点
while(i < s.size() && s[i]!='(') b.x = b.x*10 + s[i]-'0', b.y = b.y*10, i++; // 分解出不循环小数部分 {1,100}
i++;//跳过左括号
while(i < s.size() && s[i]!=')') c.x = c.x*10 + s[i]-'0', c.y = c.y*10+9, i++;// 分解出循环小数部分 {52,99}
c.y *= b.y;//把循环小数前面的0也计算在内 {52,9900}
if(c.y==0) c.y = 1;//注意 可能无循环部分 分母不能为零 这里把分母设为1即可
// cout<<a.x<<" "<<a.y<<"--"<<b.x<<" "<<b.y<<"--"<<c.x<<" "<<c.y<<endl;
return add(add(a,b),c);
}
bool isRationalEqual(string s, string t) {
auto t1 = convert(s), t2 = convert(t);
return t1.x == t2.x && t1.y == t2.y;
}
};
