695. max-area-of-island

• 방문한 곳은 1 to 2로 치환하고 연결된 모든 섬의 count를 구해서 max sum을 구한다.

Runtime: 2 ms, faster than 100.00% of Java online submissions for Max Area of Island.
Memory Usage: 43.6 MB, less than 55.56% of Java online submissions for Max Area of Island.

public class Solution {
    int maxSum =0;
    public  int maxAreaOfIsland(int[][] grid) {
        if(grid.length ==0){
            return 0;
        }

        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j] == 1){
                    int sum = visit(i, j, grid);
                    maxSum = Math.max(maxSum, sum);
                }
            }
        }
        return maxSum;
    }

    private int visit(int i, int j, int[][] grid) {
        int sum=0;
        if(i >=0 && i<grid.length && j>=0 && j<grid[i].length){
            if(grid[i][j] ==1){
                sum++;
                grid[i][j] =2;
                sum+=visit(i+1, j, grid);
                sum+=visit(i-1, j, grid);
                sum+=visit(i, j-1, grid);
                sum+=visit(i, j+1, grid);
            }
        }
        return sum;
    }
}

342. power of four

https://leetcode.com/problems/power-of-four/

해결과정

10진수 to 2진수

• 4 -> 100
• 16 -> 10000
• 64 -> 1000000

Runtime: 7 ms, faster than 5.74% of Java online submissions for Power of Four.
Memory Usage: 34.3 MB, less than 6.67% of Java online submissions for Power of Four.

public boolean isPowerOfFour(int num) {
        String binarySring = Integer.toBinaryString(num);
        if(binarySring.length()>=3 && (binarySring.length()-1)%2 ==0){
           return  "1".equals(binarySring.replaceAll("0", ""));
        }

        return false;
    }

second soluton

민수님 numberOfTrailingZero꺼랑 And 논리 연산자를 이용함.
100
011 의 and 0

class Solution {
    public boolean isPowerOfFour(int num) {
        if(num==0)return false;
        return Integer.numberOfTrailingZeros(num) % 2==0 && ((num & num-1) == 0);
    }
}

979. Distribute Coins in Binary Tree

https://leetcode.com/problems/distribute-coins-in-binary-tree/

• 이문제는 풀이는 조금더 생각을 해서 코딩 라인수를 줄여야할필요가 있음

• 실제 코인의 이동이 아니라 코인이 없더라도 음수대로 값을 채움 ( 있는것처럼 가상의 코인을 움직인다 )

• data를 채우는것은 inorder 순서로 적용

Runtime: 1 ms, faster than 87.01% of Java online submissions for Distribute Coins in Binary Tree.
Memory Usage: 37.7 MB, less than 100.00% of Java online submissions for Distribute Coins in Binary Tree.

public class Solution {

    int count =0;
    public int distributeCoins(TreeNode root) {
        if(root == null){
            return 0;
        }
        conqer(root);

        return count;
    }

    public void conqer ( TreeNode root){
        if(root.left != null){
            conqer(root.left);
            calclator(root, root.left);
        }
        if(root.right != null){
            conqer(root.right);
            calclator(root, root.right);
        }
    }
    public void calclator(TreeNode root, TreeNode child){
        if(child.val <=0){
            int increase = 1-child.val;
            count += increase;
            child.val = 1;
            root.val = root.val - increase;
        }else {
            int decrease =  child.val - 1;
            count += decrease;
            child.val = 1;
            root.val = root.val + decrease;
        }
    }
}

1047. Remove All Adjacent Duplicates In String

-https://leetcode.com/problems/verifying-an-alien-dictionary/

Hi! I’m your first Markdown file in StackEdit. If you want to learn about StackEdit, you can read me. If you want to play with Markdown, you can edit me. Once you have finished with me, you can create new files by openi

1차 코드

49 ms	38.5 MB	java

class Solution {
    public String removeDuplicates(String S) {
        // "abbaca"

        if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();
        Stack<Character> stack  = new Stack<Character>();
        for(int i=0; i<chars.length; i++){


            if(!stack.isEmpty()) {
                Character cha = stack.peek();
                if (cha != null && cha == chars[i]) {
                    stack.pop();
                    continue;
                }
            }
            stack.push(chars[i]);
        }

        char [] result = new char[stack.size()];
        int index = stack.size()-1;
        while(!stack.isEmpty()){
            Character  last = stack.pop();
            result[index--] = last;
        }

        return new String(result);
    }
}

2차코드

• 자료구조 안쓰고 다시 한번더 풀어봐야겠다.
• 조건이 바로 앞뒤 2개의 character 값만 비교하는거라서 마지막 last index를 기억하는걸로
• 앞뒤가 서로 다를때 last index = currentIndex
• 앞뒤가 서로 같을때 find last index and check index ‘0’

Runtime: 4 ms, faster than 98.11% of Java online submissions for Remove All Adjacent Duplicates In String.
Memory Usage: 37.7 MB, less than 100.00% of Java online submissions for Remove All Adjacent Duplicates In String.

