1. 数组
1.1 最大连续 1 的个数
给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
思路
一次遍历模拟即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int ans=0,total=0;
for(int num:nums){
if(num==1){
total++;
}else{
ans=Math.max(ans,total);
total=0;
}
}
ans=Math.max(ans,total);
return ans;
}
}
|
1.2 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
思路
Boyer-Moore 投票算法。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int majorityElement(int[] nums) {
int count=0;
int candidate=0;
for(int num:nums){
if(count==0){
candidate=num;
}
count+=(candidate==num)?1:-1;
}
return candidate;
}
}
|
1.3 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
思路
将非零数移到数组前面，后面补0。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public void moveZeroes(int[] nums) {
int index=0;
int n=nums.length;
for(int i=0;i<n;i++){
if(nums[i]!=0){
nums[index++]=nums[i];
}
}
for(int i=index;i<n;i++){
nums[i]=0;
}
}
}
|
2. 矩阵
2.1 转置矩阵
给你一个二维整数数组 matrix， 返回 matrix 的 转置矩阵 。
矩阵的 转置 是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。
思路
矩阵模拟，即将行变成列，列变成行。
注意：矩阵行和列数可能不等。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int[][] transpose(int[][] matrix) {
int n=matrix.length,m=matrix[0].length;
int[][] ans=new int[m][n];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
ans[j][i]=matrix[i][j];
}
}
return ans;
}
}
|
2.2 矩阵对角线元素的和
给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。
思路
按照题意进行模拟即可。
注意：判断n的奇偶性。
代码
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int diagonalSum(int[][] mat) {
int ans=0;
int n=mat.length;
for(int i=0;i<n;i++){
ans+=mat[i][i]+mat[i][n-i-1];
}
return (n&1)==1?ans-mat[n/2][n/2]:ans;
}
}
|
2.3 重塑矩阵
在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。
给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。
如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
思路
二维矩阵表示成一维矩阵后，将其转为目标矩阵。
若m为原矩阵的行数，n为原矩阵的列数，那么元素总数为m×n，对于第x个元素，在目标矩阵中的位置即为第x/c行，第x%c列，因为每行有c个数，转换后即得到目标数组。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[][] matrixReshape(int[][] mat, int r, int c) {
int n=mat.length,m=mat[0].length;
if(n*m!=r*c) return mat;
int[][] ans=new int[r][c];
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
int x=i*c+j;
ans[i][j]=mat[x/m][x%m];
}
}
return ans;
}
}
|
2.4 托普利茨矩阵
给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。
如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。
思路
按照题意进行模拟。
题目要求判断从左上到右下的斜线是否符合要求，即首先从左下角开始向上，到达左上角后再往右移动，最终到达右上角。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
int n=matrix.length,m=matrix[0].length;
int left=0,bottom=n-1;
while(left<m&&bottom>=0){
int i=bottom,j=left;
while(i<n&&j<m){
if(matrix[i][j]!=matrix[bottom][left]){
return false;
}
i++;
j++;
}
if(bottom>0){
bottom--;
}else{
left++;
}
}
return true;
}
}
|