Common data structures and algorithm implementation (sorting / searching / array / linked list / stack / queue / tree / recursion / massive data processing / graph / bitmap / Java data structure)

As the basic skills of programmers, data structures and algorithms must be studied steadily. The bottom layer of our common framework is all kinds of data structures, such as jump table for redis, B + tree for mysql and inverted index for ES. If we are familiar with the bottom data structure and have a deeper understanding of the framework, we can be more handy in the subsequent programming process. The importance of mastering common data structures and algorithms is obvious. This paper mainly explains several common data structures and basic sorting and search algorithms, and finally summarizes the written interview questions of high-frequency algorithm. This article will continue to supplement, hoping to help you in your daily study or looking for a job. This article is the second lecture: arrays and linked lists

5. Some interview questions

Definition: it is a collection of multiple data of the same type arranged in a certain order, named with a name, and managed uniformly by numbering.

• 1. Implement an array that supports dynamic capacity expansion
• 2. An ordered array with a fixed size is implemented to support dynamic addition, deletion and modification. In actual development, we use ArrayList, which is more efficient
• 3. Realize the combination of two ordered arrays into an ordered array
• 4. Common problems of array operation (ArrayIndexOutOfBoundsException / null pointer exception)
• leetcode15: sum of three numbers
  Given an array num containing n integers, judge whether there are three elements a, b and c in num, so that a + b + c = 0? Find all triples that meet the conditions and are not repeated
  Idea: first sort the data, then determine the first number, use the for loop, use two pointers for the last two numbers, and try in turn. If the value is greater than 0-num[i], the right pointer moves left; If the value is less than 0-num[i], the left pointer moves to the right.

class Solution {
	public List<List<Integer>> threeSum(int[] nums) {
		Arrays.sort(nums);//From small to large
		List<List<Integer>> ls = new ArrayList<>();
		for (int i = 0; i < nums.length - 2; i++) {
			if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {  // Skip possible duplicate answers
 
				int l = i + 1, r = nums.length - 1, sum = 0 - nums[i];
				while (l < r) {
					if (nums[l] + nums[r] == sum) {
						ls.add(Arrays.asList(nums[i], nums[l], nums[r]));
						while (l < r && nums[l] == nums[l + 1]) l++;
						while (l < r && nums[r] == nums[r - 1]) r--;
						l++;
						r--;
					} else if (nums[l] + nums[r] < sum) {
						while (l < r && nums[l] == nums[l + 1]) l++;   // Skip duplicate values
						l++;
					} else {
						while (l < r && nums[r] == nums[r - 1]) r--;
						r--;
					}
				}
			}
		}
		return ls;
	}
}//The time complexity is O(n^2)

• leetcode169: find the mode. Given an array of size n, find the mode. Mode refers to the number of occurrences in the array greater than? n/2? Element of
  Prerequisite: the given array always has a mode
  Ideas: 1. Using Moore voting method 2. Using java api

public int majorityElement(int[] nums){
	int count = 1;
	int maj = nums[0];
	for (int i = 1; i < nums.length; i++){
		if (maj == nums[i])
			count++;
		else {
			count--;
			if (count == 0) {//Note: the number represented by maj cannot exceed half
				maj = nums[i + 1];
			}
		}
	}//Time complexity O(n)
	return maj;
}

• The second solution: use the java api to sort

public int majorityElement(int[] nums){
	Arrays.sort(nums);//Time complexity O(nlgn)
	return nums[nums.length / 2];
}

• LeetCode41: find the first positive number missing
  Given an unordered array of integers, find the smallest positive integer that does not appear.

class Solution {
	public int firstMissingPositive(int[] nums) {
		//Sort first, and then there are two cases: with 1 and without 1 (negative numbers are omitted)
		//1. If there is no 1, output 1
		//2. If there is 1, judge whether the next number is equal to the previous number, difference 1 or several numbers. If equal, continue, and difference 1 continues, otherwise exit
		boolean flag = false;
		int i;
		Arrays.sort(nums);
		for(i=0;i<nums.length;i++)
		{
			if(nums[i]<0)
				continue;//Negative skip
			if(nums[i]==1)
				flag=true;
			if(i+1<nums.length && nums[i]==nums[i+1])
				continue;
			if(i+1==nums.length || nums[i]+1!=nums[i+1])
					break;
		}
		if(flag==true)
			return nums[i]+1;
		if(flag==false)
			return 1;
		return 0;
	}
}//Time complexity O(n)

