LeetCode 283. Move Zeroes

Follow up: Could you minimize the total number of operations done?

https://leetcode.com/problems/move-zeroes/

    //firstZeroIndex -> z
// z: -1
    // i
    //[1,3,12,0,0]
    //when nums[i] = 0
       //if z = -1, then z = i
    //else
       //if z != -1 (had zero in front)
       // swap
      // z += 1;
    //from z ~ i as t, nums[t] = 0 is promised
    

class Solution {
    public void moveZeroes(int[] nums) {
        int firstZeroIndex = -1;
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == 0){
                if (firstZeroIndex == -1){
                    firstZeroIndex = i;
                }
            } else {
                if (firstZeroIndex != -1){
                    int temp = nums[firstZeroIndex];
                    nums[firstZeroIndex] = nums[i];
                    nums[i] = temp;
                    
                    firstZeroIndex += 1;
                }
            }
        }
    }
}

LeetCode 200. Number of Islands

UnionFind island count direction

https://leetcode.com/problems/number-of-islands/

class Solution {
    public int numIslands(char[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int countIslands = 0;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        UnionFind uf = new UnionFind(rows * cols);
        
        for (int x = 0; x < rows; x++){
            for (int y = 0; y < cols; y++){
                if (grid[x][y] == '1') {
                    countIslands++;
                }
            }
        }
        
        for (int x = 0; x < rows; x++){
            for (int y = 0; y < cols; y++){
                if (grid[x][y] == '1'){
                    for (int[] dir : directions) {
                        int nx = x + dir[0];
                        int ny = y + dir[1];
                        if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == '1'){
                            if (uf.merge(x * cols + y, nx * cols + ny)){
                                countIslands--;
                            }
                        }
                    }
                }
            }
        }
        
        return countIslands;
        
    }
}

class UnionFind{
    int[] father;
    public UnionFind(int size){
        father = new int[size];
        for (int i = 0; i < size; i++){
            father[i] = i;
        }
    }
    
    public int getFather(int x){
        if (father[x] == x){
            return x;
        }
        return father[x] = getFather(father[x]);
    }
    
    public boolean isSameFather(int a, int b){
        int fa = getFather(a);
        int fb = getFather(b);
        return fa == fb;
    }
    
    public boolean merge(int a, int b){
        int fa = getFather(a);
        int fb = getFather(b);
        if (fa == fb) return false;
        father[fa] = fb;
        return true;
    }
}

LeetCode 392. Is Subsequence

Easy question

https://leetcode.com/problems/is-subsequence/

class Solution {
    public boolean isSubsequence(String s, String t) {
        int sIndex = 0;
        int tIndex = 0;
        while (sIndex < s.length() && tIndex < t.length()){
            //"abc"
        //      s
            //"ahbcgd"
       //       t
            
            int target = s.charAt(sIndex);
            if (t.charAt(tIndex) == target){
                tIndex += 1;
                sIndex += 1;
            } else {
                tIndex += 1;
            }
            
        }
        
        if (sIndex == s.length()){
            return true;
        }
        return false;
    }
}

LeetCode 20. Valid Parentheses

Considering with following cases "]" "{[}]"

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            
            if (c == '(' || c == '[' || c == '{'){
                stack.push(c);
            } else if (stack.size() == 0){
                return false;
            } else if (c == ')' && stack.pop() != '('){
                return false;
            } else if (c == ']' && stack.pop() != '['){
                return false;
            } else if (c == '}' && stack.pop() != '{'){
                return false;
            }
        }

        return stack.size() == 0;
    }
}

LeetCode 967. Numbers With Same Consecutive Differences

interestring question.

The order of calculation is very important.

class Solution {
    public int[] numsSameConsecDiff(int n, int k) {
        //10 ^ n => max 10^9..
        List<Integer> answer = new ArrayList<>();
        
        for (int lastDigit = 1; lastDigit <= 9; lastDigit++){
            findAnswer(n, k, 1, lastDigit, lastDigit, answer);
        }
        
        int[] finalAnswer = new int[answer.size()];
        for (int i = 0; i < answer.size(); i++){
            finalAnswer[i] = answer.get(i);
        }
        
        return finalAnswer;
    }
    
    private void findAnswer(int n, int k, int digit, int lastDigit, int currentNumber, List<Integer> answer){
        if (digit == n){
            answer.add(currentNumber);
            return;
        }
        
        if (lastDigit - k >= 0 && k != 0){
            findAnswer(n, k, digit + 1, lastDigit - k, currentNumber * 10 + lastDigit - k, answer);
        }
       
        if (lastDigit + k < 10)  {
            findAnswer(n, k, digit + 1, lastDigit + k, currentNumber * 10 + lastDigit + k, answer);
        }
    }
}

LeetCode 213. House Robber II

Very interesting question 0 ~ n - 2 また 1 ~ n -1 に２つに分けることを思いつかなかったな。

class Solution {
    public int rob(int[] nums) {
        
        int n = nums.length;
        if (n <= 3){
            int max = 0;
            for (int i = 0; i < n; i++){
                max = Math.max(nums[i], max);
            }
            return max;
        }
        
        return Math.max(findMaxSum(nums, 0, n - 1), findMaxSum(nums, 1, n));
       
    }
    
    private int findMaxSum(int[] nums, int start, int end){
        int prev = 0;
        int beforePrev = 0;
        
        for (int i = start; i < end; i++){
            //prev -> beforePrev
            //prev -> new max
            int temp = prev;
            //rob or not
            prev = Math.max(beforePrev + nums[i], prev);
            beforePrev = temp;
        }
        
        return prev;
    }
}

LeetCode 605. Can Place Flowers

https://leetcode.com/problems/can-place-flowers/

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        //max: 0 adjacent 1
        //dont create like this: [1, 0, 0, 1, 0, 0, 1] and do like this [1,0,1,0,0,0,1], then we can put one more flower in the flower bed
        
       
        
        if (flowerbed.length == 1){
            //n >= 1;
            if (n >= 1 && flowerbed[0] == 1) return false;
            return true;
        }
        
         //find if maximum is >= n;
        int max = 0;
        int size = flowerbed.length;
        //size is bigger than 1
        for (int i = 0; i < size; i++){
            if (flowerbed[i] == 1){
                continue;
            }
            
            if (i == 0){
                max += flowerbed[i + 1] == 0? 1: 0;
                flowerbed[i] = 1;
            } else if (i == size - 1){
                max += flowerbed[i - 1] == 0? 1:0;
                flowerbed[i] = 1;
            } else if (flowerbed[i - 1] == 0 && flowerbed[i + 1] == 0){
                max += 1;
                flowerbed[i] = 1;
            }
            
        }
        
        System.out.print(max);
        return max >= n;
    }
}