C++ isalpha、isalnum、islower、isupper用法
isalnum()用来判断一个字符是否为数字或者字母，判断一个字符是否属于a~z || A ~ Z||0 ~ 9。
class Solution {
public:
bool isPalindrome(string s) {
int left_index = 0;
int right_index = s.size() - 1;
while(left_index < right_index)
{
//当left_index < right_index 且 s[left_index]不是数字或字母，往右进一
while(left_index < right_index && !isalnum(s[left_index]))
++left_index;
//当left_index < right_index 且 s[right_index]不是数字或字母，往左进一
while(left_index < right_index && !isalnum(s[right_index]))
--right_index;
if(left_index < right_index)
if(tolower(s[left_index]) != tolower(s[right_index]))
return false;
++left_index;
--right_index;
}
return true;
}
};
1.1.2 891 · 有效回文 II
class Solution {
public:
bool validPalindrome(string &s) {
int left_index = 0;
int right_index = s.size() - 1;
while(left_index < right_index)
{
if(s[left_index] != s[right_index])
//两种情况有一种是true即可
return isValid(s, left_index, right_index - 1) ||
isValid(s, left_index + 1, right_index);
++left_index;
--right_index;
}
return true;
}
private:
bool isValid(string s, int left_index, int right_index)
{
while(left_index < right_index)
{
if(s[left_index] != s[right_index])
return false;
++left_index;
--right_index;
}
return true;
}
};
1.2TwoSum型
1.2.1 1. 两数之和
暴力枚举
class Solution {
public:
vector twoSum(vector& nums, int target) {
for(int i = 0; i < nums.size(); ++i)
{
for(int j = i + 1; j < nums.size(); ++j)
{
if(nums[i] + nums[j] == target)
return {i, j};
}
}
return {};
}
};
复杂度分析
- 时间复杂度：O(N^2)，其中 N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
- 空间复杂度：O(1)。
哈希表
创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配
class Solution {
public:
vector twoSum(vector& nums, int target) {
unordered_map hash_map;
for(int i = 0; i < nums.size(); ++i)
{
auto it = hash_map.find(target - nums[i]);
if(it != hash_map.end())
return {it->second, i};
hash_map[nums[i]] = i;
}
return {};
}
};
复杂度分析
- 时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1)地寻找 target - x。
- 空间复杂度：O(N)，其中 NN 是数组中的元素数量。主要为哈希表的开销。
使用二分法优化到 O(nlogn)
class Solution {
public:
vector twoSum7(vector &nums, int target) {
if(nums.size() < 2)
return {-1, -1};
target = abs(target);//将数据转成绝对值
for(int i = 0; i < nums.size(); i++)
{
int j = binarySearch(nums, i + 1, nums.size() - 1, target + nums[i]);
if(j != -1)
return {nums[i], nums[j]};
}
return {-1, -1};
}
private:
int binarySearch(vector& nums, int left_index, int right_index, int target)
{
while(left_index <= right_index)
{
int middle_index = left_index + ((right_index - left_index) >> 1);
if(nums[middle_index] == target)
return middle_index;
else if(nums[middle_index] < target)
left_index = middle_index + 1;
else if(nums[middle_index] > target)
right_index = middle_index - 1;
}
return -1;
}
};
同向双指针
class Solution {
public:
vector twoSum7(vector &nums, int target) {
if(nums.size() < 2)
return {-1, -1};
target = abs(target);
int j = 1;
for(int i = 0; i < nums.size(); i++)
{
j = max(j, i + 1);
while(j < nums.size() && nums[j] - nums[i] < target)
j++;
if(j >= nums.size())
break;
if(nums[j] - nums[i] == target)
return {nums[i], nums[j]};
}
return {-1, -1};
}
};
class Solution {
public:
int stringCount(string &str) {
if("" == str)
return 0;
int j = 1, result = 0;
for(int i = 0; i < str.length(); i++)
{
if(str[i] != '0')
continue;
j = max(j, i + 1);
while(j < str.length() && str[j] == '0')
j++;
result += j - i;
}
return result;
}
};
2.3 数组去重
27. 移除元素
class Solution {
public:
int removeElement(vector& nums, int val) {
int left_index = 0;//左指针从0开始，指向下一个将要赋值的位置
//右指针从0开始，指向当前要处理的元素
for(int right_index = 0; right_index < nums.size(); right_index++)
{
//右指针指向的元素不等于val，是输出数组的元素
if(val != nums[right_index])
{
//将右指针指向的元素复制到左指针位置，然后将左右指针同时右移
nums[left_index++] = nums[right_index];
}
//右指针指向的元素等于val，不在输出数组里，左指针不动，右指针右移一位
}
//left_index就是输出数组的长度
return left_index;
}
};
双指针优化（相向双指针）
class Solution {
public:
int removeElement(vector& nums, int val) {
int left_index = 0;
int right_index = nums.size();
while(left_index < right_index)
{
//左指针等于val，将右指针元素复制到左指针的位置，右指针左移一位
if(nums[left_index] == val)
{
nums[left_index] = nums[right_index - 1];
right_index--;
}
else//左指针不等于val,左指针右移一位，右指针不动
left_index++;
}
return left_index;
}
};
26. 删除有序数组中的重复项
class Solution {
public:
int removeDuplicates(vector& nums) {
if(0 == nums.size())
return 0;
//删除重复元素后也至少剩下一个元素
int left_index = 1, right_index = 1;
while(right_index < nums.size())
{
//说明nums[right_index]和之前的元素都不同
if(nums[right_index] != nums[right_index - 1])
nums[left_index++] = nums[right_index];
++right_index;
}
//从nums[0]到nums[leftIndex - 1]的每个元素都不相同
return left_index;
}
};
80. 删除有序数组中的重复项 II
class Solution {
public:
int removeDuplicates(vector& nums) {
if(nums.size() <= 2)
return nums.size();
//数组的前两个数必然会被保留
int left_index = 2, right_index = 2;
while(right_index < nums.size())
{
//检查上上个应该被保留的元素nums[left_index - 2]是否和当前待检查元素nums[right_index]相同
if(nums[left_index - 2] != nums[right_index])
{
nums[left_index++] = nums[right_index];
}
++right_index;
}
//从nums[0]到nums[left_index - 1]的每个元素都不相同
return left_index;
}
};
通用扩展
class Solution {
public:
int removeDuplicates(vector& nums) {
return generalRemoveFunction(nums, 2);
}
private:
//最多保留k位相同的数字
int generalRemoveFunction(vector& nums, int k)
{
//慢指针从0开始
int left_index = 0;
//快指针遍历整个数组
for(int right_index = 0; right_index < nums.size(); right_index++)
{
//检查被保留的元素nums[left_index - k]是否和当前待检查的元素nums[right_index]相同
if(left_index < k || nums[left_index - k] != nums[right_index])
nums[left_index++] = nums[right_index];
}
//从nums[0]到nums[left_index - k]的每个元素都不相同
return left_index;
}
};
3.背向双指针
参考资料
1.一起学计算机
2.九章算法
3.代码随想录
