김태영

[LeetCode] Grind 75 questions (25/75) Maximum Subarray

Grind75 문제로 풀이2 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int maxSubArray(int[] nums) { int maxCurrent = nums[0]; int maxGlobal = nums[0]; for(int i = 1; i < nums.length; i++) { maxCurrent = Math.max(nums[i], maxCurrent + nums[i]); if(maxCurrent > maxGlobal) maxGlobal = maxCurrent; } return maxGlobal; } } ...

[LeetCode] Grind 75 questions (21/75) Diameter of Binary Tree

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 28 29 30 31 32 33 34 35 36 37 38 39 /** * 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 { private int diameter = 0; // 두 점을 연결하는 가장 긴 경로, 지름 public int diameterOfBinaryTree(TreeNode root) { getHeight(root); return diameter; } public int getHeight(TreeNode node) { if (node == null) return 0; int leftHeight = getHeight(node.left); int rightHeight = getHeight(node.right); // 노드를 통해 지나가는 경로의 길이 int pathThroughNode = leftHeight + rightHeight; // 현재까지의 최대 직경 갱신 diameter = Math.max(diameter, pathThroughNode); // 현재 노드의 높이 반환 return Math.max(leftHeight, rightHeight) + 1; } }

[LeetCode] Grind 75 questions (22/75) Middle of the Linked List

Grind75 문제로 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 /** * 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 middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } }

[LeetCode] Grind 75 questions (23/75) Maximum Depth of Binary Tree

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

[LeetCode] Grind 75 questions (24/75) Contains Duplicate

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

[LeetCode] Grind 75 questions (20/75) Add Binary

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

[LeetCode] Grind 75 questions (16/75) Climbing Stairs

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

[LeetCode] Grind 75 questions (17/75) Longest Palindrome

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

[LeetCode] Grind 75 questions (18/75) Reverse Linked List

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

[LeetCode] Grind 75 questions (19/75) Majority Element

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