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: ...
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there? Above is a 7 x 3 grid. How many possible unique paths are there? ...
You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin. Example 1: Input: amount = 5, coins = [1, 2, 5] Output: 4 Explanation: there are four ways to make up the amount: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 Example 2: Input: amount = 3, coins = [2] Output: 0 Explanation: the amount of 3 cannot be made up just with coins of 2. Example 3: Input: amount = 10, coins = [10] Output: 1 Note: ...
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue. Note: The number of people is less than 1,100. Example Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]] Solution: ...