- 浏览: 130516 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 2
Input: "2*3-4*5"
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]
[分析] 这题参考https://leetcode.com/discuss/48488/c-4ms-recursive-method 。 思路类似Unique Binary Search Trees II,以某个运算符为分界线,递归计算左右两边可能的值,然后根据当前运算符归并结果。纯粹的递归含有冗余计算,可同时保留中间结果来提高效率。
Example 2
Input: "2*3-4*5"
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]
[分析] 这题参考https://leetcode.com/discuss/48488/c-4ms-recursive-method 。 思路类似Unique Binary Search Trees II,以某个运算符为分界线,递归计算左右两边可能的值,然后根据当前运算符归并结果。纯粹的递归含有冗余计算,可同时保留中间结果来提高效率。
public class Solution { // method 2: dp public List<Integer> diffWaysToCompute(String input) { HashMap<String, List<Integer>> dpMap = new HashMap<String, List<Integer>>(); return computeWithDP(input, dpMap); } public List<Integer> computeWithDP(String input, HashMap<String, List<Integer>> dpMap) { List<Integer> result = new ArrayList<Integer>(); if (input == null || input.length() == 0) return result; int N = input.length(); for (int i = 0; i < N; i++) { char c = input.charAt(i); if (c == '+' || c == '-' || c == '*') { String leftSubStr = input.substring(0, i); String rightSubStr = input.substring(i + 1, N); List<Integer> left = dpMap.get(leftSubStr); if (left == null) left = computeWithDP(leftSubStr, dpMap); List<Integer> right = dpMap.get(rightSubStr); if (right == null) right = computeWithDP(rightSubStr, dpMap); for (int op1: left) { for (int op2: right) { if (c == '+') result.add(op1 + op2); else if (c == '-') result.add(op1 - op2); else result.add(op1 * op2); } } } } if (result.isEmpty()) result.add(Integer.parseInt(input)); dpMap.put(input, result); return result; } // method 1: recursive public List<Integer> diffWaysToCompute1(String input) { List<Integer> result = new ArrayList<Integer>(); if (input == null || input.length() == 0) return result; int N = input.length(); for (int i = 0; i < N; i++) { char c = input.charAt(i); if (c == '+' || c == '-' || c == '*') { List<Integer> left = diffWaysToCompute(input.substring(0, i)); List<Integer> right = diffWaysToCompute(input.substring(i + 1, N)); for (int op1 : left) { for (int op2 : right) { if (c == '+') result.add(op1 + op2); else if (c == '-') result.add(op1 - op2); else result.add(op1 * op2); } } } } // if the string contains only number if (result.isEmpty()) result.add(Integer.parseInt(input)); return result; } }
发表评论
-
Leetcode - The Skyline Problem
2015-09-04 19:09 1056[分析] 思路1参考https://leetcode.com/ ... -
Leetcode - Ugly Number II
2015-08-24 22:54 1118[分析] 暴力的办法就是从1开始检查每个数是否是丑数,发现丑数 ... -
Leetcode - Paint House II
2015-08-20 20:37 1572There are a row of n houses, ea ... -
Leetcode - Maximum Square
2015-08-16 13:33 464Given a 2D binary matrix filled ... -
Leetcode - Paint House
2015-08-16 10:48 1114There are a row of n houses, ea ... -
Leetcode - Sort List
2015-08-15 17:41 440Sort a linked list in O(n log n ... -
Leetcode - Median of Two Sorted Arrays
2015-07-12 11:02 427There are two sorted arrays num ... -
Leetcode - Merge k Sorted Lists
2015-07-08 09:57 424Merge k sorted linked lists and ... -
Jump Game II
2015-07-05 16:49 501Given an array of non-negative ... -
Leetcode - Jump Game
2015-07-05 15:52 488Given an array of non-negative ... -
Leetcode - Interleaving String
2015-06-07 11:41 566Given s1, s2, s3, find whe ... -
Leetcode - Wildcard Matching
2015-06-06 20:01 951Implement wildcard pattern ma ... -
Leetcode - Maximal Square
2015-06-04 08:25 588Given a 2D binary matrix fille ... -
Leetcode - Kth Largest Element in an Array
2015-05-23 21:25 508Find the kth largest element ... -
Leetcode - Palindrome Partition II
2015-05-21 21:15 638Given a string s, partition ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 747Given a string s, partition s s ... -
Leetcode - House Robber II
2015-05-20 22:34 730Note: This is an extension of ... -
Leetcode - Maximum Rectangle
2015-05-20 08:58 462Given a 2D binary matrix fill ... -
Leetcode - Scramble String
2015-05-17 14:22 540Given a string s1, we may repre ... -
Leetcode - Regular Expression Matching
2015-05-16 16:31 385Implement regular expression ma ...
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode 答案解析 golang解答
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
leetcode-helper-1.7.1
leetcode-tag-dynamic programming
leetcode-tag-Tree
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-tag-Stack
leetcode-tag-array
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。