1. Basic operations for one-dimensional arrays

One-dimensional arrays are the most basic data structure, and regular array interviews are easy to learn how to do it. The main challenge lies in the handling of boundaries. There are more than 360 titles for arrays in leetcode, but arrays are carriers of a large number of advanced algorithms, and the difficulty varies greatly, so here we comb the general titles first, and then discuss the corresponding chapters after the difficulties.

The basic operation of arrays is to create + add, delete, alter and check. In fact, the basic operation of any data structure is these five, so you can master half of them if you know them clearly.

In interviews, arrays are mostly of type int, so we use the type int to accomplish these basic functions.

1.1 Creation and Initialization

One-dimensional arrays are created as follows:

int[] arr = new int[10];

Here's a point to keep in mind that during an interview the interviewer will give you some examples to run and pass the test, such as giving you two arrays [0,1,2,3,5,6,8] => ['0->3','5->6','8'] [1,4,5,6,7,9,10] => ['1','4->7','9->10'], all of which can run. So how do I initialize at this point? One way is to use loops:

for(int i = 0 ; i < arr.length ; i ++)
   arr[i] = i;

But it's obviously not continuous here. Are you a little panic? You can do this:

int[] arr = new int[]{0,1,2,3,5,6,8};

If you want to test the second group, just assign it to the back. This is a very simple way to initialize. It is very useful during an interview, but you may be panicked or forget to write incorrectly during the interview, which invisibly results in a loss of points.

1.2 Find an element

Finding is the most basic operation. Finding is the core problem of data structure and algorithm. Many complex strategies are used to improve the efficiency of finding, such as binary search, binary tree, red-black tree, B+tree, Hash and heap.

On the other hand, many algorithmic problems are essentially problem finding, such as nSum problem, sliding window problem and dynamic programming problem, which occur frequently in leetcode, many of which are looking for the best number.

There are many implementation strategies to find, and some require more complex strategies, such as sorting before finding. Let's start with two simple scenarios: one based on index and one based on element linearity. Complex situations are combed in later chapters.

Finding based on index location is implemented as follows:

/**
* @param arr
* @param index Location to find
* @return
*/
public static int findByIndex(int[] arr,int size, int index) {
​
  if (index < 0 || index > size-1)
     throw new IllegalArgumentException("Add failed. Require index >= 0 and index < size.");
     return arr[index];
}

More often than not, you need to find the location of the target element:

/**
* @param arr
* @param size Stored element capacity
* @param key  Elements to Find
* @return
*/
public static int findByElement(int[] arr, int size, int key) {
​
  for (int i = 0; i < size; i++) {
       if (arr[i] == key)
          return i;
  }
  return -1;
}

Test:

public static void main(String[] args) {
    int[] arr = new int[10];
    int size = 10;
    for (int i = 0; i < size; i++)
       arr[i] = i;
​
     int a = findByIndex(arr, 5);
     System.out.println("5 The element at the number position is:" + a);
     int b = findByElement(arr, 10, 7);
     System.out.println("Element 7 is located at:" + b);
​
}

1.3 Add an element

There are also two common cases of adding an element: adding at a specified location, or giving an ordered array and adding an element at the correct location.

If an index is given, since adding elements to an array mostly requires elements to be moved, simply walk backwards and forwards while moving, and assign values directly after finding the corresponding location.

In addition, it is important to detect whether the boundary is crossed. This is the basic work of the array, and if you don't think about it, you can just finish it.

(1) Implementation of adding elements at specified locations

Here you need to know the reference to the array, the number of elements stored in the array, the insertion position, and the four parameters of the element to be inserted. Some materials customize an object to encapsulate multiple entries together, but in order not to create obstacles to an interview, we write them all in the most basic way.

/*** @param arr   Array * @param size Number of elements already stored * @param index insert position * @param key Insert elements*/public static void add(int[] arr, int size, int index, int key) {​   if (size >= arr.length) {      throw new IllegalArgumentException("Add failed. array is full.");   }   if (index < 0 || index > arr.length)      throw new IllegalArgumentException("Add failed. Require index >= 0 and index < arr.length.");​   for (int i = size - 1; i >= index; i--)       arr[i + 1] = arr[i];​   arr[index] = key;      size++;​}