Demo Gobang program has the functions of saving, exiting and hanging. Because many values in the two-dimensional array are 0 by default, many meaningless data are recorded

6. Interview questions in linked list

6.1. Single linked list: next pointer (the special place of the tail node is that the pointer does not point to the next node, but points to an empty address NULL, indicating that this is the last node on the linked list)

public class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
	}
}

Circular linked list: the advantage of circular linked list is that it is more convenient from the end of the chain to the end of the chain. When the data to be processed has the characteristics of ring structure, it is particularly suitable to use circular linked list (such as the famous Joseph problem)

ListNode p = null;//Based on the single chain list, the chain tail points to the chain head
q =p;
for (int i = 2; i <= N; i++) {
	p = p.getNext();
	p.setVal(i);
}
p.setNext(q);//Building circular linked list

Be very careful when traversing the circular linked list, otherwise you will traverse the linked list indefinitely, because each node of the circular linked list has a successor node
Bidirectional linked list: (two additional spaces are required to store the address prev of the successor node next and the predecessor node)

public class ListNode {
	int value;
	ListNode prev;
	ListNode next;
	ListNode(int key, int val) {
		this.key = key;
		this.value = val;
	}
}

Tips:
1. Understand the meaning of pointer or reference: it is to store the memory address of the object (assigning a variable to the pointer is actually assigning the address of the variable to the pointer)
2. Beware of pointer loss and memory leakage. java does not need to consider (using jvm to automatically manage memory)
3. Simplify the implementation difficulty by using sentinel: if we introduce sentinel node, the head pointer will always point to this sentinel node (insert sort, merge sort, dynamic programming) at any time, whether the linked list is empty or not
Delete the last node and delete other nodes. Inserting the first node and inserting other nodes can be unified into the same code logic.
The advantage of sentinel: it can reduce the judgment of special situations, such as empty judgment and boundary crossing judgment, because empty boundary crossing can be considered as a small probability situation. It is true to walk through the code every time it is executed, which is more than in most cases.
For example, give a sentinel node and assign a key to the end element, so that the array traversal can stop because of equality without judging whether it is out of bounds.
4. Focus on convenient condition processing: (if the linked list is empty, can the code work normally? If the linked list contains only one node, can the code work normally? Can the code logic work normally when processing the head node and tail node?)
5. Drawing with examples to assist thinking: (example method and drawing method)

6.2. Describe the chain storage structure

• Any group of storage units can be used to store the data structure in the single linked list (it can be discontinuous), store the value a of each element, and also store the information of the post assembly point. These two information form a node.

6.3. Reverse a LinkedList (i.e. reverse of the linked list)

Collection toolkit used in development, collections reverse(List<?> list)
Principle: if i m n is adjacent, adjust the pointing of the pointer, adjust the pointing of M, and point to node i, the linked list will be disconnected. You need to save n before adjustment, code P236

