# 54. Spiral Matrix

This problem is a two-dimensional array processing problem.The test point is how to loop and iterate when facing different situations.We can draw a picture to better understand.

We can get the the array location [row,col].So we only need to proceed according to the requirements of the question.The difficulty of this question is that every time the position of the element is determined,it is easy to confirm the error.When we search for a complete row or column,we must subtract the current row or column,otherwise an error will occur.

Solution

  public List<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
//define row and col
int rowStart = 0, rowEnd = matrix.length - 1;
int colStart = 0, colEnd = matrix[0].length - 1;
//the number of all elements
int allElement = (rowEnd + 1) * (colEnd + 1);
//count the number of the elements what we add
int counter = 0;
while (rowStart <= rowEnd || colStart <= colEnd) {
//top from left to right
for (int i = colStart; i <= colEnd; i++) {
counter++;
}
//we must subtract the current row or column,otherwise an error will occur
rowStart++;
if (counter == allElement) {
break;
}
//right from top to bottom
for (int i = rowStart; i <= rowEnd; i++) {
counter++;
}
colEnd--;
if (counter == allElement) {
break;
}
//bottom from right to left
for (int i = colEnd; i >= colStart; i--) {
counter++;
}
rowEnd--;
if (counter == allElement) {
break;
}
//left from bottom to top
for (int i = rowEnd; i >= rowStart; i--) {
counter++;
}
colStart++;
if (counter == allElement) {
break;
}
}
return list;
}

# 55. Jump Game

If you have already written the question 45. Jump Game II.So you can know this problem is also a greedy problem.The main idea to solve this question is the farthest distance every time you jump.The distance that each position can jump out is i+nums[i].So we can set a value maxMove,but we can;t judge the maxMove at last.For example [0,2,3].The maxMove is larger than the array's length,but we will stuck at first.So we will set another value endIndex.This value is we can actually reach the location.If we reach the endIndex,we just need to update this value and judge this value whether larger than the array's length.

Solution

  public boolean canJump(int[] nums) {
//for example [0,2,3],the maxMove is larger than the array's length,but we will stuck at first
int l = nums.length - 1, maxMove = 0, endIndex = 0;
for (int i = 0; i < nums.length - 1; i++) {
//the farthest you can reach in theory
maxMove = Math.max(maxMove, i + nums[i]);
//if you reach the actual end location,just update the end location
if (i == endIndex) {
endIndex = maxMove;
}
}
return endIndex >= l;
}

# 56. Merge Intervals

This problem is an abstract double pointer porblem.First of this we must sort this Two-dimensional array.Why we must sort,i will draw a picture to describe it.

Why can merge [1,3] to [2,6],for convenience,we call it A B array.Because A[1] is larger than B[0],so we can merge theme.But if this array is unordered,it will very difficult.For example [1,3] [8,10] [2,6] [15,18],so that's why we should sort it at first.

We can override the sort function,the comparison is the size of the first element of each array.We must pay attention to one small point,which is the end of the new array.For example [1,8] [5,7] the new array is [1,8].So the new array's end is Math.max(A[1],B[1]).

Why i say this problem is an abstract double pointer porblem.Because we can treat each small array as a pointer.We set the current pointer is slow pointer,and set the next position pointer is the faster pointer.And use double pointer can traverse all the arrays.

Solution

  public int[][] merge(int[][] intervals) {
//the special situation
if (intervals.length == 1) {
return intervals;
}
//override the sort function
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
//because we don't know how long the result will be,so we use arraylist
ArrayList<int[]> list = new ArrayList<>();
//set a slow pointer
int[] current_interval = intervals[0];
//and add it at first,if don't add it,we will miss the first of the result array
//traverse the array
for (int[] interval : intervals) {
//because we don't need to judge the current[0],we just need to judge the current[1],so we
// don't need this step
//int current_begin = current_interval[0];
int current_end = current_interval[1];
//the faster pointer
int next_begin = interval[0];
int next_end = interval[1];
//merge the two arrays to be a new result array
if (current_end >= next_begin) {
current_interval[1] = Math.max(current_end, next_end);
} else {
//we just need to update the two pointers
current_interval = interval;
}
}
return list.toArray(new int[list.size()][]);
}

