leetcode 剑指offer刷题归类之 三 数组篇
----------------------------------------------------------------------------
41. 缺失的第一个正数
public int firstMissingPositive(int[] nums) {
if(nums == null || nums.length == 0){
return 1;
}
int len = nums.length;
for (int i = 0; i < len ; i++) {
while (nums[i] >0 && nums[i] <= len && nums[i]!=nums[nums[i]-1]){
swap(nums,i,nums[i]-1);
}
}
int res = 1;
for (int i = 0; i < len; i++) {
if(nums[i] != i+1){
break;
}
res++;
}
return res;
}
private void swap(int[] nums,int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
} leetcode 48. 旋转图像
public void rotate(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return;
}
int rowStart = 0;
int colStart = 0;
int rowEnd = matrix.length - 1;
int colEnd = matrix[0].length - 1;
while (rowStart < rowEnd) {
help(matrix,rowStart,colStart,rowEnd,colEnd);
rowStart++;
colStart++;
rowEnd--;
colEnd--;
}
}
private void help(int[][] matrix, int rowStart, int colStart, int rowEnd, int colEnd) {
int time = rowEnd - rowStart ;
for (int i = 0; i < time; i++) {
int tmp = matrix[rowStart][colStart + i];
matrix[rowStart][colStart + i] = matrix[rowEnd - i][colStart];
matrix[rowEnd - i][colStart] = matrix[rowEnd][colEnd - i];
matrix[rowEnd][colEnd - i] = matrix[rowStart + i][colEnd];
matrix[rowStart + i][colEnd] = tmp;
}
} leetcode 54. 螺旋矩阵
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return list;
}
int startx = 0;
int starty = 0;
int endx = matrix.length-1;
int endy = matrix[0].length-1;
while (startx < endx && starty < endy) {
for (int i = starty; i < endy ; i++) {
list.add(matrix[startx][i]);
}
for (int i = startx; i < endx ; i++) {
list.add(matrix[i][endy]);
}
for (int i = endy; i > starty; i--) {
list.add(matrix[endx][i]);
}
for (int i = endx ; i > startx; i--) {
list.add(matrix[i][starty]);
}
startx++;
endx--;
starty++;
endy--;
}
//只有一行时
if(starty == endy){
while (startx <= endx) {
list.add(matrix[startx++][starty]);
}
}else {
//只有一列时
if(startx == endx){
while (starty <= endy) {
list.add(matrix[startx][starty++]);
}
}
}
return list;
} leetcode 59. 螺旋矩阵 II
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
if(n == 0){
return matrix;
}
int num = 1;
int startX = 0;
int startY = 0;
int endX = n-1;
int endY = n-1;
int tar = n*n;
while (num <= tar){
for (int i = startY; i <= endY ; i++) {
matrix[startX][i] = num++;
}
startX++;
for (int i = startX; i <= endX ; i++) {
matrix[i][endY] = num++;
}
endY--;
for (int i = endY; i >= startY ; i--) {
matrix[endX][i] = num++;
}
endX--;
for (int i = endX; i >= startX ; i--) {
matrix[i][startY] = num++;
}
startY++;
}
return matrix;
} leetcode 66. 加一
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10;
if (digits[i] != 0){
return digits;
}
}
digits = new int[digits.length + 1];
digits[0] = 1;
return digits;
} leetcode 73. 矩阵置零
public void setZeroes(int[][] matrix) {
if(matrix == null || matrix.length == 0){
return;
}
int row = matrix.length;
int col = matrix[0].length;
boolean firstColHasZero = false;
for (int i = 0; i < row ; i++) {
//第一列是否有0值
if(matrix[i][0] == 0){
firstColHasZero = true;
}
for (int j = 1; j < col; j++) {
if(matrix[i][j] == 0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
//行置零
for (int i = 1; i < row; i++) {
if(matrix[i][0] == 0){
for (int j = 1; j <col; j++) {
matrix[i][j] = 0;
}
}
}
//列置零
for (int i = 1; i < col; i++) {
if(matrix[0][i] == 0){
for (int j = 1; j<row; j++) {
matrix[j][i] = 0;
}
}
}
//第一行
if(matrix[0][0] == 0){
for (int j = 1; j <col; j++) {
matrix[0][j] = 0;
}
}
//第一列
if(firstColHasZero){
for (int i = 0; i < row ; i++) {
matrix[i][0] = 0;
}
}
}
------------------------------------------------------------------------------
package leetcode;
/*created by fanqunsong
Date : 2017/12/22
Time : 16:32
Tips：先买才能卖
*/
public class Solution210 {
public static void main(String[] args) {
int[] num = new int[]{1,2};
System.out.println(maxProfit(num));
}
public static int maxProfit(int[] prices) {
if(prices.length == 0 ||prices.length == 1 || prices == null){
return 0;
}
int min = prices[0];
int res = 0;
for (int i = 1; i < prices.length; i++) {
if(prices[i]>min){
res = res > prices[i] - min?res : prices[i] - min;
}
else {
min = prices[i];
}
}
return res;
}
} 42. 接雨水
public int trap(int[] height) {
if(height == null || height.length < 3){
return 0;
}
//left[i]表示第i列左边的最高的列值,包含第i列
int[] left = new int[height.length];
left[0] = height[0];
for (int i = 1; i < height.length ; i++) {
left[i] = left[i-1] > height[i]?left[i-1] : height[i];
}
//right[i]表示第i列右边的最高的列值,包含第i列
int[] right = new int[height.length];
right[height.length -1] = height[height.length-1];
for (int i = height.length-2; i >= 0 ; i--) {
right[i] = right[i+1] > height[i]?right[i+1] : height[i];
}
int sum = 0;
for (int i = 1; i < height.length-1 ; i++) {
sum += Math.min(left[i],right[i])-height[i];
}
return sum;
} -------------------------------------------------------------------------------------
package leetcode;
/*created by fanqunsong
Date : 2017/12/22
Time : 17:09
*/
public class Solution209 {
public static void main(String[] args) {
int[] num = new int[]{1,2};
System.out.println(maxProfit(num));
}
public static int maxProfit(int[] prices) {
if(prices.length == 0 ||prices.length == 1 || prices == null){
return 0;
}
int[] profit = new int[prices.length-1];
for (int i = 1; i < prices.length; i++) {
profit[i-1] = prices[i] - prices[i-1];
}
int sum = 0;
for (int i = 0; i < profit.length; i++) {
if (profit[i]>0){
sum += profit[i];
}
}
return sum;
}
}
------------------------------------------------------------------------------------
The number of elements initialized in A and B are m and n respectively.
package leetcode;
/*created by fanqunsong
Date : 2017/12/21
Time : 16:59
*/
/*
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B.
The number of elements initialized in A and B are m and n respectively.
*/
/*
tips:从后往前记录
*/
public class Solution401 {
public void merge(int A[], int m, int B[], int n) {
int j = m+n-1;
m--;
n--;
while(m>=0 && n>=0){
A[j--] = A[m] > B[n]? A[m--] : B[n--];
}
if(n>=0){
while (n>=0){
A[j--] = B[n--];
}
}
}
}
-------------------------------------
502 Given a number represented as an array of digits, plus one to the number
public class Solution {
public int[] plusOne(int[] digits) {
int sum = digits.length;
digits[sum-1] ++;
for (int i = sum-1; i >0 ; i--) {
if(digits[i]>9){
digits[i] = 0;
digits[i-1]++;
}
}
if(digits[0]<10){
return digits;
}
int[] res = new int[sum+1];
res[0] = 1;
res[1] = 0;
for (int i = 2; i <= sum ; i++) {
res[i] = digits[i-1];
}
return res;
}
}
-------------------------------------
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> list = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return list;
}
int startx = 0;
int starty = 0;
int endx = matrix.length-1;
int endy = matrix[0].length-1;
while (startx < endx && starty < endy) {
for (int i = starty; i < endy ; i++) {
list.add(matrix[startx][i]);
}
for (int i = startx; i < endx ; i++) {
list.add(matrix[i][endy]);
}
for (int i = endy; i > starty; i--) {
list.add(matrix[endx][i]);
}
for (int i = endx ; i > startx; i--) {
list.add(matrix[i][starty]);
}
startx++;
endx--;
starty++;
endy--;
}
//只有一行时
if(starty == endy){
while (startx <= endx) {
list.add(matrix[startx++][starty]);
}
}else {
//只有一列时
if(startx == endx){
while (starty <= endy) {
list.add(matrix[startx][starty++]);
}
}
}
return li
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
if(n == 0){
return matrix;
}
int num = 1;
int startX = 0;
int startY = 0;
int endX = n-1;
int endY = n-1;
int tar = n*n;
while (num <= tar){
for (int i = startY; i <= endY ; i++) {
matrix[startX][i] = num++;
}
startX++;
for (int i = startX; i <= endX ; i++) {
matrix[i][endY] = num++;
}
endY--;
for (int i = endY; i >= startY ; i--) {
matrix[endX][i] = num++;
}
endX--;
for (int i = endX; i >= startX ; i--) {
matrix[i][startY] = num++;
}
startY++;
}
return matrix;
} ---
public int[] plusOne(int[] digits) {
for (int i = digits.length - 1; i >= 0; i--) {
digits[i]++;
digits[i] = digits[i] % 10;
if (digits[i] != 0) return digits;
}
digits = new int[digits.length + 1];
digits[0] = 1;
return digits;
}
查看13道真题和解析
投递OPPO等公司10个岗位 >