leetcode刷题学习（9）

前言：考虑到本人是能力有限，算法题解只能示例一种本人能够理解和实现的方式，可能不是最优的。

 

一、随机数索引（题号：398）

    给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

    注意：数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);

// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);

 

    解题思路：蓄水池抽样算法，算法的概念很深奥，但是貌似用java实现起来好像很简单；把符合要求的数字单独存放在“蓄水池”中，然后使用随机算法采样。

public class TestMain {


    public static void main(String[] args) {
        int[] source = {1,2,3,3,3};
        System.out.println(execute(source,3));
    }

    public static int execute(int[] source,int target) {
        RandomIndex ri = new RandomIndex(source);
        return ri.pick(target);
    }

    /**
     * Random Pick Index
     * 随机数索引
     */
    public static class RandomIndex {

        private int[] source;
        Random random = new Random();

        public RandomIndex(int[] source) {
            this.source = source;
        }

        public int pick(int target) {
            List<Integer> list = new ArrayList();//蓄水池？
            for (int i = 0; i < source.length; i++) {
                if (source[i] == target) {
                    list.add(i);
                }
            }
            if (list.size() == 1) {
                return list.get(0);
            }
            int randomIndex = random.nextInt(list.size());
            return list.get(randomIndex);
        }
    }

}

 

二、移除K为数字（题号：402）

    给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

    注意:

    1）num 的长度小于 10002 且 ≥ k。

    2）num 不会包含任何前导零。

示例 1 :

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :

输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :

输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

 

    解题思路：既然需要输出的结果数字最小，我们只有保证数字的高位数字最小，因为是移除不是重排，所以剩余数字的顺序应该保持；保持顺序，我们首先想到的是使用队列或者栈。思路参考代码注释部分。

public class TestMain {


    public static void main(String[] args) {
        System.out.println(execute("1432219",3));
        //不能输出0200
        System.out.println(execute("10200",1));
        //不能输出空
        System.out.println(execute("10",2));
    }

    /**
     * 以1432219，k=3为例，如下过程为栈操作过程
     * 1、(1) -> 1
     * 2、(4) -> 1 4  因为4比1大，加入栈
     * 3、(3) -> 1 4 -> 1 [4] 因为3比4小，将四移除（3还不能加入栈，需要继续比较剩余栈元素）
     * 4、-> 1 -> 1 3   因为3比1大，加入栈
     * 5、(2) -> 1 3 -> 1 [3] 因为2比3小，移除3
     * 6、-> 1 -> 1 2  因为2比1大，加入栈
     * 7、(2) -> 1 2 -> 1 2 2 因为2不大于栈顶2，所以加入栈
     * 8、(1) -> 1 2 2 -> 1 2 [2] 因为1比栈顶2小，所以移除2
     * 9、-> 1 2 1 虽然1比当前栈顶2小，但是已经移除了3个元素，不能再移除，则直接入栈
     * 10、(9) -> 1 2 1 9，因为已经移除了足够多多元素，所以只能之际入栈。
     *
     * @param source
     * @param k
     * @return
     */
    public static String execute(String source, int k) {
        //用于保存剩余的数字，因为输出结果字面值为合法数字，所以结果多最大长度不会超过length - k
        //此外栈底还存在0的情况、已经栈中所有元素都是0，需要特殊对待
        int length = source.length() - k;
        if (length <= 0) {
            return "0";
        }
        char[] stack = new char[length];
        //当前栈顶的索引值，默认从空开始
        int top = -1;
        for (int i = 0; i < source.length(); i++) {
            char value = source.charAt(i);

            while (true) {
                //如果栈为空，则跳过，其实就是直接加入栈
                if(top < 0) {
                    break;
                }
                //如果栈顶的值不大于当前数字，或者已经移除了指个数的数字，直接跳过
                // （即直接将当前数字加入栈）
                if (stack[top] <= value || k == 0) {
                    break;
                }
                //如果栈顶的值，比当前数字大，且还没有移除足够个数的数字
                //则栈顶移除，直到找到不大于当前数字的栈元素为止
                //移除栈顶，也意味着移除一个数字，k--
                top--;
                k--;
            }
            stack[++top] = value;
        }
        int offset = 0;//移除栈底底'0'，直到遇到首个合法数字为止
        for(; offset < length; offset++) {
            if (stack[offset] != '0') {
                break;
            }
        }
        return new String(stack,offset,length - offset);
    }
}

 