public class Linked list inversion {
//The inversion of a single linked list adjusts the direction of the pointer. Before adjusting the next pointer, you need to save the previous value. After the inversion, the head node of the linked list is the tail node of the original linked list, that is, the node where next is a null pointer
	public void reverseIteratively(Node head) {
		Node pReversedHead = head;
		Node pNode = head;
		Node pPrev = null;
		while (pNode != null) {
			Node pNext = pNode.next;
			if (pNext == null) {
				pReversedHead = pNode;//pNode is the last node. After inversion, the head node of the linked list is the tail node of the original linked list
			}
			pNode.next = pPrev;
			pPrev = pNode;
			pNode = pNext;
		}
		head = pReversedHead;
}		

6.4. Judge whether there is a ring in a single linked list? Ali leetcode 141

• Idea 1: brute force method
  If the subsequent pointers of multiple nodes in the linked list are repeated, it indicates that there is a ring. Start with the first node, make it the current node, and then check whether the subsequent pointers of other nodes in the linked list point to the current node. If so, it indicates that there are rings in the linked list.
  Disadvantages: if the tail of the linked list cannot be determined, the algorithm will have an endless loop.

*Idea 2: use hash table (time complexity O(n), space complexity O(n))
Start from the header node and go through each node in the linked list one by one;
For each node, check whether the address of the node exists in the hash table;
If it exists, it indicates that the currently accessed node has been accessed. The reason for this is that there are links in the given linked list;
If there is no address of the current node in the hash table, insert the address into the hash table;
Repeat the above process until you reach the end of the table or find the ring.

• Idea 3: if there are rings in a single linked list, traversal with one pointer will never end, so you can use two pointers. One pointer takes one step at a time and the other takes two steps at a time. If there is a ring, the two pointers will meet in the ring. The time complexity is O(n) indeed (whether the number of rings is odd or even). It is called Floyd algorithm

public static  boolean checkCircle(Node list){
	if (list == null) {
		return false;
	}
	Node fast = list.next;
	Node slow = list;
	while (fast != null && fast.next !=null) {
		fast = fast.next.next;
		slow = slow.next;
		if (slow ==fast) {
			return true;
		}
	}        
	return false;
}//Time complexity O(n) space complexity O(1)

Supplement to floyd algorithm: if two pointers move two nodes and three nodes at a time instead of one and two nodes, is the algorithm still valid?
Yes, the complexity of the algorithm may increase

6.5. Determine whether the given linked list has ended NULL. If there is a ring in the linked list, return the length of the ring?

Idea: after finding the ring in the linked list, keep the slowPtr pointer unchanged, and the fastPtr pointer continues to move. Each time the fastPtr pointer is moved, the counter variable increases by 1 until it returns to the position of the slowPtr pointer again, that is, the length of the ring.

public class Length of detection ring {
	int FindLoopLength(ListNode head){
		ListNode slowPtr =head,fastPtr =head;
		boolean loopExists = false;
		int counter = 0;
		if (head == null) {
			return 0;
		}
		while (fastPtr.next != null && fastPtr.next.next != null) {
			slowPtr = slowPtr.next;
			fastPtr = fastPtr.next.next;
			if (slowPtr == fastPtr) {
				loopExists =true;
				break;
			}
		}
		if (loopExists) {
			fastPtr =fastPtr.next;
			while (slowPtr != fastPtr) {
				fastPtr =fastPtr.next;
				counter++;
			}
			return counter;
		}
		return 0;  //There is no ring in the linked list
	}
}	//Time complexity O(n)

Supplement: this idea can be extended to find the starting position (the number of digits after the decimal point) and the length of the cycle

6.6 what problems can the speed pointer solve? Ali

• 1. Given the header pointer of the single linked list, find the penultimate node, and then delete this node
  Idea 1: fast and slow pointer method:
  We define a fast pointer P and a slow pointer Q. first, let the P pointer go to the position of K nodes, and then the Q pointer starts from the pointer and moves with P. when P moves to the tail, the position of the Q node is the penultimate node

public static Node deleteLastKth(Node list,int k){
	Node fast =list;
	int i =1;
	while (fast !=null && i<k) {
		fast =fast.next;
		++i;//The first pointer goes k steps first
	}
	if (fast ==null) {
		return list;
	}
	Node slow =list;
	Node prev =null;
	while (fast.next !=null) {
		fast = fast.next;
		prev =slow;  //prev is the penultimate number k
		slow =slow.next;
	}
	if (prev ==null) {
		list = list.next;
	}else {
		prev.next =prev.next.next;
	}
	return list;
}//Time complexity O(n)

Idea 2: brute force method (with the highest time complexity)
Starting from the first node of the linked list, count the number of nodes behind the current node. If the number of subsequent nodes is less than k-1, the algorithm ends; If it is greater than k-1, move to the next node and repeat the process
Idea 3: hash table O(m) in order to reduce the number of times the linked list is traversed
The entry of the hash table is < node location and node address >. When traversing the linked list, you can get the length of the linked list and let M represent the length of the linked list. In this way, the problem of finding the nth node of the linked list is transformed into finding the positive number of the linked list
The M-n+1 node. Return the value with the primary key M-n+1 in the hash table. Time complexity O(m), space complexity O(m): create a hash table with size M.

• 2. The head node of the single linked list is known, and the middle node of the linked list is found (only one scan is allowed)
  A fast pointer P and a slow pointer Q start from the pointer at the same time. The fast pointer P moves two steps each time and the slow pointer moves one step each time. When the fast pointer P reaches the tail, the position of the slow pointer q is the position of the intermediate node

public class Find the middle node of the linked list {
	ListNode FindMiddle(ListNode head) {
		ListNode ptr1x, ptr2x;
		ptr1x = ptr2x = head;
		int i = 0;
		//Loop until the first pointer reaches the end of the table
		while (ptr1x.getNext() !=null) {
			if (i == 0) {
				ptr1x =ptr1x.getNext();//Move only the first pointer
				i = 1;
			}
			else if (i== 1) {
				ptr1x = ptr1x.getNext();
				ptr2x = ptr2x.getNext();
				i =0;
			}
		}        
		return ptr2x;//The returned value of ptr2x is the intermediate node
	}
}//Time complexity O(n) space complexity O(1)

6.7. Merge two ordered linked lists into one ordered linked list (double traversal). LeetCode23 merges k sorted linked lists

Idea: use the idea of divide and conquer and merge two

class Solution {
	 public ListNode mergeKLists(ListNode[] lists) {

		if (lists.length == 0)
			return null;
		if (lists.length == 1)
			return lists[0];
		if (lists.length == 2) {
			return mergeTwoLists(lists[0], lists[1]);
		}
		int mid = lists.length/2;
		ListNode[] l1 = new ListNode[mid];
		for(int i = 0; i < mid; i++){
			l1[i] = lists[i];
		}
		ListNode[] l2 = new ListNode[lists.length-mid];
		for(int i = mid,j=0; i < lists.length; i++,j++){
			l2[j] = lists[i];
		}
		return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));

	}
	//Recursive method of merging two ordered linked lists into a new ordered linked list
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1 == null) return l2;
		if (l2 == null) return l1;

		ListNode head = null;
		if (l1.val <= l2.val){
			head = l1;
			head.next = mergeTwoLists(l1.next, l2);
		} else {
			head = l2;
			head.next = mergeTwoLists(l1, l2.next);
		}
		return head;
	}
}

