前缀树问题-LeetCode 409、412、414、415、419、421
前缀树问题-LeetCode 409、412、414、415、419、421
前缀树问题：
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
腾讯云开发者
