leetcode解题思路分析（四十九）420 - 426 题

深藏阁楼爱情的钟 2022-12-20 11:08 286阅读 0赞
  1. 强密码校验器
    一个强密码应满足以下所有条件：由至少6个，至多20个字符组成。至少包含一个小写字母，一个大写字母，和一个数字。同一字符不能连续出现三次 (比如 “…aaa…” 是不允许的, 但是 “…aa…a…” 是可以的)。编写函数 strongPasswordChecker(s)，s 代表输入字符串，如果 s 已经符合强密码条件，则返回0；否则返回要将 s 修改为满足强密码条件的字符串所需要进行修改的最小步数。插入、删除、替换任一字符都算作一次修改。

本题难点在于分阶段讨论，其中连续的字符可以通过插入/替换的方式轻松解决，对于超过20个字符的，则需要考虑如何删除才能最轻松的满足条件

  1. class Solution { 
  2. public:
  3.     int strongPasswordChecker(string s) { 
  4.         int lower = 1, upper = 1, number = 1;
  5.         int once = 0, twice = 0, replace = 0;
  6.         for (size_t k = 0; k < s.size(); k++) { 
  7.             if (islower(s[k])) lower = 0;
  8.             if (isupper(s[k])) upper = 0;
  9.             if (isdigit(s[k])) number = 0;
  10.             int num = -1;
  11.             if (0 < k && k < s.size() - 1) { 
  12.                 if (s[k - 1] == s[k] && s[k] == s[k + 1]) { 
  13.                     num = 3;
  14.                     while (k + 2 < s.size() && s[k + 1] == s[k + 2]) { 
  15.                         num++;
  16.                         k++;
  17.                     }
  18.                     k++;
  19.                 }
  20.             }
  21.             if (num > 0) { 
  22.                 if (num % 3 == 0) once++;
  23.                 if (num % 3 == 1) twice++;
  24.                 replace += num / 3;
  25.             }
  26.         }
  27.         int miss = lower + upper + number;
  28.         if (s.size() < 6) return max(6 - (int)s.size(), miss);
  29.         if (s.size() <= 20) return max(replace, miss);
  30.         int del = s.size() - 20;
  31.         replace -= min(del, once);
  32.         if (del > once) { 
  33.             replace -= min((del - once) / 2, twice);
  34.         }
  35.         if (del - once - 2 * twice > 0) { 
  36.             replace -= (del - once - 2 * twice) / 3;
  37.         }
  38.         return del + max(replace, miss);
  39.     }
  40. };
  1. 数组中两个数的最大异或值
    给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。

采用Trie树来存取，距离最远的分支即为所求解

  1. class Trie{ 
  2. public:
  3.     Trie* next[2];
  4.     Trie()
  5.     { 
  6.         memset(next, 0, sizeof(next));
  7.     }
  8. };
  9. class Solution { 
  10.     Trie* root = new Trie();
  11. public:
  12.     int findMaximumXOR(vector<int>& nums) { 
  13.         // 将数按照二进制形式全部存入字典树里面
  14.         for(int num : nums)
  15.         { 
  16.             Trie* node = root;
  17.             for(int i = 30; i >= 0; i--)
  18.             { 
  19.                 int bt = num >> i & 1;
  20.                 if(node->next[bt] == nullptr)
  21.                 { 
  22.                     node->next[bt] = new Trie();
  23.                 }
  24.                 node = node->next[bt];
  25.             }
  26.         }
  27.         // 找最大值
  28.         int res = 0;
  29.         for(int num : nums)
  30.         { 
  31.             Trie* node = root;
  32.             int sum = 0;
  33.             for(int i = 30; i >= 0; i--)
  34.             { 
  35.                 int bt = num >> i & 1;  
  36.                 // 如果bt==1则贪心的去找0异或 否则找1异或
  37.                 if(bt == 1)
  38.                 { 
  39.                     sum += node->next[0] != nullptr ? 1 << i : 0 ;
  40.                     node = node->next[0] != nullptr ? node->next[0] : node->next[1];
  41.                 }
  42.                 else
  43.                 { 
  44.                     sum += node->next[1] != nullptr ? 1 << i : 0 ;
  45.                     node = node->next[1] != nullptr ? node->next[1] : node->next[0];
  46.                 }
  47.             }
  48.             res = max(res, sum);
  49.         }
  50.         return res;
  51.     }
  52. };
  1. 从英文中重建数字
    给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。