6.8. Insert a node in the ordered linked list

		public class Insert a node in the ordered linked list {
			ListNode InsertSortedList(ListNode head, ListNode newNode){
				ListNode current =head;
				ListNode temp = null;
				if (head ==null) {
					return newNode;
				}
				//Traverse the linked list until a node larger than the data value in the new node is found
				while (current != null && current.val < newNode.val) {
					temp = current;//temp is the previous node of current
					current = current.next; //current is a number greater than the newNode value
				}
				//Insert a new node before the node
				newNode.setNext(current);
				temp.setNext(newNode);
				return null;  
			}   
		}//Time complexity O(n)

6.9. Find the merging point of two one-way linked lists and combine them to form a one-way linked list. Assuming that the number of nodes of list 1 and list 2 before intersection is n and m respectively, and the size of n/m is uncertain, find the merging point of the two linked lists.

Method 1: brute force method
Compare each node pointer in the first linked list with each node pointer in the second linked list. When the nodes are equal, it is the intersection node. The time complexity is O(mn)
Method 2: hash table
Select a linked list with fewer nodes (if the length of the linked list is unknown, select any linked list at will) and save the pointer values of all nodes in the hash table; Traverse another linked list and check the hash table for each node in the linked list
Whether its node pointer has been saved in. If there is a merge point between the two linked lists, records must be found in the hash table. Time complexity O(m)+O(n); Spatial complexity O(m) or O(n)
Method 3: two stacks
Create two stacks, then traverse the two linked lists, and store all nodes in the first and second stacks respectively. The two stacks contain the node addresses of the corresponding linked list. Compare the top elements of the two stacks. If they are equal, two stacks will pop up
And save it in a temporary variable. Continue the above operation until the top elements of the two stacks are not equal. At this time, the merging point of the two linked lists is found. Time complexity O(m+n), space complexity O(m+n)
Method 4: the solution with ultra-low time complexity
Obtain the length of two linked lists L1/L2, O(max(m,n)); Calculate the difference d between the two lengths, move D steps from the header of the longer linked list, and then move the two linked lists at the same time until the two subsequent pointers are equal.

			public class Find the merging point of two linked lists {
				ListNode FindIntersectingNode(ListNode list1, ListNode list2){
					int L1=0,L2=0,diff=0;//L1 is the length of the first linked list, L2 is the length of the second linked list, and diff is the difference between the two linked lists
					ListNode head1=list1,head2=list2;
					while (head1 !=null) {
						L1++;
						head1 = head1.getNext();
					}
					while (head2 !=null) {
						L2++;
						head2 = head2.getNext();
					}
					if (L1<L2) {
						head1 = list2;
						head2 = list1;
						diff = L2-L1;
					}
					else  {
						head1 = list1;
						head2 = list2;
						diff = L1-L2;
					}
					for (int i = 0; i < diff; i++) {
						head1 = head1.getNext();
					}
					while (head1 != null && head2 != null) {
						if (head1 == head2) {
						   return head1;
						}
						head1= head1.getNext();
						head2 = head2.getNext();
					}
					return null;
				}
			}//Time complexity O(max(m,n)) space complexity O(1)

