Algorithm chapter 02, array related algorithms-hash table, priority queue, collection, sliding window, double pointer, binary search, etc.

Algorithm chapter 02, array related algorithms-hash table, priority queue, collection, sliding window, double pointer, binary search, etc.

The topics covered in this article are all array-related, and the solutions mainly include hash tables, sets, priority queues, sliding windows, double pointers, binary search and other technologies;

1. Leetcode349-the intersection of two arrays

Given two arrays, write a function to calculate their intersection. Each element in the output result must be unique. We can ignore the order of output results.

The problem requirement is to find the intersection of two arrays, and there can be no duplicate elements, so we can solve it with the help of HashSet;

The solution is as follows. 1. put the elements in the nums1 array into HashSet1, so that the elements in the array 1 are automatically de-duplicated, and then create a new HashSet2, and traverse the array 2 in turn. If there are elements traversed in HashSet1, then Put the elements into HashSet2, so that the elements in HashSet2 are the final required results;

//leetcode349 the intersection of two arrays //Not repeatable public int[] intersection(int[] nums1, int[] nums2) { HashSet<Integer> num1Set = new HashSet<>(); for (int i = 0; i <nums1.length; i++) { num1Set.add(nums1[i]); } HashSet<Integer> res = new HashSet<>(); for (int i = 0; i <nums2.length; i++) { if (num1Set.contains(nums2[i])){ res.add(nums2[i]); } } int[] result = new int[res.size()]; Object[] objects = res.toArray(); for (int i = 0; i <result.length; i++) { result[i] = (int) objects[i]; } return result; } Copy code

2. Leetcode350-the intersection of two arrays II

Given two arrays, write a function to calculate their intersection. The number of occurrences of each element in the output result should be consistent with the minimum number of occurrences of the element in the two arrays. We can ignore the order of output results.

The only difference between this question and 349 is that there can be repeated elements, and the number of occurrences is consistent with the minimum of the number of occurrences in the two arrays;

The solution is as follows, we can use HashMap to solve the problem; first use HashMap to save the elements in array 1 and the number of occurrences, and then traverse array 2 once, if there are elements traversed in HashMap, take them out and put them in the result set. Then reduce the number of times of this element in the HashMap by one. If the number of times becomes 0, it means that this element is no longer needed, so remove it from the HashMap; in this way, after traversing array 2, the result set is the result we need;

//leetcode350 The intersection of two arrays II //Can be repeated, subject to the array with the least number of occurrences public int[] intersect(int[] nums1, int[] nums2) { HashMap<Integer,Integer> nums1Map = new HashMap<>(); for (int i = 0; i <nums1.length; i++) { nums1Map.put(nums1[i],nums1Map.getOrDefault(nums1[i],0) + 1); } ArrayList<Integer> res = new ArrayList<>(); for (int i = 0; i <nums2.length; i++) { if (nums1Map.containsKey(nums2[i])){ res.add(nums2[i]); nums1Map.put(nums2[i],nums1Map.get(nums2[i])-1); if (nums1Map.get(nums2[i]) == 0){ nums1Map.remove(nums2[i]); } } } Object[] objects = res.toArray(); int[] result = new int[objects.length]; for (int i = 0; i <objects.length; i++) { result[i] = (int) objects[i]; } return result; } Copy code

3. Leetcode209-the smallest length sub-array

Given an array containing n positive integers and a positive integer target.

Find the continuous sub-array [numsl, numsl+1, ..., numsr-1, numsr] with the smallest length satisfying its sum target in the array, and return its length. If there is no sub-array that meets the criteria, 0 is returned.

This problem is a type of problem that can be solved by a typical sliding window. The solution is as follows;

The idea of sliding window is to always maintain a sliding window of [l...r] to make the elements in the window meet the requirements, and then constantly update the final result according to the window; this question is to maintain the elements in the window and the target is greater than or equal to the target, if the window length If it is less than the length of the current record, it will be updated to the length of the window;

//leetcode 209 the smallest length sub-array public int minSubArrayLen(int target, int[] nums) { //Maintain a sliding window of [l...r] int l = 0; int r = -1; int res = Integer.MAX_VALUE; int sum = 0; while (r <nums.length-1) { if (sum <target) { r++; sum += nums[r]; } while (sum >= target) { if (r-l + 1 <res) { res = r-l + 1; } //Here is the mistake made at the beginning, it should be to subtract nums[l] first, and then perform the operation of l++! ! ! ! ! //l++; //sum -= nums[l]; sum -= nums[l]; l++; } } return res == Integer.MAX_VALUE? 0: res; } Copy code

4. Leetcode283-move zero to the end of the array

Given an array of nums, write a function to move all zeros to the end of the array while maintaining the relative order of non-zero elements.