因为题意保证输入合法，所以我们只需要检测每个数字的英文独有的字母即可。对于重复的，则用独有的去减即可

  1. class Solution { 
  2. public:
  3.     map<string, int> M = { 
  4.         { "one", 1},
  5.         { "two", 2},
  6.         { "three", 3},
  7.         { "four", 4},
  8.         { "five", 5},
  9.         { "six", 6},
  10.         { "seven", 7},
  11.         { "eight", 8},
  12.         { "nine", 9},
  13.         { "zero", 0}
  14.     };
  15.     string originalDigits(string s) { 
  16.         map<char, int> m;
  17.         for (auto c : s) ++m[c];
  18.         map<int, int> num;
  19.         num[0] = m['z'];
  20.         num[2] = m['w'];
  21.         num[4] = m['u'];
  22.         num[6] = m['x'];
  23.         num[8] = m['g'];
  24.         num[1] = m['o'] - num[0] - num[2] - num[4];
  25.         num[3] = m['r'] - num[0] - num[4];
  26.         num[5] = m['f'] - num[4];
  27.         num[7] = m['s'] - num[6];
  28.         num[9] = m['i'] - num[5] - num[6] - num[8];
  29.         string res;
  30.         for (auto& p : num) { 
  31.             res.insert(res.end(), p.second, p.first + '0');
  32.         }
  33.         return res;
  34.     }
  35. };
  1. 替换后的最长重复字符
    给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

本题是一个典型的滑动窗口问题，右指针移动，然后判断当前窗口内最多的重复字符数是否加上k以内的值可以小于窗口总大小，不行则移动左边指针使得满足条件，最终得到的最大窗口大小即为最长重复字符子串长

  1. class Solution { 
  2. public:
  3.     int characterReplacement(string s, int k) { 
  4.         vector<int> counts(26, 0); //记录当前窗口字母出现的个数
  5.         int left = 0, res = 0, maxCnt = 0; // maxCnt记录字符出现次数最多那个字符 的次数
  6.         for(int i = 0; i < s.size(); i++) 
  7.         { 
  8.             counts[s[i] - 'A']++;
  9.             maxCnt = max(maxCnt, counts[s[i] - 'A']); // 比较之前记录的最大数 和 当前字符的数量
  10.             while(i - left + 1 - maxCnt > k)
  11.             {  // 若当前窗口大小 减去 窗口中最多相同字符的个数 大于 k 时
  12.                 counts[s[left]-'A']--; // 将窗口最左边的字符 在计数数组中减1
  13.                 left++; // 滑动窗口
  14.             }
  15.             res = max(res, i - left + 1);
  16.         }
  17.         return res;
  18.     }
  19. };
  1. 建立四叉树
    给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。你需要返回能表示矩阵的四叉树的根结点。

