494. Objectives and (medium)

This is the third day of my participation in Gwen Challenge

Topic describes

Source: LeetCode

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

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.

Example 1:

Enter: nums = [1,1,1,1,1], target = 3

Output: 5

Explanation: There are 5 ways to make the final goal sum 3.

Minus 1 plus 1 plus 1 plus 1 plus 1 is 3

+1-1 +1 +1 +1 = 3

+1 +1-1 +1 +1 = 3

+1 +1 +1-1 +1 = 3

+1 +1 +1 + 1-1 = 3

Example 2:

Enter: nums = [1], target = 1

Output: 1.

Tip:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 100

title

Build a binary tree

Suppose we have a numS array {1, 2, 3}, and all of its possibilities are 23 and there are eight possibilities: +1+2+3, +1+2+3, +1-2+3, +1-2-3, all the way to -1-2-3,

I can construct a binary tree where the path from the root to each leaf represents one of the cases, so for example the first leaf is +3, and all the nodes between root 0 and leaf +3 are 0,+1,+2,+3, and it represents one of the eight cases +1+2+3. So all the possibilities are represented through a binary tree

The binary tree on the right is the result of the calculation, again for 0,+1,+2,+3, the root node is 0, the next node used to be +1, plus the previous node 0+1 is 1, the next node used to be +2, plus the previous node 1+2 is 3, and finally it used to be +3, plus the previous node 3+3 is 6

So the leaves in the binary tree on the right are the calculated values for each case, and you can compare each value to target

public class Solution {
  public int findTargetSumWays(int[] nums, int target) {
    int result = 0;
    int len = nums.length;
      SumLen is the number of nodes in the binary tree
    int sumLen = (int) Math.pow(2, len + 1) - 1;
    int[] sum = new int[sumLen];
    for (int i = 0; i < len; i++) {
        // j represents the subscript of the first node in each row of the binary tree
      int j = (int) (Math.pow(2, i + 1) - 1);
        // k represents the index of the last node in each row of the binary tree
      int k = 2 * j;
      for (; j <= k; j++) {
          // The left child is equal to the parent plus the current element
        if (j % 2= =1) {
          sum[j] = sum[j / 2] + nums[i];
        } else {
            // Right child is equal to parent minus current element
          sum[j] = sum[j / 2 - 1] - nums[i];
        }
        if(i == len -1&& sum[j] == target){ result++; }}}returnresult; }}Copy the code

conclusion

The method of building a binary tree is not very good, equivalent to a violent method, and the values of j and K variables in the code are easy to see by looking for rules

Let me summarize some of the properties of binary trees

  • A full binary tree, in which the number of nodes at each level reaches its maximum, is shown in the figure above. The number of layers is N, the total number of nodes is 2n-1, and the number of nodes on the KTH layer is 2K-1.
  • A complete binary tree has a maximum number of nodes at every level except the last one
  • So if YOU store binary trees in one-dimensional arrays,nums[i]The child to the left isnums[2*i+1]The child on the right isnums[2*i+2]. In the same way,nums[i]If it’s the left node, its parent isnums[i/2].nums[i]If it’s the right node, its parent node isnums[i/2-1]