66
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n=digits.size();
int d=0;
for(int i=n-1;i>=0;i--)
{
d+=digits[i]+((i==n-1)?1:0);
digits[i]=d%10;
d=d/10;
if(!d)break;
}
if(d){
digits.resize(n+1);
for(int i=n;i>0;i--)
digits[i]=digits[i-1];
digits[0]=1;
}
return digits;
}
};
724
class Solution {
public:
int pivotIndex(vector<int>& nums) {
double sum=0;
int n=nums.size();
for(auto i:nums)sum+=i;
int left,right=0;
left=0;
right=sum-left-nums[0];
if(left==right)return 0;
for(int j=1;j<n;j++)
{
left=left+nums[j-1];
right=sum-left-nums[j];
if(left==right)return j;
}
return -1;
}
};
189
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n=nums.size();
k%=n;
vector<int>temp(n);
for(int i=0;i<n;i++)
{
temp[(i+k)%n]=nums[i];
}
copy(temp.begin(),temp.end(),nums.begin());
}
};
48旋转图像
思路：先对角元素交换，再同一行中左右两侧对应位置交换元素。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n=matrix.size();
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
swap(matrix[i][j],matrix[j][i]);
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n/2;j++)
{
swap(matrix[i][j],matrix[i][n-1-j]);
}
}
}
};
54.螺旋矩阵
思路：模拟矩阵的螺旋运动方式，其中的细节真的很drama，改了很多遍，尤其是右侧，下侧，左侧的补充限制条件。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m=matrix.size(),n=matrix[0].size();
vector<int>res;
for(int i=0;i<m-i;i++)
{
for(int j=i;j<=n-1-i;j++)
{
res.push_back(matrix[i][j]);
}
for(int j=i+1;j<m-i&&n-1-i>=i;j++)
{
res.push_back(matrix[j][n-1-i]);
}
for(int j=n-2-i;j>=i&&m-1-i>i;j--)
{
res.push_back(matrix[m-1-i][j]);
}
for(int j=m-2-i;j>i&&i<n-1-i;j--)
{
res.push_back(matrix[j][i]);
}
}
return res;
}
};
498.对角线遍历
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
vector<int>res;
int m=mat.size();
if(mat.size()==0)return res;
int n=mat[0].size();
if(n==0)return res;
bool flag=true;
for(int i=0;i<m+n;i++){
int xm=flag?m:n;
int xn=flag?n:m;
int x=(i<xm)?i:xm-1;
int y=i-x;
while(x>=0&&y<xn){
res.push_back(flag?mat[x][y]:mat[y][x]);
x--;
y++;
}
flag=!flag;
}
return res;
}
};
