Offer II 102+LC667+1306+2321

加减的目标值

给定一个正整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

分析：

首先想到用回溯，列出所有情况找出结果为target的个数，但时间效率较低。

class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        backtrack(nums, 0, target , 0);
        return count;
    }
    public void backtrack(int[] nums, int index, int target, int sum){
        if (index == nums.length){
            if (sum == target) count++;
            return;
        }
        backtrack(nums, index+1, target, sum+nums[index]);
        backtrack(nums, index+1, target, sum-nums[index]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

第二种方法是动态规划。设数组中取正号的数字之和为sum1，取符号的数字之和为sum2，数组值和为sum，则有sum1-sum2=(sum-sum2)-sum2=target，即$sum2=\frac{sum-target}{2}$。由于数组nums 中的元素都是非负整数，sum2 也必须是非负整数，所以上式成立的前提是sum−target 是非负偶数。若不符合该条件可直接返回 0。
于是定义二维数组dp，$dp[i][j]$表示nums[0:i]中取若干数字之和能否等于j。初始化：$dp[0][0]=1,dp[0][j]=0，1<=j<=\frac{sum-target}{2}$。开始遍历$1<=i<=n,1<=j<=\frac{sum-target}{2}$, 令num=nums[i]：

• 如果j$dp[i][j]=dp[i-1][j]$;
• 如果j>=num，$dp[i][j]=dp[i-1][j]+dp[i-1][j-num]$

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
}
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

优美的排列 II

给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：

• 假设该列表是 answer = [a1, a2, a3, … , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|] 中应该有且仅有 k 个不同整数。

返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。

分析：

想要找到有k个不同整数的序列，设列表的数字最大为n，则k的取值范围是[1,n-1]。构造任意k的序列，可以将序列分为两部分：
在构造前边的摆动序列时，先摆放前k个数字，表示不同的k-1个整数，然后摆放再后边|ak-1 - ak| = 1的序列。前k个数字采用一大一小排列，后边的序列采用：

• 当k等于偶数时，后边|ak-1 - ak| = 1的序列一定是降序序列。
• 当k等于奇数时，后边|ak-1 - ak| = 1的序列一定是升序序列。

class Solution {
    public int[] constructArray(int n, int k) {
        int[] ans = new int[n];
        int i = 0;
        //p从小到大 q从大到小
        int p = 1, q = n;
        //构造前k个数组 k-1个不同的整数
        //奇数位从大到小，偶数位从小到大
        for (int j = 0; j < k; j++) {
            if (j % 2 == 0) {
                ans[i++] = p++;
            } else {
                ans[i++] = q--;
            }
        }
        //构造剩下的绝对值为1的序列
        if (k % 2 == 0) {
            //偶数时，降序
            while (i < n) {
                ans[i++] = q--;
            }
        } else {
            //奇数时，升序
            while (i < n) {
                ans[i++] = p++;
            }
        }
        return ans;
    }
}
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

跳跃游戏 III

这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。

注意，不管是什么情况下，你都无法跳到数组之外。

分析：

采用dfs。首先定义一个visited数组来记录当前访问的节点有没有被访问过，当前搜索的arr[start]==0，则返回true，如果start<0或者start>=arr.length或者visited[start]=true则直接返回false。如果以上情况都不是则递归去访问start+arr[start]和start-arr[start]。

class Solution {
    public boolean canReach(int[] arr, int start) {
        boolean[] visited = new boolean[arr.length];
        return dfs(arr,start,visited);
    }
    boolean dfs(int[] arr, int start, boolean[] v){
        if (start>=arr.length || start<0) return false;
        if (v[start]) return false;
        v[start] = true;
        if (arr[start] == 0) return true;
        return dfs(arr, start+arr[start],v) || dfs(arr, start-arr[start],v);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

拼接数组的最大分数

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，长度都是 n 。

你可以选择两个整数 left 和 right ，其中 0 <= left <= right < n ，接着 交换 两个子数组 nums1[left…right] 和 nums2[left…right] 。

• 例如，设 nums1 = [1,2,3,4,5] 和 nums2 = [11,12,13,14,15] ，整数选择 left = 1 和 right = 2，那么 nums1 会变为 [1,12,13,4,5] 而 nums2 会变为 [11,2,3,14,15] 。

你可以选择执行上述操作 一次 或不执行任何操作。

数组的 分数 取 sum(nums1) 和 sum(nums2) 中的最大值，其中 sum(arr) 是数组 arr 中所有元素之和。

返回 可能的最大分数 。

子数组 是数组中连续的一个元素序列。arr[left…right] 表示子数组包含 nums 中下标 left 和 right 之间的元素（含 下标 left 和 right 对应元素）。

分析：

令s1=sum(nums1)，则交换之后的和s = s1-(nums1[left]+…+nums1[right])+(num2[left]+…+nums2[right])，整理得s=s1+(nums2[i]-nums1[i])，left<=i<=right。令differ[i]=nums2[i]-nums1[i]，只需求出最大的differ[left]+…+differ[right]即可。

class Solution {
    public int maximumsSplicedArray(int[] nums1, int[] nums2) {
        return Math.max(helper(nums1, nums2),helper(nums2, nums1));
    }
    public int helper(int[] nums1, int[] nums2){
        int maxAdd = 0,sum = 0;
        for (int i = 0, add = 0; i < nums1.length; i++) {
            sum += nums1[i];
            add = Math.max(add+nums2[i]-nums1[i], 0);
            maxAdd = Math.max(maxAdd, add);
        }
        return sum + maxAdd;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14