# 2021-05-23 meituan test top1-5

Field 1Field 1 linkdifficultyRecent inspection timeFrequency testnotes
1. Sum of two numbershttps://leetcode-cn.com/problems/two-sumeasily2021/4/248The sum of the two numbers of this topic 1 is topic 15 The deformation of the sum of three. The initial idea is: first sort the array, and then use the double pointer method to approximate the result. However, sorting will change the index of the array, and the result to be returned is the index of the array. This is not possible. hashmap is required. Using hashmap storage, key is nums[i], val is I.
Longest non repeating character stringhttps://leetcode-cn.com/problems/longest-substring-without-repeating-characterssecondary2021/4/148When you encounter the substring problem, the first thing you think of is the sliding window technique. Sliding window means moving the right pointer to add data to the window and moving the left pointer to delete data. In addition, note that when hashmap val=0, it will occupy space. You need to manually remove (when hashmap.size() is used as the return result), otherwise, use right left.
20. Valid bracketshttps://leetcode-cn.com/problems/valid-parentheseseasily2021/4/226Through example 5 "{[]}", we can know that this topic needs the help of the nature of the stack: first in and then out. My writing is very complicated and not concise. Often brush familiar routines. The details are s.toCharArray(), stacksack = new stack < > ();! stack. isEmpty(). Finally, judge whether the stack is empty. If not, for example, there is still '{[(', indicating that there is still room left, then return false;
704. Binary searchhttps://leetcode-cn.com/problems/binary-searcheasily2021/4/206In the back-end, the test frequency accounts for a small proportion. This topic is the classic template topic of binary search.
141. Circular linked listhttps://leetcode-cn.com/problems/linked-list-cycleeasily2021/4/275Just have to recite the memory and brush it repeatedly. The classic solution is to use two pointers, one running fast and the other running slow. If it does not contain rings, the pointer running fast will eventually encounter null, indicating that the linked list does not contain rings; If it contains a ring, the fast pointer will eventually make a turn of the super slow pointer and meet the slow pointer, indicating that the linked list contains a ring.

# 1. Sum of two numbers

The basic form of this problem is as follows: give you an array and an integer target, which can ensure that the sum of two numbers in the array is target. Please return the index of these two numbers.

For the TwoSum problem, one difficulty is that the given array is out of order. For an unordered array, we don't seem to have any skills. We can only violently enumerate all the possibilities.

Generally, we will sort the array first, and then consider the double pointer technique. TwoSum inspired us that HashMap or HashSet can also help us deal with simple problems related to unordered arrays.

The sum of the two numbers of this topic 1 is topic 15 The deformation of the sum of three. The initial idea is: first sort the array, and then use the double pointer method to approximate the result. However, sorting will change the index of the array, and the result to be returned is the index of the array. This is not possible. hashmap is required. Using hashmap storage, key is nums[i], val is I.

## code:

```class Solution {
public int[] twoSum(int[] nums, int target) {
// Using hashmap storage, key is nums[i], val is I
HashMap<Integer,Integer>map=new HashMap<>();
// Traverse array elements
for(int i=0;i<nums.length;i++){
if(map.containsKey(target-nums[i])){
return new int[]{i,map.get(target-nums[i])};
}
// In hashmap, key is nums[i], val is I
map.put(nums[i],i);
}
// Indicates that the result does not exist
return new int[]{};
}
}
```

## Double pointer doesn't work

The initial idea is: first sort the array, and then use the double pointer method to approximate the result. However, sorting will change the index of the array, and the result to be returned is the index of the array. This is not possible.

```class Solution {
public int[] twoSum(int[] nums, int target) {
// Firstly, the array is sorted, and then the double pointer method is used to approximate the result
Arrays.sort(nums);
int left=0,right=nums.length-1;
while(left<right){
int sum=nums[left]+nums[right];
if(sum<target){
left++;
}else if(sum>target){
right--;
}else{
return new int[]{left,right};
}
}
return new int[]{};
}
}
```

# 3. Longest substring without duplicate characters

When you encounter the substring problem, the first thing you think of is the sliding window technique. Sliding window means moving the right pointer to add data to the window and moving the left pointer to delete data. In addition, note that when hashmap val=0, it will occupy space. You need to manually remove (when hashmap.size() is used as the return result), otherwise, use right left.

## Remember: pseudo code framework:

```string s, t;
// Find the "minimum covering substring" of t in s
int left = 0, right = 0;
string res = s;

while(right < s.size()) {
right++;
// If it meets the requirements, move left to narrow the window
while (window Meet the requirements) {
// If the substring of this window is shorter, update res
res = minLen(res, window);
window.remove(s[left]);
left++;
}
}
return res;
```

