相隔为 1 的编辑距离
寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]
进阶：你可以实现时间复杂度为 O(logN) 的解决方案吗？
解题思路：按照常规的想法以及对峰值的定义来说，这道题的解法就是遍历寻找，知道一个点的左右两边都小于该点，则返回该点。
但是这样的做法时间复杂度是 O(N), 是达不到题目的要求的，而且这个时间复杂度已经明示要用二分法来解决。
那是要怎么用二分法呢？这里就需要提到题目的两个 tips，这两个条件非常的重要，也是使用二分法的充分条件。
- nums[-1] = nums[n] = -∞
- nums[i] != nums[i + 1]
这两个限制条件的存在，保证了数组要不是递增就是递减，且在这个递增递减的序列中必存在峰值，所以这也就是表明了可以利用二分法去找到某一段的峰值点。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int start = 0, end = nums.size() - 1;
while(start < end) {
int mid = start + (end - start) / 2;
if(nums[mid] < nums[mid + 1]) {
start = mid + 1;
}else {
end = mid;
}
}
return start;
}
};
缺失的区间
最大间距
给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
如果数组元素个数小于 2，则返回 0。
示例 1:
输入: [3,6,9,1]
输出: 3
解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
示例 2:
输入: [10]
输出: 0
解释: 数组元素个数小于 2，因此返回 0。
说明:
你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
解题思路：首先通过要求
- 线性时间复杂度：排除排序
- 线性空间复杂度：利用空间换时间
事实证明，我还是太狭隘了，基数排序就能满足，不过基数排序是针对整数的排序，而恰好题目要求的非负整数完全契合。
不过这里更推荐使用利用更好的方法，利用桶的思想，我们可以将一组数组依据最大值、最小值以及数组的个数划分成 bucketSize 个桶。
那么如何找到这个 bucketSize 呢？下面请看分析：
假设数组有 n 个值，最大值为 max， 最小值为 min。
- 两个相邻的数字最大间距 d 肯定大于等于 (max−min) / (n−1)
- 然后可以将桶的大小设为 (max−min) / (n−1)，这样的话就能保证元素之间的最大间距一定不会出现在某个桶的内部，而一定会出现在不同桶当中。
- 维护每个桶的最大值与最小值，遍历桶得到结果
//利用基数排序
class Solution {
public:
int maximumGap(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return 0;
}
int exp = 1;
vector<int> buf(n);
int maxVal = *max_element(nums.begin(), nums.end());
while (maxVal >= exp) {
vector<int> cnt(10);
for (int i = 0; i < n; i++) {
int digit = (nums[i] / exp) % 10;
cnt[digit]++;
}
for (int i = 1; i < 10; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = 0; i < n; i++) {
int digit = (nums[i] / exp) % 10;
buf[cnt[digit] - 1] = nums[i];
cnt[digit]--;
}
copy(buf.begin(), buf.end(), nums.begin());
exp *= 10;
}
int ret = 0;
for (int i = 1; i < n; i++) {
ret = max(ret, nums[i] - nums[i - 1]);
}
return ret;
}
};
//利用桶思想
class Solution {
public:
int maximumGap(vector<int>& nums) {
int mMax = *max_element(nums.begin(), nums.end());
int mMin = *min_element(nums.begin(), nums.end());
int n = nums.size();
if(n < 2) return 0;
int d = max(1, (mMax - mMin) / (n - 1));
int bucketSize = (mMax - mMin) / d + 1;
vector<pair<int, int>> bucket (bucketSize, {-1, -1});
for(auto i : nums) {
int index = (i - mMin) / d;
if (bucket[index].first == -1) {
bucket[index].first = bucket[index].second = i;
} else {
bucket[index].first = min(bucket[index].first, i);
bucket[index].second = max(bucket[index].second, i);
}
}
int res = 0;
int prev = -1;
for (int i = 0; i < bucketSize; i++) {
if (bucket[i].first == -1) continue;
if (prev != -1) {
res = max(res, bucket[i].first - bucket[prev].second);
}
prev = i;
}
return res;
}
};
比较版本号
给你两个版本号 version1 和 version2 ，请你比较它们。
版本号由一个或多个修订号组成，各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。
比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。
返回规则如下：
- 如果 version1 > version2 返回 1，
- 如果 version1 < version2 返回 -1，
- 除此之外返回 0。
示例 1：
输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"
示例 2：
输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"
示例 3：
输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2
示例 4：
输入：version1 = "1.0.1", version2 = "1"
输出：1
示例 5：
输入：version1 = "7.5.2.4", version2 = "7.5.3"
输出：-1
提示：
1 <= version1.length, version2.length <= 500
version1 和 version2 仅包含数字和 '.'
version1 和 version2 都是 有效版本号
version1 和 version2 的所有修订号都可以存储在 32 位整数 中
解题思路：这道题的解法就是去比较相同位置的大小，以 ‘.’ 分割，依次去两个字符串的数字去对比，若相等则继续比较，不等则返回结果。
class Solution {
public:
int compareVersion(string version1, string version2) {
int fir = 0, sec = 0;
while(fir < version1.size() || sec < version2.size()) {
int f = 0, s = 0;
if(fir < version1.size()) {
string tmp;
while(version1[fir] != '.' && fir != version1.size()) {
tmp += version1[fir];
fir++;
}
f = atoi(tmp.c_str());
fir++;
}
if(sec < version2.size()) {
string tmp;
while(version2[sec] != '.' && sec != version2.size()) {
tmp += version2[sec];
sec++;
}
s = atoi(tmp.c_str());
sec++;
}
cout << f << " " << s << endl;
if(f < s) {
return -1;
}else if(f > s) {
return 1;
}
}
return 0;
}
};
分数到小数
给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以 字符串形式返回小数 。
如果小数部分为循环小数，则将循环的部分括在括号内。
如果存在多个答案，只需返回 任意一个 。
对于所有给定的输入，保证 答案字符串的长度小于 10^4 。
示例 1：
输入：numerator = 1, denominator = 2
输出："0.5"
示例 2：
输入：numerator = 2, denominator = 1
输出："2"
示例 3：
输入：numerator = 2, denominator = 3
输出："0.(6)"
示例 4：
输入：numerator = 4, denominator = 333
输出："0.(012)"
示例 5：
输入：numerator = 1, denominator = 5
输出："0.2"
提示：
-2^31 <= numerator, denominator <= 2^31 - 1
denominator != 0
解题思路：思路和小学学的除法是一样的，两个数相除求得商，将商加入结果，余数乘 10 继续相除，直到找到循环部分或者除完。
需要注意的地方有
- int 类型溢出，转成 long long 去解决
- 正负号，最开始判断然后转成正数计算
class Solution {
public:
string fractionToDecimal(int numerator, int denominator) {
map<int, int> numPos;
string res;
long long num = static_cast<long long>(numerator);
long long denom = static_cast<long long>(denominator);
if(num * denom < 0) {res = "-";};
num = abs(num);
denom = abs(denom);
long long beforePos = num / denom;
num = (num - denom * beforePos)*10;
res = res + to_string(beforePos) + ".";
int pos = res.size();
while(num != 0) {
int tmp = num / denom;
// cout << res << " " << num << endl;
if(numPos.find(num) != numPos.end()) {
res.insert(numPos[num], "(");
res.insert(res.end(), ')');
break;
}else {
numPos[num] = pos;
res += to_string(tmp);
}
num = num % denom * 10;
pos++;
}
if(*(res.end() - 1) == '.'){
res.erase(res.end() - 1);
}
return res;
}
};
两数之和 II - 输入有序数组
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
提示：
2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
numbers 按 递增顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案
解题思路，利用 map 记录当前节点的需要匹配的数字以及当前节点的 index，在遍历数组的时候检查 map 是否包含当前节点的值。
和第一道题一模一样，记忆深刻。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> res;
unordered_map<int, int> resPos;
for(int i = 0; i < numbers.size(); ++i) {
if(resPos.find(numbers[i]) != resPos.end()) {
res.push_back(resPos[numbers[i]] + 1);
res.push_back(i + 1);
break;
}
resPos[target - numbers[i]] = i;
}
return res;
}
};
Excel表列名称
给定一个正整数，返回它在 Excel 表中相对应的列名称。
例如，
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...
示例 1:
输入: 1
输出: "A"
示例 2:
输入: 28
输出: "AB"
示例 3:
输入: 701
输出: "ZY"
解题思路：类似于进制转换，不过值的注意的地方是，余数是从 1-26，所以当是 26 整数倍的时候余数为 0，这里需要特殊处理。
我处理的方式就是先把需要转换的十进制数字转换成二十六进制，最后单独去处理位数为 0 的位，当遇到位数为 0 的时候，需要将该为设置为 ‘Z’,并将其前置位减一，若前置位被减到 0 时，往前移动，直到首位。
class Solution {
public:
string res;
void mergeRes(int num) {
char tmp = 'A' + (num - 1);
res.insert(res.begin(), tmp);
}
void getChar(int num) {
if(num <= 26) {
mergeRes(num);
return;
}
int re = num % 26;
mergeRes(re);
re = num / 26;
getChar(re);
}
string convertToTitle(int columnNumber) {
res.clear();
getChar(columnNumber);
for(int i = 1; i < res.size(); ++i) {
int j = i;
while(j != 0 && res[j] == 'A' - 1) {
res[j-1] = res[j-1] - 1;
res[j] = 'Z';
j = j-1;
}
}
if(*res.begin() == 'A' - 1) res.erase(res.begin());
return res;
}
};
多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2
进阶：
尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
解题思路：关键在于多数元素出现次数是大于 [ n/2 ] 的元素。说明数组里面有大于一半的元素是答案。那么怎么去筛选出这个答案呢？
利用投票的思想，每个元素都投自己，那么票数最多的肯定是最终的答案，但是这样的话是需要额外空间去记录票数的，空间复杂度不符合标准。
投票的结果就是成功选举，那么是不是可以不记录票数，直接让候选人当选，然后利用支持反对票对当选人进行操作呢？
可以知道的是，最终候选人是占有半数以上的票的，所以只要是投票选择，那么当选人必是这个多数元素。
在这里维护两个值，一个代表当前的候选人(candidate)以及该候选人的票数(count)；
然后遍历数组，若当前元素支持候选人，则票数加 1， 否则减 1，当票数为 -1 时则表明候选人下选，让新候选人上任票数重置为 1。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = -1;
int count = 0;
for (int num : nums) {
if (num == candidate)
++count;
else if (--count < 0) {
candidate = num;
count = 1;
}
}
return candidate;
}
};