三、分割等和子集（题号：416）

    给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

    注意:

    1）每个数组中的元素不会超过 100

    2）数组的大小不会超过 200

 

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

 

 

public class TestMain {

    public static void main(String[] args) {
        int[] source = {1,2,3};
        System.out.println(execute(source));
    }


    public static boolean execute(int[] source) {
        if(source.length == 0) {
            return false;
        }
        int sum = 0;
        for(int i : source){
            sum += i;
        }

        if(sum % 2 != 0) {
            return false;//集合总和为奇数
        }

        boolean[] dp = new boolean[sum+1];
        dp[0] = true;
        for (int j = 0; j < source.length; j++) {
            for (int k = sum; k >= 0 && k >= source[j]; k--) {
                dp[k] =  dp[k] || dp[k - source[j]];
            }
            if(dp[sum / 2]) {//存在某个子集的和sum / 2
                return true;
            }
        }
        return false;
    }
}

 

四、两数相加II（题号：445）

    给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。

    进阶:如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

   

    解题思路：将链表转换成栈，才能进行从低位到高位的计算，同时需要注意满10进位，因为结果链表需要在字面上是个数字。

public class TestMain {

    public static void main(String[] args) {
        ListNode r1 = new ListNode(7);
        ListNode l1n1 = new ListNode(2);
        ListNode l1n2 = new ListNode(4);
        ListNode l1n3 = new ListNode(3);
        r1.next = l1n1;
        l1n1.next = l1n2;
        l1n2.next = l1n3;

        ListNode r2 = new ListNode(5);
        ListNode l2n1 = new ListNode(6);
        ListNode l2n2 = new ListNode(4);

        r2.next = l2n1;
        l2n1.next = l2n2;

        ListNode result = execute(r1,r2);
        System.out.println(result);
    }

    /**
     * 主要思路就是使用栈
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode execute(ListNode l1,ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        ListNode h1 = l1;
        while (h1 != null) {
            s1.push(h1.value);
            h1 = h1.next;
        }
        ListNode h2 = l2;
        while (h2 != null) {
            s2.push(h2.value);
            h2 = h2.next;
        }
        ListNode result = null;
        int mark = 0;
        while (true) {
            if (s1.isEmpty() && s2.isEmpty()) {
                break;
            }
            
            ListNode current = new ListNode(mark);
            if (!s1.isEmpty()) {
                current.value += s1.pop();
            }
            if (!s2.isEmpty()) {
                current.value += s2.pop();
            }
            //对于计算值超过10的，进行一次进位
            mark = current.value / 10;
            current.value %= 10;

            current.next = result;
            result = current;
        }

        return result;
    }

    public static class ListNode {
        private int value;
        private ListNode next;

        public ListNode(int value) {
            this.value = value;
        }

        public boolean hasNext() {
            return next != null;
        }
    }

}

  

五、序列化和反序列化二叉搜索树（题号：449）

    序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

    设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

    编码的字符串应尽可能紧凑。

 

    注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。

 

    解题思路：二叉搜索树BST，特点是有序，为了便于确定根节点，所以序列化时采用前序遍历（首个元素为根节点）可以更易于确定根节点；在反序列化时，一旦确定了根节点，BST的树结构基本可以确定，因为前序遍历的结果，是“所有的右子树节点元素均在左子树元素之后”，所以反序列化时，首先构建完毕左子树，然后是右子树，不会出现结构不一致问题。

 

public class TestMain {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode t1 = new TreeNode(3);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(4);
        t1.left = t2;
        t1.right = t3;

        TreeNode t4 = new TreeNode(8);
        TreeNode t5 = new TreeNode(6);
        TreeNode t6 = new TreeNode(9);
        TreeNode t7 = new TreeNode(10);
        t4.left = t5;
        t4.right = t6;
        t6.right = t7;

        root.left = t1;
        root.right = t4;

        String ds = serialize(root);
        System.out.println(ds);
        TreeNode dds = deserialize(ds);
        System.out.println(dds);
    }

    public static String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder();
        return serialize(root, stringBuilder);
    }

    public static TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] values = data.split(" ");
        return deserialize(values);
    }

    /**
     * 针对BST:
     * 前序遍历，主要特点，是首个元素就是跟节点，这对保持树的结构原型很重要。
     * 此外，前序遍历的特点很明显，[跟节点元素][所有左子树元素][所有右子树元素]
     * 后续遍历，刚好相反。
     *
     * @param root
     * @param stringBuilder
     * @return
     */
    private static String serialize(TreeNode root, StringBuilder stringBuilder) {
        if (root == null) {
            return null;
        }
        stringBuilder.append(root.value).append(" ");
        serialize(root.left, stringBuilder);
        serialize(root.right, stringBuilder);
        return stringBuilder.toString();
    }


