数组

1.寻找数组的中心索引
给定一个整数类型的数组 nums，编写一个能够返回数组 “中心索引” 的方法。
中心索引：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果不存在中心索引，返回 -1。如果有多个中心索引，返回最左边一个。

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sumLeft = 0;
        int sum = 0;
        for(int i=0; i<nums.size(); i++)
            sum += nums[i];
        for(int j=0; j<nums.size(); j++)
        {
          if(sumLeft*2 == sum - nums[j])
              return j;
            sumLeft += nums[j];
        }
        return -1;
    }
};

2.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。假设数组中无重复元素。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while(l < r) {
            int mid = l + r >> 1;
            if(nums[mid] == target) return mid; //最求简洁可以删除此行，追求时间可以加入此行
            nums[mid] < target ? l = mid + 1 : r = mid;
        }
        return l;
    }
};

3.旋转矩阵
由 N × N 矩阵表示的图像，每个像素的大小为 4 字节。设计一种算法，将图像旋转 90 度。不占用额外内存空间
[
[1,2,3],
[4,5,6],
[7,8,9]
],
使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
};

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        auto matrix_new = matrix;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        matrix = matrix_new;
    }
};