1, Divide and conquer method of reducing complexity to simplicity
1. Design priority for arithmetic expressions
Question:
Give you a string expression composed of numbers and operators, combine numbers and operators according to different priorities, calculate and return the results of all possible combinations. You can return answers in any order.
Example 1:
Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:
Input: expression = "2*3-4*5"
Output: [- 34, - 14, - 10, - 10,10]
Explanation:
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 6 public class ques_241_Design priority for arithmetic expressions { 7 public List<Integer> diffWaysToCompute(String expression) { 8 List<Integer> ways = new ArrayList<>(); 9 for (int i = 0; i < expression.length(); i++) { 10 char c = expression.charAt(i); 11 if (c == '+' || c == '-' || c == '*') { 12 List<Integer> left = diffWaysToCompute(expression.substring(0, i)); // left = 2 13 List<Integer> right = diffWaysToCompute(expression.substring(i + 1)); // right = 1 14 for (Integer l : left) { 15 for (Integer r : right) { 16 if (c == '+') { 17 ways.add(l + r); 18 } else if (c == '-') { 19 ways.add(l - r); 20 } else { 21 ways.add(l * r); 22 } 23 } 24 } 25 } 26 } 27 if (ways.size() == 0) { 28 ways.add(Integer.valueOf(expression)); 29 } 30 return ways; 31 } 32 } 33 34 class Test_241 { 35 public static void main(String[] args) { 36 String expression = "2-1"; 37 ques_241_Design priority for arithmetic expressions s = new ques_241_Design priority for arithmetic expressions(); 38 System.out.println(s.diffWaysToCompute(expression)); 39 } 40 }
2. Beautiful array
Question:
For some fixed N, if the array A is an integer 1, 2, The arrangement of n ￠ components such that:
For every ， I < J, there is no ， K satisfying ， I < K < J ， such that ， A[k] * 2 = A[i] + A[j].
Then array A ， is A beautiful array.
Given ＾ N, return any array ＾ A (ensure there is one).
Example 1:
Input: 4
Output: [2,1,4,3]
Example 2:
Input: 5
Output: [3,1,2,5,4]
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 import java.util.Arrays; 4 import java.util.HashMap; 5 import java.util.Map; 6 7 /** 8 * Idea: A[k]*2=A[i]+A[j], I < K < J, it can be seen that the left side of the equation must be an even number. As long as the sum on the right side is an odd number, it can be guaranteed that it is not tenable. Let A[i] and A[j] be an odd number and an even number. 9 * For all integers from 1 to N, the odd number is (N + 1) / 2 and the even number is N / 2 10 * 1,For all integers x from 1 to (N + 1)/2, get their beautiful array and map to all odd numbers 2 * x - 1 in the range of 1 to N 11 * 2,For all integers x from 1 to N/2, get their beautiful array and map to all even numbers 2 * x in the range of 1 to n 12 * Example: n = 1 [1] 13 * N = 2 [1,2] 14 * N = 3 Odd n = 2 1 * 2-1 2 * 2-1 [1,3] 15 * Even n = 1 * 2 [2] 16 * [1,3,2] after combination 17 * N = 4 Odd n = 2 1 * 2-1 2 * 2-1 [1,3] 18 * Even n = 2 1 * 2 2 * 2 [2,4] 19 * [1,3,2,4] after combination 20 * N = 5 Odd n = 3 1 * 2-1 3 * 2-1 2 * 2-1 [1,5,3] 21 * Even n = 2 1 * 2 2 * 2 [2,4] 22 * After combination, it is [1,5,3,2,4] 23 * ...... 24 */ 25 public class ques_932_Beautiful array { 26 Map<Integer, int[]> map = new HashMap<>(); 27 public int[] beautifulArray(int n) { 28 map.put(1, new int[]{1}); 29 return f(n); 30 } 31 32 public int[] f(int n) { 33 if (!map.containsKey(n)) { 34 int[] res = new int[n]; 35 int index = 0; 36 for (int x : f((n + 1) / 2)) { 37 res[index++] = 2 * x - 1; 38 } 39 for (int x : f(n / 2)) { 40 res[index++] = 2 * x; 41 } 42 map.put(n,res); 43 } 44 return map.get(n); 45 } 46 } 47 48 class Test_932 { 49 public static void main(String[] args) { 50 int n = 4; 51 ques_932_Beautiful array s = new ques_932_Beautiful array(); 52 System.out.println(Arrays.toString(s.beautifulArray(n))); 53 } 54 }
3. Poke balloon
Question:
There are n balloons, numbered from 0 to n - 1. Each balloon is marked with a number. These numbers exist in the array # nums #.
Now I ask you to pierce all the balloons. Pierce the i-th balloon and you can get} nums[i - 1] * nums[i] * nums[i + 1] coins. Here, i - 1 and I + 1 represent the serial numbers of two balloons adjacent to # I #. If i - 1 or I + 1 goes beyond the bounds of the array, it is regarded as a balloon with a number of 1.
Find the maximum number of coins you can get.
Example 1:
Input: num = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
Example 2:
Input: num = [1,5]
Output: 10
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 import java.util.Arrays; 4 5 /** 6 * Idea: let solve(i,j) represent the maximum number of coins that can be obtained by filling all the positions in the open section (i,j) with balloons. Since it is an open interval, the numbers of balloons at both ends of the interval are i and j, 7 * Corresponding to val[i] and val[j]. 8 * When i ≥ j − 1, there is no balloon in the open section, and the value of solve(i,j) is 0; 9 * When I < J − 1, enumerate all position mid in the open interval (i,j) so that mid is the first balloon added in the current interval. This operation can get the number of coins as val[j]val[i] × val[mid] × val[j]. 10 * At the same time, the contribution of the divided two intervals to solve(i,j) is recursively calculated. The maximum value of the sum of these three terms is the value of solve(i,j). 11 * In this way, the problem is transformed into solving (I, mid) and solving (mid, J). 12 */ 13 public class ques_312_Poke balloon { 14 int[] val; 15 int[][] res; 16 17 public int maxCoins(int[] nums) { 18 int n = nums.length; 19 val = new int[n + 2]; 20 val[0] = 1; 21 for (int i = 1; i <= n; i++) { 22 val[i] = nums[i - 1]; 23 } 24 val[n + 1] = 1; // val = [1, 3, 1, 5, 8, 1] 25 res = new int[n + 2][n + 2]; 26 for (int i = 0; i < n + 2; i++) { 27 Arrays.fill(res[i], -1); 28 } 29 return solve(0, n + 1); 30 } 31 32 private int solve(int left, int right) { 33 if (left >= right - 1) { // nums = [] val = [1,1]This situation 34 return 0; 35 } 36 if (res[left][right] != -1) { // Without this, the time limit will be exceeded 37 return res[left][right]; 38 } 39 for (int k = left + 1; k < right; k++) { // [1, 0, 0, 0, 0, 1] other: nums = [8] val = [1,8,1] res[0][2] 40 int sum = val[left] * val[k] * val[right]; // [1, 8, 1] k = 4 41 sum += solve(left, k) + solve(k, right); 42 res[left][right] = Math.max(res[left][right], sum); 43 } 44 return res[left][right]; 45 } 46 } 47 48 class Test_312 { 49 public static void main(String[] args) { 50 int[] nums = {3, 1, 5, 8}; 51 ques_312_Poke balloon s = new ques_312_Poke balloon(); 52 System.out.println(s.maxCoins(nums)); 53 } 54 }
2, Skillfully solve mathematical problems
Demo, common multiple and common factor
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 public class demo { 4 /** 5 * Finding the greatest common factor by rolling Division 6 * 7 * @param a 8 * @param b 9 * @return 10 */ 11 int gcd(int a, int b) { 12 return b == 0 ? a : gcd(b, a % b); 13 } 14 15 /** 16 * Find the least common multiple 17 * 18 * @param a 19 * @param b 20 * @return 21 */ 22 int lcm(int a, int b) { 23 return a * b / gcd(a, b); 24 } 25 } 26 27 class Test_demo { 28 public static void main(String[] args) { 29 demo s = new demo(); 30 int a = 9; 31 int b = 12; 32 System.out.println(s.gcd(a, b)); 33 System.out.println(s.lcm(a, b)); 34 } 35 }
4. Count prime
Question:
Given an integer n, returns the number of all prime numbers less than the nonnegative integer n #.
Example 1:
Input: n = 10
Output: 4
Explanation: there are four prime numbers less than 10. They are 2, 3, 5 and 7.
Example 2:
Input: n = 0
Output: 0
Example 3:
Input: n = 1
Output: 0
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 4 import java.util.Arrays; 5 6 /** 7 * Idea: traverse from 1 to n, assuming that the current traversal reaches m, mark all integers less than n and multiple of m as sums; After traversal, numbers that are not marked as sum are prime numbers. 8 */ 9 public class ques_204_Count prime { 10 public int countPrimes(int n) { 11 if (n <= 2) { 12 return 0; 13 } 14 Integer[] prime = new Integer[n]; // eg: [_,_,2,3,4,5,6,7,8,9] 10 individual 15 Arrays.fill(prime, 1); 16 prime[0] = 0; 17 prime[1] = 0; 18 for (int i = 2; i < Math.sqrt(n); i++) { // eg: Number 2-9 Math.sqrt(n)optimization 19 if (prime[i] == 1) { 20 for (int j = i * 2; j < n; j += i) { // 2_4_6_8 3_6_9 4_8 5 21 if (prime[j] == 1) { 22 prime[j] = 0; 23 } 24 } 25 } 26 } 27 // [0, 0, 1(2), 1(3), 0(4), 1(5), 0(6), 1(7), 0(8), 0(9)] 28 // return Arrays.asList(prime).strem().reduce(0, Integer::sum); 29 int sum = 0; 30 for (Integer p : prime) { 31 sum += p; 32 } 33 return sum; 34 } 35 } 36 37 class Test_204 { 38 public static void main(String[] args) { 39 int n = 10; 40 ques_204_Prime count s = new ques_204_Count prime(); 41 System.out.println(s.countPrimes(n)); 42 } 43 }
5. Hex number
Question:
Given an integer num, it is converted to 7-ARY and output in the form of string.
Example 1:
Input: num = 100
Output: "202"
Example 2:
Input: num = -7
Output: - 10
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 6 /** 7 * Idea: 2753 8 * 2753 = 393*7 +2 9 * 393 = 56*7 +1 10 * 56 = 8*7 + 0 11 * 8 = 1*7 +1 12 * 1 = 0*7 +1 13 * (2753)|10 = ( 11012) |7 14 */ 15 public class ques_504_Hex number { 16 public String convertToBase7(int num) { 17 if (num == 0) { 18 return "0"; 19 } 20 boolean flag = false; 21 if (num < 0) { 22 num = -num; 23 flag = true; 24 } 25 List<Integer> res = new ArrayList<>(); // [2, 1, 0, 1, 1] 26 while (num != 0) { 27 res.add(num % 7); 28 num = num / 7; 29 } 30 StringBuilder ans = new StringBuilder(); 31 for (int i = res.size() - 1; i >= 0; i--) { 32 ans.append(res.get(i)); 33 } 34 return flag ? "-" + ans.toString() : ans.toString(); 35 } 36 } 37 38 class Test_504 { 39 public static void main(String[] args) { 40 int num = -8; 41 ques_504_Hex number s = new ques_504_Hex number(); 42 System.out.println(s.convertToBase7(num)); 43 } 44 }
6. Zero after factorial
Question:
Given an integer n, return n! The number of trailing results in zero.
Prompt: n= n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
Example 1:
Input: n = 3
Output: 0
Explanation: 3= 6, excluding trailing 0
Example 2:
Input: n = 5
Output: 1
Explanation: 5= 120, with a trailing 0
Example 3:
Input: n = 0
Output: 0
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 /** 4 * Idea: 0 of each tail consists of 2 × 5 = 10, so you can divide each element of factorial into prime numbers and multiply them, and count how many 2 and 5 there are. 5 * Obviously, the number of quality factors 2 is much more than that of quality factors 5, so we can only count how many quality factors 5 are in the factorial result. 6 * (In a factorial, multiply all numbers between 1 and N, which is the same as multiplying the factors of all numbers between 1 and n.) 7 * If n=16, you need to check the factors of all numbers between 1 and 16. We are only interested in 2 and 5. The numbers containing five factors are 5, 10, 15, 8 * The numbers containing factor 2 are 2, 4, 6, 8, 10, 12, 14, 16. Because there are only three complete pairs, so 16! There are three zeros after. 9 */ 10 public class ques_172_Zero after factorial { 11 public int trailingZeroes(int n) { 12 // return n/5; // Wrong practice eg:30 13 return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5); 14 } 15 } 16 17 class Test_172 { 18 public static void main(String[] args) { 19 int n = 30; 20 ques_172_Zero after factorial s = new ques_172_Zero after factorial(); 21 System.out.println(s.trailingZeroes(n)); 22 } 23 }
7. String addition
Question:
Given two non negative integers in the form of string, {num1 and num2, calculate their sum and return them in the form of string.
You cannot use any built-in library for handling large integers (such as BigInteger), nor can you directly convert the input string to integer form.
Example 1:
Input: num1 = "11", num2 = "123"
Output: "134"
Example 2:
Input: num1 = "456", num2 = "77"
Output: "533"
Example 3:
Input: num1 = "0", num2 = "0"
Output: '0'
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 public class ques_415_String addition { 4 public String addStrings(String num1, String num2) { 5 int len = num1.length() - num2.length(); 6 StringBuilder res = new StringBuilder(); 7 for (int i = 0; i < Math.abs(len); i++) { 8 res.append('0'); 9 } 10 if (len > 0) { 11 num2 = res.toString() + num2; 12 } else { 13 num1 = res.toString() + num1; 14 } 15 char[] chars1 = num1.toCharArray(); 16 char[] chars2 = num2.toCharArray(); 17 int addbit = 0; 18 for (int i = chars1.length - 1; i >= 0; i--) { 19 int cur_sum = (chars1[i] - '0') + (chars2[i] - '0') + addbit; 20 addbit = cur_sum < 10 ? 0 : 1; 21 chars1[i] = (char) (cur_sum % 10 + '0'); 22 } 23 StringBuilder output = new StringBuilder(); 24 if (addbit == 1) { 25 output.append("1"); 26 } 27 for (int i = 0; i < chars1.length; i++) { 28 output.append(chars1[i]); 29 } 30 return output.toString(); 31 } 32 } 33 34 class Test_415 { 35 public static void main(String[] args) { 36 String num1 = "19"; 37 String num2 = "123"; 38 ques_415_String addition s = new ques_415_String addition(); 39 System.out.println(s.addStrings(num1, num2)); 40 } 41 }
8. Power of 3
Question:
Given an integer, write a function to determine whether it is a power of 3. If yes, return true; Otherwise, false is returned.
The integer n is to the power of 3, which needs to be satisfied: there is an integer x so that n == 3x
Example 1:
Input: n = 27
Output: true
Example 2:
Input: n = 0
Output: false
Example 3:
Input: n = 9
Output: true
Example 4:
Input: n = 45
Output: false
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 public class ques_326_3 Power of { 4 public boolean isPowerOfThree(int n) { 5 // Constantly n Divide by three until n=1. If this process n If it can't be divided by 3, it means n Not a power of 3. 6 if (n == 0) { 7 return false; 8 } 9 while (n % 3 == 0) { 10 n = n / 3; 11 } 12 return n == 1; 13 } 14 } 15 16 class Test_326 { 17 public static void main(String[] args) { 18 int n = 26; 19 ques_326_3 Power of s = new ques_326_3 Power of(); 20 System.out.println(s.isPowerOfThree(n)); 21 } 22 }
9. Scramble array
Question:
Give you an integer array nums and design an algorithm to disrupt an array without duplicate elements. After scrambling, all permutations of the array should be {and so on.
Implement Solution class:
Solution(int[] nums) initializes the object with an integer array nums
int[] reset() resets the array to its initial state and returns
int[] shuffle() returns the result of random array scrambling
Example 1:
input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
explain
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // Scramble the array [1,2,3] and return the result. The return probability of any arrangement of [1,2,3] should be the same. For example, return [3, 1, 2]
solution.reset(); // Reset the array to its initial state [1, 2, 3]. Return to [1, 2, 3]
solution.shuffle(); // Randomly returns the result after the array [1, 2, 3] is disrupted. For example, return [1, 3, 2]
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 import java.util.Arrays; 4 import java.util.Random; 5 6 /** 7 * Idea: set the array nums to be out of order in place. 8 * Cycle n times, in cycle i (0 ≤ i < n): 9 * 1.Randomly select a subscript j in [i,n); 2. Exchange the i-th element with the j-th element. 10 * The part of num [i.. N − 1] in the array is the array to be disordered, and its length is n − i; The part of num [0.. i − 1] is an out of order array with a length of i. 11 */ 12 public class ques_384_Scramble array { 13 int[] nums; 14 int[] original; 15 16 public ques_384_Scramble array(int[] nums) { 17 this.nums = nums; 18 this.original = new int[nums.length]; 19 System.arraycopy(nums, 0, original, 0, nums.length); 20 } 21 22 public int[] reset() { 23 System.arraycopy(original, 0, nums, 0, nums.length); 24 return nums; 25 } 26 27 public int[] shuffle() { 28 Random random = new Random(); 29 for (int i = 0; i < nums.length; i++) { 30 int j = i + random.nextInt(nums.length - i); 31 int temp = nums[i]; 32 nums[i] = nums[j]; 33 nums[j] = temp; 34 } 35 return nums; 36 } 37 } 38 39 class Test_384 { 40 public static void main(String[] args) { 41 String[] actions = {"Solution", "shuffle", "reset", "shuffle"}; 42 int[] nums = {1, 2, 3}; 43 ques_384_Scramble array s = new ques_384_Scramble array(nums); 44 System.out.println(Arrays.toString(s.shuffle())); 45 System.out.println(Arrays.toString(s.reset())); 46 System.out.println(Arrays.toString(s.shuffle())); 47 } 48 }
10. Random selection by weight
Question:
Give you an array of positive integers with subscripts starting from 0, where w[i] represents the weight of the ith subscript.
Please implement a function named pickIndex, which can randomly select and return a subscript from the range [0, w.length - 1] (including 0 and w.length - 1). The probability of selecting subscript i ， is w[i] / sum(w).
For example, for w = [1, 3], the probability of selecting subscript 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), while the probability of selecting subscript 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).
Example 1:
Input:
["Solution","pickIndex"]
[[[1]],[]]
Output:
[null,0]
Explanation:
Solution solution = new Solution([1]);
solution.pickIndex(); // Return 0. Because there is only one element in the array, the only option is to return the subscript 0.
Example 2:
Input:
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output:
[null,1,1,1,1,0]
Explanation:
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // Return 1, return subscript 1, and the probability of returning this subscript is 3 / 4.
solution.pickIndex(); // Return 1
solution.pickIndex(); // Return 1
solution.pickIndex(); // Return 1
solution.pickIndex(); // Return 0, return subscript 0, and the probability of returning this subscript is 1 / 4.
Since this is a random question and multiple answers are allowed, the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 import java.util.Arrays; 4 5 /** 6 * Idea: w=[3,1,2,4] 7 * The sum of weights is total=10. Divide [1,10] according to [1,3], [4,4], [5,6], [7,10], so that their lengths are exactly 3,1,2,4 in turn. 8 * Use pre[i] to represent the prefix sum of array W. the left boundary of the ith interval is pre[i] − w[i]+1, and the right boundary is pre[i]. 9 * pre[0] = 3 10 * pre[1] = pre[0] + 1 = 4 11 * pre[2] = pre[1] + 2 = 6 12 * pre[3] = pre[2] + 4 = 10 13 */ 14 public class ques_528_Random selection by weight { 15 int[] pre; 16 int total; 17 18 public ques_528_Random selection by weight(int[] w) { 19 pre = new int[w.length]; 20 pre[0] = w[0]; 21 for (int i = 1; i < w.length; i++) { 22 pre[i] = pre[i - 1] + w[i]; 23 } 24 total = Arrays.stream(w).sum(); 25 } 26 27 public int pickIndex() { 28 int x = (int) (Math.random() * total) + 1; 29 System.out.println(x); 30 return binarySearch(x); 31 } 32 33 private int binarySearch(int x) { 34 int left = 0; 35 int right = pre.length - 1; 36 while (left < right) { 37 int mid = (right - left) / 2 + left; 38 if (pre[mid] < x) { 39 left = mid + 1; 40 } else { 41 right = mid; 42 } 43 } 44 return left; 45 } 46 } 47 48 class Test_528 { 49 public static void main(String[] args) { 50 int[] weights = {3, 1, 2, 4}; 51 ques_528_Random selection by weight s = new ques_528_Random selection by weight(weights); 52 System.out.println(s.pickIndex()); 53 } 54 }
11. Linked list random node
Question:
Give you a single linked list, randomly select a node in the linked list, and return the corresponding node value. Each node has the same probability of being selected.
Implement Solution class:
Solution(ListNode head) initializes the object with an array of integers.
int getRandom() randomly selects a node from the linked list and returns the value of the node. All nodes in the linked list have the same probability of being selected.
Example:
input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
output
[null, 1, 3, 2, 2, 3]
explain
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // Return 1
solution.getRandom(); // Return 3
solution.getRandom(); // Return 2
solution.getRandom(); // Return 2
solution.getRandom(); // Return 3
//The getRandom() method should randomly return one of 1, 2 and 3, and the probability of each element being returned is equal.
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 import java.util.Random; 6 7 class ListNode { 8 int val; 9 ListNode next; 10 11 ListNode() { 12 } 13 14 ListNode(int val) { 15 this.val = val; 16 } 17 18 ListNode(int val, ListNode next) { 19 this.val = val; 20 this.next = next; 21 } 22 } 23 24 public class ques_382_Linked list random node { 25 List<Integer> list; 26 Random random; 27 28 public ques_382_Linked list random node(ListNode head) { 29 random = new Random(); 30 list = new ArrayList<>(); 31 PrintOrder(head); 32 } 33 34 public int getRandom() { 35 return list.get(random.nextInt(list.size())); 36 } 37 38 public void PrintOrder(ListNode root) { 39 if (root == null) 40 return; 41 list.add(root.val); 42 PrintOrder(root.next); 43 } 44 } 45 46 class Test_382 { 47 public static void main(String[] args) { 48 String[] root = {"1", "2", "3"}; 49 int index = 0; 50 ListNode bt = createBTree(root, index); 51 // PrintOrder(bt); 52 ques_382_Random node list s = new ques_382_Linked list random node(bt); 53 System.out.println(s.getRandom()); 54 } 55 56 public static ListNode createBTree(String[] root, int index) { 57 ListNode rootNode; // Define root node 58 if (index >= root.length || root[index] == null) { 59 return null; 60 } 61 rootNode = new ListNode(Integer.parseInt(root[index])); 62 rootNode.next = createBTree(root, index + 1); 63 return rootNode; 64 } 65 66 public static void PrintOrder(ListNode root) { 67 if (root == null) 68 return; 69 System.out.print(root.val + " "); 70 PrintOrder(root.next); 71 } 72 }
practice
Basic difficulty
168. Excel Sheet Column Title (Easy)
7-ARY conversion variants, it should be noted that starting from 1 rather than 0.
67. Add Binary (Easy)
Variant of string addition.
238. Product of Array Except Self (Medium)
Can you do this problem without division? The topic 135 we talked about a long time ago may give you some ideas.
Advanced difficulty
462. Minimum Moves to Equal Array Elements II (Medium)
This question is one of the author's favorite LeetCode questions. You need to reason out how to move optimally before considering the following questions:
Where to move. You may need some of the algorithms described in the previous chapters.
169. Majority Element (Easy)
If you can't think of a simple solution, search Boyer Moore majority vote algorithm.
470. Implement Rand10() Using Rand7() (Medium)
How to use one random number generator to generate another random number generator? You may need to use the original generator multiple times.
202. Happy Number (Easy)
You can simply use a while loop to solve this problem, but is there a better solution? If we put each
If the number is imagined as a node, can it be transformed into loop detection?
3, Magical bit operation
12. Hamming distance
Question:
The Hamming distance between two integers refers to the number of different positions of these two numbers corresponding to binary bits.
Give you two integers x and y, calculate and return the Hamming distance between them.
Example 1:
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The arrows above indicate the different positions of the corresponding binary bits.
Example 2:
Input: x = 3, y = 1
Output: 1
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 /** 4 * Idea: XOR operation, 0 for the same and 1 for the different 5 * Constantly check the lowest bit of S. if the lowest bit is 1, increase the counter by one, and then move the whole s to the right by one bit, so that the lowest bit of s will be rounded off, 6 * The original sub low has become the new lowest. Repeat this process until s=0. 7 * System.out.println(diff); //0101 5 8 * System.out.println("###"); 9 * System.out.println(diff&1); // 0101&0001 = 1 10 * System.out.println(diff >>= 1); //0010 2 11 * System.out.println("###"); 12 * System.out.println(diff&1); // 0010&0001 = 0 13 * System.out.println(diff >>= 1); // 0001 1 14 * System.out.println("###"); 15 * System.out.println(diff&1); // 0001&0001 = 1 16 * System.out.println(diff >>= 1); // 0000 0 17 */ 18 public class ques_461_Hamming distance { 19 public int hammingDistance(int x, int y) { //Perform bitwise exclusive or operation on two numbers and count the number of 1s. 20 int diff = x ^ y; // 0001^0100-> 0101 = 1*2^2+1*2^0=5 21 int ans = 0; 22 while (diff != 0) { 23 ans += diff & 1; 24 // 1 Except that the last bit of binary is 1, the front is all 0, so no matter what the front number is, it is 0. Only compare the lowest bit with 1. If the lowest bit is 0, it is 0, and if the lowest bit is 1, it is 1. 25 diff >>= 1; 26 // eg: a=a>>2 take a The binary bit of is shifted by 2 bits to the right, and the left complement 0 or left complement 1 depends on whether the shifted number is positive or negative(Positive numbers complement 0 to the left and negative numbers complement 1 to the left). 27 } 28 return ans; 29 } 30 } 31 32 class Test_461 { 33 public static void main(String[] args) { 34 int x = 1; 35 int y = 4; 36 ques_461_Hamming distance s = new ques_461_Hamming distance(); 37 System.out.println(s.hammingDistance(x, y)); 38 } 39 }
13. Reverse binary
Question:
Inverts the binary bits of a given 32-bit unsigned integer.
Tips:
Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be specified as signed integer types and should not affect your implementation, because the internal binary representation of an integer is the same whether it is signed or unsigned.
In Java, the compiler uses binary complement notation to represent signed integers. Therefore, in example 2}, the input represents a signed integer-3 and the output represents a signed integer-1073741825.
Example 1:
Input: n = 000000 1010010100000 1111010011100
Output: 964176192 (001110010111100000010100101000000)
Explanation: the input binary string 000000 1010010100000 1111010011100 represents an unsigned integer 43261596,
Therefore, 964176192 is returned, and its binary representation is 001110010111100000010100101000000.
Example 2:
Input: n = 11111111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)
Explanation: the input binary string 11111111111111111111111101 represents an unsigned integer 4294967293,
Therefore, 3221225471 is returned, and its binary representation is 10111111111111111111111111111.
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 public class ques_190_Reverse binary { //Shift left and shift right using binary arithmetic. 4 public int reverseBits(int n) { // eg: 0101 5 int ans = 0; // ans Move the left position, n Shift right to the lowest position. 6 for (int i = 0; i < 32; i++) { 7 ans <<= 1; 8 ans += n & 1; // 0101 & 0001 = 0001 -> 001_0(give room) 9 n >>= 1; // 0101 -> 0_010 10 } 11 return ans; 12 } 13 } 14 15 class Test_190 { 16 public static void main(String[] args) { 17 int n = 43261596; 18 ques_190_Reverse binary s = new ques_190_Reverse binary(); 19 System.out.println(s.reverseBits(n)); 20 } 21 }
14. A number that appears only once
Question:
Given a non empty array of integers, each element appears twice except that one element appears only once. Find the element that appears only once.
explain:
Your algorithm should have linear time complexity. Can you do it without using extra space?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 /** 4 * Idea: use the characteristics of X Λ x=0 and X Λ 0=x to XOR all the numbers in the array. 5 * The result of bitwise XOR of all numbers appearing twice is 0, and the XOR of numbers appearing once can get the number itself. 6 * 0000∧0001∧0001=0001∧0001=0(2 (Times) 7 * 0000∧0001=0001 8 */ 9 public class ques_136_A number that appears only once { 10 public int singleNumber(int[] nums) { 11 int ans = 0; 12 for (int num : nums) { 13 ans ^= num; 14 } 15 return ans; 16 } 17 } 18 19 class Test_136 { 20 public static void main(String[] args) { 21 int[] nums = {4, 1, 2, 1, 2}; 22 ques_136_A number that appears only once s = new ques_136_A number that appears only once(); 23 System.out.println(s.singleNumber(nums)); 24 } 25 }
15. Power of 4
Question:
Given an integer, write a function to determine whether it is a power of 4. If yes, return true; Otherwise, false is returned.
The integer n is to the power of 4, which needs to be satisfied: there is an integer x so that n == 4x
Example 1:
Input: n = 16
Output: true
Example 2:
Input: n = 5
Output: false
Example 3:
Input: n = 1
Output: true
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 /** 4 * If a number n is an integer power of 2, its binary must be 0 010... 0 in this form; Considering that the binary of n − 1 is 0 001... 1， 5 * The result of bitwise sum of these two numbers must be 0. So if n & (n - 1) is 0, then the number is to the power of 2. 6 * If the number is also to the power of 4, the position of 1 in the binary representation must be odd. We can put n and binary 10101 one hundred and one 7 * (That is 1431655765 in decimal system). If the result is not 0, it means that the number is to the power of 4. 8 * 000100&000101=000100(Not 0) 000010 & 000101 = 000000 (0) 9 */ 10 public class ques_342_4 Power of { 11 public boolean isPowerOfFour(int n) { 12 return n > 0 && (n & (n - 1)) == 0 && (n & 1431655765) != 0; 13 } 14 } 15 16 class Test_342 { 17 public static void main(String[] args) { 18 int n = 16; 19 ques_342_4 Power of s = new ques_342_4 Power of(); 20 System.out.println(s.isPowerOfFour(n)); 21 } 22 }
16. Maximum word length product
Question:
Give you a string array of words, find out and return the maximum value of length(words[i]) * length(words[j]), and the two words do not contain common letters. If there are no such two words, return 0.
Example 1:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: these two words are "abcw" and "xtfn".
Example 2:
Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: these two words are "ab" and "CD".
Example 3:
Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: there are no such two words.
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 /** 4 * Idea: if and only if masks [i] & masks [j] = 0, the ith word and the jth word have no common letters. At this time, the maximum word length product is updated by the length product of the two words. 5 */ 6 public class ques_318_Maximum word length product { 7 public int maxProduct(String[] words) { 8 int length = words.length; 9 int[] masks = new int[length]; 10 for (int i = 0; i < length; i++) { 11 String word = words[i]; 12 for (int j = 0; j < word.length(); j++) { 13 masks[i] = masks[i] | (1 << (word.charAt(j) - 'a')); 14 // eg: "ab"(a Shift 0 bit left, b Shift left 1 bit) masks[0]=000|001=001 masks[0]=001|010=011 011 namely"ab"Representation of 15 } 16 } 17 int maxLength = 0; 18 for (int i = 0; i < masks.length; i++) { 19 for (int j = i + 1; j < masks.length; j++) { 20 if ((masks[i] & masks[j]) == 0) { 21 maxLength = Math.max(maxLength, words[i].length() * words[j].length()); 22 } 23 } 24 } 25 return maxLength; 26 } 27 } 28 29 class Test_318 { 30 public static void main(String[] args) { 31 String[] words = {"abcw", "baz", "foo", "bar", "xtfn", "abcdef"}; 32 ques_318_Maximum word length product s = new ques_318_Maximum word length product(); 33 System.out.println(s.maxProduct(words)); 34 } 35 }
17. Bit count
Question:
Give you an integer n. for each i in "0 < = i < = n", calculate the number of 1 in its binary representation, and return an array ans with length of n + 1 as the answer.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
1 package LeetCode.test7_fenzhi_shuxue_weiyunsuan; 2 3 import java.util.Arrays; 4 5 /** 6 * Idea: dp[i] represents the number of 1 contained in the binary of the number I. 7 * For the ith digit, if the last bit of its binary is 1, the number of digits containing 1 is dp[i-1]+1; 8 * If the last bit of its binary is 0, the number of 1 is the same as its arithmetic right shift result, that is, DP [I > > 1]. 9 * 01000&00001=00000 01001&00001=00001 10 * (111) = (110) + 1; (110) = (011) 11 */ 12 public class ques_338_Bit count { 13 public int[] countBits(int n) { 14 int[] dp = new int[n + 1]; 15 for (int i = 1; i <= n; i++) { 16 dp[i] = (i & 1) == 1 ? dp[i - 1] + 1 : dp[i >> 1]; 17 // dp[1] = dp[0] + 1 = 1 18 } 19 return dp; 20 } 21 } 22 23 class Test_338 { 24 public static void main(String[] args) { 25 int n = 5; 26 ques_338_Bit count s = new ques_338_Bit count(); 27 System.out.println(Arrays.toString(s.countBits(n))); 28 } 29 }
practice
Basic difficulty
268. Missing Number (Easy)
Variant of Single Number. In addition to using binary, Gaussian summation formula can also be used.
693. Binary Number with Alternating Bits (Easy)
Use bit operation to judge whether there will be continuous 0 and 1 in the binary of a number.
476. Number Complement (Easy)
Variant of binary inversion.
Advanced difficulty
260. Single Number III (Medium)
For the follow-up of Single Number, we need to seriously think about how to use bit operation to solve it.