六月刷题01——数组

今日刷题内容： 数组

前言

• 更新每天刷题的题解内容
• 注重个人理解，看难度更新题目数量
• 题目来源于力扣
• 争取每日都能做出至少一题
• 语言java、python、c\c++

---

一、今日题目

1. 1588. 所有奇数长度子数组的和
2. 1848. 到目标元素的最小距离
3. 1652. 拆炸弹
4. 1640. 能否连接形成数组

二、解题思路

1. 1588. 所有奇数长度子数组的和

1. 要求所有奇数子序列的和
2. 即从每个元素开始遍历，为奇数个元素时将当前元素和加到结果中
3. 返回结果即可

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. 到目标元素的最小距离

1. 找到该元素所在下标，维护一个最小值即可

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. 拆炸弹

1. 根据k的值有三种情况，为了便于理解，直接将三种情况标明
2. 如果k为0返回全0即可
3. 如果k大于或小于0，分两种情况讨论，这里展开大于0的
   1. 如果i+k大于数组最右边下标，会回到数组起始开始算的第i + k - n个位置
   2. 如果小于数组最右边下标，则直接相加即可
4. 小于0的情况也是一样

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. 能否连接形成数组

这题有两种思路
思路一
第一种是用哈希表的方式

1, 将二维数组中所有的子集转化为字符串作为key存入哈希表中，默认value为false
2. 遍历一维数组，如果当前数存在于哈希表的key中，则将value置为true
3. 按顺序拼接当前数字，判断是否存在于key中，如果存在则重复步骤2

class Solution {
    
    public boolean canFormArray(int[] arr, int[][] pieces) {
    
        // 定义一个哈希表
        HashMap<String, Boolean> map = new HashMap<>();
        int i = 0, j, n = arr.length;
        // 将二维数组中的所有子集转化为字符串存入哈希表中
        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);  // 默认将value置为false
        }
        while(i < n){
    
            String s = Integer.toString(arr[i]);
            // 如果是个单子集（只有一个数字）
            if (map.containsKey(s)){
    
                map.put(s, true);
            }else{
    
                // 是多个数字的子集
                for(j = i+1; j < n; j++){
    
                    s += Integer.toString(arr[j]);
                    if (map.containsKey(s)){
    
                        map.put(s, true);
                        i = j;
                        break;
                    }
                }
            }
            i++;
        }
        // 遍历查看是否还有为false的值
        for (Boolean b: map.values()){
    
            if (!b) return false;
        }
        return true;
    }
}

思路二：

1. 遍历一维数组，用一个flag标识返回结果
2. 从第二个数组中找相等的数，一定会按照顺序来排列
3. 根据flag判断结果即可

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++){
    
            // 如果首位不等于arr[i]则跳过
                if (pieces[j][0] != arr[i]){
    
                    continue;
                }
   // 首位等于arr[i]时，判断pieces[j]的子集是否和arr接下来的数对应
                for(k = 0; k < pieces[j].length; k++){
    
                    if (pieces[j][k] == arr[i]){
    
                        i++;
                        flag = true;
                    }else{
    
                        return false;
                    }
                }
                // 如果此时i已经遍历完成
                if (i == arr.length){
    
                return true;
                }
            }
            if(!flag){
    
                return false;
            }
        }
        return true;
    }
}