- 移动零
void moveZeroes(vector<int>& nums)
{
size_t front = 0;
size_t back = 0;
while(back < nums.size() && nums[back] != 0)
{
++back;
}
front = back++;
while(back < nums.size())
{
if(0 == nums[back])
{
++back;
}
else
{
swap(nums[front++], nums[back++]);
}
}
}
- 复写零
先找到最后一个被“复写”的数,然后从后向前完成“复写”操作。同时要注意处理一下边界情况。
void duplicateZeros(vector<int>& arr)
{
int front = 0;
int back = -1;
while(true)
{
if(0 == arr[front])
{
back += 2;
}
else
{
back += 1;
}
if(back == arr.size())
{
--back;
arr[back--] = 0;
--front;
break;
}
if(back == arr.size() - 1)
{
break;
}
++front;
}
while(front >= 0)
{
if(arr[front] == 0)
{
arr[back--] = 0;
arr[back--] = 0;
--front;
}
else
{
arr[back--] = arr[front--];
}
}
}
- 快乐数
// 方法一
bool isHappy(int n)
{
unordered_set<int> res({n});
int num = 0;
while(true)
{
while(n != 0)
{
num += pow((n % 10), 2);
n /= 10;
}
if(num == 1)
{
return true;
}
else if(res.find(num) != res.end())
{
return false;
}
else
{
res.insert(num);
}
n = num;
num = 0;
}
}
// 方法二
int Run(int num)
{
int ret = 0;
while(num != 0)
{
ret += pow((num % 10), 2);
num /= 10;
}
return ret;
}
bool isHappy(int n)
{
int slow = n;
int fast = n;
while (true)
{
slow = Run(slow);
fast = Run(fast);
fast = Run(fast);
if (slow == fast && fast == 1)
{
return true;
}
else if (slow == fast)
{
return false;
}
}
}
- 盛最多水的容器
int maxArea(vector<int>& height)
{
size_t left= 0;
size_t right = height.size() - 1;
size_t ret = (right - left) * min(height[left], height[right]);
size_t tmp = 0;
size_t area = 0;
do
{
if(height[left] < height[right])
{
tmp = height[left];
while(left < right && height[++left] <= tmp);
}
else
{
tmp = height[right];
while(left < right && height[--right] <= tmp);
}
if(left < right)
{
area = (right - left) * min(height[left], height[right]);
if(area > ret) ret = area;
}
}while(left < right);
return ret;
}
- 有效三角形的个数
利用单调性,先固定最大的数,在最大的数的左区间内使用双指针算法。
inline bool check(int side1, int side2, int side3)
{
return (side1 + side2 > side3);
}
int triangleNumber(vector<int>& nums)
{
if(nums.size() < 3) return 0;
sort(nums.begin(), nums.end());
size_t max_index = nums.size() - 1;
size_t left_index = 0;
size_t right_index = max_index - 1;
int ret = 0;
while(max_index > 1)
{
while(left_index < right_index)
{
if(check(nums[left_index], nums[right_index], nums[max_index]))
{
ret += (right_index - left_index);
--right_index;
}
else
{
++left_index;
}
}
--max_index;
left_index = 0;
right_index = max_index - 1;
}
return ret;
}
- 查找总价格为目标值的两个商品
vector<int> twoSum(vector<int>& price, int target)
{
size_t left = 0;
size_t right = price.size() - 1;
vector<int> v(2);
while(left < right)
{
if(price[left] + price[right] < target)
{
++left;
}
else if(price[left] + price[right] > target)
{
--right;
}
else
{
v[0] = price[left];
v[1] = price[right];
break;
}
}
return v;
}
- 三数之和
注意对去重的处理(跳过重复元素)。
vector<vector<int>> threeSum(vector<int>& nums)
{
vector<vector<int>> vv;
sort(nums.begin(), nums.end());
size_t max_index = nums.size() - 1;
size_t left_index = 0;
size_t right_index = max_index - 1;
while(max_index > 1)
{
while(left_index < right_index)
{
if(nums[left_index] + nums[right_index] + nums[max_index] > 0)
{
while(left_index < --right_index && nums[right_index] == nums[right_index + 1]);
}
else if(nums[left_index] + nums[right_index] + nums[max_index] < 0)
{
while(++left_index < right_index && nums[left_index] == nums[left_index - 1]);
}
else
{
vv.push_back({nums[left_index], nums[right_index], nums[max_index]});
while(left_index < --right_index && nums[right_index] == nums[right_index + 1]); // or ++left_index
}
}
while(--max_index > 1 && nums[max_index] == nums[max_index + 1]);
left_index = 0;
right_index = max_index - 1;
}
return vv;
}
- 四数之和
结合三数之和解题。
long long Sum(long long num1, long long num2, long long num3)
{
return num1 + num2 + num3;
}
void threeSum(vector<vector<int>>& vv, vector<int>& nums, size_t max_index, int max, int target)
{
size_t left_index = 0;
size_t right_index = max_index - 1;
while(max_index > 1)
{
while(left_index < right_index)
{
if(Sum(nums[left_index], nums[right_index], nums[max_index]) > target)
{
while(left_index < --right_index && nums[right_index] == nums[right_index + 1]);
}
else if(Sum(nums[left_index], nums[right_index], nums[max_index]) < target)
{
while(++left_index < right_index && nums[left_index] == nums[left_index - 1]);
}
else
{
vv.push_back({nums[left_index], nums[right_index], nums[max_index], max});
while(left_index < --right_index && nums[right_index] == nums[right_index + 1]);
}
}
while(--max_index > 1 && nums[max_index] == nums[max_index + 1]);
left_index = 0;
right_index = max_index - 1;
}
}
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> vv;
if(nums.size() < 4) return vv;
sort(nums.begin(), nums.end()); // 排序
size_t max_index = nums.size() - 1; // 固定第4个数
while(max_index > 2)
{
threeSum(vv, nums, max_index - 1, nums[max_index], target - nums[max_index]);
while(--max_index > 2 && nums[max_index] == nums[max_index + 1]);
}
return vv;
}