The essential

Then “linear data structure (Part 1)”, we continue to finish the topic, directly do!

In the code

The list

“2. Determine whether there are rings in a linked list;“

“Analysis” : cycle through the nodes, each one will be marked, the traversal process to determine whether it is marked, if it is marked, it indicates that there is a ring. The head pointer moves. If it reaches the previous position, it indicates a loop. If it does not, it goes to the end of the list.

package com.demo.linklist;

import java.util.HashSet;
import java.util.Set;

/ * ** Determine if there are any changes in the linked list *  * @author dongx on 2020/9/20 * / public class LinkedListHaveCycleDemo {   static class ListNode {  int val;  ListNode next;  ListNode(int x) {  val = x;  next = null;  }  }   public static class Solution {  public boolean hasCycle(ListNode head) {  // Declare a set to hold a traversal node, i.e. a marker node.  Set<ListNode> set = new HashSet<>();  while(head! =null) {  if(set.contains(head)) {  return true;  }else {  set.add(head);  head = head.next;  }  }  return false;  }  }   public static void main(String[] args) {  ListNode head = new ListNode(0);  ListNode tail = null;  ListNode temp = null;  for (int i = 1; i < 8; i++) {  ListNode listNode = new ListNode(i);  if (null! = temp) { temp.next = listNode;  } else {  head.next = listNode;  }  temp = listNode;  System.out.print(temp.val + ",");  tail = listNode;  }  Solution solution = new Solution();  System.out.println("Do linked lists have rings?" + solution.hasCycle(head));  // Connect the tail to the head  tail.next = head;  System.out.println("Does a linked list have a ring after it is joined head to tail:" + solution.hasCycle(head));  } }    Copy the code

Results:


The stack and queue

“1. Judge whether the various brackets (large, medium and small) in a passage are legal;“

“Analysis” : this should be easy, we can use the stack properties, matching the corresponding parentheses, if the stack is empty at the end, all the parentheses are matched. Notice that if the first close parenthesis is pushed, it immediately returns illegal;

“The results of“:

“2. Use stack to implement a queue;“

“Analysis” : The stack is FILO and the queue is FIFO. If we want to implement this transformation, we can think of two stacks. Start by adding the tail-of-the-team element to Stack1 at a time. If the header element needs to be ejected, the element in Stack1 is ejected and pushed into Stack2, and the stack element at the top of Stack2 is ejected. If stack2 is non-empty, the element is still added to Stack1 when the element is added to the end of the queue, and the header element is popped from Stack2. Only when Stack2 is empty does the pop-up queue header element need to be moved from Stack1 to Stack2.

“The results of“:

“3. Design a circular queue;“

“Analysis” : Circular queue is the sequential representation and realization of queue, and its advantage is that the time complexity of queue entry and queue exit is O(1), which is attributed to the thinking mode of “circular queue transforms the understanding of storage structure from sequential to circular”.

package com.demo.stackandqueue;

/ * ** Loop queue interface *  * @author dongx on 2020/9/21 * / public interface ISequenceQueue<T> {  public boolean push(T t);   public T pop(a);   public int length(a);   public int size(a);   public boolean isEmpty(a);   public boolean isFull(a); } Copy the code
package com.demo.stackandqueue;

import java.util.Stack;

/ * ** Loop queue *  * @author dongx on 2020/9/21 * / public class CycleQueueDemo<T> implements ISequenceQueue<T> {   Object[] datas;  int size;  int front = 0;  int rear = 0;   public CycleQueueDemo(int size) {  this.size = size;  this.datas = new Object[size];  }   @Override  public boolean push(T t) {  if (isFull()) {  return false;  }  datas[rear] = t;  rear = (rear + 1) % size;  return true;  }   @Override  public T pop(a) {  if (isEmpty()) {  return null;  }  @SuppressWarnings("unchecked")  T t = (T) datas[front];  datas[front] = null;  front = (front + 1) % size;  return t;  }   @Override  public int length(a) {  return (rear - front + size) % size;  }   @Override  public boolean isEmpty(a) {  if (rear == front) {  return true;  }  return false;  }   @Override  public boolean isFull(a) {  if ((rear + 1) % size == front) {  return true;  }  return false;  }   @Override  public int size(a) {  return size;  }   public static void main(String[] args) {  CycleQueueDemo<Integer> o = new CycleQueueDemo<Integer>(10);  for (int i = 1; i <= 30; i++) {  boolean b = o.push(i);  System.out.println("Queue length after joining" + o.length());  if (i % 2= =0) {  Integer out = o.pop();  System.out.println(i + "The present length is." + o.length() + ", exit value =" + out);  }  if(! b) { System.out.println("Not in the team" + i);  }  }  for (int i = 1; i <= 10; i++) {  Integer out = o.pop();  System.out.println(i + "The present length is." + o.length() + ", exit value =" + out);  }  System.out.println("");  } }  Copy the code

“The results of“:

Hash table

“1. Check whether the letters of two strings are identical. For example: ABC and CBA;“

“Analysis” : this is also relatively simple, there are a variety of methods, here I use the ASCII with the letter to do addition and subtraction to determine whether the two sides of the same; .

“The results of“:

“2. Given an int and an array, return the subscript of the sum of two numbers. For example: value 11, array [1,10,9,2,3,7,8], return 0,1 and 2,3 and 4,6;“

The key and value of a HashMap can also be added and subtracted by using an array to store subscripts.

“The results of“:

At the end

Through two practical articles, the code to help you to strengthen memory and understanding, I believe that you have a certain understanding of some common interview questions of linear data structure, is not the opposite question to do have a good idea? Ha, ha, ha. If you have harvest is also the meaning of my article, I will continue to update the “internal exercise series” article, hope you continue to pay attention to, thank you for your support!

Special statement

This article is an original article. If you need to reprint it, please contact me and indicate the source. Thank you very much!

“Previous articles:“

Linear Data Structure (Part 1)

Linear Data Structure (Part 1)