A parentheses string is valid if and only if: It is the empty string, It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string. You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string. ...
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order. Example 1: Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]] Example 2: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Constraints: 1 <= nums.length <= 8 -10 <= nums[i] <= 10 Solution class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> res = new ArrayList<>(); permuteAt(0, nums, res); return res; } void permuteAt(int i, int[] nums, List<List<Integer>> res) { if (i == nums.length) { res.add(toList(nums)); return; } Set<Integer> seen = new HashSet<>(); for (int j = i; j < nums.length; j++) { if (seen.add(nums[j])) { swap(i, j, nums); permuteAt(i + 1, nums, res); swap(i, j, nums); } } } void swap(int i, int j, int[] arr) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } List<Integer> toList(int[] values) { List<Integer> res = new ArrayList<>(values.length); for (int val : values) { res.add(val); } return res; } }
Given two strings s and t, return true if they are both one edit distance apart, otherwise return false. A string s is said to be one distance apart from a string t if you can: Insert exactly one character into s to get t. Delete exactly one character from s to get t. Replace exactly one character of s with a different character to get t. Example 1: Input: s = "ab", t = "acb" Output: true Explanation: We can insert 'c' into s to get t. Example 2: Input: s = "", t = "" Output: false Explanation: We cannot get t from s by only one step. Example 3: Input: s = "a", t = "" Output: true Example 4: Input: s = "", t = "A" Output: true Constraints: ...
Given a string queryIP, return “IPv4” if IP is a valid IPv4 address, “IPv6” if IP is a valid IPv6 address or “Neither” if IP is not a correct IP of any type. A valid IPv4 address is an IP in the form “x1.x2.x3.x4” where 0 <= xi <= 255 and xi cannot contain leading zeros. For example, “192.168.1.1” and “192.168.1.0” are valid IPv4 addresses but “192.168.01.1”, while “192.168.1.00” and “192.168@1.1” are invalid IPv4 addresses. ...
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3]. ...
Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them. A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1. Example 1: Input: root = [1,null,2,null,3,null,4,null,null] Output: [2,1,3,null,null,null,4] Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct. ...
Given two sparse vectors, compute their dot product. Implement class SparseVector: SparseVector(nums) Initializes the object with the vector nums dotProduct(vec) Compute the dot product between the instance of SparseVector and vec A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector. Follow up: What if only one of the vectors is sparse? ...
Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. Implement the MovingAverage class: MovingAverage(int size) Initializes the object with the size of the window size. double next(int val) Returns the moving average of the last size values of the stream. Example 1: Input ["MovingAverage", "next", "next", "next", "next"] [[3], [1], [10], [3], [5]] Output [null, 1.0, 5.5, 4.66667, 6.0] Explanation MovingAverage movingAverage = new MovingAverage(3); movingAverage.next(1); // return 1.0 = 1 / 1 movingAverage.next(10); // return 5.5 = (1 + 10) / 2 movingAverage.next(3); // return 4.66667 = (1 + 10 + 3) / 3 movingAverage.next(5); // return 6.0 = (10 + 3 + 5) / 3 Constraints: ...
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Note: You must not use any built-in BigInteger library or convert the inputs to integer directly. Example 1: Input: num1 = "2", num2 = "3" Output: "6" Example 2: Input: num1 = "123", num2 = "456" Output: "56088" Constraints: 1 <= num1.length, num2.length <= 200 num1 and num2 consist of digits only. Both num1 and num2 do not contain any leading zero, except the number 0 itself. Solution class Solution { public String multiply(String num1, String num2) { int[] products = new int[num1.length() + num2.length()]; for (int i = 0; i < num1.length(); i++) { for (int j = 0; j < num2.length(); j++) { int d1 = num1.charAt(i) - '0'; int d2 = num2.charAt(j) - '0'; products[i + j + 1] += d1 * d2; } } int carry = 0; for (int i = products.length - 1; i >= 0; i--) { int tmp = (products[i] + carry) % 10; carry = (products[i] + carry) / 10; products[i] = tmp; } StringBuilder sb = new StringBuilder(); for (int product: products) { if (product == 0 && sb.length() == 0) { continue; } sb.append(product); } if (sb.length() == 0) { sb.append("0"); } return sb.toString(); } }
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function). The algorithm for myAtoi(string s) is as follows: Read in and ignore any leading whitespace. Check if the next character (if not already at the end of the string) is ‘-’ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored. Convert these digits into an integer (i.e. “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2). If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1. Return the integer as the final result. Note: ...