java 刷题4

https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array/description/

// 原地 hash
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        int i;
        int index;
        for(i=0;i<n;++i) {
            index = (nums[i]-1)%n;
            nums[index] += n;
        }
        List<Integer> ret = new ArrayList<>();
        for(i = 0;i<n;++i) {
            if (nums[i] <= n) {
                ret.add(i+1);
            }
        }
        return ret;
    }
}
/*
class Solutionv1 {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        boolean[] statis = new boolean[n+1];
        for(int num : nums) {
            statis[num] = true;
        }
        List<Integer> ret = new ArrayList<Integer>();
        for(int i=1;i<=n;i++) {
            if (!statis[i]) {
                ret.add(i);
            }
        }
        return ret;
    }
}*/

https://leetcode.cn/problems/can-place-flowers/submissions/

// 贪心



class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if (n <=0) {
            return true;
        }
        int total = flowerbed.length;
        
        for(int i = 0;i<total;++i) {
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == total -1 || flowerbed[i+1] == 0)) {
                flowerbed[i] = 1;
                --n;
            }
        
            if(n <= 0) {
                return true;
            }
        }
        
        if(n <= 0) {
            return true;
        }

        return false;
    }
}

https://leetcode.cn/problems/pascals-triangle-ii/submissions/

class Solution {

    private int[][] grid;

    public Solution() {
        int rowIndex = 33;
        grid = new int[rowIndex+1][];
        for (int i=0;i<=rowIndex;++i) {
            grid[i] = new int[i+1];
            grid[i][0] = 1;
            grid[i][i] = 1;
        }
        for (int i=2;i<=rowIndex;++i) {
            for(int j = 1;j<i;++j) {
                grid[i][j] = grid[i-1][j-1] + grid[i-1][j];
            }
        }
    }
    public List<Integer> getRow(int rowIndex) {
        
        List<Integer> ret = new ArrayList<>();
        for(int j=0;j<=rowIndex;++j) {
            ret.add(grid[rowIndex][j]);
        }
        return ret;

    }
}

class Solutionv1 {

    
    public List<Integer> getRow(int rowIndex) {
        int [][] grid = new int[rowIndex+1][];
        for (int i=0;i<=rowIndex;++i) {
            grid[i] = new int[i+1];
            grid[i][0] = 1;
            grid[i][i] = 1;
        }
        for (int i=2;i<=rowIndex;++i) {
            for(int j = 1;j<i;++j) {
                grid[i][j] = grid[i-1][j-1] + grid[i-1][j];
            }
        }
        List<Integer> ret = new ArrayList<>();
        for(int j=0;j<=rowIndex;++j) {
            ret.add(grid[rowIndex][j]);
        }
        return ret;

    }
}

ref

• https://blog.csdn.net/HyOneCess/article/details/108710719