class Solution {
    public String removeDuplicates(String S) {
        // "abbaca"

       if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();

        int last = 0;
        for(int i=1; i<chars.length; i++){
            if(last >= 0 && chars[last] == chars[i]){ // 같을때
                chars[i] = '0';
                chars[last] = '0';
                last --;
                while(last >=0 && chars[last] == '0'){
                    last --;
                }
            }else{
                last = i;
            }
        }
        StringBuilder builder = new StringBuilder();
        for(int i=0; i<chars.length; i++){
            if(chars[i] != '0'){
                builder.append(chars[i]);
            }
        }

        return builder.toString();
    }
}

3차코드

Runtime: 3 ms, faster than 99.83% of Java online submissions for Remove All Adjacent Duplicates In String.
Memory Usage: 38.1 MB, less than 100.00% of Java online submissions for Remove All Adjacent Duplicates In String.

• 2차코드에서 StringBilder 제거

// "abbaca"

       if(S.length()<= 1){
            return S;
        }

        char[] chars = S.toCharArray();

        int last = 0;
        int resltLenth = chars.length;
        for(int i=1; i<chars.length; i++){
            if(last >= 0 && chars[last] == chars[i]){ // 같을때
                chars[i] = '0';
                chars[last] = '0';
                last --;
                resltLenth-=2;
                while(last >=0 && chars[last] == '0' ){
                    last --;
                }
            }else{
                last = i;
            }
        }

        char[] result = new char[resltLenth];
        int resultIndex =0;
        for(int i=0; i<chars.length; i++){
            if(chars[i] != '0'){
                result[resultIndex++] = chars[i];
            }
        }
        return new String(result);

290. word-pattern

• 문제 이해가 문제보다 더 어려운 문제

bijection :  전단사 

class Solution {
    public boolean wordPattern(String pattern, String str) {
        
        String[] map = new String[30];
        char [] patternArr  = pattern.toCharArray();
        String[] strArr = str.split(" ");

        Set<String> used = new HashSet<>();

        if(patternArr.length != strArr.length){
            return false;
        }

        for(int i=0; i<patternArr.length; i++){
            String value = map[patternArr[i]-'a'] ;
            if(value == null){
                if(used .contains(strArr[i])){
                    return false;
                }
                used.add(strArr[i]);
                map[patternArr[i]-'a']  = strArr[i];
            }else{
                if(!map[patternArr[i]-'a'].equals(strArr[i])){
                    return false;
                }
            }
        }

        return true;
    }
}

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

• 정방향 탐색하면서 앞뒤가 0이면 1로 변경하고 n–해준다.
• n <= 작으면 return true

Runtime: 1 ms, faster than 100.00% of Java online submissions for Can Place Flowers.
Memory Usage: 38.6 MB, less than 100.00% of Java online submissions for Can Place Flowers.

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if(flowerbed.length ==0){
            return false;
        }
        if(flowerbed.length==1){
            if(flowerbed[0] == 0){
                if(n <=1){
                    return true;
                }else{
                    return false;
                }
            }else{
                return n==0;
            }
        }

        for( int i=0; i<flowerbed.length; i++){
            if(flowerbed[i]==1){
                continue;
            }
            if(i ==0){
                if(flowerbed[i+1]==0){
                    n--;
                    flowerbed[i]=1;
                }
            }else if(i == flowerbed.length-1){
                if(flowerbed[i-1] == 0){
                    flowerbed[i] =1;
                    n--;
                }
            }else{
                if(flowerbed[i-1] == 0 && flowerbed[i+1]==0){
                    flowerbed[i] =1;
                    n--;
                }
            }
        }
        return n<=0;
    }
}

665. non-decreasing-array

• Runtime: 1 ms, faster than 99.48% of Java online submissions for Non-decreasing Array.
• 이 문제 조금 어렵네요
• for문 한번돌리려고 했는데 너무 로직이 복잡해서 2번돌리는걸로

class Solution {
    public boolean checkPossibility(int[] nums) {
       if(nums.length <= 2){
            return true;
        }

        int count =0;
        boolean pre = true;
        boolean after = true;
        for(int i=0; i<nums.length-1; i++){
            if(nums[i] <= nums[i+1]){

            }else{
                if(count >0){
                    pre =  false;
                    break;
                }
                count++;
                if(i >0){
                    if(nums[i-1] >nums[i+1]){
                        pre= false;
                        break;
                    }
                }
            }
        }
        count =0;
        for(int i=0; i<nums.length-1; i++){
            if(nums[i] <= nums[i+1]){

            }else{
                if(count >0){
                    after =  false;
                    break;
                }
                count++;
                if(i+2 <nums.length){
                    if(nums[i] >nums[i+2]){
                        after= false;
                        break;
                    }
                }
                i++;
            }
        }

        return (pre || after);
    }
}

• 윗코드 리팩토링

public class Solution {
    public boolean checkPossibility(int[] nums) {

        if(nums.length <= 2){
            return true;
        }

        int count =0;
        for(int i=0; i<nums.length-1; i++){
            if(nums[i] > nums[i+1]){
                if(count++ >0)    return false;
                if(i >0){
                    if(nums[i-1] <=nums[i+1]){
                        nums[i-1] = nums[i];
                        continue;
                    }
                }
                if(i+2 <nums.length){
                    if(nums[i]<=nums[i+2]){
                        nums[i+1] = nums[i];
                        continue;
                    }else{
                        if(i>0){
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}