Interview question 39 — Numbers that occur more than half the time in an array
There is a number in the array that appears more than half the length of the array. Find the number. For example, enter an array of length 9 {1,2,3,2,2,2,5,4,2}. Since the number 2 appears in 5 words in the array, more than half the length of the array, 2 is printed.
By enumerating several cases, we can conclude that the number that occurs more than half of The Times in the array must be the median after the array is sorted. Therefore, the question becomes the median after the array is sorted. And the most intuitive way to figure out the median is to sort the array, and then return the middle number in order nlogn. So is there a faster way?
Time Complexity O(n) Algorithm based on Parititon function (Variable input array required)
We noticed that what we needed was the median of the sorted number, the len/2 number, and we didn’t have to worry about the order of the smaller number before it and the larger number after it, so we came up with the idea of quick sort, which is to partition the number. The idea of fast sorting is to recurse each heap down to the point where it can’t be divided, so the population is sorted, and we only need to get halfway through, when we’re done dividing [0,len/2) and (len/2, len), and we’re done.
public int majorityElement(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("nums should not be empty");
}
int middle = nums.length/2;
int index = partition(nums, 0, nums.length);
int start = 0;
int end = nums.length;
while(index ! = middle) {if (middle < index) {
end = index;
} else {
start = index + 1;
}
index = partition(nums, start, end);
}
return nums[index];
}
// return the index of pivot
private int partition(int[] nums, int start, int end) {
int pivot = nums[end-1];
int firstOfLarger = start;
for (int i = start; i < end-1; i++) {
if (nums[i] <= pivot) {
swap(nums, i, firstOfLarger);
firstOfLarger++;
}
}
swap(nums, firstOfLarger, end-1);
return firstOfLarger;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
Copy the codeAs for the time complexity of Parition, it has been analyzed in “Introduction to Algorithms”. Instead of sorting all elements, the time complexity of parition to a certain position is O(n), and there is a more rigorous proof formula in the book. The first partition needs to be traversed once, but the second partition needs to be traversed half of the previous partition, and the third partition needs to be traversed half of the previous partition. So the next couple of runs don’t make an order of magnitude difference to the overall time complexity, so it’s order n.
Moore voting method
Although the time complexity of the algorithm O(n) in this case has been optimized, the problem with this solution is that the input int[] NUMS array needs to be changed, and changing the parameters entered by the requester is generally not acceptable in real use scenarios. So there’s a more subtle solution — the Moore vote.
As for the principle of Moore’s voting law, Zhihu God has a good explanation here
Moore algorithm of the core of the fight consumption, assuming that you are playing in the War of The Ren Village, or you are in The Three Kingdoms chaos of one of the forces (such as Cao Cao), as long as your forces are strong enough (refers to more than half of the total), then no matter how to fight no matter who hit who, a small soldier for a final winner must be you.
public int majorityElement(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("nums should not be empty");
}
int winner = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == winner) { // winner's strength up
count++;
} else {
count--; // winnner's strength down
if (count == 0) { // winner is down, new winner come up
winner = nums[i];
count = 1; }}}return winner;
}
Copy the codeInterview question 40 — The smallest number of k
Input n integers to find the smallest k number. For example, if you enter 4, 5, 1, 6, 2, 7, 3, and 8, the smallest four digits are 1, 2, 3, and 4
The time complexity O(n) algorithm based on Parition needs to modify the input array
And just like in the previous problem, when we’re trying to find the smallest number of k, we don’t need to know the order of the smallest number of k, and we don’t need to know the order of the next number. So this idea is very suitable for the parition partition idea of fast row. So in that sense, this is an extension of the last problem, where we wanted the median to be the smallest len over 2, and we want to expand this to the smallest k.
public int[] getLeastNumbers(int[] arr, int k) {
if (arr == null || arr.length == 0 || arr.length < k || k == 0) {
return new int[0];
}
int index = partition(arr, 0, arr.length-1);
int start = 0;
int end = arr.length-1;
while(index ! = k-1) {
if (index > k-1) {
end = index - 1;
} else {
start = index + 1;
}
index = partition(arr, start, end);
}
return Arrays.copyOf(arr, k);
}
private int partition(int[] arr, int start, int end) {
int firstOfBigger = start;
int pivot = arr[end];
for (int i = start; i < end; i++) {
if (arr[i] <= pivot) {
swap(arr, i, firstOfBigger);
firstOfBigger++;
}
}
swap(arr, firstOfBigger, end);
return firstOfBigger;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Copy the codeAlgorithm based on Big Top Heap, time complexity O(Nlogk)
The data structure design of the big top heap is used to find topK data. Different from the above solution, increasing the time complexity to O(nlogk) brings an array that does not need to adjust the input and is suitable for processing massive data. Why is it good for handling large amounts of data? Suppose the input array is a huge 1T number, and you want to ask for the top10, the above method can’t load it into memory at all, and the big top heap only maintains the top10 so far.
public class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr == null || arr.length == 0) {
return new int[0];
}
Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
for (int num : arr) {
if (pq.size() < k) { // build max heap
pq.offer(num);
} else {
if (num < pq.peek()) { // only when num is less than heap top, replace root and adjustpq.poll(); pq.offer(num); }}}int[] res = new int[pq.size()];
int idx = 0;
for (int num : pq) {
res[idx++] = num;
}
returnres; }}Copy the codeAbout the big top heap/small top heap
When writing the big top heap (similar to the small top heap), first carry the binary tree with an array, and then in two steps:
- BuildHeap, adjust from the last non-root node (heap/2-1) all the way to the root, initialize the entire heap, takes log(k)
- Whenever a number needs to be added, replace the root node with the input number, and then adjust the root node
The process of adjustment is to find a larger node from the left and right children, swap with it, and then adjust in a new position
Method based on Red-black Tree, time complexity O(Nlogk)
Similar to the idea of the big top heap, maintaining a red-black tree of size K requires a Map data structure to maintain num -> count of num because the numbers can be repeated.
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr == null || arr.length == 0) {
return new int[0];
}
TreeMap<Integer, Integer> map = new TreeMap<>();
int cnt = 0;
for (int num : arr) {
if (cnt < k) {
map.put(num, map.getOrDefault(num, 0) + 1);
cnt++;
continue;
}
int maxInMap = map.lastEntry().getKey();
if (num < maxInMap) {
map.put(num, map.getOrDefault(num, 0) + 1); countDownOrRemove(map, maxInMap); }}int[] result = new int[k];
int idx = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int freq = entry.getValue();
for (int i = 0; i < freq; i++) { result[idx++] = entry.getKey(); }}return result;
}
private void countDownOrRemove(TreeMap<Integer, Integer> map, int num) {
if (map.get(num) == 1) {
map.remove(num);
} else {
map.put(num, map.get(num) - 1); }}Copy the codeInterview question 41 — The median in the data stream
Title: How to obtain a median of data streams? If an odd number of values are read from the data stream, the median is the number in the middle of all values sorted. If an even number of values are read from the data stream, the median is the average of the middle two numbers sorted by all the values.
There are two methods in this problem, one is addNum and the other is findMedian. The simplest method that comes to mind at first is to sort the array every time. In this way, the time complexity is:
- addNum–O(1)
- findMedian–O(nlogn)
A faster way to find the median can be seen from interview question 39. According to Parition’s method, the time complexity is:
- addNum — O(1)
- findMedian — O(n)
If the order of the array is to be maintained during insertion rather than query, then insertion sort is required, and the time complexity is:
- AddNum — O(n), because each insertion needs to find the position of num and move the array behind it one bit
- FindMedian — O(1), just find the middle value in the sorted array
If numbers are maintained by a hierarchical binary search tree instead of an ordinary array, the time complexity of inserted nodes can be reduced to:
- addNum — O(logn)
- findMedian — O(1)
If you have a normal binary search tree, there’s a chance that you’re going to get extremely lopsided in the insertion process and end up with a linked list, and then you’re back to O(n), so you’re going to need a balanced binary/red-black tree
The idea of balancing binary trees is to use the tree hierarchy to reduce the complexity of add operations, and the same can be done with big/small top heaps. Maintain two heaps, with the smaller half on the left and the larger half on the right, maintaining a balance of size between the left and right
class MedianFinder {
private Queue<Integer> smaller;
private Queue<Integer> larger;
/** initialize your data structure here. */
public MedianFinder(a) {
smaller = new PriorityQueue<>((v1, v2) -> (v2 - v1));
larger = new PriorityQueue<>();
}
public void addNum(int num) {
if (smaller.size() == larger.size()) {
if (larger.size() == 0 || num <= larger.peek()) {
smaller.offer(num);
} else {
intsmalliestOfLarger = larger.poll(); larger.offer(num); smaller.offer(smalliestOfLarger); }}else {
if (smaller.size() == 0 || num >= smaller.peek()) {
larger.offer(num);
} else {
intlargestOfSmaller = smaller.poll(); smaller.offer(num); larger.offer(largestOfSmaller); }}}public double findMedian(a) {
if (smaller.size() == 0 && larger.size() == 0) {
return -1;
}
if (smaller.size() == larger.size()) {
return (smaller.peek() + larger.peek()) / 2.0;
} else {
returnsmaller.peek(); }}}/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); * /
Copy the codeInterview question 42 — The largest sum of consecutive subarrays
Input an array of integers with both positive and negative numbers. One or more consecutive arrays of an array form a subarray. Find the maximum sum of all subarrays. The time complexity is O(n).
The first and most intuitive way to do this is to list all the continuous subarrays in order n^2 time.
The method proposed in the book is to analyze the rule of array by example, in fact, here can be understood as a sliding window
At the same time, it can be analyzed that this problem has the characteristics of dynamic programming by enumerating examples. Let f(I) be the maximum sum of the subarray ending with the ith digit.
- Overlap subproblem: f(I) depends on the maximum sum of f(i-1), the subarray ending in bit i-1
- Optimal substructure: f(I) depends on whether f(i-1), the largest sum of the subarray ending in bit i-1, is negative or not, do not start from scratch
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return Integer.MIN_VALUE;
}
int max = Integer.MIN_VALUE;
int curSum = 0;
for (int num : nums) {
curSum += num;
if (num > curSum) {
curSum = num;
}
max = Math.max(max, curSum);
}
returnmax; }}Copy the codeInterview question 43 — The number of occurrences of 1 in the integer 1 to n
Input an integer n and find the number of occurrences of 1 in the decimal representation of n integers. For example, if you enter 12, 1, and 12, the numbers that contain 1 are 1, 10, 11, and 12, and 1 appears five times.
The simplest solution is to start from 1 to n, and determine the number of each number that contains 1. The time complexity is O(nlogn) because we need to judge each number. There are n numbers and each number needs to judge logn bits.
You can also think of summing up the pattern by listing all the numbers
As we go on, it’s not hard to see,
Number of 1s in 1 to 99 = Number of 1s in 1 to 9 * 10 + 10 Number of 1s in 1 to 999 = Number of 1s in 1 to 99 * 10 + 100 Number of 1s in 1 to 9999 = number of 1s in 1 to 999 * 10 + 1000... The number of 1s in 1 to 999(n nines) = the number of 1s in 1 to 999(n minus 1 nines) * 10 + 10^nCopy the codeTake the number 10086 as an example, through the above rule, we can get the number of 1 from 1 to 9999, equivalent to the number of 1 to 9999, there are still 10000 to 10086, the case of the first 1 is special, for example, the number of 1 here is the number of 1 from 0 to 86 +86 (because the number of 86 times 1xxxx), namely
Number of 1s from 1 to 10086 = number of 1s from 1 to 9999 + number of 1s from 0 to 86+ 86+1Copy the codeIf the number is 50086, then this is
The number of 1s from 1 to 50086 = the number of 1s from 1 to 9999 * 5 + 10000 (because 1xxxx is counted so many times) + the number of 1s from 0 to 86Copy the codeYou get the following code
class Solution {
public int countDigitOne(int n) {
if(n < 1) {
return 0;
}
if(n < 10) {
return 1;
}
int powOfTen = powOfTen(n); // What is the highest decimal digit of n
int highNum = n / (int)Math.pow(10, powOfTen); // The highest bit value
int remain = n % (int)Math.pow(10, powOfTen); // The rest of it
if(highNum == 1) { // the highest bit is 1
return countDigitOneOfDecimal(powOfTen) + (remain + 1) + countDigitOne(remain);
} else {
return countDigitOneOfDecimal(powOfTen) * highNum + (int)Math.pow(10, powOfTen) + countDigitOne(remain); }}private int powOfTen(int n) {
int res = 0;
while(n ! =0) {
n /= 10;
res++;
}
return res-1;
}
private int countDigitOneOfDecimal(int powOfTen) {
if(powOfTen == 1) {
return 1;
}
return countDigitOneOfDecimal(powOfTen-1) * 10 + (int)Math.pow(10, powOfTen-1); }}Copy the codeInterview question 44 — The number in a sequence of numbers
Topic: number 0123456789101112131415… Serialized to a character sequence. In this sequence, bit 5 (counting from 0) is 5, bit 13 is 1, bit 19 is 4, and so on. Write a function to find the corresponding number for any NTH.
Again, enumerate as many numbers as you can and then find patterns
As shown in the figure, we need to find a certain digit in the sequence. We need to find:
- What is the integer number corresponding to this bit (e.g. Index =15, the corresponding number is 12)
- The number of digits in the corresponding integer (e.g. Index =15, the corresponding number 12 is 0 from left to right)
Through enumeration, it can be seen that the formulas to be calculated are shown as above, and the following codes can be written after the formulas are obtained. The author did not pass 100% of the case at the beginning, and the final investigation found that the problem of INT overflow should be paid attention to
class Solution {
public int findNthDigit(int n) {
if (n < 0) {
return -1;
}
int index = n;
int digits = 1; // 1 digit
while(true) {
long numbers = countOfDigits(digits); // Count the total number of digits. Note the int overflow problem, use long
if (index < numbers*digits) {
returndigitAtIndex(index, digits); } index -= (numbers*digits); digits++; }}private long countOfDigits(int digits) {
if (digits == 1) {
return 10;
}
return (long)Math.pow(10, digits-1) * 9;
}
private int digitAtIndex(int index, int digits) {
long num = beginNumber(digits) + (index/digits); // Calculate which integer index of digits falls to
int pos = digits - (index % digits) - 1; // Calculate which digit is in the number
for (int i = 0; i < pos; i++) {
num /= 10;
}
return (int) (num % 10);
}
private int beginNumber(int digits) {
if (digits == 1) {
return 0;
}
return (int)Math.pow(10, digits-1); }}Copy the codeInterview question 45 — Arrange the array to the smallest number
Enter an array of positive integers, concatenate all the numbers in the array into a number, and print the smallest number that can be concatenated. For example, if you enter the array {3,32,321}, you print 321323, the smallest number that the three digits can form.
When there are only two digits, such as {32,321}, the number that can be concatenated is 32’321 and 321’32, and the smaller number is 321’32. It can be defined that 321 is “less than” 32. 321 must also be less than 3.
Sort the input array according to our special sorting method, which can be implemented by 1) self-sorting or 2) using the SORTING capabilities provided in the JDK library, the implementation code is as follows.
class Solution {
public String minNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return "";
}
quickSort(nums, 0, nums.length - 1);
StringBuilder sb = new StringBuilder();
for (int num : nums) {
sb.append(num);
}
return sb.toString();
}
private void quickSort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int index = partition(nums, start, end);
quickSort(nums, start, index-1);
quickSort(nums, index, end);
}
private int partition(int[] nums, int start, int end) {
int pivot = nums[end];
int firstOfLarger = start;
for (int i = start; i < end; i++) {
if (concatCompare(nums[i],pivot) < 0) {
swap(nums, i, firstOfLarger);
firstOfLarger++;
}
}
swap(nums, firstOfLarger, end);
return firstOfLarger;
}
private int concatCompare(int a, int b) {
return Long.parseLong(""+a+b) - Long.parseLong(""+b+a) > 0 ? 1 : -1;
}
private void swap(int[] nums, int i, int j) {
inttemp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}Copy the codeThe point of this case is to understand this particular sort of ordering, to understand its transitive nature, and to be convincing requires a detailed list of the steps of a reduction, which is more mathematically understandable, and can be proved in detail here
All that is left is handwritten quicktypesetting.
Interview question 46 — Translate numbers into strings
Given a number, we translate it as a string as follows: 0 as “a”,1 as “b”… 11 is translated as “L”… 25 translates as “z”. A number can have multiple translations. For example: 12258 has 5 different translations, which are “bCCFI “,” bwFI “,” BCzi “,” MCFI “,”mzi”. Program to implement a function that calculates how many different ways a number can be translated.
Recursive solution
Through the analysis of the topic and examples, we can find that, taking 12258 as an example, the string combination 12258 May be translated into is
- 1 as the letter B concatenates all possible string combinations of the remaining number 2258
- 12 as the letter M concatenates all possible string combinations of the remaining number 258
The resulting call stack is recursively executed as follows
You can easily get the recurrence as follows
class Solution {
private int result = 0;
public int translateNum(int num) {
if (num < 0) {
return -1; // illegal input
}
dfs(0, num+"");
return result;
}
private void dfs(int index, String num) {
if (index >= num.length()) {
result+=1;
return;
}
dfs(index+1, num);
if (index + 1 < num.length() && isLegalAlpha(num.substring(index, index+2))) {
dfs(index+2, num); }}private boolean isLegalAlpha(String num) {
if (num.charAt(0) = ='0') {
return false;
}
int digit = Integer.parseInt(num);
return digit >=0 && digit <= 25; }}Copy the codeAs can be seen from the above call stack of DFS recursive execution, a large number of repeated calculations exist in recursive methods. For example, translateNum(58) is calculated repeatedly every time, so it occurs to us that we can use dynamic programming iteration to solve the problem of repeated calculations.
The solution to dp
Through the above DFS recursive call analysis, we can get the following state transition equation
So the example that we plug in to 12258 is the following,
- The one-digit number 1 has to be a letter, so the question is how many different letter combinations 2258 can have
- Two-digit numbers can form letters, so you need to determine, if you can form letters, then the question is how many combinations can 258 have; If no letter can be formed, 0 is displayed
- It’s impossible to form letters with more than three digits. Forget it. No way
class Solution2 {
public int translateNum(int num) {
if (num < 0) {
return -1; // illegal input
}
int dp_next = 1;
int dp_next2 = 1;
int x = num % 10;
int y = num % 10;
while(num ! =0) {
num /= 10;
x = num % 10;
int temp = isAlpha(10 * x + y) ? (dp_next + dp_next2) : dp_next;
dp_next2 = dp_next;
dp_next = temp;
y = x;
}
return dp_next;
}
private boolean isAlpha(int temp) {
return temp >= 10 && temp <= 25;
}
public int translateNum2(int num) {
int a = 1, b = 1, x, y = num % 10;
while(num ! =0) {
num /= 10;
x = num % 10;
int tmp = 10 * x + y;
int c = (tmp >= 10 && tmp <= 25)? a + b : a; b = a; a = c; y = x; }returna; }}Copy the codeThe above solution is represented by a GIF as follows
Interview question 47 — The greatest value of a gift
Title: An M * N chessboard has a gift placed on each square, and each gift has a value (value greater than 0). You can start at the top left corner of the board and move one space to the right or down until you reach the bottom right corner. Given a chess board and the gifts on it, calculate the maximum value of gifts you can get.
Through the analysis of the problem, we can see that the optimal solution to reach a certain position depends on:
- The optimal solution to that position
- The best solution to the left of that position
Taking the largest of the above two, which has typical dynamic programming characteristics, the following state transition equation can be obtained
The final calculation process is as follows
class Solution {
public int maxValue(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int[] dp = new int[grid[0].length];
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
int up = i == 0 ? 0 : dp[j];
int left = j == 0 ? 0 : dp[j-1]; dp[j] = Math.max(up, left) + grid[i][j]; }}return dp[dp.length-1]; }}Copy the codeInterview question 48 — The longest substring without repeating characters
Find the longest substring that does not contain repeated characters and calculate the length of the longest substring. Assume that the string contains only ‘a’ to ‘z’ characters. For example, in the string “arabcacfr”, the longest substring without repeating characters is “ACFR” of length 4.
The solution in the book is through dynamic programming + hash table. In this paper, we use a more intuitive sliding window + hash table to solve this problem.
The sliding process of the sliding window is shown in the figure below. Non-repeating letters are always maintained in the window. When repeated letters are encountered, the left boundary of the window is shrunk until repeated letters pop up.
We can see that, unlike the dynamic programming solution in the book, we need O(n) time shrinking Windows when we encounter repeated letters. Obviously this can be optimized because we can store the subscript position of each letter in the hashed data structure, and then directly locate in O(1) time where the left edge of the window should shrink. The optimized process is as follows
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
Map<Character, Integer> char2Index = new HashMap<>();
int longestLength = 0;
int left = 0;
for (int i = 0; i < s.length(); i++) {
if (char2Index.containsKey(s.charAt(i))) {
left = Math.max(left, char2Index.get(s.charAt(i)) + 1); // Take the largest window, the left window can not return
}
char2Index.put(s.charAt(i), i);
longestLength = Math.max(longestLength, i-left+1); // Update the maximum value
}
returnlongestLength; }}Copy the codeInterview question 49 — Ugly numbers
Title: We call numbers that contain only factors 2, 3, and 5 the Ugly Number. Find the 1,500th ugly number in ascending order. For example, 6 and 8 are both ugly numbers, but 14 is not because it contains the factor 7. Traditionally, we think of 1 as the first ugly number.
The simplest and most crude method is to start at 1 and run through each number to determine whether the current number is ugly. If so, increase the count by one until the 1,500th ugly number is found.
The way to determine whether it is an ugly number is to continuously divide the number by 2, 3 and 5. If the number can be divided by all (i.e. by 1), it is an ugly number, otherwise it is not. Because the idea is very simple, directly paste the code as follows:
private boolean isUgly(int number) {
while(number % 2= =0) {
number /= 2;
}
while(number % 3= =0) {
number /= 3;
}
while(number % 5= =0) {
number /= 5;
}
return number == 1;
}
public int getUglyNumber(int index) {
if(index <= 0) return 0;
int number = 0;
int uglyFound = 0;
while(uglyFound < index) {
number++;
if(isUgly(number)) { unglyFound++; }}return number;
}
Copy the codeThe optimized solution, combined with the property of ugly numbers (the product combination of 2, 3 and 5), allows us to find the 1,500th ugly number in the range of ugly numbers, i.e. skip the non-ugly numbers.
The execution process of the solution is shown in the figure below. The core idea is to make use of the existing ugly number to calculate, find the next nearest ugly number (a large number of non-ugly numbers can be skipped between the two ugly numbers), define three Pointers M2, M3 and M5, the implementation process of the algorithm can be imagined as a game of flying chess, in order to find the next smallest ugly number, M2, M3, and M5 are multiplied by 2/3/5 each time, and the smallest number is chosen as the next ugly number, and each player jumps to the next candidate position.
class Solution {
public int nthUglyNumber(int n) {
if (n <= 0) {
return 0;
}
int m2 = 0;
int m3 = 0;
int m5 = 0;
int[] uglyNumbers = new int[n];
uglyNumbers[0] =1;
for (int index = 1; index < n; index++) {
int nextUgly = min(uglyNumbers[m2]*2, uglyNumbers[m3]*3, uglyNumbers[m5]*5);
uglyNumbers[index] = nextUgly;
while(uglyNumbers[m2] * 2 <= uglyNumbers[index]) {
m2++;
}
while(uglyNumbers[m3] * 3 <= uglyNumbers[index]) {
m3++;
}
while(uglyNumbers[m5] * 5<= uglyNumbers[index]) { m5++; }}return uglyNumbers[n-1];
}
private int min(int a, int b, int c) {
int relativeMin = Math.min(a,b);
returnMath.min(relativeMin, c); }}Copy the code
Interview question 50 — The first character that appears only once
Topic 1: The first character in a string that occurs only once
Find the first character in a string that occurs only once. If “abaccdeff” is entered, ‘b’ is printed.
In this case, we store the number of occurrences of each character in a hash table (a 256 size array provided by the JDK or implemented by ourselves), then iterate through the string again to find the first character of degree 1 and return it.
public class Solution {
public char firstUniqChar(String s) {
if (s == null || s.length() == 0) {
return ' ';
}
int[] charMap = new int[256];
for (int i = 0; i < s.length(); i++) {
charMap[s.charAt(i)]++;
}
for (int i = 0; i < s.length(); i++) {
if (charMap[s.charAt(i)] == 1) {
returns.charAt(i); }}return ' '; }}Copy the codeTopic 2: The first character in a character stream that occurs only once
Implement a function to find the first character in a character stream that occurs only once. For example, when only the first two characters “go” are read from the character stream, the first character that occurs only once is ‘g’; When the first six characters “Google” are read from this character stream, the first character that appears only once is “L”.
Different from the previous problem, because the input is a character stream, there will be no second round of iteration of the previous problem, and the first round will need to mark the characters that have already been repeated:
- The solution in the book is to record the sequence number of characters in the hash table. For characters that have already been repeated, the sequence number is negative
- Maintain an ordered Set to record all characters that are not repeated, and another Set to record characters that have already been repeated
public class CharStatistics {
private Set<Character> appearingOnceChars = new LinkedHashSet<>();
private Set<Character> duplicateChars = new HashSet<>();
public void insert(char ch) {
if (duplicateChars.contains(ch)) {
return;
}
if (appearingOnceChars.contains(ch)) {
appearingOnceChars.remove(ch);
duplicateChars.add(ch);
return;
}
appearingOnceChars.add(ch);
}
public char firstAppearingOnce(a) {
if (appearingOnceChars.isEmpty()) {
return ' ';
}
returnappearingOnceChars.iterator().next(); }}Copy the codeInterview question 51 — Pairs of inversions in arrays
Two digits in an array form a reverse pair if the preceding digit is larger than the following digit. Enter an array and find the total number of inversions in the array. For example, in the array,5,6,4} {7, 5 reverse for a total of existence, respectively (7, 6), (7, 5), (7, 4), (6, 4) and (5, 4).
In this case, the most intuitive solution is to iterate through each pair of numbers in a two-layer loop to determine whether they are in reverse order. The time complexity is O(n^2). Obviously, it can’t be that simple.
It can be seen that there is such a law of inversions: taking {7,5,6,4} as an example, if we know that {5,4} can constitute inversions and that there are two numbers larger than 5, namely 6 and 7, we can quickly get the number of inversions ending in 4. And one way to take advantage of that is merge sort.
As shown in the figure below, we use the idea of divide-and-conquer algorithm to split the number of inversion pairs in the calculation {7,5,6,4} into
- Count leftPairs in {7,5}
- Calculate rightPairs for the number of reverse pairs in {6,4}
- Count the number of inversions that precede the first two arrays crossPairs
Step 1 and step 2 can continue to recursively split, until the array size is 1, an array of elements can not form a reverse pair, so return 0 (recursive exit).
And the step of 3 is merge sort, which is also the core work of calculating inversions in this problem.
class Solution {
public int reversePairs(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
int[] clones = new int[nums.length];
return reversePairsCore(nums, 0, nums.length-1, clones);
}
private int reversePairsCore(int[] nums, int left, int right, int[] clones) {
if(left == right) {
return 0;
}
int mid = left + (right - left) / 2;
int leftPairs = reversePairsCore(nums, left, mid, clones);
int rightPairs = reversePairsCore(nums, mid+1, right, clones);
if(nums[mid] < nums[mid+1]) {
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(nums, left, mid, right, clones);
return leftPairs + rightPairs + crossPairs;
}
private int mergeAndCount(int[] nums, int left, int mid, int right, int[] clones) {
for(int i = left; i <= right; i++) clones[i] = nums[i];
int pairs = 0;
int i = left;
int j = mid+1;
int cur = left;
while(i <= mid && j <= right) {
if(clones[i] <= clones[j]) {
nums[cur++] = clones[i++];
} else {
pairs += (mid-i+1); nums[cur++] = clones[j++]; }}while(i <= mid) nums[cur++] = clones[i++];
while(j <= right) nums[cur++] = clones[j++];
returnpairs; }}Copy the codeInterview question 52 — The first common node of two linked lists
Title: Enter two linked lists and find their first common node.
Violence method, for each node in linked list 1, we walk through linked list 2 to determine whether there is any equality, in which case the time complexity is O(mn), m and N are the length of the two linked lists respectively.
By analyzing the characteristics of linked lists, we can see that when two linked lists have a common node, they completely overlap. Therefore, the structure of the two linked lists is similar to the figure below
To find the first common node, we can find the “last common node” backwards from the end to the head of the list, so we need to take advantage of the last-in, first-out feature of the stack structure, so we need O(m+ N) auxiliary space.
The optimal solution is to iterate over the two lists to get their respective lengths. According to the structural characteristics of the two lists as shown in the figure, as long as the long list takes a few more steps, then the two lists move forward at the same pace, common nodes will be found. This approach does not require the use of additional auxiliary space.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) {
return null;
}
int listALength = len(headA);
int listBLength = len(headB);
int delta = listALength > listBLength ? (listALength - listBLength) : (listBLength - listALength);
ListNode longerList = listALength > listBLength ? headA : headB;
ListNode anotherList = listALength > listBLength ? headB : headA;
for(int i = 0; i < delta; i++) longerList = longerList.next;
ListNode node1 = longerList;
ListNode node2 = anotherList;
while(node1 ! = node2) {if(node1 == null || node2 == null) return null;
node1 = node1.next;
node2 = node2.next;
}
return node1;
}
private int len(ListNode head) {
int len = 0;
for(ListNode node = head; node ! =null; node = node.next) {
len++;
}
returnlen; }}Copy the codeIn addition to the book’s solution, there is another, more ingenious solution to the problem, which I would like to name as your Name solution.
On the second encounter at the common node, both Pointers A and B have traveled the same distance at the same time, common + lenA_before_common + lenB_before_comon, so they meet. If A and B do not overlap, the correct answer will be returned.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode node1 = headA;
ListNode node2 = headB;
while(node1 ! = node2) { node1 = node1 ! =null? node1.next : headB; node2 = node2 ! =null ? node2.next : headA;
}
returnnode1; }}Copy the codeAn interesting reading from LeetCode is 23333.
