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;
    }
}

오랫만에 쓰는 일기

오늘은 그냥 이런저런 잡담이다. ㅎ

어제는 꿈을 꾸었는데 회사에 입사를 했는데 알고리즘 문제가 나왔다.
이런~ 꿈속에서 알고리즘 문제를 푸는것은 처음이었다.

문제

1, 2, 3   ( 2개  )  81, 91 이런 문제였던것 같다. 123과 81, 91 사이에 나올수 있는
(2개에서) 숫자의 경우의 수가 몇가지인가???
(단 정렬된 구조이며, 숫자가 중복이 가능하다 )

이 문제가 나왔네.. 이 문제는 나의 기억이 만들어낸 문제인가? 아니면 화가나 음악가들은 꿈속에서 영감을 받는다고 하는데 이것도 그것중의 하나인가?


(근황)
- 요즘 애들보느라 너무 공부를 안한다. 핑계인가? 놀고싶어서인가?
- 오늘 월요일아침 출근길에 문뜩 내가 살아있고 숨쉬고 있음을 느꼈다.