June brush question 01 - array

Today's brush topic content ： Array

Preface

• Update the problem solution content of the problem brush every day
• Focus on personal understanding , Look at the difficulty and update the number of questions
• The title comes from Li Kou
• Try to work out at least one question every day
• Language java、python、c\c++

---

One 、 Today's topic

1. 1588. The sum of all odd length subarrays
2. 1848. Minimum distance to target element
3. 1652. Dismantle the bomb
4. 1640. Can you join to form an array

Two 、 Their thinking

1. 1588. The sum of all odd length subarrays

1. Require the sum of all odd subsequences
2. That is, start traversing from each element , Add the current element sum to the result when it is an odd number of elements
3. Return the result

class Solution {
    
    public int sumOddLengthSubarrays(int[] arr) {
    
        int i = 0, j, count = 0, ans = 0;
        int n = arr.length;
        while( i < n){
    
            j = i;
            count = 0;
            while(j < n){
    
                count += arr[j];
                if ((j - i + 1) % 2 == 1){
    
                    ans += count;
                }
               j++;     
            }
            i++;
        }
        return ans;
    }
}

---

2. 1848. Minimum distance to target element

1. Find the subscript of the element , Maintain a minimum value

class Solution {
    
    public int getMinDistance(int[] nums, int target, int start) {
    
        int i;
        int n = nums.length;
        int ret = 10010;
        for (i = 0; i < n; ++i){
    
            if (nums[i] == target){
    
                ret = Math.min(ret, Math.abs(i - start));
            }
        }
        return ret;
    }
}

---

3. 1652. Dismantle the bomb

1. according to k There are three cases for the value of , For the sake of understanding , Directly mark the three situations
2. If k by 0 Back to full 0 that will do
3. If k Greater than or less than 0, There are two scenarios , The expansion here is larger than 0 Of
   1. If i+k Greater than the rightmost subscript of the array , It will return to the first... From the beginning of the array i + k - n A place
   2. If it is less than the rightmost subscript of the array , Then add it directly
4. Less than 0 It's the same thing

class Solution {
    
    public int[] decrypt(int[] code, int k) {
    
        int i, n = code.length;
        int t = k;
        int[] ret = new int[n];
        if (k == 0){
    
            return ret;
        }else if (k < 0){
    
            for (i = 0; i < n; ++i){
    
                int temp = 0;
                while(k < 0){
    
                    if (i + k < 0){
    
                        temp += code[n + i + k];
                    }else{
    
                        temp += code[i + k];
                    }
                    k++;
                }
                k = t;
                ret[i] = temp;
            }
        }else{
    
            for (i = 0; i < n; ++i){
    
                int temp = 0;
                while(k > 0){
    
                    if (i + k > n - 1){
    
                        temp += code[i + k - n];
                    }else{
    
                        temp += code[i + k];
                    }
                    k--;
                }
                k = t;
                ret[i] = temp;
            }
        }

        return ret;
    }
}

---

4. 1640. Can you join to form an array

There are two ways of thinking about this question
Train of thought
The first is to use hash table

1, Convert all subsets of the two-dimensional array into strings as key In the hash table , Default value by false
2. Traversing a one-dimensional array , If the current number exists in the... Of the hash table key in , Will value Set as true
3. Splice the current numbers in order , Judge whether there is in key in , If it exists, repeat step 2

class Solution {
    
    public boolean canFormArray(int[] arr, int[][] pieces) {
    
        //  Define a hash table 
        HashMap<String, Boolean> map = new HashMap<>();
        int i = 0, j, n = arr.length;
        //  Convert all subsets in the two-dimensional array into strings and store them in the hash table 
        for(int[] item: pieces){
    
            String s = Integer.toString(item[0]);
            for(int k = 1; k < item.length; k++){
    
                s += Integer.toString(item[k]);
            }
            map.put(s, false);  //  By default value Set as false
        }
        while(i < n){
    
            String s = Integer.toString(arr[i]);
            //  If it is a single subset （ There's only one number ）
            if (map.containsKey(s)){
    
                map.put(s, true);
            }else{
    
                //  Is a subset of multiple numbers 
                for(j = i+1; j < n; j++){
    
                    s += Integer.toString(arr[j]);
                    if (map.containsKey(s)){
    
                        map.put(s, true);
                        i = j;
                        break;
                    }
                }
            }
            i++;
        }
        //  Traverse to see if there is still false Value 
        for (Boolean b: map.values()){
    
            if (!b) return false;
        }
        return true;
    }
}

Train of thought two ：

1. Traversing a one-dimensional array , Use one flag Identify the return result
2. Find an equal number from the second array , It must be arranged in order
3. according to flag Judge the result

class Solution {
    
    public boolean canFormArray(int[] arr, int[][] pieces) {
    
        int i = 0, j, k;
        boolean flag;
        while (i < arr.length){
    
            flag = false;
            for(j = 0; j < pieces.length; j++){
    
            //  If the first is not equal to arr[i] Then skip 
                if (pieces[j][0] != arr[i]){
    
                    continue;
                }
   //  First equals arr[i] when , Judge pieces[j] Whether the subset of and arr The next number corresponds to 
                for(k = 0; k < pieces[j].length; k++){
    
                    if (pieces[j][k] == arr[i]){
    
                        i++;
                        flag = true;
                    }else{
    
                        return false;
                    }
                }
                //  If at this time i The traversal is complete 
                if (i == arr.length){
    
                return true;
                }
            }
            if(!flag){
    
                return false;
            }
        }
        return true;
    }
}