Leetcode

Design a data structure that supports all following operations in average O(1) time. insert(val): Inserts an item val to the set if not already present. remove(val): Removes an item val from the set if present. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned. Example: // Init an empty set. RandomizedSet randomSet = new RandomizedSet(); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomSet.insert(1); // Returns false as 2 does not exist in the set. randomSet.remove(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomSet.insert(2); // getRandom should return either 1 or 2 randomly. randomSet.getRandom(); // Removes 1 from the set, returns true. Set now contains [2]. randomSet.remove(1); // 2 was already in the set, so return false. randomSet.insert(2); // Since 2 is the only number in the set, getRandom always return 2. randomSet.getRandom(); Solution: ...

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library’s sort function for this problem. Example: Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Follow up: ...

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A. You may return any answer array that satisfies this condition. Example 1: Input: [3,1,2,4] Output: [2,4,3,1] The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted. Note: 1 <= A.length <= 5000 0 <= A[i] <= 5000 Solution: class Solution { public int[] sortArrayByParity(int[] A) { int n = A.length; int i = 0; int j = 1; while (i < n && j < n) { if (A[i] % 2 == 1) { j = i + 1; while (j < n && A[j] % 2 == 1) { j++; } if (j == n) { break; } int c = A[i]; A[i] = A[j]; A[j] = c; } i++; } return A; } }

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even. Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even. You may return any answer array that satisfies this condition. Example 1: Input: [4,2,5,7] Output: [4,5,2,7] Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted. Note: 2 <= A.length <= 20000 A.length % 2 == 0 0 <= A[i] <= 1000 Solution: ...

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n? Example: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 Notes: Catalan’s numbers: C(0) = C(1) = 1 C(2) = C(1) * C(0) + C(0) * C(1) C(3) = C(2) * C(1) + C(1) * C(1) + C(1) * C(2) Solution: ...

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C. Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.) Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], …, C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.) ...

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle. Solution: class Solution { public int maxSubArray(int[] nums) { if (nums.length == 1) { return nums[0]; } int dp = nums[0]; int answer = nums[0]; for (int i = 1; i < nums.length; i++) { dp = Math.max(dp, 0) + nums[i]; answer = Math.max(answer, dp); } return answer; } } Solution 2021-11-20 class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int[] dp = new int[n]; int max = nums[0]; for (int i = 0; i < n; i++) { if (i == 0) { dp[i] = nums[i]; } else { dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); max = Math.max(dp[i], max); } } return max; } }

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1: Input: [1,3,5,6], 5 Output: 2 Example 2: Input: [1,3,5,6], 2 Output: 1 Example 3: Input: [1,3,5,6], 7 Output: 4 Example 4: Input: [1,3,5,6], 0 Output: 0 Solution: class Solution { public int searchInsert(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] < target) { l = mid + 1; } else { r = mid - 1; } } return l; } }

Given an integer, write a function to determine if it is a power of two. Example 1: Input: 1 Output: true Explanation: 20 = 1 Example 2: Input: 16 Output: true Explanation: 24 = 16 Example 3: Input: 218 Output: false Solution: class Solution { public boolean isPowerOfTwo2(int n) { if (n == 0 ) { return false; } if (n == 1) { return true; } while (n % 2 == 0 && n > 2) { n = n / 2; } return n == 0 || n == 2; } public boolean isPowerOfTwo(int n) { if (n == 0 ) { return false; } if (n == Integer.MIN_VALUE) { return false; } return (n & (n - 1)) == 0; } }

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element. Now given an M x N matrix, return True if and only if the matrix is Toeplitz. Example 1: Input: matrix = [ [1,2,3,4], [5,1,2,3], [9,5,1,2] ] Output: True Explanation: In the above grid, the diagonals are: "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]". In each diagonal all elements are the same, so the answer is True. Example 2: ...