The solution of the problem is shown below. For this problem, we can use ArrayList to save the order of non-zero elements in the original array through ArrayList, and then fill this ArrayList to the elements in ArrayList.size() positions before the original array, then the remaining positions of the original array The elements must all be 0, at this time, fill the data in the remaining positions with 0;

//leetcode 283 move zero to the end of the array public void moveZeroes(int[] nums) { ArrayList<Integer> nonZeroElements = new ArrayList<>(); for (int i = 0; i <nums.length; i++) { if (nums[i] != 0){ nonZeroElements.add(nums[i]); } } for (int i = 0; i <nonZeroElements.size(); i++) { nums[i] = nonZeroElements.get(i); } for (int i = nonZeroElements.size(); i <nums.length; i++) { nums[i] = 0; } } Copy code

5. Leetcode167-the sum of two numbers

Given an integer array numbers arranged in ascending order, please find two numbers from the array that satisfy the sum of the target number target.

The function should return the subscript values of these two numbers in the form of an integer array of length 2. The subscript of numbers starts counting from 1, so the answer array should satisfy 1 <= answer[0] <answer[1] <= numbers.length.

You can assume that each input only corresponds to a unique answer, and you cannot reuse the same elements.

The solution of the problem is shown below. This problem is a typical problem that can be solved using left and right double pointers;

Define the left and right pointers to be located at the head and end of the array, and then add the elements at the two pointers, because the array is ordered, if the sum is less than the target, the left pointer is shifted to the right; if the sum is greater than the target, then Move the right pointer one place to the left; if the sum is equal to target, it means that the answer is found, just return;

//leetcode 167 The sum of two numbers array is ordered //Dual pointer public int[] twoSum(int[] numbers, int target) { int l = 0; int r = numbers.length -1; int[] res = new int[2]; while (l <r){ if (numbers[l] + numbers[r] <target){ l++; } else if (numbers[l] + numbers[r] >target) { r--; }else { res[0] = l+1; res[1] = r+1; return res; } } return res; } Copy code

6. Leetcode01-the sum of two numbers

Given an integer array nums and an integer target value target, please find the two integers whose sum is the target value in the array and return their array subscripts.

You can assume that each input will only correspond to one answer. However, the same element in the array cannot be repeated in the answer.

You can return the answers in any order.

Solution 1: The brute force solution can traverse the array in a two-level nested for loop until it finds that the sum of two numbers is equal to the target; because it is a two-level nested for loop, the time complexity is O(n^2) Level

//leetcode01 Two-number sum array disordered violence solution time complexity O(n^2) public int[] twoSum3(int[] nums, int target) { int[] res = new int[2]; for (int i = 0; i <nums.length-1; i++) { for (int j = i+1; j <nums.length; j++) { if (nums[j] + nums[i] == target){ res[0] = i; res[1] = j; } } } return res; } Copy code

Solution 2: With the help of HashMap, we can save the element value and index in the array with the help of HashMap, and then traverse the array to find whether there is a target-traversed current value in the HashMap. If it exists, it means that the sum of the two numbers is the target. The index saved in the HashMap and the index of the current value traversed can be returned; and this process only needs to traverse the array once, is it very clever~ The time complexity is O(n) level;

//leetcode01 The sum of two numbers is unordered and the index is recorded by hashmap, and the time complexity is O(n) public int[] twoSum2(int[] nums, int target) { int[] res = new int[2]; HashMap<Integer,Integer> hashMap = new HashMap<>(); for (int i = 0; i <nums.length; i++) { if (hashMap.containsKey(target-nums[i])){ res[0] = hashMap.get(target-nums[i]); res[1] = i; } hashMap.put(nums[i],i); } return res; } Copy code

7. Leetcode804--the only Morse code

The International Morse Code defines a standard encoding method, each letter corresponds to a string consisting of a series of dots and dashes, for example: "a" corresponds to ".-", "b" corresponds to "-..." , "c" corresponds to "-.-.", etc.

For convenience, the Morse code table for all 26 English letters is as follows:

[".-","-...","-.-.","-..",".","..-.","--.","....", "..",".---","-.-",".-..","--","-.","---",".--.","- -.-",".-.","...","-","..-","...-",".--","-..-","-. --","--.."]

Given a list of words, each word can be written as a combination of each letter corresponding to the Morse code. For example, "cab" can be written as "-.-..--...", (ie, a combination of "-.-." + ".-" + "-..." strings). We call such a connection process a word translation.

Return we can get the number of translations of all words and different words.

The solution is as follows. Translate all the words in the array into Morse passwords, then save them in HashSet, and finally return the size of HashSet, because HashSet can automatically de-duplicate;

