Linear Data Structure (Part 1)

preface

In the previous article, Linear Data Structures (Part 1), we introduced the concepts of linear data structures: arrays, linked lists, stacks, queues, and hash tables and their suitable application scenarios. In this article, we will combine some common interview questions to analyze the questions and use Java code to implement these scenarios. Hope that through the actual code writing, deepen the understanding of these data, encounter similar scenarios in the future, we will appear handy. Don’t say a word, just do it!

Introduce ideas

No matter you are a fledgling “Java bird”, or a veteran of many years. For those in the tech world who want to improve their life quality and realize their dreams on a larger platform, there is an unavoidable wall: the technical interview. Of course, developers at different levels will encounter the corresponding level of interview questions. So I thought I’d throw out some common interview questions for you to think about. After the “real operation code” link with the code to achieve it, one let us think about it first, and then you can see the implementation code, brothers can give some advice, let us optimize together.

Practice the interview questions

In this section, no matter whether you are a novice or a master, I hope you think about your own ideas first. See oneself finally after all clear a few questions? Please post your results in the comments section (e.g. number of questions, time spent answering, or even if they are not answered). These are the same questions I ask people when I interview them. Your participation and the “three companies” are the source of my motivation, otherwise I would be on my own, sorting out articles is also very time-consuming…

An array of

• Array inversion;
• Removes duplicate elements from an array.
• An array of pairs equal to each other except for one element, which element;
• Write an algorithm that rotates a two-dimensional array 90 degrees clockwise.

The list

• Invert two adjacent nodes of a linked list; For example, 1->2->3->4 displays 2->1->4->3.
• Determine if there are rings in a linked list;

The stack and queue

• Determine whether the brackets (large, medium, small) in a paragraph are valid.
• Implement a queue with a stack;
• Design a loop queue;

Hash table

• Check whether the letters of two strings are exactly the same. For example: ABC and CBA;
• 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;

Think time

Get out your computers and read the code.

In the code

An array of

“1. Array inversion;“

“Analysis” : this problem is the basic operation, do not need to analyze. If you got a better idea, leave a comment.

package com.demo.array;