    /**
     * 本文基于前序遍历的结果，进行反序列化。所有，数组应该正序遍历；
     * 如果基于后序遍历进行反序列化，需要倒序遍历数组。
     * @param values
     * @return
     */
    private static TreeNode deserialize(String[] values) {
        TreeNode root = new TreeNode(Integer.valueOf(values[0]));
        for (int i = 1; i < values.length; i++) {
            insert(root,Integer.valueOf(values[i]));
        }
        return root;
    }

    /**
     * BST，本身有序，规则明确，所以，我们简化设计，使用insert机制构建树；
     * 不支持子树反转。
     * 暂定此算法只对反序列化方式有意义。
     * @param root
     * @param value
     */
    private static void insert(TreeNode root,int value) {
        if (root.value > value) {
            if (root.left == null) {
                root.left = new TreeNode(value);
            } else {
                insert(root.left, value);
            }
        } else {
            if (root.right == null) {
                root.right = new TreeNode(value);
            } else {
                insert(root.right, value);
            }
        }
    }

    /**
     * BST
     */
    public static class TreeNode {
        TreeNode left;
        TreeNode right;
        int value;

        public TreeNode(int value) {
            this.value = value;
        }
    }
}

 

六、删除二叉搜索树中的节点（题号：450）

    给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。一般来说，删除节点可分为两个步骤：

    1）首先找到需要删除的节点；

    2）如果找到了，删除它。

    说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

 

示例:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

 

    解题思路：找到待删除的节点，然后从此节点的右子树中找到最小值，替换掉此节点的值；然后在右子树中删除那个最小值节点；这种操作简单/易于实现，当删除根节点时，也是可控的；而且结果树仍然符合BST的要求；通常这个最小值位于右子树的最左侧叶子节点。

public class TestMain {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode l1 = new TreeNode(3);
        TreeNode l2 = new TreeNode(2);
        TreeNode l3 = new TreeNode(4);
        TreeNode l4 = new TreeNode(-1);
        TreeNode l5 = new TreeNode(1);
        l1.left = l2;
        l1.right = l3;
        l2.left = l4;
        l2.right = l5;

        TreeNode r1 = new TreeNode(6);
        TreeNode r2 = new TreeNode(7);

        r1.right = r2;

        root.left = l1;
        root.right = r1;

