Logs

Grind75 문제로 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int maxDepth(TreeNode root) { if(root == null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } }

Grind75 문제로 풀이2 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public boolean containsDuplicate(int[] nums) { Map<Integer, Integer> numsMap = new HashMap(); for(int num : nums) { numsMap.put(num, numsMap.getOrDefault(num, 0) + 1); if(numsMap.get(num) > 1) return true; } return false; } } 풀이2 1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> numsSet = new HashSet(); for(int num : nums) { if(numsSet.add(num)) ; else return true; } return false; } }

Grind75 문제로 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public String addBinary(String a, String b) { StringBuilder result = new StringBuilder(); int sizeA = a.length() - 1; int sizeB = b.length() - 1; int carry = 0; while(sizeA >= 0 || sizeB >= 0) { int digitA = sizeA >= 0 ? a.charAt(sizeA) - '0' : 0; int digitB = sizeB >= 0 ? b.charAt(sizeB) - '0' : 0; int sum = digitA + digitB + carry; result.append(sum % 2); carry = sum / 2; sizeA--; sizeB--; } if(carry != 0) result.append(carry); return result.reverse().toString(); } }

Grind75 문제로 풀이 시간 복잡도 $O(2^n)$ 1 2 3 4 5 6 7 8 class Solution { public int climbStairs(int n) { if (n <= 1) { return 1; } return climbStairs(n - 1) + climbStairs(n - 2); } } 풀이2 시간 복잡도 $O[n]$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution { public int climbStairs(int n) { if (n <= 1) return 1; int[] dp = new int[n+1]; dp[0] = 1; dp[1] = 1; for(int i = 2; i <= n; i++) { dp[i] = dp[i-2] + dp[i-1]; } return dp[n]; } } ...

Grind75 문제로 풀이 시간 복잡도 $O(2^n)$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int longestPalindrome(String s) { Map<Character, Integer> map = new HashMap(); for(char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) +1); } int result = 0; for(int i : map.values()) { if(i % 2 == 0) result = result + i; else if(i-1 != 0 && (i -1) % 2 == 0) result = result + (i - 1); // ccc } for(int i : map.values()) { if(i % 2 == 1) return result + 1; } return result; } } ...

Grind75 문제로 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; while(head != null) { ListNode next = head.next; head.next = prev; prev = head; head = next; } return prev; } }

Grind75 문제로 풀이 Boyer-Moore Voting Algorithm 시간복잡도 $O(1)$ 공간복잡도 $O(n)$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int majorityElement(int[] nums) { int candidate = nums[0]; int count = 0; for(int num : nums) { if(count == 0) { candidate = num; } if(candidate == num) { count++; } else { count--; } } return candidate; } }

Grind75 문제로 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 /* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion(int n) { int left = 1; int right = n; while(left < right) { int mid = left + (right - left) / 2; // 정수 오버플로를 방지하면서 중간값 계산 if(isBadVersion(mid)) right = mid; // mid가 불량이면 그 이전에도 불량이 있을 수 있으므로 right를 mid로 설정 else left = mid + 1; // mid가 불량이 아니라면 그 이후에 불량이 있으므로 left를 mid + 1로 설정 } return left; // left가 right와 같아지는 시점에 첫 번째 불량품을 찾는다. } }

Grind75 문제로 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public boolean canConstruct(String ransomNote, String magazine) { Map<Character, Integer> magazineMap = new HashMap(); for(char c : magazine.toCharArray()) { magazineMap.put(c, magazineMap.getOrDefault(c, 0) + 1); } for(char c : ransomNote.toCharArray()) { magazineMap.put(c, magazineMap.getOrDefault(c, 0) - 1); } for(int i : magazineMap.values()) { if(i < 0) return false; } return true; } } ...

Grind75 문제로 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isBalanced(TreeNode root) { if(root == null) return true; if(Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) return false; return isBalanced(root.left) && isBalanced(root.right); } private int getHeight(TreeNode node) { if(node == null) return 1; return Math.max(getHeight(node.left), getHeight(node.right)) + 1; } }