열심히 생각하는 공간

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4x.

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

아직까지 조금 헤매기는 하지만 그래도 실력이 늘고있다고 믿고있다 ㅎㅎ 

하지만 다른사람들의 풀이는 진짜 놀라울 따름이다..

 public static boolean isPowerOfFour(int n) {
        if (n==0) return false;
        double x;
        double doubleN = n;
        x = (Math.log10(doubleN) / Math.log10(4));
        System.out.println("x = "+ x);
        if(isNumeric(x) == true) {
            return true;
        }
        else
            return false;
    }

    public static boolean isNumeric(double x) {
        if(Math.ceil(x) == Math.floor(x)) return true;
        else return false;
    }

double x가 정수인지 아닌지를 판별하는 방법을 생각하던 와중에 다양한 방법을 제시한 사이트를 찾았다. 이 사람들 처럼 창의적인 아이디어가 마구 떠올랐으면 좋겠다.ㅎㅎ

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

https://leetcode.com/problems/flood-fill/

Description보고 이해 안돼서 유투브도 같이 봤다. 

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 sr, int sc, int color, int newColor) {
 	if(sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] != color) return;
    image[sr][sc] = newColor;
    fill(image, sr+1, sc, color, newColor);
    fill(image, sr-1, sc, color, newColor);
    fill(image, sr, sc+1, color, newColor);
    fill(image, sr, sc-1, color, newColor);
    
    }
  }

참고 코드

참고 영상

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

머리로는 푸는데 코드로 나타내기만 좀 더.. 해야겠다.

Description이 이해가 안되는 중에 정말 설명이 간단하고 잘 된 영상을 발견했다.

public Node connect(Node root) {
        if(root == null) 
            return root;
        
        Node leftNode = root;
        while(leftNode.left != null) {
            Node head = leftNode;
            while(head != null) {
                head.left.next = head.right;
                if(head.next != null) {
                    head.right.next = head.next.left;
                } head = head.next;
            }
           leftNode = leftNode.left;
        }
        return root;
        
    }

참코 코드

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

https://leetcode.com/problems/merge-two-binary-trees/

두 트리의 합을 구해 새 트리를 만드는 문제이다.

그래도 아이디어까진 얼추 맞힌 것 같다.

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null) return root2;
        if(root2 == null) return root1;
        
        TreeNode root3 = new TreeNode(root1.val + root2.val);
      
            root3.left = mergeTrees(root1.left, root2.left);
            root3.right = mergeTrees(root1.right, root2.right);
     
        
        return root3;
    }

참고 코드

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

https://leetcode.com/problems/partition-labels/

문자열을 끊되, 중복되지 않는 한에서 가장 많이 끊을 수 있는 경우의 수를 구하는 문제이다.

이 문제를 어떻게든 풀고싶어서. . 며칠을 고민하고 풀었는데

간단하지만 직관적인 해설방법을 역시나 찾았다 ㅎㅎ;

  public static List<Integer> partitionLabels(String s) {
        Map<Character, Integer> map = new HashMap();
        for(int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch,i);
        }

        List<Integer> res = new LinkedList();
        int prev = -1;
        int max = 0;

        for(int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            max = Math.max(max, map.get(ch));

            // 끝에 달았을때
            if(max == i) {
                res.add(max - prev) ;
                prev = max;
            }
        }
        return res;
    }

참고 코드

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

https://leetcode.com/problems/generate-parentheses/

n쌍의 괄호가 나올 수 있는 경우의 수를 구하는 문제이다.

이런 문제를 접할때 마다 정말. . 이렇게 간단하게 풀어내는 사람들이 신기할 뿐이다. .

List<String> res = new LinkedList();
    public List<String> generateParenthesis(int n) {
        dfs(new StringBuilder(), 0, n);
        return res;
    }
    private void dfs(StringBuilder sb, int close, int n) {
        if(n==0 && close==0) {
            res.add(sb.toString());
            return;
        }

        //Add open parenthese
        if(n>0) {
            sb.append('(');
            dfs(sb, close+1, n-1);
            sb.setLength(sb.length()-1);
        }

        //Add close parenthese
        if(close>0) {
            sb.append(')');
            dfs(sb, close-1, n);
            sb.setLength(sb.length()-1);
        }
    }

참고 코드

https://leetcode.com/problems/intersection-of-two-linked-lists/

두 ListNode가 교차하는 첫번째 ListNode를 구하는 문제이다.

ListNode를 거꾸로 해서 뒤에서부터 같은지점까지를 반환하게끔 고민했으나 

순번대로 하는게 더 쉬웠음을.. 깨닫는다.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
            
        ListNode pa = headA, pb = headB;
        while(pa != pb) {
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }
        return pa;
    }

참고 코드

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

https://leetcode.com/problems/merge-two-sorted-lists/

두 LinkedList의 대소관계를 따져 순차적으로 반환하는 문제이다. while을 쓰기전에 재귀로 풀 수 있는지를 따져보면 좀더 수월할 것 같다.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
      
        
            if(list1.val > list2.val) {
                list2.next = mergeTwoLists(list2.next, list1);
                return list2;
            } else {
                list1.next = mergeTwoLists(list2, list1.next);
                return list1;
            }   
       
    }

참고 코드

Given the head of a singly linked list, return true if it is a palindrome.

https://leetcode.com/problems/palindrome-linked-list/

다시 합창합시다~를 거꾸로하면 다시 합창합시다~ 이런 LinkedList를 구하는 문제이다. 전 포스팅에서 다룬 ReverseLinkedList를 이용해서 코드를 작성했었으나. . . . 안됐다. 왜????

public boolean isPalindrome(ListNode head) {
        ListNode reverseHead = reverseList(head);
        
        ListNode p1 = head;
        ListNode p2 = reverseHead;
        
        while(head != null) {          
            if(head.val != reverseHead.val)  return false;     
            
            head = head.next;
            reverseHead = reverseHead.next;
        }
        
        return true;
    }
    
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = null;
     
        while(head != null) {
            ListNode newNode = new ListNode(head.val);
            newNode.next = dummy.next;
            dummy.next = newNode;
            head = head.next;
        }
        return dummy.next;
        
        
    }

참고 코드

이 분과 내가 구현하고자 하는 코드가 비슷해서 참고했는데 왜 내가 작성한 reverse화 하는 코드는 안되고 이것은 되는가 좀 더 고민해봐야겠다.

참고로 내가 작성한 코드 또한 참고 코드이다. (전 포스팅 206번에도 언급)

// 이것과
public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        
        
        if (head == null) {
            return head;
        }
        while(head != null) {
            ListNode cur = head;
            head = head.next;
            cur.next = prev;
            prev = cur;
            
        }
        return prev;
        
        
    }
    
 // 이것의 차이
 
 public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = null;
     
        while(head != null) {
            ListNode newNode = new ListNode(head.val);
            newNode.next = dummy.next;
            dummy.next = newNode;
            head = head.next;
        }
        return dummy.next;
       
    }

Given the head of a singly linked list, reverse the list, and return the reversed list.

https://leetcode.com/problems/reverse-linked-list/

LinkedList를 역순으로 만드는 문제이다.  참고 코드가 많아지면서 블로그에 올리지 못한 문제들이 많다. 이 문제는 다음 포스팅할 234번을 위해 작성한다. (Palindrome 문제인데 이 문제를 기본으로 작성해봤기 때문이다.)

public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        
        
        if (head == null) {
            return head;
        }
        while(head != null) {
            ListNode cur = head;
            head = head.next;
            cur.next = prev;
            prev = cur;
            
        }
        return prev;
        
        
    }

참고 코드