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

深藏阁楼爱情的钟 2022-12-20 11:08 180阅读 0赞

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

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

class Solution { 
    public:
        int strongPasswordChecker(string s) { 
            int lower = 1, upper = 1, number = 1;
            int once = 0, twice = 0, replace = 0;
            for (size_t k = 0; k < s.size(); k++) { 
                if (islower(s[k])) lower = 0;
                if (isupper(s[k])) upper = 0;
                if (isdigit(s[k])) number = 0;
                int num = -1;
                if (0 < k && k < s.size() - 1) { 
                    if (s[k - 1] == s[k] && s[k] == s[k + 1]) { 
                        num = 3;
                        while (k + 2 < s.size() && s[k + 1] == s[k + 2]) { 
                            num++;
                            k++;
                        }
                        k++;
                    }
                }
                if (num > 0) { 
                    if (num % 3 == 0) once++;
                    if (num % 3 == 1) twice++;
                    replace += num / 3;
                }
            }
            int miss = lower + upper + number;
            if (s.size() < 6) return max(6 - (int)s.size(), miss);
            if (s.size() <= 20) return max(replace, miss);
            int del = s.size() - 20;
            replace -= min(del, once);
            if (del > once) { 
                replace -= min((del - once) / 2, twice);
            }
            if (del - once - 2 * twice > 0) { 
                replace -= (del - once - 2 * twice) / 3;
            }
            return del + max(replace, miss);
        }
    };

1.  数组中两个数的最大异或值  
    给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。

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

class Trie{ 
    public:
        Trie* next[2];
        Trie()
        { 
            memset(next, 0, sizeof(next));
        }
    };
    class Solution { 
        Trie* root = new Trie();
    public:
        int findMaximumXOR(vector<int>& nums) { 
            // 将数按照二进制形式全部存入字典树里面
            for(int num : nums)
            { 
                Trie* node = root;
                for(int i = 30; i >= 0; i--)
                { 
                    int bt = num >> i & 1;
                    if(node->next[bt] == nullptr)
                    { 
                        node->next[bt] = new Trie();
                    }
                    node = node->next[bt];
                }
            }
            // 找最大值
            int res = 0;
            for(int num : nums)
            { 
                Trie* node = root;
                int sum = 0;
                for(int i = 30; i >= 0; i--)
                { 
                    int bt = num >> i & 1;  
                    // 如果bt==1则贪心的去找0异或 否则找1异或
                    if(bt == 1)
                    { 
                        sum += node->next[0] != nullptr ? 1 << i : 0 ;
                        node = node->next[0] != nullptr ? node->next[0] : node->next[1];
                    }
                    else
                    { 
                        sum += node->next[1] != nullptr ? 1 << i : 0 ;
                        node = node->next[1] != nullptr ? node->next[1] : node->next[0];
                    }
                }
                res = max(res, sum);
            }
            return res;
        }
    };

1.  从英文中重建数字  
    给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。

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

class Solution { 
    public:
        map<string, int> M = { 
            { "one", 1},
            { "two", 2},
            { "three", 3},
            { "four", 4},
            { "five", 5},
            { "six", 6},
            { "seven", 7},
            { "eight", 8},
            { "nine", 9},
            { "zero", 0}
        };
        string originalDigits(string s) { 
            map<char, int> m;
            for (auto c : s) ++m[c];
            map<int, int> num;
            num[0] = m['z'];
            num[2] = m['w'];
            num[4] = m['u'];
            num[6] = m['x'];
            num[8] = m['g'];
            num[1] = m['o'] - num[0] - num[2] - num[4];
            num[3] = m['r'] - num[0] - num[4];
            num[5] = m['f'] - num[4];
            num[7] = m['s'] - num[6];
            num[9] = m['i'] - num[5] - num[6] - num[8];
            string res;
            for (auto& p : num) { 
                res.insert(res.end(), p.second, p.first + '0');
            }
            return res;
        }
    };

1.  替换后的最长重复字符  
    给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

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

