头像

长街听风




离线:19天前



@[TOC]

LeetCode 150. 逆波兰表达式求值

根据 逆波兰表示法,求表达式的值。

有效的算符包括 +、-、*、/。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1:

输入: tokens = [“2”,”1”,”+”,”3”,”*”]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

示例 2:

输入: tokens = [“4”,”13”,”5”,”/”,”+”]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

示例 3:

输入: tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,””,”/”,””,”17”,”+”,”5”,”+”]
输出: 22
解释:
该算式转化为常见的中缀算术表达式为:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示:

  • 1 <= tokens.length <= 10^4
  • tokens[i] 要么是一个算符("+"、"-"、"*" 或 "/"),要么是一个在范围 [-200, 200]内的整数

逆波兰表达式:

逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 )
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * )

逆波兰表达式主要有以下两个优点:

  • 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中

解题思路

该题看上去比较难,事实上只要记住了逆波兰表达式求值的步骤就很简单了,且题目中最后告知了逆波兰表达式的两个优点,其中第二个优点就是代码的思路。我们把第二个优点用代码实现,题目就完成了。

唯一要注意的一点就是:从栈中弹出两个数进行计算时,第一个弹出的数是第二个操作数b,第二个弹出来的数才是第一个操作数a。对于+*无影响,但是对于-/,显然a - bb - a是不同的,故要注意一下。

Java代码

class Solution {
    private Stack<Integer> stack = new Stack<>();

    public int evalRPN(String[] tokens) {
        //遍历完整个数组,遇到运算符就从栈中弹出两个数,将运算结果压回栈,
        //若遇到的不是运算符,则一定是数,直接入栈
        for(int i = 0;i < tokens.length;i++){
            if(tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")){
                int res = eval(tokens[i]);
                stack.push(res);
            }else{
                stack.push(Integer.valueOf(tokens[i]));
            }

        }
        return stack.peek();
    }

    private int eval(String op){
        int b = stack.pop();//注意栈是先进后出的,故先弹出的才是第二个操作数
        int a = stack.pop();
        if(op.equals("+")) return a + b;
        else if(op.equals("-")) return a - b;
        else if(op.equals("*")) return a * b;
        else return a / b;
    }
}

在这里插入图片描述




@[TOC]

LeetCode 150. 逆波兰表达式求值

根据 逆波兰表示法,求表达式的值。

有效的算符包括 +、-、*、/。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1:

输入: tokens = [“2”,”1”,”+”,”3”,”*”]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

示例 2:

输入: tokens = [“4”,”13”,”5”,”/”,”+”]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

示例 3:

输入: tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,””,”/”,””,”17”,”+”,”5”,”+”]
输出: 22
解释:
该算式转化为常见的中缀算术表达式为:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示:

  • 1 <= tokens.length <= 10^4
  • tokens[i] 要么是一个算符("+"、"-"、"*" 或 "/"),要么是一个在范围 [-200, 200]内的整数

逆波兰表达式:

逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 )
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * )

逆波兰表达式主要有以下两个优点:

  • 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中

解题思路

该题看上去比较难,事实上只要记住了逆波兰表达式求值的步骤就很简单了,且题目中最后告知了逆波兰表达式的两个优点,其中第二个优点就是代码的思路。我们把第二个优点用代码实现,题目就完成了。

唯一要注意的一点就是:从栈中弹出两个数进行计算时,第一个弹出的数是第二个操作数b,第二个弹出来的数才是第一个操作数a。对于+*无影响,但是对于-/,显然a - bb - a是不同的,故要注意一下。

Java代码

class Solution {
    private Stack<Integer> stack = new Stack<>();

    public int evalRPN(String[] tokens) {
        //遍历完整个数组,遇到运算符就从栈中弹出两个数,将运算结果压回栈,
        //若遇到的不是运算符,则一定是数,直接入栈
        for(int i = 0;i < tokens.length;i++){
            if(tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")){
                int res = eval(tokens[i]);
                stack.push(res);
            }else{
                stack.push(Integer.valueOf(tokens[i]));
            }

        }
        return stack.peek();
    }

