今天写了几道LeetCode。虽然都不难，但是想到现在正是一天结束之时，也是对"收获"(划水)的一天进行总结的时候了，那就分享下今天给我留下印象的题吧
三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
分析与解题
这个题不难，最简单的方法就是暴力搜索了，注意去除重复的vectort<int>
当然，在搜索前，为了避免重复，应该对 nums 进行升序排序
之后进行穷举，最后去重复的元素
这里先简单介绍下vector排序和去重复元素
我们知道，c++里面有一个sort()函数，它不仅仅可以对数组进行排序，而它对vector进行的排序的操作如下：
sort(result.begin(),result.end());
其中，result是一个vector类型的变量。
再说说去重复，使用如下：
result.erase(unique(result.begin(),result.end()),result.end());
两者结合起来，便是对vector进行去重了。
回到本题，理论上，我们的思路是没问题的，结果如何呢？
先展示程序：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
for(int k=j+1;k<nums.size();k++){
vector<int> temp;
if(nums[i]+nums[j]+nums[k]==0){
temp.push_back(nums[i]);
temp.push_back(nums[j]);
temp.push_back(nums[k]);
sort(temp.begin(),temp.end());
result.push_back(temp);
}
}
}
}
sort(result.begin(),result.end());
result.erase(unique(result.begin(),result.end()),result.end());
return result;
}
};
测试了一些样例，没有问题，那么系统判别结果如何呢？
又超时了。。。
暴力搜索当然是一种好方法，它能得到预期结果，但是呢，绝大多情况下，不是最佳方法
那如何改进呢？
分析过程，我们可以发现，在搜索过程中，很多检索是不需要的
例如，在已经排好序的vector中，如果说第一个加数nums[i]大于0了，那么无论第二，三个数为多少，三数之和不可能为0，后面的检索都是不必要的，鉴于此，我们对原程序进行改进
程序如下：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> result;
for(int i=0;i<nums.size();++i){
if(nums[i]>0){
break;
}
if(i && nums[i]==nums[i-1]){
continue;
}
int j=i+1;
int k=nums.size()-1;
while(j<k){
if(nums[i]+nums[j]+nums[k]==0){
vector<int> temp={nums[i],nums[j],nums[k]};
result.push_back(temp);
while(j+1<nums.size()&&nums[j+1]==nums[j]){
++j;
}
while(k-1>=0 && nums[k-1]==nums[k]){
--k;
}
++j,--k;
}else if(nums[j]+nums[k]+nums[i]>0){
--k;
}else{
++j;
}
}
}
return result;
}
};
结果如下：
因为去除了很多不必要的循环，因此也就不会超时了。那么下一题！
旋转图像
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-image
分析与解题
如果没有任何要求，这题很简单，此处有空间上的限制，但也不难，这里只介绍下个人的思路
比较好的处理方式是一圈圈的旋转，从里到外的旋转
基于此，有两个方法：
第一个是每一圈以一行或者一列为单位进行交换，每一圈需要四次交换，需要一个圈边长大小的vector
第二个是每一圈的元素一次顺时针移动一位，移动次数视圈所在的位置来定，只需要一个int大小空间。
鉴于题目要求，不确定第一张方法是否违反了题意，因此从第二种方法出发
需要注意每次移动的边界条件，本人在做的时候，因为边界条件而浪费了一些时间
下面直接展示程序：
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
for(int i=0;i<matrix.size()/2;i++){
for(int j=0;j<matrix.size()-2*i-1;j++){
fun(matrix,i);
}
}
}
void fun(vector<vector<int>>& matrix,int x_){
int length=matrix.size()-2*x_;
int temp=matrix[x_][x_];
for(int i=x_+1;i<x_+length;i++){
matrix[i-1][x_]=matrix[i][x_];
}
for(int i=x_+1;i<x_+length;i++){
matrix[x_+length-1][i-1]=matrix[x_+length-1][i];
}
for(int i=x_+length-1;i>=x_+1;i--){
matrix[i][x_+length-1]=matrix[i-1][x_+length-1];
}
for(int i=x_+length-1;i>=x_+1;i--){
if(i==x_+1){
matrix[x_][i]=temp;
}else{
matrix[x_][i]=matrix[x_][i-1];
}
}
}
};
提交结果：
看上去结果还不错！