class Solution { 
    public:
        int characterReplacement(string s, int k) { 
            vector<int> counts(26, 0); //记录当前窗口字母出现的个数
            int left = 0, res = 0, maxCnt = 0; // maxCnt记录字符出现次数最多那个字符 的次数
            for(int i = 0; i < s.size(); i++) 
            { 
                counts[s[i] - 'A']++;
                maxCnt = max(maxCnt, counts[s[i] - 'A']); // 比较之前记录的最大数 和 当前字符的数量
                while(i - left + 1 - maxCnt > k)
                {  // 若当前窗口大小 减去 窗口中最多相同字符的个数 大于 k 时
                    counts[s[left]-'A']--; // 将窗口最左边的字符 在计数数组中减1
                    left++; // 滑动窗口
                }
                res = max(res, i - left + 1);
            }
            return res;
        }
    };

1.  建立四叉树  
    给你一个 n \* n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。你需要返回能表示矩阵的四叉树的根结点。

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

/* // 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; } }; */
    
    class Solution { 
    public:
    
        Node* helper(vector<vector<int>>& grid, int row, int col, int N) { 
            int first = grid[row][col];
            Node *result = new Node();
            bool isLeaf = true;
            int m, n;
            m = row+N;
            n = col+N;
            
            // 遍历比较每个元素与左上角元素的值
            for (int i = row; i < m; ++i) { 
                for (int j = col; j < n; ++j)
                    if (grid[i][j] != first) { 
                        isLeaf = false;
                        break;
                    }
                if (!isLeaf) break;
            }
            
            if (isLeaf) { 
                result->val = first;
                result->isLeaf = isLeaf;
            } else { 
                // 存在不一样的元素，递归计算子节点，每个子矩阵的行列数减半
                N /= 2;
                result->isLeaf = isLeaf;
                result->topLeft = helper(grid, row, col, N);
                result->topRight = helper(grid, row, col+N, N);
                result->bottomLeft = helper(grid, row+N, col, N);
                result->bottomRight = helper(grid, row+N, col+N, N);
            }
            return result;
        }
        
        Node* construct(vector<vector<int>>& grid) { 
            int N = (int)grid.size();
            if (N == 0) return NULL;
            return helper(grid, 0, 0, N);
        }
    };

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

class Solution { 
    public:
        vector<vector<int>> levelOrder(Node* root) { 
            queue<Node*> que;
            if (root != NULL) que.push(root);
            vector<vector<int>> result;
            while (!que.empty()) { 
                int size = que.size();
                vector<int> vec;
                for (int i = 0; i < size; i++) {  
                    Node* node = que.front();
                    que.pop();
                    vec.push_back(node->val);
                    for (int i = 0; i < node->children.size(); i++) {  // 将节点孩子加入队列
                        if (node->children[i]) que.push(node->children[i]);
                    }
                }
                result.push_back(vec);
            }
            return result;
    
        }
    };

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

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

class Solution { 
    public:
      //建立两个节点的双向关系
      void twoWay(Node *pre, Node *now) { 
        now->prev = pre;
        pre->next = now;
      }
    
      Node *flatten(Node *head) { 
        Node *pre = NULL, *now = head;
        stack<Node *> s;
    
        while (true) { 
          if (now == NULL) { 
            //若当前节点为空，且栈为空或栈顶的节点为NULL，则代表已遍历完成，直接返回head
            if (s.empty() || s.top() == NULL) { 
              return head;
            }
            //否则，取出栈顶的节点作为当前节点
            now = s.top();
            s.pop();
            //建立双向关系
            twoWay(pre, now);
          }
          //若当前节点有子链表
          if (now->child != NULL) { 
            //将当前节点的下一个结点压入栈中（该节点可能为空）
            s.emplace(now->next);
            //处理子链表
            pre = now;
            now = now->child;
            pre->child = NULL;
            //建立双向关系
            twoWay(pre, now);
          } else { 
            //若当前节点没有子链表，则向后移动
            pre = now;
            now = now->next;
          }
        }
        return NULL;
      }
    };