//leetcode 804 unique Morse code public int uniqueMorseRepresentations(String[] words) { HashSet<String> set = new HashSet<>(); for (String word: words) { String morseCode = transformWordToMorseCode(word); set.add(morseCode); } return set.size(); } private String transformWordToMorseCode(String word) { String[] morse = {".-","-...","-.-.","-..",".","..-.","--.",". ...","..",".---","-.-",".-..","--","-.","---",".-- .","--.-",".-.","...","-","..-","...-",".--","-..- ","-.--","--.."}; char[] chars = word.toCharArray(); StringBuilder builder = new StringBuilder(); for (int i = 0; i <chars.length; i++) { builder.append(morse[chars[i]-'a']); } return builder.toString(); } Copy code

8. Leetcode75--color classification

Given an array of n elements containing red, white, and blue, sort them in place so that the elements of the same color are adjacent and arranged in the order of red, white, and blue.

In this question, we use integers 0, 1, and 2 to represent red, white, and blue, respectively.

The solution is shown below. We can solve this problem with the idea of three-way quick sorting in quick sort; when the element is 0, it is placed on the left, when the element is 1, it is placed in the middle, and when the element is 2, it is placed on the right, and finally traversed. After that, the order will be finished, and the time complexity is O(n) level;

//leetcode 75 color sorting, with the help of three-way quick sorting ideas public void sortColors(int[] nums) { int l = 0; int r = nums.length-1; int m = l -1; int n = r + 1; //After the for loop, [l...m] means 0; (m...n) means 1; [n...r] means 2; for (int i = 0; i <n;) { if (nums[i] == 0){ swap(nums,m+1,i); m++; i++; }else if (nums[i] == 2){ swap(nums,n-1,i); n--; }else { i++; } } } //Exchange the elements at positions a and b in the nums array private void swap(int[] nums, int a, int b) { int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } Copy code

9. Leetcode347-the first K high-frequency elements

Give you an integer array nums and an integer k. Please return the element with the highest frequency of k. You can return the answers in any order.

The solution of the problem is shown below. This problem is a good combination of hash table and priority queue; we first traverse one side of the array and save the elements and the number of occurrences in the HashMap; then create a priority queue and use the value of HashMap to subtract as Comparator, this ensures that the higher the frequency of the number, the lower the priority; the last traverse the HashMap, and put it directly when the element in the priority queue is less than K, otherwise it will compare the element at the top of the queue with the element traversed, if The frequency of the traversed element is higher than the frequency of the element at the head of the queue, so the first element of the queue is dequeued and the traversed element is enqueued; because the element at the head of the queue is always the one with the lowest frequency in the priority queue;

Because the array is traversed twice, the time complexity is O(2n), ignoring the constant, the time complexity is O(n) level;

//leetcode347 The first K high-frequency elements public int[] topKFrequent(int[] nums, int k) { HashMap<Integer,Integer> hashMap = new HashMap<>(); for (int num: nums) { hashMap.put(num, hashMap.getOrDefault(num, 0) + 1); } PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return hashMap.get(a)-hashMap.get(b); } }); for (Integer key: hashMap.keySet()) { if (queue.size() <k){ queue.add(key); }else if (hashMap.get(key)> hashMap.get(queue.peek())) { queue.remove(); queue.add(key); } } int[] res = new int[k]; for (int i = 0; i <k; i++) { res[i] = queue.remove(); } return res; } Copy code

10. Leetcode454--a tuple whose sum of four numbers is 0

Given four array lists A, B, C, D containing integers, calculate how many tuples (i, j, k, l) there are, such that A[i] + B[j] + C[k] + D [l] = 0.

In order to simplify the problem, all A, B, C, D have the same length N, and 0 N 500. All integers range from -2^28 to 2^28-1 and the final result will not exceed 2^31-1.

Solution-violent solution

Directly use the four-level nested for loop to traverse the array, but the time complexity of this method is O(n^4) level, and the performance is too poor;

//leetcode454 a tuple with the sum of four numbers being 0 //Quadruple cycle of violent solution, time complexity O(n^4), explosion, unbearable public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { int res = 0; for (int i = 0; i <nums1.length; i++) { for (int j = 0; j <nums2.length; j++) { for (int k = 0; k <nums3.length; k++) { for (int l = 0; l <nums4.length; l++) { if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) { res ++; } } } } } return res; } Copy code

Solution two with the help of a hash table

1. use a two-level nested for loop to traverse the first two arrays, and save all the sums of the first two arrays and the number of occurrences in the HashMap; then use a two-level nested for loop to traverse the last two arrays, in the HashMap Find the opposite number of the sum of these two array elements, mainly after finding the value of HashMap;

