Ten Tencent algorithm real problem analysis!

preface

Hello, everyone. I am a little boy picking up field snails. Collected Tencent often test ten algorithm questions (real questions). In jinsan Yinsi, I hope to help you.

Rearrange the list
Longest increasing subsequence
Circular linked list
Reverse a linked list
Longest string of subroutines
The whole arrangement
The LRU cache
Merge K ascending linked lists
The oldest string without repeating characters
Delete the penultimate node of the linked list

Public number: a boy picking up snails

1. Rearrange linked lists

Given a head node head of singly linked list L, singly linked list L can be expressed as:

L0 → L1 →... → Ln minus 1 → LnCopy the code

Please rearrange it to become:

L0 → Ln → L1 → ln-1 → L2 → ln-2 →...Copy the code

Input:

The head = [1, 2, 3, 4]Copy the code

Output:

,4,2,3 [1]Copy the code

Ideas:

It would have been nice if it had been an array, haha, because arrays can be accessed directly by subscripts, so it’s easy to solve this problem. But this is a linked list. Linked lists do not support subscript access, we can not randomly access any element in the list, what to do?

We can go through it, store the elements of the list in order with an array, and then we can access it as an array, right? And then we can rebuild the list.

An ArrayList is an array, so we can use it to store linked lists as follows:

List<ListNode> list = new ArrayList<ListNode>(); ListNode node = head; while (node ! = null) { list.add(node); node = node.next; }Copy the code

Once you have an array structure linked list, how do you rebuild it? Looking back at the examples, it’s easy to see a pattern: first, then last, then second, then last. This rule is obvious and the code is easy to implement:

int i = 0; int j = list.size()-1; while(i<j){ list.get(i).next = list.get(j); i++; if(i==j){ break; } list.get(j).next = list.get(i); j--; } list.get(I).next = null;Copy the code

The complete implementation code is as follows:

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }
}
Copy the code

2. Longest increasing subsequence

Given an integer array nums, find the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18] output: 4 explanation: the longest increasing subsequence is [2,3,7,101], so length is 4.Copy the code

Example 2:

Input: nums = [0,1,0,3, 3] Output: 4Copy the code

Ideas:

This problem is a maximization problem, which can be solved using dynamic programming. The overall idea of dynamic programming is:

Exhaustive analysis
Analysis to find rules, molecular problems
To determine the boundary
Determine the optimal substructure
Write the state transition equation

2.1 Exhaustive analysis

The core idea of dynamic programming includes the problem of splitting molecules, remembering the past and reducing double calculation. If num[I] is the longest increasing subsequence of num[I -1], then the maximum increasing subsequence of num[I -1] is the longest increasing subsequence of num[I -1].

A bottom-up exhaustive process:

When NUMs has only one element, 10, the longest increasing subsequence [10] is of length 1.
When NUMS requires the addition of an element 9, the longest increasing subsequence is either [10] or [9] of length 1.
When numS adds another element 2, the longest increasing subsequence is [10] or [9] or [2] and has length 1.
When numS adds an additional element 5, the longest increasing subsequence is [2,5] of length 2.
When nums adds an element of 3, the longest increasing subsequence is [2,5] or [2,3] of length 2.
When nums adds an element 7, the longest increasing subsequence is [2,5,7] or [2,3,7] of length 3.
When nums adds an element 101, the longest increasing subsequence is [2,5,7,101] or [2,3,7,101] of length 4.
When nums adds an element 18, the longest increasing subsequence is [2,5,7 101] or [2,3,7 101] or [2,5,7,18] or [2,3,7,18], with length 4.
When nums adds another element 7, the longest increasing subsequence is [2,5,7 101] or [2,3,7 101] or [2,5,7,18] or [2,3,7,18], with length 4.

2.2 Analyze and find rules and dismantle molecules

Through the above analysis, we can find a rule:

If a new element nums[I] is added, the longest increasing subsequence is either the one ending in nums[I] or the longest increasing subsequence of nums[i-1]. The longest increasing subsequence of nums[I] has been associated with the longest increasing subsequence of the subproblem nums[i-1].

