Midterm

1. Two Sum

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        int x = 0;
        int y = 1;
        boolean found = (nums[x] + nums[y] == target);
        while (!found && x < nums.length - 1 && y < nums.length ) {
            for (int i = 0; i < nums.length - 1; i++) {
                x = i;
                int xval = nums[i];
                for (int j = i; j < nums.length; j++) {
                    y = j;
                    int yval = nums[j];

                    found = nums[x] + nums[y] == target;
                }
            }
        }

        if (found) {
            result[0] = x;
            result[1] = y;
            return result;
        } else {
            return null;
        }
    }
}

testcase는 통과했지만 실전은 통과 못했다는점~
답안 보고 난 후) 븅신인가? 내 사랑 해쉬맵 미안해 사랑해 내가 더 잘할게🤙

121. Best Time to Buy and Sell Stock

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        int maxProfit = 0;
        int curProfit = 0;
        int bought = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < bought) {
                bought = prices[i];
            } else {
                curProfit = prices[i] - bought;
                if (curProfit > maxProfit) {
                    maxProfit = curProfit; 
                }
            }
        }
        return maxProfit;
    }
}

Runtime: 1 ms, faster than 97.54% of Java online submissions for Best Time to Buy and Sell Stock.
Memory Usage: 38.5 MB, less than 81.84% of Java online submissions for Best Time to Buy and Sell Stock.

거저 먹는 문제로 내고 거저먹었다~

70. Climbing Stairs

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        int one = 1;
        int two = 2;
        int cur = 3; 
        for (int i = 3; i <= n; i++) {
            cur = one + two;
            one = two;
            two = cur; 
        }
        
        return cur;
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Climbing Stairs.
Memory Usage: 35.9 MB, less than 25.77% of Java online submissions for Climbing Stairs.

피보나치 다시 그려서 풀었다~

202. Happy Number

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> list = new HashSet<Integer>();
        
        int start = n;
        int end = squared(n);
        
        while (end != 1 && start != end) {
            start = squared(start);
            end = squared(squared(end));
        }
        
        return end == 1;
    }
    
    private int squared(int n) {
        int val = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            val = val + d * d;
        }
        return val;
    }
}

Runtime: 1 ms, faster than 82.65% of Java online submissions for Happy Number.
Memory Usage: 36.3 MB, less than 30.93% of Java online submissions for Happy Number.

트라우마 1 해피넘버..
왜 이게 맞는진 가물가물하지만 어쩌구 circle algorithm 기억해 내서 풀었다~

160. Intersection of Two Linked Lists

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        ListNode a = headA;
        ListNode b = headB;
        
        while (a != b) {
            a = a == null? headB : a.next;
            b = b == null? headA : b.next;
        }
        
        return a; 
        
    }
}

Runtime: 1 ms, faster than 97.67% of Java online submissions for Intersection of Two Linked Lists.
Memory Usage: 42 MB, less than 51.17% of Java online submissions for Intersection of Two Linked Lists.

천재 답안 문제
아직도 차이 없애는 방법 생각하면 놀랍다

234. Palindrome Linked List

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        ListNode cur = head;
        List<Integer> vals = new ArrayList<Integer>();
        while (cur != null) {
            vals.add(cur.val);
            cur = cur.next;
        }
        
        int size = vals.size();
        
        for (int i = 0; i < size / 2; i++) {
            if (! vals.get(i).equals(vals.get(size - i - 1))) {
                return false;
            }
        }
        
        return true; 
    }
}

Runtime: 3 ms, faster than 25.21% of Java online submissions for Palindrome Linked List.
Memory Usage: 42.9 MB, less than 33.67% of Java online submissions for Palindrome Linked List.