This is the sixth day of my participation in Gwen Challenge

1. Arrays and strings

1.1 One-dimensional Array

One-dimensional arrays are well-known data structures. The elements in an array are stored consecutively in memory. Each element in the array has an index value (array subscript). Through the index, the elements in the array can be accessed quickly.

Array 4 common operations

  • Read elements by index value in O(1) time
  • Find a particular element in order n time
  • Insert elements in order n time
  • Delete elements in order n time

1.2 Two-dimensional Array

A two-dimensional array is a special kind of array, which only transforms each element into a one-dimensional array. Similar to A one-dimensional array, for A two-dimensional array A = [[1, 2, 3, 4],[2, 4, 5, 6],[1, 4, 6, 8]], the computer will also apply for A contiguous space in memory and record the index position of the array in the first row, namely the memory address of A[0][0].

1.3 the string

Wikipedia: A string is a finite sequence of zero or more characters. Generally written as s = a1A2… The an. It is a data type that represents text in a programming language.

Strings and arrays have many similarities, such as the use of ** name [subscript]** to get a character, for example, Java String object is the bottom of the array implementation. As one of the most common and important data types in programming, it is also very important to study string. String manipulation is more complex than other data types. Common operations include flipping strings, editing distances, string matching algorithms… These are things that take a lot of research to write well.

2. Double pointer technique

Solving a problem by iterating through an array is one of the general operations. Usually, we only need a pointer to iterate, starting with the first element in the array and ending with the last. However, sometimes we iterate with two Pointers.

2.1 Head and tail Pointers

A header pointer, as the name suggests, has two Pointers to the beginning and end of an array. Some problems are immediately obvious and can be solved quickly by using tips such as reversing strings. Quick sorting, as we know it, also has the technique of using a head and tail pointer.

2.1.1 Question Type Analysis:Sum of two numbers II – Enter an ordered array

Given an array of integers in ascending order numbers, find two numbers that add up to the target number.

The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts at 1, so the answer array should be 1 <= answer[0] < answer[1] <= numbers. Length.

You can assume that each input corresponds to a unique answer, and you can’t reuse the same elements.

Example:

  • Type: numbers = [2,7,11,15], target = 9
  • Output: [1, 2]
  • Explanation: The sum of 2 and 7 equals the target number 9. So index1 = 1, index2 = 2.

Because a given array is ordered, one can first consider using dichotomy, which is order (log n) efficient for ordered arrays. Fix the first number, then use dichotomy to find the other number so that the sum of the two numbers equals target. If found, return, if not found, fix the second number, continue searching, as follows.

for i to n
    if(binarySearch(i+1, n, target - num[i], int[] num){
        return;
    }       
Copy the code

Using binary search method, although the binary search efficiency is very fast, but need to fix a number from beginning to end, the overall time complexity is O(n * log n).

Use the head and tail pointer method, starting with two Pointers to the first and last element positions. Because the array is ordered, we can get a clear direction of pointer movement.

  • Each time the sum of the two elements pointed to by the two Pointers is evaluated and compared with the target value.
  • If the sum of the two elements equals the target value, a unique solution is found.
  • If the sum of the two elements is less than the target value, move the left pointer one bit to the right.
  • If the sum of the two elements is greater than the target value, the right pointer is moved one bit to the left.
  • After you move the pointer, repeat until you find the answer.

Complexity analysis

  • Time complexity: O(n) where n is the length of the array. The total number of moves of the two Pointers is at most N.
  • Space complexity: O(1).
class Solution {
    public int[] twoSum(int[] numbers, int target) {
    	int[] result = new int[2];
    	int minIndex = 0;
    	int maxIndex = numbers.length-1;
    	while(minIndex ! = maxIndex){if(numbers[minIndex] + numbers[maxIndex] == target){
    			result[0] = minIndex+1;
    	    	result[1] = maxIndex+1;
    	    	return result;
    		}
    		if(numbers[minIndex] + numbers[maxIndex] < target){
    			minIndex ++;
    		}
    		if(numbers[minIndex] + numbers[maxIndex] > target){ maxIndex --; }}returnresult; }}Copy the code

Head and tail pointer exercise: square an ordered array

2.2 Fast and slow pointer

The head and tail pointer can traverse the number group by running the head and tail pointer opposite to each other. Fast and slow Pointers, on the other hand, use two out of sync Pointers to solve the problem. Unlike the head and tail Pointers, the fast and slow Pointers move in the same direction. Classic questions like removing elements.

2.2.2 Question type analysisRemove elements

Given an array of nums and a value of val, you remove all elements equal to val in place and return the new length of the array.

Instead of using extra array space, you must only use O(1) extra space and modify the input array in place.

The order of elements can be changed. You don’t need to worry about the element after the new length in the array.

They say, remove all elements with a value equal to val in place. Each time you remove an element, you need to move the following element forward. The brute force solution is a two-level for loop, with a for loop iterating through the array of elements and a second for loop updating the array. The solution is O(n^2). ** If you know how many elements with a value of val precede each element, each element can be moved to its desired location in one step. ** This can be done using the fast or slow pointer.

  • The fast pointer points to the element to be manipulated, and the slow pointer points to the next location to be assigned.
  • If the fast pointer points to an element with the value val, the fast pointer moves one bit to the right, and the slow pointer does not move.
  • If the element to which the fast pointer points does not have a value of val, the element to which the fast pointer points is assigned a slow pointer, with both the fast and slow Pointers moved one bit to the right.
  • The fast pointer completes the array traversal and removes elements. The slow pointer’s value is the length of the output array.
class Solution {
    public int removeElement(int[] nums, int val) {
    	int result = 0;
        for(int i = 0; i<nums.length; i++){if(nums[i] != val){
        		nums[result] = nums[i];
        		result++;
        	}
        }
    	returnresult; }}Copy the code

As an aside, you can also remove elements using a pointer to a header or a pointer to a tail.

3. Sliding Windows

Sliding Windows can be seen as a variation of the two-pointer technique. The so-called sliding window is constantly adjusting the start and end positions of the subsequence to get the result we want. Because constantly adjusting the start position (start pointer) and end position (end pointer) of the subsequence looks like a window moving through an array, it is called a sliding window.

Sliding window question type, mainly pay attention to the following three points:

  • What’s in the window
  • How do I move the starting position of the window
  • How do I move the end of a window

Let’s do this with a problem: the smallest subarray.

Given an array of n positive integers and a positive integer s, find the smallest contiguous subarray in the array whose sum is ≥ s and return its length. If no subarray exists, return 0.

  • Example:
  • Input: s = 7, nums = [2,3,1,2,4,3]
  • Output: 2
  • Explanation: the subarray [4,3] is the smallest subarray for this condition.

Let’s go back to the three points

  • In this case, the window is the smallest contiguous subarray whose sum ≥ s.
  • How to move the starting position of the window: If the value of the current window is greater than s, the window will move forward (that is, shrink).
  • How to move the end position of the window: The end position of the window is the pointer to iterate over the array. The start position of the window is set to the start position of the array.
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0: ans; }}Copy the code