# 57. Insert Interval

This problem is very similar with problem 56. Merge Intervals.If you want to understand this problem easier.You should understand that problem at first.

This problem has three situations.I will use pictures to explain.

There has two special situations,one is array interval are all less than new,another situation is new are all less than array interval.I circled it in the picture.

The last situation is merger two arrays into a new array.As long as the two arrays have intersecting parts,so just merge it.The result of the merge is the new newInterval.So we only need to traversal this array,from the head to the end can get the result.

Solution

  public int[][] insert(int[][] intervals, int[] newInterval) {
//we don't know how long the result will be,so use arraylist to store
ArrayList<int[]> list = new ArrayList<>();
//special situation
if (intervals.length == 0 && intervals == null) {
return list.toArray(new int[list.size()][]);
}
//traversal the intervals
for (int[] interval : intervals) {
//situation1,interval < new
if (interval[1] < newInterval[0]) {
} else if (newInterval[1] < interval[0]) {
//situation2,new < interval
newInterval = interval;
} else {
//situation3,merge the two arrays into a new array
newInterval[0] = Math.min(interval[0], newInterval[0]);
newInterval[1] = Math.max(interval[1], newInterval[1]);
}
}
//if we don't add it at last,we will lose the last answer of array
return list.toArray(new int[list.size()][]);
}

# 59. Spiral Matrix II

This problem is the same as problem 54. Spiral Matrix.If you want to solve this problem,just need to create a counter.Because each step moves to the position you need to fill in a number.But this number is exactly the number of steps you move.

Solution

  public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int rowStart = 0, rowEnd = n - 1;
int colStart = 0, colEnd = n - 1;
int allElement = n * n;
//creat the counter
int counter = 0;
while (rowStart <= rowEnd || colStart <= colEnd) {
for (int i = colStart; i <= colEnd; i++) {
//because the first number is 1,the counter is 0,so need +1
matrix[rowStart][i] = counter + 1;
counter++;
}
if (counter == allElement) {
break;
}
rowStart++;
for (int i = rowStart; i <= rowEnd; i++) {
matrix[i][colEnd] = counter + 1;
counter++;
}
if (counter == allElement) {
break;
}
colEnd--;
for (int i = colEnd; i >= colStart; i--) {
matrix[rowEnd][i] = counter + 1;
counter++;
}
if (counter == allElement) {
break;
}
rowEnd--;
for (int i = rowEnd; i >= rowStart; i--) {
matrix[i][colStart] = counter + 1;
counter++;
}
if (counter == allElement) {
break;
}
colStart++;
}
return matrix;
}

# 61. Rotate List

This problem is a list problem,let's take a closer look.If the k is larger than the list's length.So it is equivalent to doing it all over again.So in order to go around and search for the unnecessary ones,we should get the list's length L.And k%L can get the position of the node that needs to be rotated.

This problem is very easy,we just make a new node key point to head,and the list last position is temp,just just let temp point to head,and key point to rotate position.At last,don't forget to make the cut note point to null,otherwise it will create a circle.

Solution

  public ListNode rotateRight(ListNode head, int k) {
//the special situation
if (head == null || k == 0) {
}
//get the list's length
int length = 1;
while (temp.next != null) {
temp = temp.next;
length++;
}
//get the position of the node that needs to be rotated
k %= length;
//special situation
if (k == 0) {
}
//find the position before the rotating node
for (int i = 0; i < length - k - 1; i++) {
cut = cut.next;
}
ListNode rotate = cut.next;
ListNode key = new ListNode(0);
//key point to rotate
key.next = rotate;
//cut point to null
cut.next = null;
//key -> rotate -> temp -> head ->cut -> null
return key.next;
}

# 62. Unique Paths

This problem is a very interesting problem.It has a very important requirement,the robot can only move either down or right at any point in time.I draw a picture to explain.

The start point can only move either down or right.If the down point has m possible unique paths and the right point has n unique paths.So obviously,the start point has m+n unique paths. When the point moves to the bottom or the right.Because it can only move either down or right,so it can just only move follow the yellow arrow. So we make a summary.[m][n] possible = [m-1][n] possible + [m][n-1] possible

