LeetCode (40) 썸네일형 리스트형 [Medium] 238. Product of Array Except Self (애플 코딩 테스트 문제) Leetcode 238번 문제는 정수로 채워진 array가 주어지고, 원래의 index에있는 값을 제외한 모든 index의 값을 곱한 값이 들어있는 array를 return하는 문제이다. class Solution { public int[] productExceptSelf(int[] nums) { int product = 1; for(int i = 0; i < nums.length;i++){ product *= nums[i]; } int[] arr = new int[nums.length]; for(int i = 0; i < nums.length;i++){ if(nums[i] == 0){ arr[i] = product; } else{ arr[i] = product / nums[i]; } } return a.. [Medium] 39. Combination Sum #Backtracking 풀이 class Solution{ public List combinationSum(int[] nums, int target) { List list = new ArrayList(); backtrack(list, new ArrayList(), nums, target, 0); return list; } private void backtrack(List list, List tempList, int [] nums, int remain, int start){ if(remain < 0) return; else if(remain == 0) list.add(new ArrayList(tempList)); else{ for(int i = start; i < nums.length; i++){ temp.. [Easy] 104. Maximum Depth of Binary Tree Leetcode 104번 문제는 주어진 binary tree의 최대 깊이 (Maximum depth)를 구하는 문제이다. #풀이 class Solution { public int maxDepth(TreeNode root) { if(root == null){ return 0; } int left = 1 + maxDepth(root.left); int right = 1 + maxDepth(root.right); return Math.max(left, right); } } 이 문제는 recursion를 통해 쉽게 풀수 있다. 왼쪽 tree의 깊이를 구하고 오른쪽 트리의 깊이와 비교해 더 큰 값을 return하는 식으로 풀수 있다. 위의 코드를 간략하면 아래처럼 된다. class Solution { public.. [Medium] 53. Maximum Subarray Leetcode 53번 문제는 주어진 array에서 주어진 값을 더했을때 가장 합이 큰 subarray를 찾는 문제이다. #Brute Force 풀이 class Solution { public int maxSubArray(int[] nums) { int max = nums[0]; for(int i=0; i [Medium] 142. Linked List Cycle II Leetcode 142번 문제에서는 Linked List가 주어지고, 주어진 Linked List에서 cycle이 발생하는지 알아내고, 발생하면 발생 지점의 노드를 반환하고, cycle이 발생 하지 않으면 null를 return해주면 된다. #풀이 public class Solution { public ListNode detectCycle(ListNode head) { HashSet hs = new HashSet(); boolean dup = false; while(head != null){ if(!hs.add(head)){ //HashSet에 add가 중복이 발생해 false return시 현재노드 반환 return head; } head = head.next; } return null; } } 이 풀.. [Easy] 35. Search Insert Position Leetcode 35번 문제는 주어진 정렬된 array에서 target을 찾는 문제이다. 만약 target이 array안에 없다면, insertion point를 찾는 문제이다. Searching algorithm의 time complexity는 O(log n) 이어야 한다. Time complextiy와 array가 sorted 돼있다는 점을 고려하면 Binary Search Algoritm를 써서 풀수 있다. #풀이 public int searchInsert(int[] A, int target) { int low = 0, high = A.length-1; while(low target) high = mid-1; else low = mid+1; } return low; } Binary Search후에 .. [Easy] 100. Same Tree Leetcode 100번 문제는 이진 트리 문제이다. 2개의 이진 트리의 root가 주어진다. 두 개의 이진 트리가 똑같은지 알아내는 문제이다. 여기서 똑같다는 정의는 트리의 형태가 같고 모든 노드의 값들도 같아야 한다. #풀이 class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (q == null && p == null){ return true; } if(q != null && p == null || q == null && p != null){ return false; } if(p.val != q.val){ return false; } return isSameTree(p.left, q.left) && isSameTree(p.r.. [Easy] 141. Linked List Cycle Leetcode 141번 문제는 주어진 Linkedlist에 cycle ,즉 순환인 발생하는지 알아내는 문제이다. 위의 예제처럼 어느 한 노드에서 뒤에 노드로 뒤돌아가 반복된다면 cycle이 발생한 것이므로 true를 return 하면 된다. #풀이 Hashset을 사용한 풀이 public class Solution { public boolean hasCycle(ListNode head) { HashSet set = new HashSet(); boolean isCycle = false; while(head != null){ isCycle = set.add(head); head = head.next; if(!isCycle){ return !isCycle; } } return !isCycle; } } Set.. 이전 1 2 3 4 5 다음
