5.25号刷题

第一题 35. Search Insert Position

算法

本质即是一个二分查找的问题，较为简单

public class searchInsert35 {
    public int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        if (nums == null || nums.length == 0) return 0;

        while(low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > target) high = mid - 1;
            else if (nums[mid] < target) low = mid + 1;
            else return mid;
        }
        return low;
    }
}

第二题 42. Trapping Rain Water

算法

本题目较为复杂，有两种方法，自己选择是比较容易理解的方法。用Stack对所有的降序的index进行存储.如果在Array中遇到了升序，那说明可能出现了可以存储水的情况，进行判断，并计算出可以储存睡的容积。
自己还是有一小部分没有搞得太明白（关于index部分升序降序的），之后再看看

public class Solution {
    public int trap(int[] height) {
        if (height == null || height.length == 0) return 0;
        Stack<Integer> indices = new Stack<>();
        int i = 0, maxVolume = 0;
        while(i < height.length) {
            if (indices.isEmpty() || height[i] <= height[indices.peek()]) {
                indices.add(i);
                i++;
            } else {
                int bar = indices.pop(), volume = 0;
                if (indices.isEmpty()) {
                    volume = 0;
                }
                else {
                    volume = (Math.min(height[indices.peek()], height[i]) - height[bar]) * (i - indices.peek() - 1);
                }
                maxVolume += volume;
            }

        }
        return maxVolume;       
    }
}

学到的东西

关于Stack 的操作链接

第三题 48. Rotate Image

算法

自己的

自己的算法主要是按照绕圈的方式进行转换，需要用到额外的空间O(n)且效率较低。但是结果是正确的

public class rotate48 {
    public static void rotate(int[][] matrix) {
       int rotateNum = 0, direction = 1, length = matrix.length;
       int[][] result = new int[matrix.length][matrix.length];

       while (2 * rotateNum < matrix.length) {
           if (direction % 4 == 1 ) {
               for (int i = matrix.length - 1 - rotateNum, j = rotateNum; i >= rotateNum; i--) {
                   result[j][length - 1 - i] = matrix[i][j];
               }
               direction++;
           }
           if (direction % 4 == 2) {
               for (int i = rotateNum, j = rotateNum; j <= matrix.length - 1 - rotateNum; j++) {
                   result[j][length - 1 - rotateNum] = matrix[i][j];
               }
               direction++;
           }
           if (direction % 4 == 3) {
               for (int i = rotateNum, j = length - 1 - rotateNum; i <= length - 1 - rotateNum; i++) {
                   result[j][length - 1 - i] = matrix[i][j];
               }
               direction++;
           }
           if (direction % 4 == 0) {
               for (int i = length - 1 - rotateNum, j = length - 1 - rotateNum; j >= rotateNum; j-- ) {
                   result[j][rotateNum] = matrix[i][j];
               }
               direction++;
               rotateNum++;
           }
       }
       for (int i = 0; i < matrix.length; i++) {
           matrix[i] = result[i];
       }
    }
}

别人的

对于图片旋转问题，有特定的解法。
顺时针旋转90°的时候，先将上下对换，之后在进行转置。
对于逆时针90°的时候，先将左右进行对换，然后再进行转置。

public class rotate48 {
    public void rotate2(int[][] matrix) {
        int up = 0, down = matrix.length - 1;
        //Step1, flip up and down
        while (up < down) {
            int[] tmp = matrix[up];
            matrix[up] = matrix[down];
            matrix[down] = tmp;
            up++; down--;
        }
        //Step2, swap the symmetry
        for (int i = 0; i < matrix.length; i++)
            for (int j = i; j < matrix.length; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
    }
}

学到的东西

• 当对矩阵某一行进行赋值的时候，可以整行赋值。
• 转置的时候注意，循环的第二层不应该是0 -> length，这样相当于转置了两次，等于没有转置。