class Solution {
public:
stack<int> nums;
stack<char> op;
void calc() {
int a = nums.top();
nums.pop();
int b = nums.top();
nums.pop();
switch (op.top()) {
case '+':
nums.push(b + a);
break;
case '-':
nums.push(b - a);
break;
case '*':
nums.push(b * a);
break;
case '/':
nums.push(b / a);
break;
}
}
int calculate(string s) {
unordered_map<char, int> pr;
pr['+'] = pr['-'] = 1, pr['*'] = pr['/'] = 2;
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') continue;
if ('0' <= s[i] && s[i] <= '9') {
int t = 0, j = i;
while (j < s.size() && '0' <= s[j] && s[j] <= '9') {
t = t * 10 + (s[j] - '0'); // first subtraction， second add （over flow）
j++;
}
nums.push(t);
i = j - 1;
} else {
while (op.size() && pr[op.top()] >= pr[s[i]]) {
calc();
op.pop();
}
op.push(s[i]);
}
}
while (op.size()) {
calc();
op.pop();
}
return nums.top();
}
};
活动打卡代码
LeetCode 227. 基本计算器 II
活动打卡代码
LeetCode 150. 逆波兰表达式求值
var stk = []int{}
func evalRPN(tokens []string) int {
for _, token := range tokens {
t := token[len(token) - 1]
if t == '+' || t == '-' || t == '*' || t == '/' {
a := stk[len(stk)-1]
stk = stk[:len(stk)-1]
b := stk[len(stk)-1]
stk = stk[:len(stk)-1]
switch t {
case '+': stk = append(stk, b + a)
case '-': stk = append(stk, b - a)
case '*': stk = append(stk, b * a)
case '/': stk = append(stk, b / a)
}
} else {
stk = append(stk, toNum(token))
}
}
return stk[len(stk)-1]
}
func toNum(s string) int {
t, flag := 0, false
i := 0
if s[0] == '-' {
flag = true
i++
}
for ; i < len(s); i++ {
t = t * 10 + int(s[i]) - int('0')
}
if flag {
return -t
}
return t
}
活动打卡代码
LeetCode 155. 最小栈
type MinStack struct {
stk []int
stkMin []int
}
func Constructor() MinStack {
return MinStack{
[]int{},
[]int{math.MaxInt64},
}
}
func (this *MinStack) Push(val int) {
this.stk = append(this.stk, val)
this.stkMin = append(this.stkMin, min(this.stkMin[len(this.stkMin)-1], val))
}
func (this *MinStack) Pop() {
this.stk, this.stkMin = this.stk[:len(this.stk)-1], this.stkMin[:len(this.stkMin)-1]
}
func (this *MinStack) Top() int {
return this.stk[len(this.stk)-1]
}
func (this *MinStack) GetMin() int {
return this.stkMin[len(this.stkMin)-1]
}
func min(a, b int) int {
if (a < b) {
return a
}
return b
}
/**
* Your MinStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* obj.Pop();
* param_3 := obj.Top();
* param_4 := obj.GetMin();
*/
活动打卡代码
LeetCode 20. 有效的括号
func isValid(s string) bool {
var m = map[rune]rune{
')' : '(',
'}' : '{',
']' : '[',
}
stk := []rune{}
for _, c := range s{
if m[c] == 0 {
stk = append(stk, c)
} else {
if len(stk) == 0 || stk[len(stk)-1] != m[c] {
return false
}
stk = stk[:len(stk)-1]
}
}
return len(stk) == 0
}
活动打卡代码
LeetCode 88. 合并两个有序数组
func merge623Version(nums1 []int, m int, nums2 []int, n int) {
i, j, k := m-1, n-1, m+n-1
for k >= 0 {
if j < 0 {
break
}
if i >= 0 && nums1[i] > nums2[j] {
nums1[k], i = nums1[i], i-1
} else {
nums1[k], j = nums2[j], j-1
}
k--
}
}
活动打卡代码
LeetCode 26. 删除排序数组中的重复项
package main
// 删除有序数组中的重复项
func removeDuplicates(nums []int) int {
n := 0
for i := 0; i < len(nums); i++ {
if i == 0 || nums[i] != nums[i-1] {
nums[n] = nums[i]
n++
}
}
return n
}
func removeDuplicatesEverNi(nums []int) int {
cnt, n := 1, len(nums)
for i, j := 0, 1; i < n; {
j = i + 1
for j < n && nums[i] == nums[j] {
j++
}
if j >= n {
break
}
nums[cnt] = nums[j]
i, cnt = j, cnt+1
}
return cnt
}
活动打卡代码
LeetCode 283. 移动零
func moveZeroes623(nums []int) {
n, k := len(nums), 0
for i := 0; i < n; i++ {
if nums[i] != 0 {
nums[k], k = nums[i], k+1
}
}
for k < n {
nums[k], k = 0, k+1
}
}
活动打卡代码
LeetCode 21. 合并两个有序链表
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(p *ListNode, q *ListNode) *ListNode {
head := &ListNode{-1, nil}
cur := head
for p != nil && q != nil {
if p.Val < q.Val {
cur.Next, p = p, p.Next
} else {
cur.Next, q = q, q.Next
}
cur = cur.Next
}
if p != nil {
cur.Next = p
}
if q != nil {
cur.Next = q
}
return head.Next
}
活动打卡代码
LeetCode 66. 加一
func plusOne(digits []int) []int {
n := len(digits)
for i := n - 1; i >= 0; i-- {
if (digits[i] != 9) {
digits[i]++;
for j := i+1; j < n; j++ {
digits[j] = 0;
}
return digits;
}
}
ans := make([]int, n+1)
ans[0] = 1
return ans
}
活动打卡代码
LeetCode 142. 环形链表 II
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
// var m = map[*ListNode]int{}
// p := head
// for p != nil {
// if m[p] != 0 {
// return p
// }
// m[p]++
// p = p.Next
// }
// return p
p, q := head, head
for q!=nil && q.Next!=nil {
q = q.Next.Next
p = p.Next
if p == q {
cur := head
for cur != p {
cur, p = cur.Next, p.Next
}
return cur
}
}
return nil
}