        deleteNode(root,3);
        System.out.println(root);
    }

    /**
     *         5
     *        /  \
     *      3     6
     *     / \     \
     *    2   4     7
     *   / \
     *  a  b
     * 删除节点，假如删除3，两种思路：
     * 1）将4节点以及起子树，直接移到3的位置，作为5的左节点；然后将2以及其子树作为4的左子树。
     * 2）不直接删除3，而是从3的右子树中找到最小的值节点，并将其值交换，此时子树为
     *        4
     *       / \
     *      2  (4)
     *     / \
     *    a   b
     *  然后在4的右子树中，删除(4),删除方式递归此方法。
     *
     *  这两种方法，其中1）比较直观，易于考虑和设计，但是需要记录待删除节点的父节点。当考虑到删除到节点是父节点时，设计就显得冗杂。
     *  2）面临各种场景比较容易适配，比如删除跟节点也不需要特殊的判断。
     * 而是将右子树重新调整---递归交换删除。
     * @param root 需要判断的绩点
     * @param key 删除节点的值
     * @return
     */
    public static TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return root;
        }
        //如果当前节点值，比key大，说明key位于此节点大左子树上
        if (root.value > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.value < key) {
            //待删除节点位于右子树
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            //如果此节点存在左右子节点
            //我们需要在右子树中找到最小值，并替换当前节点值（保持BST到合法性）
            //最小值一定位于此节点右子树到最左侧。（此最小值也比当前节点左子树到所有元素都大，所以BST仍然合法）
            TreeNode minNode = findMin(root.right);
            root.value = minNode.value;
            //删除最小值，此值位于右子树到最左侧，其左右子节点均为null，可以直接删掉
            root.right = deleteNode(root.right, root.value);
        }
        return root;
    }


    //获取指定节点的最小值节点，即最后一个左节点
    //位于此节点的左子树上
    private static TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * BST
     */
    public static class TreeNode {
        TreeNode left;
        TreeNode right;
        int value;

        public TreeNode(int value) {
            this.value = value;
        }
    }


}

 

七、132模式（题号：456）

    给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。

    注意：n 的值小于15000。

    说明：特别注意132特点，ai < ak < aj，且 i < j < k，即在数组中：1）ak出现在最后，2）ai值最小，ak次之，aj最大 3）ai、aj、ak并非连续相邻的元素

示例1:

输入: [1, 2, 3, 4]

输出: False

解释: 序列中不存在132模式的子序列。
示例 2:

输入: [3, 1, 4, 2]

输出: True

解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
示例 3:

输入: [-1, 3, 2, 0]

输出: True

解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

 

    解题思路：倒序遍历数组，确定“ak与aj”，因为这俩是升序关系。

public class TestMain {


    public static void main(String[] args) {
        int[] source = new int[]{-1, 3, 2, 0};
        System.out.println(execute(source));
    }

    /**
     * 132
     * s1最小 s3最大 s2次大
     * 如下例子中，之所以采用倒序遍历，就是维持最大、次大的顺序关系，因为"最小"不好判断。
     *
     * @param source 原始数组
     * @return
     */
    public static boolean execute(int[] source) {
        //保存最大值3
        Stack<Integer> s3 = new Stack<>();

        int s2 = Integer.MIN_VALUE;//历史最大值，即"次大"
        //倒序遍历
        for (int i = source.length - 1; i >= 0; i--) {
            //如果遇到比"次大"要小的s1
            if (source[i] < s2) {
                return true;
            } else {
                //如果遇到s3，则将s2保存在栈中，并同时计算s2
                //即s3与s2需要同时调整
                while (!s3.isEmpty() && source[i] > s3.peek()) {
                    s2 = Math.max(s2, s3.pop());
                    //清空栈
                }
            }
            s3.push(source[i]);//
        }

        return false;
    }

}

 

八、重复的子字符串（题号：459）

    给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。
示例 2:

输入: "aba"

输出: False
示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

 

    解题思路：非常佩服奇才的思路，就是将原始字符串s，拼接成ss，并将ss的首尾移除一个字符，如果在剩余字符串中还能找到s，则为true。思想类似于数据处理的“滑动窗口”。

public class TestMain {


    public static void main(String[] args) {
        String source = "abcabc";
        System.out.println(execute(source));
    }

    public static boolean execute(String source) {
        return (source + source).substring(1,source.length() * 2 -1).indexOf(source) != -1;
    }


}

 

九、LFU缓存（题号：460）

    设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。

    1）get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。

    2）put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。

 

    进阶：你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

 