核心思路：当前矩阵由三个参数确定：左上角元素的行号 row 列号 col，以及矩阵规模 N。判断当前矩阵是否为叶子节点，方法为比较左上角元素和其他元素的关系，若出现不等则为非叶节点，需要继续划分，每个划分后的矩阵规模为 N/2 * N/2，这 4 个矩阵递归地生成当前节点的 4 个子节点。若元素全相等则返回一个叶子节点 (true, grid[row][col])

  1. /* // Definition for a QuadTree node. class Node { public: bool val; bool isLeaf; Node* topLeft; Node* topRight; Node* bottomLeft; Node* bottomRight; Node() { val = false; isLeaf = false; topLeft = NULL; topRight = NULL; bottomLeft = NULL; bottomRight = NULL; } Node(bool _val, bool _isLeaf) { val = _val; isLeaf = _isLeaf; topLeft = NULL; topRight = NULL; bottomLeft = NULL; bottomRight = NULL; } Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) { val = _val; isLeaf = _isLeaf; topLeft = _topLeft; topRight = _topRight; bottomLeft = _bottomLeft; bottomRight = _bottomRight; } }; */
  3. class Solution { 
  4. public:
  6.     Node* helper(vector<vector<int>>& grid, int row, int col, int N) { 
  7.         int first = grid[row][col];
  8.         Node *result = new Node();
  9.         bool isLeaf = true;
  10.         int m, n;
  11.         m = row+N;
  12.         n = col+N;
  14.         // 遍历比较每个元素与左上角元素的值
  15.         for (int i = row; i < m; ++i) { 
  16.             for (int j = col; j < n; ++j)
  17.                 if (grid[i][j] != first) { 
  18.                     isLeaf = false;
  19.                     break;
  20.                 }
  21.             if (!isLeaf) break;
  22.         }
  24.         if (isLeaf) { 
  25.             result->val = first;
  26.             result->isLeaf = isLeaf;
  27.         } else { 
  28.             // 存在不一样的元素，递归计算子节点，每个子矩阵的行列数减半
  29.             N /= 2;
  30.             result->isLeaf = isLeaf;
  31.             result->topLeft = helper(grid, row, col, N);
  32.             result->topRight = helper(grid, row, col+N, N);
  33.             result->bottomLeft = helper(grid, row+N, col, N);
  34.             result->bottomRight = helper(grid, row+N, col+N, N);
  35.         }
  36.         return result;
  37.     }
  39.     Node* construct(vector<vector<int>>& grid) { 
  40.         int N = (int)grid.size();
  41.         if (N == 0) return NULL;
  42.         return helper(grid, 0, 0, N);
  43.     }
  44. };

  1. N叉树的层序遍历
    给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
    用一个队列存储即可

    class Solution {
    public:

    1. vector<vector<int>> levelOrder(Node* root) { 
    2.     queue<Node*> que;
    3.     if (root != NULL) que.push(root);
    4.     vector<vector<int>> result;
    5.     while (!que.empty()) { 
    6.         int size = que.size();
    7.         vector<int> vec;
    8.         for (int i = 0; i < size; i++) {  
    9.             Node* node = que.front();
    10.             que.pop();
    11.             vec.push_back(node->val);
    12.             for (int i = 0; i < node->children.size(); i++) {  // 将节点孩子加入队列
    13.                 if (node->children[i]) que.push(node->children[i]);
    14.             }
    15.         }
    16.         result.push_back(vec);
    17.     }
    18.     return result;
    20. }

    };

  2. 扁平化多级双向链表
    给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

** 用一个栈保存，然后遍历即可**

  1. class Solution { 
  2. public:
  3.   //建立两个节点的双向关系
  4.   void twoWay(Node *pre, Node *now) { 
  5.     now->prev = pre;
  6.     pre->next = now;
  7.   }
  9.   Node *flatten(Node *head) { 
  10.     Node *pre = NULL, *now = head;
  11.     stack<Node *> s;
  13.     while (true) { 
  14.       if (now == NULL) { 
  15.         //若当前节点为空，且栈为空或栈顶的节点为NULL，则代表已遍历完成，直接返回head
  16.         if (s.empty() || s.top() == NULL) { 
  17.           return head;
  18.         }
  19.         //否则，取出栈顶的节点作为当前节点
  20.         now = s.top();
  21.         s.pop();
  22.         //建立双向关系
  23.         twoWay(pre, now);
  24.       }
  25.       //若当前节点有子链表
  26.       if (now->child != NULL) { 
  27.         //将当前节点的下一个结点压入栈中（该节点可能为空）
  28.         s.emplace(now->next);
  29.         //处理子链表
  30.         pre = now;
  31.         now = now->child;
  32.         pre->child = NULL;
  33.         //建立双向关系
  34.         twoWay(pre, now);
  35.       } else { 
  36.         //若当前节点没有子链表，则向后移动
  37.         pre = now;
  38.         now = now->next;
  39.       }
  40.     }
  41.     return NULL;
  42.   }
  43. };

发表评论

表情：
评论列表 （有 0 条评论，286人围观）

还没有评论，来说两句吧...

相关阅读