We can write down the possibility of each position.

Solution

  public int uniquePaths(int m, int n) {
int[][] array = new int[m][n];
//the bottom or the right,it can only move either down or right,so the possible are all 1
for (int i = 0; i < array.length; i++) {
array[i][0] = 1;
}
for (int i = 0; i < array[0].length; i++) {
array[0][i] = 1;
}
//[m][n]=[m-1][n]+[m][n-1]
for (int i = 1; i < array.length; i++) {
for (int j = 1; j < array[0].length; j++) {
array[i][j] = array[i - 1][j] + array[i][j - 1];
}
}
return array[m - 1][n - 1];
}

# 63. Unique Paths II

This problem caused me a lot of trouble.Because it's an incomplete description of the problem.

• There may be a lot of obstacles,there may be more than one
• The obstacles' location may be anywhere,it may appear in the start,or it may be at the target place.

This problem's main idea are very same with problem 62,but there are some differences.Because if the obstacles appear the bottom place or the right place,so we can't go that way.We should mark all the.And set the initial value of 1 for the boundary between the bottom and the right,if the position is a marked obstacle,set it to -1.There is a note here,in the boundary,if one location is marked it can't walk there,so the next boundary location beside it also can't walk.When we judge the location,we need to judge the down location and the right location.If one of them is marked,we can't add it.

Solution

  public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//creat the array,and mark the obstacle
int rowNumber = obstacleGrid.length;
int colNumber = obstacleGrid[0].length;
int[][] array = new int[rowNumber][colNumber];
for (int i = 0; i < rowNumber; i++) {
for (int i1 = 0; i1 < colNumber; i1++) {
if (obstacleGrid[i][i1] == 1) {
array[i][i1] = -1;
}
}
}
//the special situation,the target is obstacle
array[0][0] = obstacleGrid[0][0] == 1 ? -1 : 1;
//judge this location and beside location,if is marked,it also marked
for (int i = 1; i < rowNumber; i++) {
array[i][0] = obstacleGrid[i][0] == 1 ? -1 : array[i - 1][0] == -1 ? -1 : 1;
}
for (int i = 1; i < colNumber; i++) {
array[0][i] = obstacleGrid[0][i] == 1 ? -1 : array[0][i - 1] == -1 ? -1 : 1;
}
//judge location,have four situation,we need also judge down and right
for (int i = 1; i < rowNumber; i++) {
for (int j = 1; j < colNumber; j++) {
//is marked
if (array[i][j] == -1) {
continue;
} else if (array[i - 1][j] != -1 && array[i][j - 1] != -1) {
array[i][j] = array[i - 1][j] + array[i][j - 1];
} else if (array[i - 1][j] != -1) {
array[i][j] = array[i - 1][j];
} else {
array[i][j] = array[i][j - 1];
}
}
}
//the special situation,the start place is marked
return array[rowNumber - 1][colNumber - 1] == -1 ? 0 : array[rowNumber - 1][colNumber - 1];
}

# 64. Minimum Path Sum

This problem is a very interesting problem.We can find an interesting phenomenon,no matter how to move the target,the number of steps we have to reach the end must be the same.

So we don't need to consider whether to go down or to the right to save steps.We only need to consider which side to go has less value.

We can find the boundary first,because it can only go down or to the right,so the boundary value should be unique.

• When at the top boundary,just continue move right.
• When on the left boundary,just continue move down.
• When in the matrix,just move to the lower value side

Solution

  public int minPathSum(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int i1 = 0; i1 < grid[0].length; i1++) {
//the start place,just continue
if (i == 0 && i1 == 0) {
continue;
} else if (i == 0) {
//the top boundary
grid[i][i1] = grid[i][i1 - 1] + grid[i][i1];
} else if (i1 == 0) {
//the left boundary
grid[i][i1] = grid[i - 1][i1] + grid[i][i1];
} else {
//in the matrix,add the lower value
grid[i][i1] = Math.min(grid[i - 1][i1], grid[i][i1 - 1]) + grid[i][i1];
}
}
}
//return the value of end place
return grid[grid.length - 1][grid[0].length - 1];
}