栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

六月刷题01——数组

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

六月刷题01——数组

六月刷题01——数组
    • 前言
    • 一、今日题目
    • 二、解题思路
      • 1. 1588. 所有奇数长度子数组的和
      • 2. 1848. 到目标元素的最小距离
      • 3. 1652. 拆炸弹
      • 4. 1640. 能否连接形成数组

今日刷题内容: 数组

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

一、今日题目
  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 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;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/944552.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号