396旋转函数

由于昨天也做了旋转函数，现在很自然地就想用昨天的函数，然后暴力求解

class Solution {
public:
    void rotate(vector<int>& nums, int k){
        int n = nums.size();
        k = k % n;
        int count = gcd(n, k);
        for(int i = 0; i < count; i++){
            int cur = i;
            int pre = nums[i];
            do{
                int next = (cur + k) % n;
                swap(nums[next], pre);
                cur = next;
            }while(cur != i);
        }
    }

    int maxRotateFunction(vector<int>& nums) {
        int maxi = INT_MIN;
        for(int i = 0; i < nums.size(); i++){
            int f = 0;
            if( i == 0);
            else 
              rotate(nums, 1);//每次都是在前面的基础上的，每次只转了1        
            for(int k = 0; k < nums.size(); k++){
                f += k * nums[k];
            }
            if(f > maxi) maxi = f;
        }
        return maxi;
    }
};

这样是n平方，超时了…

更好的解法肯定是不能用暴力，计算前后两次的区别，

F(0)= A[0] * 0 +A[1] * 1 +A[2] * 2 + … A[n-2] * (n-2) + A[n-1] * (n-1)

F(1)= A[n-1] * 0+ A[0] * 1 +A[1] * 2 +A[2] * 3 + … A[n-2] * (n-1)

F(1)-F(0)= -A[n-1] * (n-1) + A[0] + A[1] + … A[n-2]

     = -A[n-1]*n +sum

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        long long sum = 0;
        long long f = 0;
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i];
            f += i * nums[i];//计算f0;
        }
        int maxi = f;
        for(int i = 1; i < nums.size(); i++){
           f += sum - nums.size() * nums[nums.size() - i];
           if(f > maxi) maxi = f;
        }

    return maxi;
    }
};

这样的话就是O(N),空间复杂度O(1),这里要注意sum的值要用长整型

54螺旋矩阵

这题好像也不需要什么算法和想法，设置好方向和边界一个一个push就行了

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int left = 0;
        int right = matrix[0].size() - 1;
        int top = 0;
        int bottom = matrix.size() - 1;
        while(left <= right && top <= bottom){
             for(int col = left; col <= right; col ++){  //左上到右上
                 res.push_back(matrix[top][col]);
             }

             for(int row = top + 1; row <= bottom; row++){
                 res.push_back(matrix[row][right]); //右上到右下
             }
             
             if(left < right && top < bottom){
                for(int col = right - 1; col >= left; col--){
                  res.push_back(matrix[bottom][col]); //右下到左下
                }

                for(int row = bottom - 1; row > top; row--){
                   res.push_back(matrix[row][left]); //左下到左上
                }
             }
         
             left++;
             right--;
             top++;
             bottom--;
        }
        return res;
    }
};

时间复杂度O(mn),空间复杂度O(1)