“This article has participated in the good article call order activity, click to see: back end, big front end double track submission, 20,000 yuan prize pool for you to challenge!”

The linear table

In the process of LeetCode brushing, the linear table often used mainly includes the following four important data structures: array, linked list, stack and queue.

Arrays, linked lists, stacks, and queues are covered below.

Overview of Linear Tables

Linearity: Linearity here is logical continuity, not physical storage continuity.

Stored data: A linear table is an ordered sequence of n pieces of data of the same type.

An array of array

introduce

An array is a linear list of physically continuous storage. The common forms are a[0], a[1]… A [n-1], a[i-1] is the precursor of a[I], and a[I +1] is the successor of a[I].

Basic operation

insert

To insert an element, move all the elements after the insertion position back one bit.

The following figure is an example of inserting an element X at position 3 with the array length 6, data 0, 1, 2, 3, 4, 5.

delete

To delete an element, all the elements after the deletion position are moved one bit forward.

The following figure shows an example of deleting element X at position 3 with the array length 6 and data 0, 1, 2, 3, 4, 5.

reverse

Flipping an array is essentially reversing the data stored in the array.

The following figure shows an example of reversing the entire array with length 6 and data 0, 1, 2, 3, 4, 5.

sample

LeetCode 27. Remove elements

The question

Removes all elements equal to val from an array, returning the new length of the array after removal. No extra space is required.

The sample

Input: nums = [3,2, 3], val = 3 Output: 2, nums = [2,2]Copy the code

Answer key

How to delete an array without using extra space? Since the length of the deleted array is less than or equal to the length of the original array, it is possible to determine whether the original array is equal to val while putting an array that is not equal to val into the original array.

code

class Solution {
    public int removeElement(int[] nums, int val) {
        // left stores the number of digits in the current nums array that do not equal val
        int left = 0; 
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        returnleft; }}Copy the code

Problem sets is recommended

LeetCode 35. Search for insertion location

The list

introduce

The appearance of linked lists is to solve the linear overhead caused by array insertion and deletion.

Unlike arrays, the elements in a linked list can be stored discontiguously, with each element containing its data and a pointer to the next node in the list.

Basic operation

insert

To insert an element, set a pointer to the inserted element itself and a pointer to the inserted element to the previous position.

delete

Delete the element, to delete the element before the element pointer to delete the element after the element, the code implementation needs to delete the element pointer to the location of the record.

The following is an example of a linked list of length 5, deleting elements at position 3.

flip

To flip a list, you can use a temporary variable to record where the next pointer to the current element points to as you iterate, and then point the next pointer to you.

Here is an example of a list of length 5, flipped.

sample

1. LeetCode 206. Reverse the linked list

The question

For the head node of a single linked list, reverse the list and return the inverted list.

The sample

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

Answer key

According to the above list flip operation idea to achieve the code.

code

public ListNode reverseList(ListNode head) {
	  // Pre stores the previous node of the current node
    ListNode prev = null;
    // curr stores the current list traversal to the node
    ListNode curr = head;
    while(curr ! =null) {
        // Next stores the next node of the current node
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}
Copy the code

Problem sets is recommended

  1. LeetCode237. Remove nodes from the linked list
  2. LeetCode 21. Merge two ordered lists
  3. LeetCode 160. Intersect linked lists

The stack and queue

The stack is introduced

The stack is restricted to inserting and deleting operations at the top of the stack, so it is last in, first out.

The following figure is a schematic diagram of inserting (pushing) and deleting (exiting) the stack.

The queue is introduced

Queues are restricted to delete operations at the head of the queue and insert operations at the end of the queue, so they are first-in, first-out.

The following figure shows the schematic diagram of queue insertion (in queue) and deletion (out queue).

Basic operation

The insert and delete operations for stacks and queues are explained in the figure above.

sample

LeetCode 155. Minimum stack

Design a stack that supports push, pop, and top operations and can retrieve the smallest element in constant time.

  • push(x)— Push element x onto the stack.
  • pop()Delete the top element of the stack.
  • top()Get the top element on the stack.
  • getMin()Retrieve the smallest element in the stack.

The sample

Input: [" MinStack ", "push" and "push" and "push" and "getMin", "pop", "top", "getMin"] [[], [2], [0], [3], [], [], [], []] output: [null,null,null,null, null,-3,null,0,-2] MinStack MinStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Return -3. Minstack.pop (); minStack.top(); --> Return 0.minstack.getmin (); -- -- > to return to 2.Copy the code

Answer key

Create a new auxiliary stack. The top of the auxiliary stack represents the minimum value of all digits in the original stack. The following four operations required by the topic are discussed, and how to achieve them respectively.

  • push(x)If the number inserted is less than or equal to the top element of the auxiliary stack, then this number is the minimum value (one) in the original stack and we insert it into the auxiliary stack.
  • pop():If the number removed from the original stack is equal to the top element of the auxiliary stack, then this number is the minimum (one) in the original stack, and we have both the top element of the original stack and the top element of the auxiliary stack. Otherwise, only the top element of the stack is removed.
  • top():Returns the top element of the original stack.
  • getMin():Returns the top element of the auxiliary stack.

code

class MinStack {
    public Stack<Integer> s, min_s;
    public MinStack(a) {
        s = new Stack<>();
        min_s= new Stack<>();
    }
    public void push(int x) {
        s.push(x);
        if(min_s.isEmpty() || x <= min_s.peek())
            min_s.push(x);
    }
    public void pop(a) {
        if(s.pop().equals(min_s.peek()))
            min_s.pop();
    }
    public int top(a) {
        return s.peek();
    }
    public int getMin(a) {
        returnmin_s.peek(); }}Copy the code

Problem sets is recommended

LeetCode 20. Valid parentheses