    private int eval(String op){
        int b = stack.pop();//注意栈是先进后出的,故先弹出的才是第二个操作数
        int a = stack.pop();
        if(op.equals("+")) return a + b;
        else if(op.equals("-")) return a - b;
        else if(op.equals("*")) return a * b;
        else return a / b;
    }
}

在这里插入图片描述




@[TOC]

AcWing 35. 反转链表

定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

思考题:

请同时实现迭代版本和递归版本。

样例

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解法一:迭代

头插法。共三个关键结点,如图:
在这里插入图片描述
空间复杂度分析: 遍历时只有4个额外变量(dummy,tail,cur,nxt),所以额外的空间复杂度是 $O(1)$。
时间复杂度分析: 只遍历一次链表,时间复杂度是 $O(n)$。

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //思路:不断让后面的结点连到dummy的后面,结点遍历完毕,也就反转完毕了
        if(head == null) return head;
        //由于用的是头插法,即后面的节点需要插在当前头节点之前,所以声明一个虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //表示本次要插入到dummy后的结点,即插入到原始链表的头节点位置
        ListNode cur = head.next;
        //tail指向一直不变,改变的是tail.next,用于将已经反转的部分链表和剩余还需要反转的链表相连
        ListNode tail = head;

        while(cur != null){
            //记住下一个需要头插的节点,避免等下cur.next改变指向,就找不到原来的cur.next了
            ListNode nxt = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            tail.next = nxt;//将已经反转的部分链表和剩余还需要反转的链表相连
            cur = nxt;//下一个要头插的节点
        }
        return dummy.next;
    }
}

在这里插入图片描述

解法二:递归

首先我们先考虑 reverseList 函数能做什么,它可以翻转一个链表,并返回新链表的头节点,也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head.next),这样我们可以将以head.next为头节点的链表翻转,并得到原链表的尾节点tail,它也是新链表的头节点,此时因为进行了反转,head.next是新链表的尾节点,我们令它的next指针指向head,并将head.next指向空即可将整个链表翻转,且新链表的头节点是tail
在这里插入图片描述

空间复杂度分析: 总共递归 n 层,系统栈的空间复杂度是 $O(n)$,所以总共需要额外 $O(n)$ 的空间。
时间复杂度分析: 链表中每个节点只被遍历一次,所以时间复杂度是 $O(n)$。

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode tail = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }
}

在这里插入图片描述




class ParkingSystem {
    private int[] remain;

    public ParkingSystem(int big, int medium, int small) {
        remain = new int[]{big,medium,small};
    }

    public boolean addCar(int carType) {
        return remain[carType - 1] -- > 0; 
    }
}

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * ParkingSystem obj = new ParkingSystem(big, medium, small);
 * boolean param_1 = obj.addCar(carType);
 */



class ParkingSystem {
    private int[] remain;

    public ParkingSystem(int big, int medium, int small) {
        remain = new int[]{big,medium,small};
    }

    public boolean addCar(int carType) {
        return remain[carType - 1] -- > 0; 
    }
}

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * ParkingSystem obj = new ParkingSystem(big, medium, small);
 * boolean param_1 = obj.addCar(carType);
 */


活动打卡代码 AcWing 3267. 小明上学

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int y = sc.nextInt();
        int g = sc.nextInt();
        int n = sc.nextInt();
        int res = 0;

        while(n-- != 0){
            int k = sc.nextInt();
            int t = sc.nextInt();
            switch (k){
                case 0: res += t;break; //直接通行
                case 1: res += t; break;//红灯等待t秒
                case 2: res += t + r; break;//黄灯等待t秒后是红灯,还得等r秒
                case 3: break;//绿灯,不用等,即不耗时间
            }
        }
        System.out.println(res);
    } 
}



import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        int y = sc.nextInt();
        int g = sc.nextInt();
        int n = sc.nextInt();
        int res = 0;

        while(n-- != 0){
            int k = sc.nextInt();
            int t = sc.nextInt();
            switch (k){
                case 0: res += t;break; //直接通行
                case 1: res += t; break;//红灯等待t秒
                case 2: res += t + r; break;//黄灯等待t秒后是红灯,还得等r秒
                case 3: break;//绿灯,不用等,即不耗时间
            }
        }
        System.out.println(res);
    } 
}


