给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例：
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
class Solution {
public int pivotIndex(int[] nums) {
int sum=0;
for(int i=0;i
sum+= nums[i];
}
int left_num=0;
for(int i=0;i
sum-=nums[i];
if(left_num==sum){
return i;
}
left_num+=nums[i];
}
return -1;
}
}
思路： 先计算出集合之和sum,然后定义一个左边元素left_num,综合不断地减,left_num之和不断增加 当两者相等时,此时下标刚好为中心坐标2.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例： 输入: nums = [1,3,5,6], target = 2 输出: 1
class Solution {
public int searchInsert(int[] nums, int target) {
// 二分法
int left = 0, right = nums.length - 1;
while(left <= right){
// 防止 left+right 整型溢出
int mid =(right + left) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
left = mid + 1;
}else if(nums[mid] > target){
right = mid - 1;
}
}
return left;
}
}
思路： 采用二分法求解,定义一个left和rigth,两者相加除以2为其中心坐标,然后把中心坐标对应的值和目标值比较,如果小于目标值, left变为mid+1,如果大于同理,当left>rigth时表明数组中没有目标值,此时直接返回left值即为目标值按序插入下标3.合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。 示例： 输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
class Solution {
public int[][] merge(int[][] intervals) {
// 先按照区间起始位置排序
Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
// 遍历区间
int[][] res = new int[intervals.length][2];
int idx = -1;
for (int[] interval: intervals) {
// 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
// 则不合并，直接将当前区间加入结果数组。
if (idx == -1 || interval[0] > res[idx][1]) {
res[++idx] = interval;
} else {
// 反之将当前区间合并至结果数组的最后区间
res[idx][1] = Math.max(res[idx][1], interval[1]);
}
}
return Arrays.copyOf(res, idx + 1);
}
}
思路：
先通过Arrays.sort(数组名,(参数a,参数b)->a[0]-b[0]从大到小)排列之后,创建一个二维数组res,为intervals数组中数组的个数行2列.开始遍历intervals数组遍历出来的是一个一维数组interval(注意!!!)
先由inx=-1,进入第一个if中,把interval数组的[1,3]给到res[0],此时res[0]=[1,3],res={[1,3]},此时idx=0
接着遍历,此时interval=[2,6],用interval[0]即数组下标的开始数字和res[0][1]即数组下标的结束数字比较
如果后面的数组interval的起始大于前面的res的结尾的话不合并
反之合并使res[0][1]即数组的结尾数字等于后面数组interval的结尾6与res的结尾数字3比较取最大值,即合并成功res[0][1]=6
即res=[1,6]后面同理
最后res[0]=[1,6] res[1]=[8,10] res[2]=[15,18]
res={[1,6],[8,10],[15,18]}
Arrays.copyOf(原数组名,预期的新长度)
4.旋转矩阵
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 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]
]
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
//先沿斜对角线翻转
for(int i = 0;i < n;i ++){
for(int j = 0;j < i;j ++){
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
//再沿垂直竖线翻转
for(int i = 0;i < n;i ++){
for(int j = 0; j < n/2 ; j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n-j-1];
matrix[i][n-j-1] = temp;
}
}
}
}
思路： 根据观察得到想让矩阵顺时针旋转90°的话,并且开辟新空间,那么就让其先根据对角线翻转,再沿垂直竖线翻转即可得到旋转90°的矩阵5.零矩阵
编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。
示例1:
输入：
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出：
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例2：
输入：
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出：
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
public class Solution {
public void setZeroes(int[][] matrix) {
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
for(int i=0;i
for(int j=0;j
if(matrix[i][j]==0){
row[i]=1;
column[j]=1;
}
}
}
for(int i=0;i
for(int j=0;j
if(row[i]==1||column[j]==1){
matrix[i][j]=0;
}
}
}
}
}
思路： 每次找到等于零的那一个把对应的行和列都置零即可,但是会出现一个问题就是到最后所有的元素都变成零了; 因此，既然打算将整行和整列清零，因此并不需要标记录它是cell[2][4]（行2，列4），只需要知道行2有个元素为0，列4有个元素为0.不管怎样，整行和整列都要清零，又何必要记录零元素的确切位置 把是零的横纵坐标标记下来，最后根据横纵坐标使对应行和列都置为0
更新1
