열심히 생각하는 공간

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

https://leetcode.com/problems/diameter-of-binary-tree/

이진트리의 left, right 노드의 가장 긴 길이를 구하는 문제이다.

가장 큰 경우의 수를 구해야한다. 문제를 잘못이해했다..ㅎ

int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDiameter(root);
        return max;
    }
    
    private int maxDiameter(TreeNode root) {
        if(root==null) return 0;
        
        int leftCount = maxDiameter(root.left);
        int rightCount = maxDiameter(root.right);
        
        max = Math.max(max, leftCount+rightCount);
        
        return Math.max(leftCount, rightCount) +1;
        
    }

왼쪽노드와 오른쪽 노드를 더하면서 전역변수인 max와 비교한다. 이걸 재귀적으로 계속반복하여 답을 도출하는 것이다. 

참고 코드

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

https://leetcode.com/problems/counting-bits/

이게 무슨말인고 하니

2진수로 나타냈을때 1의 합을 출력하는 것이다.

number가 만일 5일때, 0~5의 total값을 반환해야하므로 [0, 1, 1, 2, 1, 2] 가 된다.

문제의 뜻은 알겠으나 0~n까지의 1의 수를 어떻게 반환할지 고민하다 고민하다 결국엔 Description을 참고했다.......ㅎ

코드를 보면 왜 이렇게 생각 못했을까...싶은데 그러면서 같이 배워간다고 믿는다.

public static int[] countBits(int num) {

        int[] answer = new int[num+1];

        if(num >= 0)
            answer[0] = 0;

        for(int i = 1;i<=num;i++){
            System.out.println("answer[i]="+answer[i]);
            answer[i] = answer[i/2] + i%2;
            System.out.println("Changed answer[i]="+answer[i]);

        }

        return answer;
    }

참고 코드

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

https://leetcode.com/problems/min-stack/

스택을 구현하는 문제인데 스택을 어떻게 구현하는지가 궁금했다.

문제를 좀더 쉽게 봐야할 것같다.

그렇지만 오늘 최솟값 구하는 알고리즘을 이용하는 것 까지 같이 적용하여 푸는 법을 배웠다.

Stack<Integer> stack = new Stack<>();
    int min = Integer.MAX_VALUE;

    public void push(int val) {
        if(val<=min) {
            stack.push(min);
            min = val;
        } stack.push(val);
    }

    public void pop() {
        if(stack.peek() == min) {
            stack.pop();
            min = stack.pop();
        } else stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        if(stack.peek() <= min) return stack.peek();
        else return min;
    }
}

참고 코드

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

https://leetcode.com/problems/maximum-depth-of-binary-tree/

고민한 시간이 무색하게 정말 간단한 코드를 발견했다. 

public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        else return 1+Math.max(maxDepth(root.left), maxDepth(root.right));
    }

출처 코드

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

https://leetcode.com/problems/majority-element/

검색 없이 풀어보고싶어서 열심히 접근했다. 시도는 좋았다.

좀 더 생각해서 나만의 코드를 짜봐야겠다.

public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        int count = 0;

        // HashMap에 값 넣기
        for(int num : nums) {
            // 이미 값이 있다면 count를 올려서 다시 저장
            if(!map.containsKey(num)) {
                map.put(num, 1);
            }
            else
                map.put(num, map.get(num)+1);
            if(map.get(num) > nums.length/2) {
                count = num;
                break;
            }
        }

        return count;
    }

해시맵을 이용해서 key값에 중복값을 넣고 value값에 중복된 수를 넣는 아이디어는 좋았으나 깔끔하게 생각을 정리할 수 있으면 더 좋겠다.

참고한 코드

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

https://leetcode.com/problems/climbing-stairs/

class Solution {
    public int climbStairs(int n) {
        if(n == 1) {return 1;}
        
        int[] arr = new int[n];
        
        arr[0] = 1; arr[1] = 2;
        for(int i=2; i<n; i++) {
            arr[i] = arr[i-1] + arr[i-2];
        }
         return arr[n-1];
    }
}