public class TestMain {

    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.put("1", 1);
        cache.put("2", 2);
        System.out.println(cache.get("1"));       // 返回 1
        cache.put("3", 3);    // 去除 key 2
        System.out.println(cache.get("2"));       // 返回 -1 (未找到key 2)
        System.out.println(cache.get("3"));       // 返回 3
        cache.put("4", 4);    // 去除 key 1
        System.out.println(cache.get("1"));       // 返回 -1 (未找到 key 1)
        System.out.println(cache.get("3"));       // 返回 3
        System.out.println(cache.get("4"));       // 返回 4
    }

    /**
     * 最近最少使用
     * 如果容量不足，应该将最近使用次数最少到key移除，如果使用次数最少到key有多个，那么优先移除最早加入到key。
     */
    public static class LFUCache {

        //主要容器，用于保存k-v
        private Map<String, Object> keyToValue = new HashMap<>();
        //记录每个k被访问的次数
        private Map<String, Integer> keyToCount = new HashMap<>();
        //访问相同次数的key列表，按照访问次数排序，value为相同访问次数到key列表。
        private TreeMap<Integer, LinkedHashSet<String>> countToLRUKeys = new TreeMap<>();

        private int capacity;

        public LFUCache(int capacity) {
            this.capacity = capacity;
            //初始化，默认访问1次，主要是解决下文
        }

        public Object get(String key) {
            if (!keyToValue.containsKey(key)) {
                return null;
            }

            touch(key);
            return keyToValue.get(key);
        }

        /**
         * 如果一个key被访问，应该将其访问次数调整。
         * @param key
         */
        private void touch(String key) {
            int count = keyToCount.get(key);
            keyToCount.put(key, count + 1);//访问次数增加
            //从原有访问次数统计列表中移除
            countToLRUKeys.get(count).remove(key);

            //如果符合最少调用次数到key统计列表为空，则移除此调用次数到统计
            if (countToLRUKeys.get(count).size() == 0) {
                countToLRUKeys.remove(count);
            }

            //然后将此key的统计信息加入到管理列表中
            LinkedHashSet<String> countKeys = countToLRUKeys.get(count + 1);
            if (countKeys == null) {
                countKeys = new LinkedHashSet<>();
                countToLRUKeys.put(count + 1,countKeys);
            }
            countKeys.add(key);
        }

        public void put(String key, Object value) {
            if (capacity <= 0) {
                return;
            }

            if (keyToValue.containsKey(key)) {
                keyToValue.put(key, value);
                touch(key);
                return;
            }
            //容量超额之后，移除访问次数最少到元素
            if (keyToValue.size() >= capacity) {
                Map.Entry<Integer,LinkedHashSet<String>> entry = countToLRUKeys.firstEntry();
                Iterator<String> it = entry.getValue().iterator();
                String evictKey = it.next();
                it.remove();
                if (!it.hasNext()) {
                    countToLRUKeys.remove(entry.getKey());
                }
                keyToCount.remove(evictKey);
                keyToValue.remove(evictKey);

            }

            keyToValue.put(key, value);
            keyToCount.put(key, 1);
            LinkedHashSet<String> keys = countToLRUKeys.get(1);
            if (keys == null) {
                keys = new LinkedHashSet<>();
                countToLRUKeys.put(1,keys);
            }
            keys.add(key);
        }
    }
}

 

十、目标和（题号：494）

    给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释: 

-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 = 3

一共有5种方法让最终目标和为3。

 

    解题思路：动态规划，每个元素都可以有“正”/“负”两个状态值。

public class TestMain {

    public static void main(String[] args) {
        int[] source = {1,1,1,1,1};
        System.out.println(execute(source,3));
    }

    public static int execute(int[] source, int target) {
        return find(0, source, target);
    }

    /**
     *
     * @param i 开始索引
     * @param source 原始数组
     * @param target 累加和，剩余
     * @return
     */
    private static int find(int i, int[] source, int target) {
        //所有元素都需要参与计算
        //如果数组遍历完毕，结果值刚好为target，则符合要求
        if (i == source.length) {
            if (target == 0) {
                return 1;
            } else {
                return 0;
            }
        }
        int value = source[i];
        //加、减，分别计算一次
        int c1 =  find(i + 1, source, target + value);
        int c2 = find(i + 1, source, target - value);
        return c1 + c2;
    }
}