LeetCode(32) -- 728, 733, 744, 746, 747

P728. Self Dividing Numbers (Easy)

一个自除数是指它能被自己的每个位数整数。

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

我的思路

最大只有10000，所以就暴力求解了。

我的代码

public class E_728_SelfDividingNumbers {
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> list = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            int temp = i;
            boolean isSelfDividable = true;
            while (temp >= 10) {
                int remainder = temp % 10;
                if (remainder == 0 || i % remainder != 0) {
                    isSelfDividable = false;
                    break;
                } else {
                    temp /= 10;
                }
            }
            if (i % temp != 0) {
                isSelfDividable = false;
            }
            if (isSelfDividable) {
                list.add(i);
            }
        }
        return list;
    }
}

39%

最优解

class Solution {
    public boolean isSelfDividing(int number) {
        int ref = number;
        boolean isSelfDivide = false;
        while(ref != 0) {
            int num = ref % 10;
            if(num == 0) {
                isSelfDivide = false;
                break;
            }
            if(number % num == 0) {
                isSelfDivide = true;
            } else {
                isSelfDivide = false;
                break;
            }
            ref = ref / 10;
        }
        return isSelfDivide;
    }

    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> result = new ArrayList<Integer>();

        for(int i = left; i<= right; i++) {
            if(isSelfDividing(i)){
                result.add(i);
            }
        }

        return result;
    }
}

感觉也跟我的思路差不多。

P733. Flood Fill (Easy)

二维数组表示的一个image，每个点代表它的一个像素。从一个点起始，把所有跟这个点相交接的点都改成同一种颜色。

我的思路

用DFS，递归遍历这个点。

我的代码

public class E_733_FloodFill {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image[sr][sc] == newColor) {
            return image;
        }
        dfs(image, sr, sc, newColor, image[sr][sc]);
        return image;
    }

    private void dfs(int[][] image, int sr, int sc, int newColor, int oldColor) {

        image[sr][sc] = newColor;

        if (sr > 0 && image[sr-1][sc] == oldColor) {
            dfs(image, sr - 1, sc, newColor, oldColor);
        }
        if (sc > 0 && image[sr][sc-1] == oldColor) {
            dfs(image, sr, sc - 1, newColor, oldColor);
        }
        if (sr < image.length - 1 && image[sr+1][sc] == oldColor) {
            dfs(image, sr + 1, sc, newColor, oldColor);
        }
        if (sc < image[0].length - 1 && image[sr][sc+1] == oldColor) {
            dfs(image, sr, sc + 1, newColor, oldColor);
        }
    }
}

87%

最优解

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (image[sr][sc] == newColor) return image;
        fill(image, sr, sc, image[sr][sc], newColor);
        return image;
    }

    private void fill(int[][] image, int row, int col, int oldColor, int newColor) {
        if (image[row][col] != oldColor) return;
        image[row][col] = newColor;
        if (row > 0) fill(image, row - 1, col, oldColor, newColor);
        if(row < image.length - 1) fill(image, row + 1, col, oldColor, newColor);
        if (col > 0) fill(image, row, col - 1, oldColor, newColor);
        if(col < image[0].length - 1) fill(image, row, col + 1, oldColor, newColor);
    }
}

第一步如果不是老颜色，直接返回，这样就不必像我一样每次再判断一下了。其他的都一样。

P744. Find Smallest Letter Greater Than Target (Easy)

一个排序过的字母数组，找到刚好比目标值大一点儿的字母。这些小写字母是可以循环的，比如，比“z”大一点儿的字母就是‘a’

我的思路

非常简单的一道题，唯一的麻烦在于循环。循环的情况只会发生在到最后都没找到比它大的，那当然就返回第一个字母即可。

我的代码

public class E_744_FindSmallestLetterGreaterThanTarget {
    public char nextGreatestLetter(char[] letters, char target) {
        for (int i = 0; i < letters.length; i++) {
            if (letters[i] > target) {
                return letters[i];
            }
        }
        return letters[0];
    }
}

100%

最优解

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.length;
        while(left<right){
            int mid = left + (right - left) / 2;
            if(letters[mid]-target<=0) left = mid + 1;
            else right = mid;
        }
        if(left == letters.length)
            return letters[0];
        return letters[left];
    }
}

用二分查找确实更好。一开始没想到。

答案

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int lo = 0, hi = letters.length;
        while (lo < hi) {
            int mi = lo + (hi - lo) / 2;
            if (letters[mi] <= target) lo = mi + 1;
            else hi = mi;
        }
        return letters[lo % letters.length];
    }
}

P746. Min Cost Climbing Stairs (Easy)

上楼梯，每一层都需要一定成本。可以上一阶，也可以上两阶。求最低成本。

我的思路

动态规划。每一步的选择，都是前两步的最小成本和前一步的最小成本中更小的一个。

我的代码

public class E_746_MinCostClimbingStairs {
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length < 2) {
            return 0;
        }
        if (cost.length < 3) {
            return Math.min(cost[0], cost[1]);
        }
        int[] min = new int[cost.length];
        min[0] = cost[0];
        min[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            min[i] = Math.min(min[i - 2], min[i - 1]) + cost[i];
        }
        return Math.min(min[cost.length - 1], min[cost.length - 2]) ;
    }

    public static void main(String[] args) {
        int[] test = {0,0,1,1};
        new E_746_MinCostClimbingStairs().minCostClimbingStairs(test);
    }
}

99%

最优解

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int first=cost[0], second=cost[1], third=0;
        for (int i=2;i<cost.length;i++) {
            third = cost[i] + Math.min(first, second);
            first = second;
            second = third;
        }
        return Math.min(first, second);
    }
}

不需要新开一个数组，直接存前两个数即可。值得学习。

答案

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int f1 = 0, f2 = 0;
        for (int i = cost.length - 1; i >= 0; --i) {
            int f0 = cost[i] + Math.min(f1, f2);
            f2 = f1;
            f1 = f0;
        }
        return Math.min(f1, f2);
    }
}

P747. Largest Number At Least Twice of Others (Easy)

一个数组，只有一个最大数。求问这个最大数是否至少是其他数的两倍。如果是，返回这个最大数的索引。否则返回-1

我的思路

保留第一大和第二大的两个数，最后看看是否大于等于两倍。

我的代码

class Solution {
    public int dominantIndex(int[] nums) {
        int first = Integer.MIN_VALUE, second = Integer.MIN_VALUE;
        int maxIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > first) {
                second = first;
                first = nums[i];
                maxIndex = i;
            } else if (nums[i] == first) {
                second = first;
            } else if (nums[i] > second) {
                second = nums[i];
            }
        }
        if (first >= second * 2) return maxIndex;
        else return -1;
    }
}

100%

最优解

class Solution {
    public int dominantIndex(int[] nums) {

        int idx = -1;
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
                idx = i;
            }
        }

        max = max / 2;
        for (int i = 0; i < nums.length; i++) {
            if ((max < nums[i]) && (i != idx)) {
                return -1;
            }
        }

        return idx;
    }
}

第一圈先找到最大数，并记录它的索引。第二圈如果有人超过了这个最大值的一半而且不是他本身，那就返回-1