[LeetCode：数组篇4-10]：

1.存在重复

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

 class Solution {
public:int singleNumber(vector<int>& nums) {int Size=nums.size();std::sort(nums.begin(),nums.end());int samenum=0;for(int i=0;i<Size-1;i++)if(nums[i]!=nums[i+1]){if(samenum==0)return nums[i];elsesamenum=0;}  elsesamenum++;return nums[Size-1];        }
};

5.两个数组的交集 II

给定两个数组，写一个方法来计算它们的交集。

例如:给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

注意：

•    输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
•    我们可以不考虑输出结果的顺序。

跟进:

• 如果给定的数组已经排好序呢？你将如何优化你的算法？
• 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
• 如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2){vector<int> out;if(nums1.size()==0||nums2.size()==0)return out;std::sort(nums1.begin(),nums1.end());std::sort(nums2.begin(),nums2.end());int temp=0;for(int i=0;i<nums1.size();i++){for(int j=temp;j<nums2.size();j++){if(nums1[i]>nums2[j])continue;else if(nums1[i]==nums2[j]){out.push_back(nums1[i]);temp=j+1;break;}elsebreak;}}return out;}
};

6.

给定一个非负整数组成的非空数组，在该数的基础上加一，返回一个新的数组。

最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

class Solution {
public:vector<int> plusOne(vector<int>& digits) {vector<int>out(digits);//printf("%d ", *(digits.end()-1));*(out.end()-1)= *(out.end()-1)+1;//printf("%d ", *(digits.end()-1));if(*(out.end()-1)!=10)return out;elsefor(int i=out.size()-1;i>=0;i--){if(out[i]==10){out[i]=0;if((i-1)>=0)out[i-1]++; elseout.insert(out.begin(),1);}}return out;}
};

7:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

//先将非0数移到首部，尾部补零
class Solution {
public:void moveZeroes(vector<int>& nums) {int len=nums.size();int index=0;for(int i=0;i<len;i++){if(nums[i]!=0){nums[index]=nums[i];index++;}  }for(int i=index;i<len;i++)nums[i]=0;//return nums;}
};

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int i;vector<int> result;vector<int> sortvec(nums);if(nums.size() < 2)return result;int stard=0;int end=nums.size()-1;sort(sortvec.begin(),sortvec.end());while(stard<end){if(sortvec[stard]+sortvec[end]<target)stard++;else if(sortvec[stard]+sortvec[end]>target)end--;elsebreak;}if(stard>=end)return result;for(i=0;i<nums.size();i++){if(nums[i]==sortvec[stard]){stard=i;result.push_back(stard);break;} }for(i=nums.size()-1;i>=0;i--){if(nums[i]==sortvec[end]){end=i;result.push_back(end);break;} }return result;}
};

9.

class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {for (size_t i = 0; i < 9; i++){for (size_t j = 0; j < 9; j++){if (board[i][j] == '.') {continue;}// 行for (size_t k = j + 1; k < 9; k++){if (board[i][j] == board[i][k]) {return false;}}// 列for (size_t k = i + 1; k < 9; k++){if (board[i][j] == board[k][j]) {return false;}}// 块for (size_t k1 = i - i % 3; k1 % 3 != 0 || k1 == i - i % 3; k1++){for (size_t k2 = j; k2 % 3 != 0 || k2 == j; k2++){if (board[i][j] == board[k1][k2] && k1 != i && k2 != j) {return false;}}}}}return true;
}
};

10.

给定一个 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]
]

reverse 函数可以反转vector内容  如 1 2 3 4    ------得到 4 3 2 1 .

swap 函数是交换两个数 

过程是先reverse   如 

1   2

3   4

得到 反转列的结果。

3   4

1   2

再转置得到

3   1

4    2

完美。

class Solution {
public:void rotate(vector<vector<int>>& matrix) {reverse(matrix.begin(), matrix.end());for (int i = 0; i < matrix.size(); ++i) {for (int j = i + 1; j < matrix[i].size(); ++j)swap(matrix[i][j], matrix[j][i]);}}
};

另一种方法： 先转置再反转行

class Solution {
public:void rotate(vector<vector<int>>& matrix) {vector<vector<int>> out(matrix);int col=matrix.size();printf("%d ",col);for(int i=0;i<col;i++)for(int j=0;j<col;j++)if(i!=j)matrix[j][i]=out[i][j];vector<vector<int>> out2(matrix);for(int i=0;i<col;i++)for(int j=0;j<col;j++)matrix[i][j]=out2[i][col-j-1];}
};