活动打卡代码 AcWing 92. 反转链表 II

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        //思路与206题反转链表类似,只是这里将第m-1个位置换成了那题的dummy
        if(head == null || head.next == null) return head;
        //建立虚拟头结点,方便对所有结点的操作统一
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //本题使用头插法的首结点应该为第m-1个结点
        ListNode pre = dummy;
        for(int i = 0;i < m - 1;i++){
            pre = pre.next;
        }
        //接下来的操作用206题一致
        ListNode tail =pre.next;
        ListNode cur = tail.next;
        //头插 n - m个结点即可
        for(int i = m;i < n;i++){
            ListNode nxt = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            tail.next = nxt;
            cur = nxt;
        }
        return dummy.next;
    }
}


活动打卡代码 AcWing 35. 反转链表

@[TOC]

剑指offer 24 反转链表 LeetCode206

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制:

0 <= 节点个数 <= 5000

注意:本题与主站 206 题相同:https://leetcode-cn.com/problems/reverse-linked-list/

解题思路:

写该题时,应该先问面试官能不能修改原链表,如果不可以,那我们看到反转,第一反应应该是想到栈的先进后出特性,即用一个栈来辅助反转,建立一个新的链表。如果可以修改原链表,那么面试官的初心应该就是让我们原地反转给定的链表。

解法一:使用栈

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        //入栈
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        //建立虚拟头节点,构建新的链表
        ListNode dummy = new ListNode(0);
        cur = dummy;
        while(!stack.isEmpty()){
            cur.next = stack.pop();
            cur = cur.next;
        }
        //注意这一句不能少,否则最后两个节点会形成环,
        //如题中反转后2的下一个节点是1,而原链表1的下一个节点是2
        //如果没有下面这行代码,2的下一个节点是1,1的下一节点是2,而不是null,形成环了
        cur.next = null;
        return dummy.next;
    }
}

在这里插入图片描述

解法二:原地反转链表

头插法。共三个关键结点,如图:
在这里插入图片描述

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //思路:不断让后面的结点连到dummy的后面,结点遍历完毕,也就反转完毕了
        if(head == null) return head;
        //由于用的是头插法,即后面的节点需要插在当前头节点之前,所以声明一个虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        //表示本次要插入到dummy后的结点,即插入到原始链表的头节点位置
        ListNode cur = dummy.next.next;
        //tail指向一直不变,改变的是tail.next,用于将已经反转的部分链表和剩余还需要反转的链表相连
        ListNode tail = head;

        while(cur != null){
            //记住下一个需要头插的节点,避免等下cur.next改变指向,就找不到原来的cur.next了
            ListNode nxt = cur.next;
            cur.next = dummy.next;
            dummy.next = cur;
            tail.next = nxt;//将已经反转的部分链表和剩余还需要反转的链表相连
            cur = nxt;//下一个要头插的节点
        }
        return dummy.next;
    }
}

在这里插入图片描述




长街听风
1个月前

@[TOC]

剑指 Offer 67. 把字符串转换成整数

写一个函数 StrToInt,实现把字符串转换成整数这个功能。不能使用 atoi或者其他类似的库函数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。

注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。

在任何情况下,若函数不能进行有效的转换时,请返回 0

说明:

假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围,请返回 INT_MAX (2^31 − 1)INT_MIN (−2^31)

示例 1:

输入: ” 42”
输出: 42

示例 2:

输入: ” -42”
输出: -42
解释: 第一个非空白字符为 ‘-‘, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。

示例 3:

输入: “4193 with words”
输出: 4193
解释: 转换截止于数字 ‘3’ ,因为它的下一个字符不为数字。

示例 4:

输入: “words and 987”
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。

示例 5:

输入: “-91283472332”
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。

注意:本题与主站 8 题相同:https://leetcode-cn.com/problems/string-to-integer-atoi/

解题思路

这个题目看上去很长,觉得有难度,但其实就是一个简单的模拟题,要说有难点的话,就是要考虑很多的情况。我写该题时遇到的几个点总结如下:
1. 找字符串中第一个不为某字符的的模板写法,假如是找第一个不为空格的字符

