This is the 7th day of my participation in the Gwen Challenge

LeetCode one problem of the Day

Link: leetcode-cn.com/problems/ta…

Tags: Dynamic programming, depth first search, breadth first search

The title

You are given an integer array nums and an integer target.

We can construct an expression by adding a ‘+’ or a ‘-‘ to each integer in the array and then concatenating all integers:

For example, nums = [2, 1], you can add ‘+’ before 2, ‘-‘ before 1, and then concatenate the expression “+2-1”. Returns the number of different expressions equal to target that can be constructed using the above method.

Enter: nums = [1.1.1.1.1], target = 3Output:5Explanation: All in all5A way to make the end goal and for3. -1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3Enter: nums = [1], target = 1Output:1
    
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 100
Copy the code

Analysis of the

(1) this problem I think should use BFS also can do, I didn’t expect the 71th / 138 cases when they hang up, really didn’t know where there can be optimized (duplicate values can need not record in the process of calculation, avoid repeating calculation, but need to write down several times), but there are using the queue data structure, unable to record the number of occurrences of, but to give up.

Change the map unexpectedly can pass, take. Different data structures are used, but the idea is the same as BFS. The queue is that after each layer is used, the elements will be cleared, and new elements will be stored, but the insertion and deletion time; A map stores the results of each layer of an element, but is relatively time saving.

(2) Use DFS

(3) It is transformed into 01 knapsack problem and solved by DP

coding

BFS uses the queue timeout version

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int len = nums.length, res = 0;
        if (len == 1) {
            if (nums[0] == target) {
                res++;
            }
            if (-nums[0] == target) {
                res++;
            }
            return res;
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(nums[0]);
        queue.offer(-nums[0]);
        int count = 1;

        while(count < len) {
            int size = queue.size();
            int index = 0;
            while (index++ < size) {
                Integer value = queue.poll();
                // The last number is not stored in the queue
                if (count == len - 1) {
                    if (value + nums[count] == target) {
                        res++;
                    }

                    if(value - nums[count] == target) { res++; }}else {
                    queue.offer(value + nums[count]);
                    queue.offer(value - nums[count]);
                }
            }
            count++;
        }

        returnres; }}Copy the code

BFS using the Map

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int len = nums.length;
        Map<Integer, Integer>[] maps = new Map[len];
        for (int i = 0; i < len; i++) {
            // maps[I]key stores the computed value. Value stores the computed value
            maps[i] = new HashMap<>();
        }
        maps[0].put(nums[0].1);
        maps[0].put(-nums[0], maps[0].getOrDefault(-nums[0].0) + 1);

        for (int i = 1; i < len; i++) {
            Set<Map.Entry<Integer, Integer>> entries = maps[i - 1].entrySet();
            for (Map.Entry<Integer, Integer> entry : entries) {
                Integer key = entry.getKey();
                Integer value = entry.getValue();
                maps[i].put(key + nums[i], maps[i].getOrDefault(key + nums[i], 0) + value);
                maps[i].put(key - nums[i], maps[i].getOrDefault(key - nums[i], 0) + value); }}return maps[len - 1].getOrDefault(target, 0); }}Copy the code

DFS:

class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int target) {
        dfs(nums, target, 0);
        return count;
    }

    private void dfs(int[] nums, int target, int index) {
        if (index == nums.length) {
           count += (target == 0 ? 1 : 0);
           return;
        }

        dfs(nums, target + nums[index], index + 1);
        dfs(nums, target - nums[index], index + 1); }}Copy the code

DFS + memorized search

class Solution {
    Map<String, Integer> map = new HashMap<>();
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, target, 0);
    }

    private int dfs(int[] nums, int target, int index) {
        String key = index + "_" + target;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        if (index == nums.length) {
           map.put(key, target == 0 ? 1 : 0);
           return map.get(key);
        }

        int left = dfs(nums, target + nums[index], index + 1);
        int right = dfs(nums, target - nums[index], index + 1);
        map.put(key, left + right);
        returnmap.get(key); }}Copy the code