8月算法训练------第一天（数组）解题报告

题目类型：数组
题目难度：简单
今天借用6月1号的题练手，因为之前6月1号没做过。

第一题、1588. 所有奇数长度子数组的和

1. 题目链接：1588. 所有奇数长度子数组的和

2. 思路分析：
   运用暴力破解，将所有情况都枚举出来，这就要用到三层for循环，第一层for循环控制奇数长度数组的长度，用第二层for循环控制在长度为i的情况下遍历数组的起止；用第三层for循环控制将遍历每个长度为i的数组的和。

3. 代码：

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int sum = 0;
        int len = arr.length;
        int a = (len % 2 == 0) ? (len - 1) : len;
        for(int i = 1; i <= a; i+=2){
            for(int j = 0; j <= len - i; j++){
                for(int k = j; k < j+i; k++){
                    sum += arr[k];
                }
            }
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第二题、1848. 到目标元素的最小距离

1. 题目链接：1848. 到目标元素的最小距离

2. 思路分析：
   将数组中与target相等的数的下标存入一个ArrayList中。
   然后遍历ArrayList，将其中与start差值绝对值最小的返回就行了。

3. 代码：

class Solution {
    public int getMinDistance(int[] nums, int target, int start) {
        List<Integer> index = new ArrayList();
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == target){
                index.add(i);
            }
        }
        int min = nums.length;
        for(int i = 0; i < index.size(); i++){
            min = Math.min(min, Math.abs(index.get(i) - start));
        }
        return min;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第三题、1652. 拆炸弹

1. 题目链接：1652. 拆炸弹
2. 思路分析：
   当k==0时，直接返回一个与code等长的全0数组；
   我们先将数组变长一倍：
   原数组：

变化后的数组：

用这样的方式来模拟循环数组；
当k>0时，将从前开始往后加，将第i位的后k位相加赋给res[i]；
当k<0时，将从后往前加，将第i位之前的k位相加赋给res[j]。
3. 代码：

class Solution {
    public int[] decrypt(int[] code, int k) {
        if(k == 0) return new int[code.length];
        int[] res = new int[code.length];
        List<Integer> tmp = new ArrayList();
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < code.length; j++){
                tmp.add(code[j]);
            }
        }
        int sum = 0;
        if(k > 0){
            for(int i = 0; i < code.length; i++){
                for(int j = i+1; j <= i+k; j++){
                    sum += tmp.get(j);
                }
                res[i] = sum;
                sum = 0;
            }
        }else{
            for(int i = tmp.size() - 1; i >= code.length; i--){
                for(int j = i - 1; j >= i+k; j--){
                    sum += tmp.get(j);
                }
                res[i - code.length] = sum;
                sum = 0;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

第四题、1640. 能否连接形成数组

1. 题目链接：1640. 能否连接形成数组

2. 代码：

class Solution {
    public boolean canFormArray(int[] arr, int[][] pieces) {
        int[]indexs=new int[101];
        Arrays.fill(indexs,-1);
        for (int i = 0; i < arr.length; i++) {
            indexs[arr[i]]=i;
        }
        for (int i = 0; i < pieces.length; i++) {
            //这里就分为两种情况讨论，
            //第一种，pieces[i].length>1，这种查看元素间的顺序是否严格对应arr的顺序
            if(pieces[i].length>1){ 
                for (int j = 1; j < pieces[i].length; j++) {
                    if(indexs[pieces[i][j]]==-1||indexs[pieces[i][j-1]]==-1){
                        return false;
                    }
                    if(indexs[pieces[i][j]]-indexs[pieces[i][j-1]]!=1){
                        return false;
                    }
                }
            }else {//第二种，pieces[i].length=1，这种查看元素是否存在arr中
                if(indexs[pieces[i][0]]==-1){
                    return false;
                }
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

剑指offer
题目类型：双指针
难度：简单

第五题、剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

1. 题目链接：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
2. 思路分析：
   这一题用双指针会非常简单：
   定义两个指针：l和r

• 当nums[l]为偶数且nums[r]为奇数时，将nums[l]和nums[r]交换，并使l++，r--；
• 当nums[l]为偶数且nums[r]为偶数时，只将r--；
• 当nums[l]为奇数且nums[r]为偶数时，已经满足题中所给要求，就将l++，r--；
• 当nums[l]为奇数且nums[r]为偶数时，只将l++。

要注意的是，这一题用的是位运算解题，所以要对位运算的写法有一定了解。
3. 代码：

class Solution {
    public int[] exchange(int[] nums) {
        int l = 0, r = nums.length - 1;
        while(l < r){
            if((nums[l] & 1) == 0 && (nums[r] & 1) == 1){ //l偶数,r奇数
                nums[l] = nums[l] ^ nums[r];
                nums[r] = nums[l] ^ nums[r];
                nums[l] = nums[l] ^ nums[r];
                l++;
                r--;
            }else if((nums[l] & 1) == 0 && (nums[r] & 1) == 0) {//l偶数，r偶数
                r--;
            }else if((nums[l] & 1) == 1 && (nums[r] & 1) == 0){ //l奇数，r偶数
                l++;
                r--;
            }else if((nums[l] & 1) == 1 && (nums[r] & 1) == 1){ //l奇数，r奇数
                l++;
            }
        }
        return nums;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

第六题、剑指 Offer 57. 和为s的两个数字

1. 题目链接：剑指 Offer 57. 和为s的两个数字
2. 思路分析：
   nums数组已经进行递增排序，我们不用再对其排序：
   运用双指针的思路：
   定义两个指针：左l和右r；
   从左右开始遍历这个数组：

• 当nums[l] + nums[r] > target时，说明需要将nums[l] + nums[r]变小，而对于左右指针而言，只有右指针左移，二者之和才会变小；
• 当nums[l] + nums[r] < target时，说明需要将nums[l] + nums[r]变大，而对于左右指针而言，只有左指针右移，二者之和才会变大；
• 当nums[l] + nums[r] == target时，这就是我们要找到的答案，就将这两个数返回。
• 当在数组中没找到这两个数时，就需要返回一个长度为0的数组。

3. 代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int[] res = new int[2];
        while(l < r){
            if(nums[l] + nums[r] > target){
                r--;
            }else if(nums[l] + nums[r] < target){
                l++;
            }else{
                res[0] = nums[l];
                res[1] = nums[r];
                return res;
            }
        }
        return new int[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第七题、剑指 Offer 58 - I. 翻转单词顺序

1. 题目链接：剑指 Offer 58 - I. 翻转单词顺序

2. 思路分析：
   现将字符串按" "进行分割，然后再声明一个StringBuilder变量，将字符串数组倒序加入到StringBuilder中，并且再每个加入单词后面添加一个空格。
   按这样加最后一个单词后面肯定会有一个空格，所以要将最后一个空格删去，方法是返回它的子串，开始是0，结束是res.length()-1。然后将StringBuilder用toString()方法将他转化为字符串。

3. 代码：

class Solution {
    public String reverseWords(String s) {
        String[] strArr = s.split(" ");
        StringBuilder res = new StringBuilder();
        for(int i = strArr.length - 1; i >= 0; i--){
            if(strArr[i] != ""){
                res.append(strArr[i]);
                res.append(" ");
            }
        }
        if(res.length() == 0){
            return "";
        }
        return res.substring(0, res.length()-1).toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16