int i = 0;
while(i < str.length() && str.charAt(i) == ' ') i++;

同理,要找是某字符的模板写法和上面类似,如要找到字符串中的空格进行一些处理

int i = 0;
while(i < str.length() && str.charAt(i) != ' ') i++;

2. 在这类字符串转数字的问题中,我们判断正负标记,写if语句时有一个要注意的地方:

//现在判断从i开始的第一个字符是否是正负号
int flag = 1;//是否是负数,是负数时flag = -1;
if(i < str.length() && str.charAt(i) == '+') i++;
if(i < str.length() && str.charAt(i) == '-'){
    flag = -1;
    i++;
}

看上去好像没有什么问题,但是当输入的字符串是"+-2"时就有问题了.
在这里插入图片描述

因为这里“+-”号连在一起了,该输入不能转为合法的有效数字,但是代入上述代码会发现,第一个“+”号被过滤了,而“-”被当成了第一个合法字符,然后和后面的数字合在一起组成一个负数。正确的写法应该把第二个if改为else if,即只判断除空格之外的第一个字符是否是正负号,,正确写法如下。

//现在判断从i开始的第一个字符是否是正负号
int flag = 1;//是否是负数,是负数时flag = -1;
if(i < str.length() && str.charAt(i) == '+') i++;
else if(i < str.length() && str.charAt(i) == '-'){
    flag = -1;
    i++;
}

3. 我们很容易就能想到输入的字符串转为数字后,可能得到的数字会很大而超过int范围,所以很自然的就先用long接收,这确实没错,所以又很自信的写了如下代码:

long res = 0;//算出的结果可能超过int范围,故先用long接收
while(i < str.length() && '0'<= str.charAt(i) && str.charAt(i) <= '9' ){
     res = res * 10 + str.charAt(i) - '0';
     i++;
 }

 //如果超出int边界,则返回相应边界
if(res > Integer.MAX_VALUE && flag == 1) return Integer.MAX_VALUE;
if(res > Integer.MAX_VALUE && flag == -1) return Integer.MIN_VALUE;

return (int)(flag * res);//记得转回int

看着很完美啊,但是如果在while中,得到的数字连long范围都超了怎么办,照样出错呀,如下:
在这里插入图片描述

所以我们应该在数字刚超int范围还未超long范围时就返回,题目本身要求的就是超出int范围的话就返回int的边界,所以我们此时返回很合理。代码如下:

long res = 0;//算出的结果可能超过int范围,故先用long接收
while(i < str.length() && '0'<= str.charAt(i) && str.charAt(i) <= '9' ){
    res = res * 10 + str.charAt(i) - '0';
    //如果超出int边界,则可立即返回相应边界
    if(res > Integer.MAX_VALUE && flag == 1) return Integer.MAX_VALUE;
    if(res > Integer.MAX_VALUE && flag == -1) return Integer.MIN_VALUE;
    i++;
}

return (int)(flag * res);//记得转回int

Java代码

class Solution {
    public int strToInt(String str) {
        //先找到第一个不为空格的地方
        int i = 0;
        while(i < str.length() && str.charAt(i) == ' ') i++;

        //现在判断从i开始的第一个字符是否是正负号
        int flag = 1;//是否是负数,是负数时flag = -1;
        if(i < str.length() && str.charAt(i) == '+') i++;
        else if(i < str.length() && str.charAt(i) == '-'){
            flag = -1;
            i++;
        }

        long res = 0;//算出的结果可能超过int范围,故先用long接收
        while(i < str.length() && '0'<= str.charAt(i) && str.charAt(i) <= '9' ){
            res = res * 10 + str.charAt(i) - '0';
            //如果超出int边界,则可立即返回相应边界
            if(res > Integer.MAX_VALUE && flag == 1) return Integer.MAX_VALUE;
            if(res > Integer.MAX_VALUE && flag == -1) return Integer.MIN_VALUE;
            i++;
        }

        return (int)(flag * res);//记得转回int

    }
}

在这里插入图片描述