- 浏览: 129250 次
文章分类
- 全部博客 (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
[分析]
思路1:逆序遍历字符串,数字和右括号保存在一个堆栈stack1中,运算符保存在另一个堆栈stack2中,跳过空格,遇到左括号时计算stack1中首个右括号之上的所有数据,也即当前括号对中的内容。 在Accept之前有两个出错点:1)采用顺序遍历。出错case:2-1+1,因为加减的运算顺序是从左至右;2)逆序遍历时拼接完一个位数大于1的完整int 后要逆序已得到实际数值。出错case: 2147483647
思路2:参考如下两篇文章
https://leetcode.com/discuss/41868/java-solution-stack
https://leetcode.com/discuss/39479/simple-c-in-24-ms
非常不错的思路,简单来说就是将算式映射为没有括号的样子来计算
思路1:逆序遍历字符串,数字和右括号保存在一个堆栈stack1中,运算符保存在另一个堆栈stack2中,跳过空格,遇到左括号时计算stack1中首个右括号之上的所有数据,也即当前括号对中的内容。 在Accept之前有两个出错点:1)采用顺序遍历。出错case:2-1+1,因为加减的运算顺序是从左至右;2)逆序遍历时拼接完一个位数大于1的完整int 后要逆序已得到实际数值。出错case: 2147483647
思路2:参考如下两篇文章
https://leetcode.com/discuss/41868/java-solution-stack
https://leetcode.com/discuss/39479/simple-c-in-24-ms
非常不错的思路,简单来说就是将算式映射为没有括号的样子来计算
public class Solution { // Method 2 public int calculate(String s) { if (s == null || s.equals("")) return 0; LinkedList<Integer> signs = new LinkedList<Integer>(); signs.push(1); int currSign = 1; int sum = 0; for (int i = 0; i < s.length(); i++) { int num = 0; while (i < s.length() && '0' <= s.charAt(i) && s.charAt(i) <= '9') { num = num * 10 + s.charAt(i++) - '0'; } // System.out.println(sum + " " + currSign + " " + signs.peek() + " " + num); sum += currSign * signs.peek() * num; if (i == s.length()) break; char c = s.charAt(i); if (c == '+') currSign = 1; else if (c == '-') currSign = -1; else if (c == '(') {signs.push(signs.peek() * currSign); currSign = 1;} else if (c == ')') signs.pop(); } return sum; } // Method 1 public int calculate1(String s) { if (s == null || s.equals("")) return 0; LinkedList<String> nums = new LinkedList<String>(); LinkedList<Character> ops = new LinkedList<Character>(); int n = s.length(); int i = n - 1; while (i >= 0) { StringBuilder num = new StringBuilder(); while (i >= 0 && s.charAt(i) >= '0' && s.charAt(i) <= '9') { num.append(s.charAt(i--)); } if (num.length() > 0) { nums.push(num.reverse().toString()); if (i < 0) break; } char c = s.charAt(i); if (c == ')') { nums.push(")"); } else if (c == '(') { while (!nums.peek().equals(")")) { sum(nums, ops); } nums.pop(); } else if (c == '+' || c == '-') { ops.push(c); } i--; } while (!ops.isEmpty()) { sum(nums, ops); } return !nums.isEmpty() ? Integer.valueOf(nums.pop()) : 0; } private void sum(LinkedList<String> nums, LinkedList<Character> ops) { int num1 = Integer.valueOf(nums.pop()); if (nums.peek().equals(")")) { nums.pop(); nums.push(String.valueOf(num1)); nums.push(")"); return; } int num2 = Integer.valueOf(nums.pop()); char op = ops.pop(); if (op == '+') nums.push(String.valueOf(num1 + num2)); else nums.push(String.valueOf(num1 - num2)); } }
评论
1 楼
qb_2008
2015-06-10
倒着遍历字符串有点别扭,成了右括号入栈,左括号出栈。不过读数字确实方便
一点。也可以用逆波兰表达式。也可以考虑加减法及时计算,这样左右括号就不必
放在操作数栈中。
一点。也可以用逆波兰表达式。也可以考虑加减法及时计算,这样左右括号就不必
放在操作数栈中。
发表评论
-
Leetcode - Closest Binary Search Tree Value II
2015-09-13 14:16 741[分析] 思路1:遍历所有节点找到和 target最接近的 k ... -
Leetcode - Integer to English Words
2015-09-04 20:53 1056[分析] 这题通过率之所以非常低是因为有很多corner ca ... -
Leetcode - Strobogrammatic Number III
2015-09-03 16:45 2119A strobogrammatic number is a n ... -
Leetcode - Closest Binary Search Tree Value II
2015-09-01 09:50 3131Given a non-empty binary search ... -
Leetcode - Binary Tree Postorder
2015-08-29 21:07 499[分析] 迭代实现后序遍历比迭代实现先序和中序都要稍微复杂,对 ... -
Leetcode - Verify Preorder Sequence in Binary Search Tree
2015-08-29 16:46 2992[分析] 思路1:暴力法,遍历当前待检查数组,找到第一个大于数 ... -
Leetcode - Min Stack
2015-08-29 11:20 506[分析] 这题属于简单题 ... -
Leetcode - Basic Calculator II
2015-08-27 09:16 859mplement a basic calculator to ... -
Leetcode - Factorial Trailing Zeroes
2015-08-25 09:00 389[思路] 数乘积结果的后缀0,其实就是数结果中有多少个因子10 ... -
Leetcode - Ugly Number II
2015-08-24 22:54 1109[分析] 暴力的办法就是从1开始检查每个数是否是丑数,发现丑数 ... -
Leetcode - Excel Sheet Column Title
2015-08-24 10:24 603[分析] 十进制转26进制,需要注意的是26进制是以1为最小数 ... -
Leetcode - Max Points on a Line
2015-08-23 15:30 660[分析] 两条直线若包含一个公共点且斜率相同,则为同一条直线。 ... -
Leetcode - Fraction to Recurring Decimal
2015-08-23 10:05 423[分析] 处理int型整数运算时,为避免溢出,省事的做法就是内 ... -
Leetcode - Count Primes
2015-08-22 13:42 469[ref] https://en.wikipedia.org/ ... -
Leetcode - Strobogrammatic Number
2015-08-22 10:48 1055A strobogrammatic number is a n ... -
Leetcode - Add Binary
2015-08-21 09:28 426[分析] 从低位往高位逐位相加,就是这么一个简单的题却花了我一 ... -
Leetcode - Rotate Image
2015-08-19 19:51 459[分析] 自己的思路:从外到内一圈圈顺时针旋转90度,坐标映射 ... -
Missing Ranges
2015-08-19 09:48 479[分析] 此题若不考虑极大值极小值相关的corner case ... -
Leetcode - Bitwise AND of Number Range
2015-08-17 09:41 460Given a range [m, n] where 0 &l ... -
Leetcode - Pow(x, n)
2015-08-11 09:45 425[分析] 数值计算类型题目,二分法或者借助位运算,本题两种方法 ...
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
leetcode 答案解析 golang解答
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
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
970. 强整数对数运算function powerfulIntegers(x: number, y: number, bound: number): numb
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-tag-dynamic programming
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
leetcode-tag-Tree
leetcode-tag-Stack
leetcode-tag-array
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-链表笔记