/ * ** Array inversion *  * @author dongx on 2020/9/20 * / public class ArrayReverseDemo {   public static int[] reverse(int[] arr){  int[] arrTemp = new int[arr.length];  for(int i = arr.length-1; i >=0; i--){ arrTemp[arr.length-i-1] = arr[i];  }  return arrTemp;  }   public static void main(String[] args) {  int[] arr = new int[] {1.0.1.3.4.2};  for (int elem : arr) {  System.out.print(elem + ",");  }  // Prints the inverted element  arr = reverse(arr);  System.out.println();  for (int elem : arr) {  System.out.print(elem + ",");  }  }  }  Copy the code

Results:

“Delete duplicate elements from an array.“

Analysis: Basic operation, no analysis. In fact, Map and Set operations can also be used to reduce the time complexity.

package com.demo.array;

import java.util.ArrayList;
import java.util.List;

/ * ** Remove duplicate elements from the array *  * @author dongx on 2020/9/20 * / public class ArrayRepeatDemo {  public static Object[] ifRepeat(Object[] arr) {  // Create a collection  List<Object> list = new ArrayList<>();  // Iterate through the array to store elements in the set  for (int i = 0; i < arr.length; i++) {  // If there are no identical elements in the set, store them in it  if(! list.contains(arr[i])) { list.add(arr[i]);  }  }  / / toArray directly  Object[] newArr = list.toArray();  return newArr;  }   public static void main(String[] args) {   String[] arr = new String[5];  arr[0] = "hello";  arr[1] = "world";  arr[2] = "Hello";  arr[3] = "hello";  arr[4] = "Enthusiastic sunrise crowd.";   System.out.println(arr.toString());  for (String s : arr) {  System.out.println(s);  }  System.out.println("======== result split line =======");  Object[] s = ifRepeat(arr);  for (Object o : s) {  System.out.println(o);  }   } }  Copy the code

Results:

“3, an array whose elements are equal to each other except one;“

“Analysis” : This can be matched in a traversal pattern, except that xOR operations are used to keep the code as simple as possible. All of them are equal except for one element, because xor can be swapped, two equal values, xor is zero, and a value xor is zero, and the result is the value itself. So this is pretty simple.

package com.demo.array;

/ * ** Find the only unpaired element in an array *  * @author dongx on 2020/9/20 * / public class ArrayFindOneDemo {   public static int findOne(int[] array) {  int result = 0;  for (int i = 0; i < array.length; i++) {  // The xOR operation  result ^= array[i];  }  return result;  }   public static void main(String[] args) {  int[] array = {2.3.3.2.5.6.6.8.8};  int result = findOne(array);  System.out.println("The different number is :" + result);  } }  Copy the code

Results:

“Write an algorithm that rotates a two-dimensional array 90 degrees clockwise.“

“Analysis of the“:

First sort out the logic according to the change order :(input parenthesis problem, so screenshots…)

package com.demo.array;

/ * ** Rotate the two-dimensional array by 90 degrees *  * @author dongx on 2020/9/20 * / public class ArraySpin90Demo {  public static int[][] rotate(int[][] matrix) {  int n = matrix.length;  // For the number to be rotated, a[I][j] satisfies I   for (int i = 0; i < n / 2; i++) {  for (int j = i; j < n - 1 - i; j++) {  // Introduce temp to solve the clockwise node swap  int temp = matrix[i][j];  matrix[i][j] = matrix[n - 1 - j][i];  matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];  matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];  matrix[j][n - 1 - i] = temp;  }  }  return matrix;  }   public static void main(String[] args) {   int[][] array = new int[3] [3];  / / the first line  array[0] [0] = 1;  array[0] [1] = 2;  array[0] [2] = 3;  / / the second line  array[1] [0] = 4;  array[1] [1] = 5;  array[1] [2] = 6;  / / the third row  array[2] [0] = 7;  array[2] [1] = 8;  array[2] [2] = 9;   System.out.println("Original array:");  for (int[] is : array) {  for (int i : is) {  System.out.print(i + "");  }  System.out.println("");  }   int[][] result = rotate(array);  System.out.println("Rotate the array 90 degrees clockwise:");  for (int[] is : result) {  for (int i : is) {  System.out.print(i + "");  }  System.out.println("");  }  } }  Copy the code

Results:

The list

“1. Reverse two adjacent nodes of a linked list; For example, 1->2->3->4 displays 2->1->4->3.“

“Analysis” : Directly swap two adjacent nodes by adjusting the pointer field. If a single list has an even number of nodes, just swap the odd-even nodes. If the list has an odd number of nodes, just swap the odd-even nodes except the last one.

package com.demo.linklist;

/ * ** Transpose two adjacent points in the list *  * @author dongx on 2020/9/20 * / public class LinkedListSwapPairsDemo {   public static void swapPairs(ListNode head) {  // Check whether it is null  if(head==null || head.next==null) { return;  }  // the node is currently traversed  ListNode cur = head.next;  // The precursor of the current node  ListNode pre = head;  // The successor of the current node  ListNode next = null;  while(cur! =null&&cur.next! =null) { next = cur.next.next;  pre.next = cur.next;  cur.next.next = cur;  cur.next = next;  pre = cur;  cur = next;  }  }   static class ListNode {  / * ** data fields* /  int data;  / * ** A reference to the next node* /  ListNode next;  }    public static void main(String[] args) {  ListNode head = new ListNode();  head.next = null;  ListNode tmp = null;  ListNode cur = head;  for (int i = 1; i < 8; i++) {  tmp = new ListNode();  tmp.data = i;  tmp.next = null;  cur.next = tmp;  cur = tmp;  }  System.out.print("Sequential output:");  for(cur = head.next; cur ! =null; cur = cur.next) {  System.out.print(cur.data + "");  }  swapPairs(head);  System.out.print("\n Reverse output:");  for(cur = head.next; cur ! =null; cur = cur.next) {  System.out.print(cur.data + "");  }  } }  Copy the code

Results:

An early end

Today, I will write the first two parts: array and linked list to share with you, because the content is more, has exceeded the word limit, so it is divided into two articles, thank you for your support, please continue to pay attention to…

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 2)