감격이다. . 진짜 오랜만에 검색없이 풀었다. 난이도 쉬움이지만 뭐 어떤가!

계단을 오를수 있는 경우의 수를 구하는 것인데 한칸과 두칸만 이동가능하다. 피보나치 수열로 풀었다.

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

https://leetcode.com/problems/permutation-in-string/

Sliding Window 알고리즘을 이용한 문제다. 하지만 나는 정렬을 이용하여 풀었다.

public class No567 {
    public boolean checkInclusion(String s1, String s2) {

        int start = 0;
        if(s1.length() > s2.length() || s1 == null || s2 == null)
            return false;
        if(s1.length() == 0)
            return true;
        s1 = sort(s1);

        while(start < (s2.length() - s1.length()+1)) {
            String str = s2.substring(start, start+s1.length());

            if(s1.equals(sort(str))) {
                return true;
            } else {
                start++;
            }
        }
        return false;

    }

그리고............ 결론은 자그마치. .  ㅋㅋ

어떻게 하면 더 빨리 풀 수 있는지를 생각해야겠다. 냅다 내 실력으로 어떻게든 풀려고만 하는게 독이됐다.

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

회전하는 오름차순에서 하위값 찾기이다.

조건식을 nums[start]를 기준으로 해서 한참을 헤매다가 내 코드와 비슷하지만 정반대로 풀어서 성공한 코드를 발견했다. 덕분에 배웠다.

public class No153 {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length - 1;

        while (start < end) {
            int mid = start + (end-start) / 2;

            if(nums[end] > nums[mid]) {
                end = mid ;
            } else if (nums[end] < nums[mid]) {
                start = mid+1;
            }

        }
        return nums[start];


    }
}

덕분에 배운 코드

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

https://leetcode.com/problems/backspace-string-compare/

#가 backspace 역할을 하면 된다.

처음엔 replace('\b') 로 해주고 넣어줬는데 빈값으로 들어갔다.

그래서 Stack으로 푸는 방법을 생각해 봤다.

속도는 여전히 남들보단 빠르지 않다.  빠른 코드는 어떤 차이가 있는지 빨리 알아가고 싶다.

Stack<Character> fakeS = new Stack<Character>();
        Stack<Character> fakeT = new Stack<Character>();

        int i=0, j=0;
        while(i<s.length()) {
            if(s.charAt(i)=='#') {
                if(!fakeS.isEmpty())
                    fakeS.pop();

            } else {
                fakeS.push(s.charAt(i));
            }

            i++;
        } while(j<t.length()) {
            if(t.charAt(j)=='#') {
                if(!fakeT.isEmpty())
                    fakeT.pop();

            } else {
                fakeT.push(t.charAt(j));
            }

            j++;
        }
        if(fakeS.equals(fakeT)) return true;
        else return false;

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.
• https://leetcode.com/problems/search-a-2d-matrix/

자꾸 Array Out of Index 오류가 나는데 게중 나와 비슷한 코드를 작성한 사람의 것을 찾았다.

참고 코드

class Solution {
 public boolean searchMatrix(int[][] matrix, int target) {        
        int i=0, j=matrix[0].length-1;
     
        while(i<matrix.length && j>=0){
            if(matrix[i][j] == target)
                return true;
            else if(matrix[i][j] < target)
                i++;
            else if(matrix[i][j] > target)
                j--;         
            
}
        return false;
        
    }
}

나의 원래 코드는 이러하다. 손으로 디버깅하면서 노가다로 풀었는데 이렇게 해도 되나 싶다. ㅎㅎ;

 public boolean searchMatrix(int[][] matrix, int target) {        
        
            int m = matrix.length;
            int n = matrix[0].length-1;

            int i=0, j=0;
            while(i<m && j <= n){
                if(matrix[i][j] == target)
                    return true;
                else if(matrix[i][j]< target){
                 if(j == n) {
                     i++;
                     j=0;
                 } else{ 
                    j++;
                 }
                }
                else if(matrix[i][j] > target){
                    i++;
                }
            }
            return false;

        
    }