`
QING____
  • 浏览: 2251324 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

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;
    }
}

 

分享到:
评论

相关推荐

    如何正确刷题?LeetCode刷题误区和刷题方法论分享【LeetCode刷题套路教程1】

    如何正确刷题?LeetCode刷题误区和刷题方法论分享【LeetCode刷题套路教程1】

    LeetCode刷题笔记.rar

    《LeetCode刷题笔记》是针对LeetCode这个在线编程挑战平台的个人学习心得与总结,主要涵盖数据结构和算法两大核心领域。LeetCode是一个全球知名的编程训练网站,它提供了丰富的编程题目,帮助开发者提升编程技能,...

    LeetCode 刷题笔记 with Java.zip

    《LeetCode刷题笔记withJava》是一份专为Java开发者准备的算法实战指南,涵盖了LeetCode网站上前一百道编程挑战题目。这份资料旨在帮助程序员提升算法能力,掌握数据结构和问题解决技巧,对于准备面试或者想要提升...

    leetcode刷题班题库

    总的来说,《leetcode刷题班题库》是一份全面而深入的学习资料,它不仅提供了大量的编程题目,更关键的是,它提供了详细的解题过程,帮助学习者逐步建立解决问题的能力。通过系统地学习和实践,你将能够在算法和数据...

    Backtracking回溯解题套路【LeetCode刷题套路教程18】

    Backtracking回溯解题套路【LeetCode刷题套路教程18】

    Heap堆解题套路【LeetCode刷题套路教程6】

    Heap堆解题套路【LeetCode刷题套路教程6】

    谷歌和阿里大佬的Leetcode刷题笔记.zip

    《谷歌和阿里大佬Leetcode刷题笔记》是一个珍贵的学习资源,专为提升算法能力和准备面试设计。LeetCode是一个在线平台,提供了大量的编程题目,旨在帮助程序员提升算法技能,特别是对于那些希望进入顶级科技公司如...

    leetcode刷题,C++刷题技巧

    《LeetCode刷题,C++刷题技巧》是一本针对有C++编程基础,希望通过LeetCode平台提升算法和数据结构能力的读者所编写的指南。作者高畅在准备实习秋招的过程中,积累了大量的LeetCode刷题经验,并在书中分享了这些宝贵...

    C++ LeetCode刷题班.zip

    在本课程中,"C++ LeetCode刷题班.zip",我们的目标是深入学习和实践C++编程语言,特别是聚焦于数据结构与算法的应用,这对于准备面试,尤其是BAT(百度、阿里巴巴、腾讯)等知名互联网公司的面试至关重要。...

    谷歌高畅Leetcode刷题笔记.pdf

    这本书名为《LeetCode101:和你一起你轻松刷题(C++)》的电子书,作者高畅ChangGao,旨在帮助有C++基础但缺乏刷题经验的读者。本文将详细阐述该电子书中提及的IT知识点,覆盖算法与数据结构两大板块,以及十五个...

    基于java的leetcode刷题与复习指南算法模板代码

    这个基于Java的LeetCode刷题与复习指南算法模板代码集合,将为学习者提供宝贵的资源和起点。 首先,让我们深入理解Java在LeetCode中的应用。Java是一种广泛使用的面向对象的编程语言,其语法清晰,性能优秀,特别...

    LeetCode刷题题解.rar

    《LeetCode刷题题解》是一份集合了多个资源的压缩包,主要目的是帮助学习者在准备面试或者提升编程技能时,通过解决LeetCode上的问题来加深对算法和数据结构的理解。LeetCode是一个在线的编程挑战平台,它包含了各种...

    基于Java语言的LeetCode刷题算法设计与实现源码分享

    该项目为Java语言编写的LeetCode刷题算法设计与实现源码,包含187个文件,其中181个为Java源文件,3个为YAML配置文件,1个为Git忽略文件,以及1个LICENSE...该源码旨在记录LeetCode刷题过程,为算法学习提供辅助工具。

    Stack堆栈解题套路【LeetCode刷题套路教程5】

    Stack堆栈解题套路【LeetCode刷题套路教程5】

    哈希表HashMap解题套路【LeetCode刷题套路教程7】

    哈希表HashMap解题套路【LeetCode刷题套路教程7】

    基于代码随想录的LeetCode刷题攻略200题学习源码包

    该项目为《代码随想录》LeetCode 刷题攻略的200题学习源码包,涵盖286个Markdown文件、6个PNG图片文件和2个JPG图片文件,共计295个文件。内容丰富,包括60万字的详细图解、视频难点剖析和50余张思维导图,支持C++、...

    Leetcode刷题笔记.zip

    在这个“Leetcode刷题笔记.zip”压缩包中,我们可以期待找到作者在解决LeetCode题目过程中积累的珍贵心得和解题策略。这份笔记可能涵盖了多种算法和数据结构的应用,对于学习和提升编程能力,特别是准备技术面试的...

    leetcode刷题LeetCode1500道单词接龙Python3

    【标题】"leetcode刷题LeetCode1500道单词接龙Python3"涉及的是一个在编程学习领域常见的挑战——通过解决LeetCode平台上的问题来提升技能,特别是使用Python3语言进行实现。LeetCode是一个在线的算法练习平台,提供...

    DynamicProgramming2D解题套路【LeetCode刷题套路教程15】

    DynamicProgramming2D解题套路【LeetCode刷题套路教程15】

    谷歌高畅、BAT霜神leetcode刷题笔记.zip

    【标题】:“谷歌高畅、BAT霜神leetcode刷题笔记.zip”是一份压缩包文件,包含两位业内专家——“谷歌高畅”和“BAT霜神”的LeetCode刷题笔记。LeetCode是一个广受欢迎的在线平台,它提供了各种编程挑战题目,帮助...

Global site tag (gtag.js) - Google Analytics