前缀树问题-LeetCode 409、412、414、415、419、421

• 2019 年 12 月 30 日
• 笔记

前缀树问题：

LeetCode # 409 412 414 415 419 421

1

编程题

【LeetCode #409】最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意: 假设字符串的长度不会超过 1010。

示例 1: 输入: "abccccdd" 输出: 7

解题思路：

统计字符串中每个字母出现的个数，如果个数为奇数，则cnt+奇数-1，否则cnt+偶数，当处理完后，如果cnt < len，那么回文串还可以使用一个字符，因此返回cnt+1, 否则直接返回cnt.

class Solution {  public:      int longestPalindrome(string s) {          int len = s.length();          map<char, int> m;          for(auto ch: s) {              m[ch]++;          }          int cnt = ;          for(auto it: m) {              if ((it.second & ) == ) {                  cnt += it.second;              }else {                  cnt += (it.second - );              }          }          return (cnt < len) ? cnt +  : cnt;  // 根据cnt大小选择是否加 1      }  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindrome

【LeetCode #412】Fizz Buzz

写一个程序，输出从 1 到 n 数字的字符串表示。

• 1. 如果 n 是3的倍数，输出“Fizz”；
• 2. 如果 n 是5的倍数，输出“Buzz”；
• 3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

class Solution {  public:      vector<string> fizzBuzz(int n) {          vector<string> res;          for(int i = ; i <= n; i++) {              if ((i %  == )) {                  res.push_back("FizzBuzz");              } else if (i %  == ) {                  res.push_back("Fizz");              } else if (i %  == ) {                  res.push_back("Buzz");              } else {                  res.push_back(to_string(i));              }          }          return res;      }  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/fizz-buzz

【LeetCode #414】第三大的数

给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例 1: 输入: [3, 2, 1] 输出: 1 解释: 第三大的数是 1.

解题思路：

维护一个长度为3的set，由于set默认从小到大排序，因此，遍历整个nums, 压入set中，当set的大小大于3, 那么将最小的元素即*（set.begin()）删除掉，维护set的大小为3.

class Solution {  public:      int thirdMax(vector<int>& nums) {          set<int> ss;    // set默认排序规则是从小到大          for(auto num: nums) {              ss.insert(num);              if (ss.size() > ) {                  ss.erase(*(ss.begin()));              }          }          if (ss.size() < )              return *(ss.rbegin());   //最大的          else              return *(ss.begin());    //第三大的      }  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/third-maximum-number

【LeetCode #415】字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意： num1 和num2 的长度都小于 5100. num1 和num2 都只包含数字 0-9. num1 和num2 都不包含任何前导零。

解题思路：链表的两数相加，也可以用这个方法。

class Solution {  public:      string addStrings(string num1, string num2) {          string res;          int tmp = , idx1 = num1.size()-1, idx2 = num2.size()-1;          while(idx1 >=  ||idx2 >=  || tmp != ) {              if (idx1 >= ) tmp += num1[idx1--] - '0';              if (idx2 >= ) tmp += num2[idx2--] - '0';              res.insert(, to_string(tmp % ));   // 在0位置插入              tmp /= ;          }          return res;      }  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-strings

【LeetCode #419】甲板上的战舰

给定一个二维的甲板， 请计算其中有多少艘战舰。战舰用 'X'表示，空位用 '.'表示。你需要遵守以下规则：

• 给你一个有效的甲板，仅由战舰或者空位组成。
• 战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成，或者 Nx1 (N 行, 1 列)组成，其中N可以是任意大小。
• 两艘战舰之间至少有一个水平或垂直的空位分隔 – 即没有相邻的战舰。

解题思路： 这是一个很巧妙的思路，只需要检查一个X的点的左边和上边是否也是X，如果是，则当前X不是战舰，否则战舰数+1，这样的话就可以进行一次遍历就好了。

class Solution {  public:      // 如果board[i][j]的左边或者上边是'X'，返回false.      bool check(vector<vector<char>>& board, int i, int j) {          return !((j >=  && board[i][j-1] == 'X') || (i >=  && board[i-1][j] == 'X'));      }        int countBattleships(vector<vector<char>>& board) {          int res = ;          for(int i = ; i < board.size(); i++) {              for(int j = ; j < board[i].size(); j++) {                  if (board[i][j] == 'X' && check(board, i, j)) res++;              }          }          return res;      }  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/battleships-in-a-board

【LeetCode #421】数组中两个数的最大异或值

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

你能在O(n)的时间解决这个问题吗？

示例: 输入: [3, 10, 5, 25, 2, 8] 输出: 28

解题思路：

构建前缀树，该棵前缀树共有32层，并且每个分支只有两个，也就是0和1, 也就代表某个数的某一位是0还是1. 在查找时，对于每个遍历的num，在某一位如果是0，那么在前缀术中查找对应位是否存在1，如果是，则计算入异或结果，进而得到最大的异或值即可。

struct TrieNode {      TrieNode *children[];      TrieNode() {          for(auto& child: children) child = nullptr;      }  };    class Solution {  public:      Solution() { root = new TrieNode(); }        void insert(int val) {          TrieNode* cur = root;          for(int i = ; i >= ; i--){              int idx = (val >> i) & ;              if (cur->children[idx] == nullptr) {                  cur->children[idx] = new TrieNode();              }              cur = cur->children[idx];          }      }        int findMaximumXOR(vector<int>& nums) {          for(auto num: nums) {              insert(num);          }          int res = ;          for(auto num: nums) {              int tmp = ;              TrieNode* cur = root;              for(int i = ; i >= ; i--){                  int idx = (num >> i) & ;                  if (cur->children[!idx] != nullptr) {  //选择每个位不同值的位置                      tmp +=  << i;                      cur = cur->children[!idx];                  } else {                      cur = cur->children[idx];                  }              }              res = max(res, tmp);          }          return res;      }  private:      TrieNode* root;  };  

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array