6.10. How to judge whether a string (linked list) is a palindrome string (strings are stored through a single linked list) (Shanghai tap water comes from the sea)

1) Premise: the string is stored in a single linked list in the form of a single character.
2) Traverse the linked list to determine whether the number of characters is odd. If it is even, it is not.
3) Store a copy of the characters in the linked list in reverse order in another linked list.
4) Synchronously traverse the two linked lists and compare whether the corresponding characters are equal. If they are equal, it is the daffodil string. Otherwise, it is not.
Idea 2: use the fast and slow pointers to find the midpoint of the linked list. The slow pointer advances one step at a time and the fast pointer advances two steps at a time. In the process of slow pointer advance, modify its next pointer at the same time to reverse the order of the first half of the linked list. Finally, compare whether the linked lists on both sides of the midpoint are equal
Time complexity O(n) space complexity O(1)

6.11. Delete a node in the single linked list within O(1) time

Assign the latter element to the node to be deleted, which is equivalent to deleting the current element
1. If the node to be deleted is not the last node, overwrite its value with the value of its next node, and then delete its next node
2. If it is the last node, traverse o (n) sequentially

6.12. How to reverse the linked list pair by pair? Initial 1 - > 2 - > 3 - > 4 - > x, after transposing pair by pair, it is 2 - > 1 - > 4 - > 3 - > X.

//Recursive version
ListNode ReversePairRecursive(ListNode head){
	ListNode temp;
	if (head ==null || head.next == null) {
		return head;  //The current linked list is empty or has only one element
	}else {
		//Inverse first pair
		temp = head.next;
		head.next = temp.next;//The next node of the first node is the third node
		temp.next = head;//The first node becomes the second
		head =temp;//The second node becomes the first
		head.next.next=ReversePairRecursive(head.next.next);
		return head;
	}
}

6.13 Joseph Ring (N people want to choose a leader. They form a ring. Every time they count to the M person along the ring, they exclude the person, and start counting again from the next person to find the last person in the ring)

		/**
		 * @param N Number of people
		 * @param M Serial number of the person to be excluded
		 * @return The last to stay
		 */
		ListNode GetJosephusPosition(int N, int M){
			ListNode p = null,q;
			//Create a circular linked list that contains everyone
			p.setVal(1);
			q =p;
			for (int i = 2; i <= N; i++) {
				p = p.getNext();
				p.setVal(i);
			}
			p.setNext(q);//Building circular linked list
			for (int count = N; count >1; --count) {
				for (int i = 0; i < M-1; i++) {
					p = p.getNext();
				}
				p.setNext(p.getNext().getNext());//Delete player
			}
			return p;//The last brave left
		}