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++) {
        list.add(matrix[rowStart][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++) {
        list.add(matrix[i][colEnd]);
        counter++;
      }
      colEnd--;
      if (counter == allElement) {
        break;
      }
      //bottom from right to left
      for (int i = colEnd; i >= colStart; i--) {
        list.add(matrix[rowEnd][i]);
        counter++;
      }
      rowEnd--;
      if (counter == allElement) {
        break;
      }
      //left from bottom to top
      for (int i = rowEnd; i >= rowStart; i--) {
        list.add(matrix[i][colStart]);
        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
    list.add(current_interval);
    //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;
        list.add(current_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) {
      list.add(newInterval);
      return list.toArray(new int[list.size()][]);
    }
    //traversal the intervals
    for (int[] interval : intervals) {
      //situation1,interval < new
      if (interval[1] < newInterval[0]) {
        list.add(interval);
      } else if (newInterval[1] < interval[0]) {
        //situation2,new < interval
        list.add(newInterval);
        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
    list.add(newInterval);
    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) {
      return head;
    }
    //get the list's length
    ListNode temp = head;
    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) {
      return head;
    }
    //find the position before the rotating node
    ListNode cut = head;
    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;
    //temp point to head
    temp.next = head;
    //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];
  }