前綴樹問題-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