13. Roman to Integer Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II. ...
1175. Prime Arrangements Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.) (Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.) Since the answer may be large, return the answer modulo 10^9 + 7. Example 1: Input: n = 5 Output: 12 Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1. Example 2: Input: n = 100 Output: 682289015 Constraints: ...
1913. Maximum Product Difference Between Two Pairs The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d). For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16. Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized. ...
50. Pow(x, n) Implement pow(x, n), which calculates x raised to the power n (i.e., xn). Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2: Input: x = 2.10000, n = 3 Output: 9.26100 Example 3: Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 Constraints: -100.0 < x < 100.0 -231 <= n <= 231-1 -104 <= xn <= 104 Solution class Solution { public double myPow(double x, int n) { long N = n; if (n < 0) { x = 1.0 / x; N = -N; } long i = N; double res = 1.0; double current = x; while (i > 0) { if (i % 2 == 1) { res = res * current; } current = current * current; i = i / 2; } return res; } } Solution 2021-11-19 class Solution { public double myPow(double x, int n) { long N = n; if (n < 0) { x = 1 / x; N = -N; } double ans = 1.0; for (long i = N; i > 0; i = i / 2) { if (i % 2 == 1) { ans = ans * x; } x = x * x; } return ans; } } Solution 2021-01-30 class Solution { public double myPow(double x, int n) { long m = n; if (m == 0) return 1; if (m < 0) { m = -m; x = 1 / x; } double base = x; long degree = 1L; while (degree < m) { x = x * x; degree *= 2; } while (degree-- != m) { x /= base; } return x; } }
1071. Greatest Common Divisor of Strings For two strings s and t, we say “t divides s” if and only if s = t + … + t (t concatenated with itself 1 or more times) Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2. Example 1: Input: str1 = "ABCABC", str2 = "ABC" Output: "ABC" Example 2: Input: str1 = "ABABAB", str2 = "ABAB" Output: "AB" Example 3: Input: str1 = "LEET", str2 = "CODE" Output: "" Example 4: Input: str1 = "ABCDEF", str2 = "ABC" Output: "" Constraints: ...
204. Count Primes Count the number of prime numbers less than a non-negative number, n. Example 1: Input: n = 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. Example 2: Input: n = 0 Output: 0 Example 3: Input: n = 1 Output: 0 Constraints: 0 <= n <= 5 * 106 Solution class Solution { public int countPrimes(int n) { boolean[] numbers = new boolean[n + 1]; for (int p = 2; p <= (int) Math.sqrt(n); p++) { if (numbers[p] == false) { for (int j = p + p; j < n; j += p) { numbers[j] = true; } } } int count = 0; for (int i = 2; i < n; i++) { if (numbers[i] == false) { count++; } } return count; } }
11004. Max Consecutive Ones III Given a binary array nums and an integer k, return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s. Example 1: Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6 Explanation: [1,1,1,0,0,1,1,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined. Example 2: Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3 Output: 10 Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined. Constraints: ...
11. Container With Most Water Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water. Notice that you may not slant the container. ...
159. Longest Substring with At Most Two Distinct Characters Given a string s, return the length of the longest substring that contains at most two distinct characters. Example 1: Input: s = "eceba" Output: 3 Explanation: The substring is "ece" which its length is 3. Example 2: Input: s = "ccaabbb" Output: 5 Explanation: The substring is "aabbb" which its length is 5. Constraints: 1 <= s.length <= 104 s consists of English letters. Solution class Solution { public int lengthOfLongestSubstringTwoDistinct(String s) { int start = 0; int end = 0; int maxLen = 0; int uniq = 0; int[] map = new int[128]; while (end < s.length()) { char c = s.charAt(end); map[c]++; if (map[c] == 1) uniq++; end++; while (uniq > 2) { char prev = s.charAt(start); map[prev]--; if (map[prev] == 0) uniq--; start++; } maxLen = Math.max(maxLen, end - start); } return maxLen; } }
209. Minimum Size Subarray Sum Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead. Example 1: Input: target = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: The subarray [4,3] has the minimal length under the problem constraint. Example 2: Input: target = 4, nums = [1,4,4] Output: 1 Example 3: Input: target = 11, nums = [1,1,1,1,1,1,1,1] Output: 0 Constraints: ...