Day 28 of leetcode

1. The distance between bus stops

There are... On the circular bus route n Individual station , From 0 To n - 1 Number . We know the distance between each pair of adjacent bus stops ,distance[i] Indicates that the number is i The station and number are (i + 1) % n The distance between the stations .

The buses on the loop line can travel clockwise and counterclockwise .

Return passengers from the starting point start Destination destination The shortest distance between .

analysis ：

according to start and destination To traverse the array , Find the shortest distance .

class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int min = 0;
        if (start == destination) return 0;
        if (start<destination){
            int count1 = 0;
            int count2 = 0;
            for (int i = start; i < destination; i++) {
                count1 += distance[i];
            }
            for (int i = 0; i < start; i++) {
                count2 += distance[i];
            }
            for (int i = destination; i < distance.length; i++) {
                count2 += distance[i];
            }
            min = Math.min(count1, count2);
        }
        else {
            int count1 = 0;
            int count2 = 0;
            for (int i = destination; i < start; i++) {
                count1 += distance[i];
            }
            for (int i = 0; i < destination; i++) {
                count2 += distance[i];
            }
            for (int i = start; i < distance.length; i++) {
                count2 += distance[i];
            }
            min = Math.min(count1, count2);
        }
        return min;
    }
}

2. 0 and 1 The same number of subarrays

Given a binary array nums , Find the same number of 0 and 1 The longest continuous subarray of , And returns the length of the subarray .

analysis ：

Use prefixes and . Define a variable pre Record traversal to nums The prefix and at each position of the array ,pre Initialize to 0, If nums[i]=1, pre += 1, If nums[i]=0,pre -= 1. If pre=0 said [0,i] There are the same number of 0 and 1.
Use a hash table to record non 0 The earliest position of each number of hours ,pre If the value of exists in the hash table, then calculate the distance between them .

class Solution {
    public int findMaxLength(int[] nums) {
        int len = 0, pre = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,0);
        for (int i = 1; i <= nums.length; i++) {
            if (nums[i-1] == 1) pre += 1;
            if (nums[i-1] == 0) pre -= 1;
            if (map.containsKey(pre)){
                len = Math.max(len, i-map.get(pre));
            }else{
                map.put(pre, i);
            }

        }
        return len;
    }
}

3. The sum of the left and right subarrays is equal

Give you an array of integers nums , Please calculate the of the array Center subscript .

Array Center subscript Is a subscript of the array , The sum of all elements on the left is equal to the sum of all elements on the right .

If the central subscript is at the leftmost end of the array , Then the sum of the numbers on the left is regarded as 0 , Because there is no element to the left of the subscript . This also applies to the fact that the central subscript is at the rightmost end of the array .

If the array has multiple central subscripts , Should return to Closest to the left The one of . If the array does not have a central subscript , return -1 .

analysis ：

Define two variables before and after Respectively represents the sum of the left numbers of the current position and The sum of the numbers on the right . The initial values are 0 And the sum of the whole array numbers . Start traversing each number of the array , Keep updating before and after, When there is a before=after Directly return the current subscript .

class Solution {
    public int pivotIndex(int[] nums) {
        int before = 0, after = 0;
        for (int i = 0; i < nums.length; i++) {
            after += nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            after -= nums[i];
            if (before == after) return i;
            before += nums[i];
        }
        return -1;
    }

4. Sum of two-dimensional submatrix

Given a two-dimensional matrix matrix, Multiple requests of the following types ：

Calculate the sum of the elements in its subrectangle , The upper left corner of the submatrix is (row1, col1) , The lower right corner is (row2, col2) .
Realization NumMatrix class ：

• NumMatrix(int[][] matrix) Given an integer matrix matrix To initialize
• int sumRegion(int row1,int col1, int row2, int col2) Return to the upper left corner (row1, col1) 、 The lower right corner (row2, col2)
  The sum of the elements of the submatrix of .

analysis ：

utilize List Store two-dimensional matrix , Then iterate and sum . This method almost timed out ..... be it so

class NumMatrix {
    List<int[]> list;
    public NumMatrix(int[][] matrix) {
        list = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            list.add(matrix[i]);
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            int[] num = list.get(i);
            for (int j = col1; j <= col2; j++) {
                sum += num[j];
            }
        }
        return sum;
    }
}