The longest increasing subsequence of the original problem array nums[I] = the longest increasing subsequence of the subproblem array nums[i-1] / the longest increasing subsequence at the end of nums[I]

Does it feel like half the battle? But how to convert the nums[I] ending increasing subsequence into the corresponding subproblem? If only the increasing subsequence ending in NUMs [I] was also related to the longest increasing subsequence in NUMs [i-1]. Num [j] (0=

Nums [I] = nums[I] = nums[I] = nums[I] = nums[I] = nums[I] = nums[I] = nums[I] = nums[I] = nums[I] = nums[I] Num [I] = dp[I] = dp[I] = dp[I] = dp[I] = dp[I]

Nums [I] = nums[I] = nums[I] = nums[I] = nums[I] Obviously, there are many new subsequences that can be formed, so let’s take the longest one, which is dp[I]

Nums [3]=5, dp[4]=2, dp[4]=2, dp[4]=2
Dp [4]= dp[4]= dp[4]= dp[4]= dp[4]= dp[4]= dp[4]= dp[4]= dp[4]= dp[4]= dp[4]= dp[4]= dp[4
Nums [5] = 7 to 7 at the end of the sequence is the firstborn [2, 5, 7] and [2,3,7], because from the array subscript 0 to 5 traversal, found 2, and 3 are smaller than 7, so there will be [2, 7], [5, 7], [3, 7], [2, 5, 7] and [2,3,7] these subsequence, The oldest sequence is [2,5,7] and [2,3,7], which are derived from the longest increasing subsequence +[7] ending in 5 and 3. So, dp[5]=3 = DP [3]+1=dp[4]+1.

There is an obvious pattern: an array nums ending in nums[I]

Num [I]>num[j]

Dp (I) = Max (dp) (j) + 1.

2.3 Determining the Boundary

When the NUMS array has only one element, the length dp(1) of the longest increasing subsequence is 1. When the NUMS array has two elements, dp(2) is either 2 or 1, so the boundary is dp(1)=1.

2.4 Determine the optimal substructure

From 2.2 exhaustive analysis to find the rule, we can get the following optimal structure:

Dp (I) = Max (dp) (j) + 1, there are j belong to the interval [0, I - 1), and num [I] > num [j].Copy the code

Max dp of j is the optimal substructure.

2.5 Write the state transition equation

From the previous analysis, we can get the state transition equation:

So the longest increasing subsequence of the array nums[I] is:

Maximum increasing subsequence = Max (dp[I])Copy the code

The complete code implementation is as follows:

class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int[] dp = new int[nums.length]; Dp [0] = 1; int maxans = 1; For (int I = 1; i < nums.length; i++) { dp[i] = 1; // for (int j = 0; j < i; If (nums[I] < nums[I]) {if (nums[I] < nums[I]) {if (nums[I] < nums[I]) {if (nums[I] < nums[I]) { We will take the biggest in the dp dp [I] [I] = math.h Max (dp [I], dp [j] + 1); Maxans = math.max (maxans, dp[I]); maxans = maxans, dp[I]; } return maxans; }}Copy the code

3. Circular lists

Given the head node of a list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

Example:

Input: head = [3,2,0,-4], pos = 1 output: returns the list node with index 1.Copy the code

To determine whether a linked list has a ring, we can use the fast or slow pointer. The fast pointer is twice as fast as the slow pointer. When the two Pointers meet, it indicates that there is a ring.

boolean hasCycle(ListNode head ){ ListNode slow = head; ListNode fast = head; while(fast! =null && fast.next! =null){ fast = fast.next.next; slow = slow.next; if(fast==slow){ return true; } } return false; }Copy the code

We can easily tell that there is a ring, but how do we return the first node into the ring? Let’s draw a graph to analyze a wave:

Assume that the starting point is A, the entry point is B, the encounter point of the fast and slow Pointers is C, the slow pointer takes K steps to the encounter point, and the distance from B to C is M. Let the circumference of the ring be X. Because a fast pointer is twice as fast as a slow pointer. There are:

K-m + X + m = 2K = example of fast pointer walkCopy the code

So perimeter X is equal to K. After the encounter, the fast pointer to continue to go, go to the entry point B, the exact distance is X-m = k-m. And the distance from the starting point to B is also K minus m. Therefore, after the fast and slow Pointers meet, the slow pointer returns to the starting point, at this time the fast and slow Pointers go at the same speed, when they meet, it is the ring point, is not a coincidence into the book, ha ha ha.

The complete code is as follows:

public class Solution { public ListNode detectCycle(ListNode head) { if(head ==null){ return null; } ListNode fast = head; ListNode slow = head; while(fast! =null&&fast.next! =null){ fast = fast.next.next; slow = slow.next; If (slow==fast){// Return to the starting point together at the same speed while(head! =fast){ head = head.next; fast = fast.next; } return head; } } return null; }}Copy the code

4. Reverse the linked list

Given the head node of a single linked list, reverse the list and return the reversed list.

Input: head = [1,2,3,4,5] output: [5,4,3,2,1]Copy the code

The complete code is as follows:

class Solution {
    public ListNode reverseList(ListNode head) {

        ListNode prev = null;
        ListNode next = head;
        ListNode curr = head ;

        while(curr!=null){
            next =  curr.next ;
            curr. next = prev;
            prev = curr ;
            curr = next ;
        }

        return prev;
    }
}
Copy the code

We’ve illustrated this problem before, so you can take a look:

See it once to understand, diagram singly linked list inversion

5. The longest subroutine string

Given a string s, find the longest substring in s.

Example 1:

Input: s = "babad" Output: "bab" Explanation: "ABA" is also the answer to the question.Copy the code

This problem can be done using the center extension method, which starts in the middle and spreads out to the sides to determine the palindrome string.

For 0 <= I < len(s): find a palindrome string centered around s[I]Copy the code

But the palindrome string may be odd or even in length, so an extra step is needed:

For 0 <= I < len(s): find a palindrome centered on s[I] and s[I +1]Copy the code

The complete code is as follows:

class Solution { public String longestPalindrome(String s) { if(s==null|| s.length()<2){ return s; } String result =""; for(int i=0; i<s.length(); i++){ String r1 = subLongestPalindrome(s,i,i); String r2 = subLongestPalindrome(s,i,i+1); String tempMax= r1.length()>r2.length()? r1 :r2; result = tempMax.length()> result.length()? tempMax:result; } return result; } private String subLongestPalindrome(String s,int l,int r){ while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){ l--; r++; } return s.substring(l+1,r); }}Copy the code

6. The whole arrangement

Given an array nums that does not contain duplicate digits, return all possible permutations. You can return the answers in any order.

Example 1:

Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the code

Example 2:

Input: nums = [0,1] output: [[0,1],[1,0]Copy the code

This problem can be solved by backtracking. The complete code is as follows:

List<List<Integer>> allPath = new LinkedList<>(); Public List<List<Integer>> Permute (int[] nums) {List<Integer> path = new LinkedList<>(); BackTrace (nums,path); return allPath; } public void backTrace(int[] nums,List<Integer> path){// The array length of path is equal to the length of nums, indicating that a leaf node is reached. If (nums.length==path.size()){allPath.add(new LinkedList(path)); return; } for(int i=0; i<nums.length; If (path.contains(nums[I])){continue; if(path.contains(nums[I])){continue; } // Make a selection and add to the current path path.add(nums[I]); BackTrace (nums,path); Remove (path.size() -1); // Deselect path.remove(path.size() -1); }}}Copy the code

So if you look at the backtracking article I wrote earlier, there’s a framework for the backtracking algorithm.

Backtracking algorithm in detail

7. The LRU cache

Design and implement a data structure that satisfies the LRU (least recently used) cache constraints.

Implement the LRUCache class:

LRUCache(int capacity) The LRU cache is initialized using a positive integer as capacity
Int get(int key) Returns the value of the key if it exists in the cache, otherwise -1 is returned.
Void put(int key, int value) If the key already exists, change its value. If not, the group key-value is inserted into the cache. If the number of keywords exceeds capacity due to an insert operation, you need to export the unused keywords.

The functions get and PUT must run in O(1) average time complexity.

Example:

Input [" LRUCache ", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2]. [4, 4], [1], [3], [4] Output [NULL, NULL, NULL, 1, NULL, -1, NULL, -1, 3, 4] LRUCache LRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} lRUCache. Get (1); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} lRUCache. Get (2); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} lRUCache. Get (1); // return -1 (not found) lRUCache. Get (3); // return 3 lRUCache. Get (4); / / return 4Copy the code

This problem, the frequency of occurrence is quite high, many small partners in the interview, feedback that they have encountered the original problem.

LRU, Least Recently Used, is useful, and can be solved by using a double-linked list +Hashmap. The double-linked list is Used to store LRUCache data, and Hashmap achieves the average time complexity of O (1).

Every time you add an element from the end of the list, the last element is the most recently used
A key can be quickly located to a node using a hash table.

So what do we have to do for double linked lists.

The first step is to initialize the linked list, and to make it easier to process I, virtualize a head node and a tail node.
When an element is added, it is placed at the end of the list to indicate that the element has been used recently
Deletes a node in a bidirectional linked list
Delete and return the head node to remove the oldest unused element
Returns the current length of the list

What are the methods of LRU cache

Constructor initialization method
Get and PUT methods
MakeRecently sets the most recently used method for an element that already exists in the hash table
AddRecently adds the most recently used element and updates the map
DeleteKey Deletes elements corresponding to a key and nodes in the map
RemoveLeastRecently Removes the oldest unused element

The complete code is as follows:

class Node { int key,val; Node next,prev; public Node(int key,int val){ this.key = key; this.val = val; }} class DoubleList {private Node head, tail; private int size; Public DoubleList() {head = new Node(0, 0); // tail = new Node(0, 0); head.next = tail; tail.prev = head; size = 0; } public void addLast(Node x) {public void addLast(Node x) { Head <-> 1 <-> tail, add node x = 2.rev = tail.prev; Head <-> 1 <- 2 -> tail; Tail. Pre = tail; //head <-> 1 <-> 2 -> tail; tail.prev.next = x; //head <-> 1 <-> 2 <-> tail; tail.prev = x; // update the list length to size++; } public void remove(Node x) {x.priv. next = x.ext; x.next.prev = x.prev; size--; } public Node removeHead() {if (head.next == tail) {return null; } Node first = head.next; // size updates remove(first) in remove; Return first; return first; } public int getSize() {return size; } } public class LRUCache { private Map<Integer, Node> map; private DoubleList doubleList; private int cap; public LRUCache(int capacity) { this.map = new HashMap<>(); this.doubleList = new DoubleList(); this.cap = capacity; } public int get(int key) {if (map.containsKey(key)) {return value makeRecently(key);} public int get(int key) {if (map.containsKey(key)) { return map.get(key).val; } else { return -1; } } public void put(int key, int value) { if (map.containsKey(key)) { deleteKey(key); AddRecently (key, value); // Update the recent use of return; } int size = doubleList.getSize(); If (size == cap) {removeLeastRecently(); } addRecently(key, value); } public void makeRecently(int key) {Node x = map.get(key); doubleList.remove(x); // Delete doublelist.addlast (x) from the list; } public void addRecently(int key, int value) {Node x = new Node(key, value); doubleList.addLast(x); map.put(key, x); Public void deleteKey(int key) {Node x = map.get(key); map.remove(key); doubleList.remove(x); Public void removeLeastRecently() {// The oldest unused element must be in the head of the list. Node oldNode = doubleList.removeHead(); int oldKey = oldNode.key; map.remove(oldKey); }}Copy the code

Merge K ascending linked lists

You are given an array of linked lists, each of which has been sorted in ascending order. Please merge all lists into one ascending list and return the merged list.

Example 1:

Input: lists = [].enlighened by [1 4], [2, 6]] output:,1,2,3,4,4,5,6 [1] : list array is as follows: [1 - > > 5, 4-1 - > 3 - > 4, 6] 2 - > merge them into an ordered list. 1 - > 1 - > 2 - > 3 - > 4 - > 4 - > 5 - > 6Copy the code

Merging two ordered lists is relatively easy, and I’m sure you can do it. So how do you merge K ordered lists? In fact, the principle is the same, we can borrow the priority queue to find the smallest node, the complete code is as follows:

class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists.length==0){ return null; } ListNode head = new ListNode(0); ListNode tail = head; // PriorityQueue<ListNode> queue = new PriorityQueue<>(lists. Length,(a, b)->(a.val-b.val)); For (ListNode node: lists) {if (node! = null) { queue.add(node); } } while (! Queue. IsEmpty ()) {// Get the smallest node and put it in the result list. tail.next = node; if (node.next ! = null) { queue.add(node.next); } // pointer to the list straight up tail = tail.next; } return head.next; }}Copy the code

9. The oldest string without repeating characters

Given a string s, find the length of the smallest string that does not contain repeating characters.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3.Copy the code

Example 2:

Input: s = "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1.Copy the code

This can be done using sliding Windows. Sliding Windows is to maintain a window, keep sliding, and update the answers.

The general logical framework of sliding window, pseudo-code is as follows:

Int left =0, right =0; While (right < s.size()){// add window.add(s[right]); right++; While (window needs shrink){// shrink the window window.remove (s[left]); left ++; }}Copy the code

The solution process is as follows:

The first is to get the length of the original string.
Then maintain a window (array, hash, queue)
The window expands to the right step by step
In the process of expanding the window to the right, you need to determine whether the left side needs to be reduced
The answer is updated at the end

The complete code is as follows:

Int lengthOfLongestSubstring(String s){// Get the length of the original String int len = s.length(); Set<Character> Windows = new HashSet<>(); int left=0,right =0; int res =0; while(right<len){ char c = s.charAt(right); // window moves right++; While (windows.contains(c)){windows.remove(s.charat (left)); left++; } windows.add(c); Res = math.max (res,windows.size()); } return res; }Copy the code

Before writing a sliding window parsing, you can have a look at it:

Leetcode’s essential algorithms: Talk about sliding Windows

Delete the NTH node from the list

Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.

Example:

Input: head = [1,2,3,4,5], n = 2Copy the code

This problem can be solved using two Pointers. Since we want to find the NTH to last node, we can traverse the list using two Pointers first and second at the same time, and first is n nodes ahead of second. When first traverses the end of the list, second is exactly the NTH node from the bottom.

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode first = head; ListNode second = dummy; For (int I = 0; i < n; ++i) { first = first.next; } // Get to the end of the list while (first! = null) { first = first.next; second = second.next; } // Delete node second.next = second.next-next; ListNode ans = dummy.next; return ans; }}Copy the code

Reference and thanks

Leetcode website
Labuladong algorithm cheat sheet

Ten Tencent algorithm real problem analysis!

preface

1. Rearrange linked lists

2. Longest increasing subsequence

2.1 Exhaustive analysis

2.2 Analyze and find rules and dismantle molecules

2.3 Determining the Boundary

2.4 Determine the optimal substructure

2.5 Write the state transition equation

3. Circular lists

4. Reverse the linked list

5. The longest subroutine string

6. The whole arrangement

7. The LRU cache

Merge K ascending linked lists

9. The oldest string without repeating characters

Delete the NTH node from the list

Reference and thanks

Related Posts

The cause of the online BUG was the Spring parent container, so I went to remove its underpants

“Recommended collection!” (3) “Index Technology” Experience unprecedented technology exploration, see through the essence of index and technical system (Part 1)

Just in time! 13 Spring Boot training programs, use it well, promotion and salary will not worry