数字问题-LeetCode 524、525、526、528、530、537、539、540
数字问题-LeetCode 524、525、526、528、530、537、539、540
作者：TeddyZhang，公众号：算法工程师之路
数字问题：
LeetCode # 524 525 526 528 530 537 539 540
1
编程题
【LeetCode #524】通过删除字母匹配到字典里最长的单词
给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例 1: 输入: s = "abpcplea", d = ["ale","apple","monkey","plea"] 输出: "apple"
解题思路：首先找出符合子序列的字符串，然后根据字典序以及长度进行排序。
class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
vector<string> tmp;
int maxIdx = ;
for(int i = ; i < d.size(); i++) {
if (isSubString(s, d[i])) {
tmp.push_back(d[i]);
}
}
if (tmp.empty()) return "";
auto cmp = [](const string& a, const string& b) {
if (a.length() == b.length()) {
return a < b;
} else {
return a.length() > b.length();
}
};
sort(tmp.begin(), tmp.end(), cmp);
return tmp[];
}
private:
bool isSubString(string a, string b) {
int i = , j = ;
while(i < a.length() && j < b.length()) {
if (a[i] == b[j]) {
i++; j++;
} else {
i++;
}
}
if (j == b.length()) return true;
else return false;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting
【LeetCode #525】连续数组
给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。
示例 1: 输入: [0,1] 输出: 2 说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
解题思路：设置一个cur变量，然后遍历数组，当遍历到 1 时，cur += 1, 当遍历到 0 时， cur -= 1, 并将对应和的索引存入哈希表即可！
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> hashmap;
int cur = ;
hashmap[] = -1; // 将第一个索引设为-1
int res = ;
for(int i = ; i < nums.size(); i++) {
cur += (nums[i] ? : -1);
if (hashmap.find(cur) != hashmap.end()) {
res = max(res, i-hashmap[cur]);
} else {
hashmap[cur] = i; // 覆盖
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/contiguous-array
【LeetCode #526】优美的排列
假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：
- 第 i 位的数字能被 i 整除
- i 能被第 i 位上的数字整除
现在给定一个整数 N，请问可以构造多少个优美的排列？
示例1: 输入: 2 输出: 2
class Solution {
public:
int countArrangement(int N) {
vector<bool> visited(N+, false);
return dfs(visited, , N);
}
private:
int dfs(vector<bool> visited, int i, int N) {
if (i > N) return ;
int res = ;
for(int j = ; j < N+; j++) {
if (!visited[j] && (j%i == || i%j == )) {
visited[j] = true;
res += dfs(visited, i+, N);
visited[j] = false;
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/beautiful-arrangement
【LeetCode #528】按权重随机选择
给定一个正整数数组 w ，其中 w[i] 代表位置 i 的权重，请写一个函数 pickIndex ，它可以随机地获取位置 i，选取位置 i 的概率与 w[i] 成正比。
示例1: 输入: ["Solution","pickIndex"] [[[1]],[]] 输出: [null,0]
解题思路：根据累加值和哈希表获取权重
class Solution {
public:
Solution(vector<int>& w) {
int n = w.size();
for(int i = ; i < w.size(); i++) {
sum += w[i];
hashmap[sum] = i;
}
}
int pickIndex() {
int num = rand() % sum + ;
auto it = hashmap.lower_bound(num); // unorder_map中没有此成员函数
return it->second;
}
private:
int sum = ;
map<int, int> hashmap;
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/random-pick-with-weight
【LeetCode #530】二叉搜索树的最小绝对值差
给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。
解题思路：对于二叉搜索树而言，中序遍历后是一个有序列表。
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
int res = INT_MAX;
findnode(root);
for(int i = ; i < vals.size(); i++) {
res = min(res, abs(vals[i]-vals[i-1]));
}
return res;
}
private:
vector<int> vals;
void findnode(TreeNode* root) { // 中序遍历
if (root == nullptr) return;
findnode(root->left);
vals.push_back(root->val);
findnode(root->right);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/submissions/
【LeetCode #537】复数乘法
给定两个表示复数的字符串。
返回表示它们乘积的字符串。注意，根据定义 i2 = -1 。
示例 1: 输入: "1+1i", "1+1i" 输出: "0+2i" 解释: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i ，你需要将它转换为 0+2i 的形式。
解题思路：通过"+"来对复数进行拆分，在C++中，atoi是将const char*类型转为int类型，而stoi是将string类型转为int类型。
class Solution {
public:
string complexNumberMultiply(string a, string b) {
auto res1 = split(a);
auto res2 = split(b);
int k1, k2, k3, k4;
k1 = res1.first * res2.first;
k2 = res1.second * res2.first;
k3 = res1.first * res2.second;
k4 = res1.second * res2.second;
return to_string(k1-k4) + "+" + to_string(k2+k3) + "i";
}
private:
pair<int, int> split(string s) {
string num1 = "", num2 = "";
int n = s.length();
int pos = s.find('+');
if (pos != s.npos) {
num1 = s.substr(, pos);
num2 = s.substr(pos+, n-pos-2);
}
int res1 = num1.length() != ? stoi(num1) : ;
int res2 = num2.length() != ? stoi(num2) : ;
return {res1, res2};
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/complex-number-multiplication
【LeetCode #539】最小时间差值
给定一个 24 小时制（小时:分钟）的时间列表，找出列表中任意两个时间的最小时间差并已分钟数表示。
示例 1： 输入: ["23:59","00:00"] 输出: 1
class Solution {
public:
int findMinDifference(vector<string>& timePoints) {
auto getMin = [](string& t1, string& t2) {
int i1 = stoi(t1.substr(, )) * + stoi(t1.substr(, ));
int i2 = stoi(t2.substr(, )) * + stoi(t2.substr(, ));
int t = abs(i1 - i2);
return min(t, * - t); // 可能瞬向差值，也可能是逆向差值
};
sort(timePoints.begin(), timePoints.end());
int len = timePoints.size();
if (len < ) return ;
int res = getMin(timePoints[], timePoints[len-1]);
for(int i = ; i < timePoints.size(); i++) {
res = min(res, getMin(timePoints[i], timePoints[i-1]));
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-time-difference
【LeetCode #540】有序数组中的单一元素
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1: 输入: [1,1,2,3,3,4,4,8,8] 输出: 2
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int i = ;
if (nums.size() == ) return nums[];
while(i+ < nums.size() && nums[i] == nums[i+]) { // 对i进行范围限制
i = i + ;
}
return nums[i];
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array