//With hashmap, the time complexity is reduced to O(n^2) public int fourSumCount2(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { //key represents the sum of nums1 and nums2 elements, and value represents the number of sums HashMap<Integer,Integer> hashMap = new HashMap<>(); for (int i = 0; i <nums1.length; i++) { for (int j = 0; j <nums2.length; j++) { int sum = nums1[i] + nums2[j]; hashMap.put(sum,hashMap.getOrDefault(sum,0) + 1); } } int res = 0; for (int i = 0; i <nums3.length; i++) { for (int j = 0; j <nums4.length; j++) { int sum = nums3[i] + nums4[j]; if (hashMap.containsKey(-sum)){ res+=hashMap.get(-sum); } } } return res; } Copy code

11. Leetcode704-binary search of ordered array

Given an n-element ordered (ascending) integer array nums and a target value target, write a function to search for the target in nums and return the subscript if the target value exists, otherwise return -1.

The binary search of an ordered array is a more classic algorithm problem, because the array is ordered, every time you go to the middle of the array to find, if the number in the middle is smaller than the target, go to the right sub-array to search; if the number in the middle is more than the target If it is bigger, go to the left sub-array to search; if it is equal to target, return directly; this way, after each search, the elements are reduced by half, and the time complexity is O(logn) level;

//leetcode 704 binary search of ordered array public int search(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 if (nums[mid]> target){ r = mid-1; }else { return mid; } } return -1; } Copy code

12. Leetcode217-there are duplicate elements

Given an integer array, determine whether there are duplicate elements.

If there is a value that appears at least twice in the array, the function returns true. If every element in the array is different, false is returned.

The solution to the problem is as follows. This problem is very simple. It is enough to directly rely on the nature of HashSet that cannot store repeated elements, and the time complexity is O(n) level;

//leetcode 217 has duplicate elements public boolean containsDuplicate(int[] nums) { HashSet<Integer> set = new HashSet<>(); for (int i = 0; i <nums.length; i++) { if (set.contains(nums[i])){ return true; } set.add(nums[i]); } return false; } Copy code

13. Leetcode219--there is a repeating element II

Given an integer array and an integer k, judge whether there are two different indexes i and j in the array, such that nums [i] = nums [j], and the absolute value of the difference between i and j is at most k.

The solution of the problem is shown below. This problem can use HashMap to save the value and index of the elements in the array to the HashMap, and traverse the array. If there are elements in the HashMap that are traversed, and the difference between the index values is less than or equal to k, just return true directly; If the traversal is still not satisfied, return false;

The process of this question is also clever in that it only needs to traverse the array once, and the time complexity is O(n) level;

//leetcode 219 there are duplicate elements II public boolean containsNearbyDuplicate(int[] nums, int k) { HashMap<Integer, Integer> hashMap = new HashMap<>(); for (int i = 0; i <nums.length; i++) { if (hashMap.containsKey(nums[i]) && Math.abs(i-hashMap.get(nums[i])) <= k) { return true; } hashMap.put(nums[i], i); } return false; } Copy code

14. Leetcode220--there is a repeating element III

Gives you an integer array nums and two integers k and t. Please judge whether there are two different subscripts i and j such that abs(nums[i]-nums[j]) <= t and at the same time satisfy abs(i-j) <= k.

Return true if it exists, false if it does not exist.

First of all, we need to know what the two apis mean; TreeSet treeSet = new TreeSet<>(); treeSet.ceiling(6); ceiling represents the smallest value in treeSet greater than 6; treeSet.floor(6); floor represents treeSet The largest value smaller than 6;

The solution of the problem is shown below. This problem uses the order of the TreeSet elements, because the underlying implementation is a red-black tree, so the order of the elements can be guaranteed;

One of the sentences

treeSet.ceiling((long) nums[i]-(long) t) <= (long) nums[i] + (long) t
Means satisfaction
abs(nums[i]-nums[j]) <= t
; And when
treeSet.size() == k + 1
When removing the element of the first method, this is sufficient
abs(i-j) <= k
; In this way, we meet these two conditions with the help of TreeSet;

This question only traverses the array once, and the time complexity is O(n) level;

//leetcode 220 there are duplicate elements III public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { TreeSet<Long> treeSet = new TreeSet<>(); for (int i = 0; i <nums.length; i++) { if (treeSet.ceiling((long) nums[i]-(long) t) != null && treeSet.ceiling((long) nums[i]-(long) t) <= (long) nums[i] + (long) t) { return true; } treeSet.add((long) nums[i]); if (treeSet.size() == k + 1) { treeSet.remove((long) nums[i-k]); } } return false; } Copy code

Source of question

Source: LeetCode Link: leetcode-cn.com/problemset/...