Similar to the previous idea, use window as a counter to record the number of characters in the window, and then move right first. When repeated characters appear in the window, start moving left to narrow the window, and so on:

```class Solution {
// The problem here is to find the substring. The substring cannot be separated.
public int lengthOfLongestSubstring(String s) {
// Define a returned result
int maxLen=0;
// Use hashMap to avoid duplicate characters in the results
HashMap<Character,Integer>window=new HashMap<>();
// Use double pointer
int left=0,right=0;
// Traversal in a large loop
while(right<s.length()){
// Value
char c1=s.charAt(right);
right++;
// Save to window
window.put(c1,window.getOrDefault(c1,0)+1);
// If the character is repeated at this time, move the pointer
while(window.get(c1)>1){
// Remove the value of left
char c2=s.charAt(left);
left++;
window.put(c2,window.getOrDefault(c2,0)-1);
// It should be noted here that when value=0, the key is not cleared.
if(window.get(c2).equals(0)){
window.remove(c2);
}
}
// Update the length at this time
maxLen=Math.max(maxLen,window.size());
}
return maxLen;
}
}
```
```class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, right = 0;
HashMap<Character, Integer> window = new HashMap<>();
int resMaxLen = 0;
while (right < s.length()) {
char c1 = s.charAt(right);
window.put(c1, window.getOrDefault(c1, 0) + 1);
right++;
// If duplicate characters appear in the window
// Start moving left to narrow the window
while (window.get(c1) > 1) {
char c2 = s.charAt(left);
window.put(c2, window.getOrDefault(c2, 0) - 1);
left++;
}
resMaxLen = Math.max(resMaxLen, right - left);
}
return resMaxLen;
}
}
```

It should be noted that because we require the longest substring, we need to update res every time we move right to increase the window, rather than update res when we move left to narrow the window as in the previous topic.

# 20. Valid brackets

Through example 5 "{[]}", we can know that this topic needs the help of the nature of the stack: first in and then out. My writing is very complicated and not concise. Often brush familiar routines. The details are s.toCharArray(), stacksack = new stack < > ();! stack. isEmpty(). Finally, judge whether the stack is empty. If not, for example, there is' {[(', indicating that there is still room left, then return false;

20. Valid brackets

```//Basic idea: each time an open bracket is encountered, the corresponding right bracket ')', ']' or '}' will be pushed onto the stack
//If a closing bracket appears in the string, you need to check whether the stack is empty and whether the top element is the same as the closing bracket. If not, the string is invalid.
//Finally, we also need to check whether the stack is empty
class Solution {
public boolean isValid(String s) {
// Using the nature of stack, first in, first out
Stack<Character>stack=new Stack<>();
// Traversing the elements of a string
for(char sc:s.toCharArray()){
if(sc=='{'){
stack.push('}');
}else if(sc=='['){
stack.push(']');
}else if(sc=='('){
stack.push(')');
}else if(!stack.isEmpty()&&sc==stack.peek()){
stack.pop();
}else{
return false;
}
}
// Finally, judge whether the stack is empty. If not, for example, there is still '{[(', indicating that there is still room left, then return false;
if(!stack.isEmpty()){
return false;
}
return true;
}
}
```

# 704. Binary search

https://leetcode-cn.com/problems/binary-search

In the back-end, the test frequency accounts for a small proportion. This topic is the classic template topic of binary search.

704. Binary search

```class Solution {
public int search(int[] nums, int target) {
// The array is in ascending order, so there is no need to sort manually. Because the subscript needs to be returned, the title can only be sorted.
// Using binary search, this topic is the classic template topic of binary search
//Left and right boundary
int left=0,right=nums.length-1;
while(left<=right){
//Index of midpoint
int mid=(right-left)/2+left;
if(nums[mid]<target){
// Change the interval to [mid+1,right]
left=mid+1;
}else if(nums[mid]>target){
// Change the interval to [left,mid-1]
right=mid-1;
}else if(nums[mid]==target){
// If the result is found, the result subscript is returned
return mid;
}
}
// non-existent
return -1;
}
}
```

Binary search framework

```int binarySearch(int[] nums, int target) {
int left = 0, right = ...;

while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
```

Just have to recite the memory and brush it repeatedly. The classic solution is to use two pointers, one running fast and the other running slow. If it does not contain rings, the pointer running fast will eventually encounter null, indicating that the linked list does not contain rings; If it contains a ring, the fast pointer will eventually make a turn of the super slow pointer and meet the slow pointer, indicating that the linked list contains a ring.

```public class Solution {
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
//The two met
if(fast==slow){
return true;
}
}
return false;
}
}
```

Added by ch1326 on Wed, 09 Feb 2022 02:48:43 +0200