标签： 递归

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = "1 + 1"
输出：2

示例 2：

输入：s = " 2-1 + 2 "
输出：3

示例 3：

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

提示：

• 1 <= s.length <= 3 * 105
• s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
• s 表示一个有效的表达式
• ‘+’ 不能用作一元运算(例如， “+1” 和 "+(2 + 3)" 无效)
• ‘-‘ 可以用作一元运算(即 “-1” 和 "-(2 + 3)" 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

等于把括号去掉算出当前+,-符号真正对应的加减操作算出来

class Solution {
    public int calculate(String s) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        int idx = -1;
        int flag = 1;
        while (++idx < s.length()){
            char c = s.charAt(idx);
            if (c == ' ')continue;
            switch (c){
                case '+':
                    flag = stack.peek();
                    break;
                case '-':
                    flag = -stack.peek();
                    break;
                case '(':
                    stack.push(flag);
                    break;
                case ')':
                    stack.pop();
                    break;
                default:
                    //取到整个数字
                    int num = c - '0';
                    while (idx+1 < s.length() && s.charAt(idx+1) - '0'>=0 && s.charAt(idx+1)-'9'<=0){
                        idx++;
                        num *= 10;
                        num += s.charAt(idx) - '0';
                    }
                    //取到了整个数字
                    res += flag * num;
                    break;
            }
        }
        return res;
    }
}

写出来好像和官方题解一样？

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

递归

class Solution {
    int[] arr;
    public int[] reversePrint(ListNode head) {
        recursion(head,0);
        return arr;
    }

    private void recursion(ListNode node, int n) {
        if (node==null) {
            arr = new int[n];
            return;
        }
        recursion(node.next,n+1);
        arr[arr.length-n-1] = node.val;
    }
}

将非负整数 num 转换为其对应的英文表示。

示例 1：

输入：num = 123
输出："One Hundred Twenty Three"

示例 2：

输入：num = 12345
输出："Twelve Thousand Three Hundred Forty Five"

示例 3：

输入：num = 1234567
输出："One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

示例 4：

输入：num = 1234567891
输出："One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

提示：

• 0 <= num <= 231 - 1

今天每日一题

随便写下
一个需要知道的基本知识点，英文和中文中的差别
中文中可以理解为4位一段，

从个到千
从万到千万
从亿到千亿
但是英文中不是这样的，英文中是按照3位一段的计数法，比如例子
1234567891，我们有某些时候看到的表达方式是这样的
1 , 234 , 567 , 891

7 Thousand
4 Million
1 Billion
对于小于3位的部分，就很简单了，就是 X hundred XX这样的结构

那么思路就是这样的了

1. 每3位处理一次，这样每次除以1000取余来处理这部分数据，然后再处理除以1000之后取整的数字
2. 百位直接按1-9取英文再加Hundred，如果没有百位,则跳过
3. 100以下的部分，1-19单独处理，大于等于20的，按照整10部分+个位数部分处理转换

class Solution {
    public String numberToWords(int num) {
        if (num ==0){
            return "Zero";
        }
        String[] arr1 = new String[]{"","Thousand","Million","Billion"};
        String[] arr2 = new String[]{"Hundred"};
        String[] arr3 = new String[]{"","One","Two","Three","Four","Five","Six","Seven","Eight","Nine"};
        String[] arr4 = new String[]{"Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
        String[] arr5 = new String[]{"","","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"};
        int idx1 = 0;
        ArrayList<String> list = new ArrayList<>();
        while (num != 0){
            int tmp = num % 1000;
            num = num / 1000;
            int hundred = tmp / 100;
            tmp = tmp % 100;
            StringBuffer sb2 = new StringBuffer();
            if (hundred>0){
//                System.out.print(arr3[hundred]+" "+arr2[0]+" ");
                sb2.append(arr3[hundred]).append(" ").append(arr2[0]).append(" ");
            }
            if (tmp>=20){
//                System.out.print(arr5[tmp/10] + " " + arr3[tmp%10] + " ");
                sb2.append(arr5[tmp/10]).append(" ");
                if (tmp%10>0){
                    sb2.append(arr3[tmp%10]).append(" ");
                }
            }else if (tmp < 10 && tmp > 0){
//                System.out.print(arr3[tmp%10] + " ");
                sb2.append(arr3[tmp%10]).append(" ");
            }else if (tmp>0){
//                System.out.print(arr4[tmp-10] + " ");
                sb2.append(arr4[tmp-10]).append(" ");
            }
//            System.out.println(arr1[idx1]);
            if (sb2.length()>0){
                sb2.append(arr1[idx1]).append(" ");
            }
            idx1++;
            list.add(0,sb2.toString());
        }
        StringBuffer sb = new StringBuffer();
        for (String s : list) {
//            System.out.println(s);
            sb.append(s);
        }
        String a = sb.toString();
        while (a.charAt(a.length()-1) == ' '){
            a = a.substring(0,a.length()-1);
        }
        return a;
    }
}

拓展小知识来源百度
1至10无规律可循： one、two、three、four、five、six、seven、eight、nine、ten；
11至19 ：eleven、twelve、thirteen、fourteen、fifteen、sixteen、seventeen、eighteen、 nineteen；
从20至99：整数的几十中除了twenty（二十）、thirty（三十）、forty（四十）、fifty（五十）、eighty（八十）为特殊形式外，sixty（六十）、seventy（七十）、ninety（九十）都是其个位数形式后添加后缀-ty构成。
百位数个数基数词形式加“hundred”，表示几百，在几十几与百位间加上and。
第四条一般认为是英式表达中会用到，本题中都没有and,一开始做的时候感觉有点怪怪的
另外还有一些其他的细节性的表达，比如2000这种的结尾加only表示整。

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

• -231 <= n <= 231 - 1

进阶：

• 你能不使用循环或者递归来完成本题吗？

今天每日一题，easy啊！~

class Solution {
    public boolean isPowerOfThree(int n) {
        long num = 1L;
        long i = 0;
        while (num < n ){
            num = num * 3L;
        }
        if (num == n){
            return true;
        }
        return false;
    }
}

用long型运算，因为如果数值特别大的话会超出Integer.MAX_VALUE，基本思路就是从3的0次方开始，一直乘以3，直到大于或者等于输入的数字n，最后判断下得到的值是否等于n，等于则说明输入的n是3的倍数，不等于则不是。

其实也可以枚举，在Integer.MAX_VALUE内，3的幂的数字个数是非常有限的，大概….就

1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467,

这么几个，所以，代码：

class Solution {
    public boolean isPowerOfThree(int n) {
        int[] arr = new int[]{1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467};
        for (int i : arr) {
            if (i == n){
                return true;
            }
        }
        return false;
    }
}

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

题解

9月2日每日一题，最常规的解法应该声明一个数组，然后就是遍历链表，记录下每个节点，最后得到总长之后，到数组中找到总长减去k位置的并返回

我这边的第一反应是递归，探底后返回依次加1，加到k的时候记录下这倒数第k个结点。原理类似DFS的后序遍历。

class Solution {
    int k = 0;
    int count = 0;
    ListNode node;
    public ListNode getKthFromEnd(ListNode head, int k) {
        this.k = k;
        func(head);
        return node;
    }


    public void func(ListNode head){
        if (head == null){
            return;
        }
        func(head.next);
        count++;
        if (count == k){
            node = head;
        }
    }
}

另外的一种，双指针，如下，具体思路逻辑详见注释

class Solution {
    ListNode node1;
    ListNode node2;
    public ListNode getKthFromEnd(ListNode head, int k) {
        node1 = head;
        node2 = head;
        //这里初始为1，举例说明 链表【1,2,3】，倒是第一个应当是3，不存在倒数第0个的这种说法
        int count = 1;
        //让node2先跑k步
        while (node2.next != null && count<k){
            node2 = node2.next;
            count++;
        }
        if (count < k){
            //假如链表总长度小于k
            return null;
        }
        //此时node2在node1后面距离k,接下来，node1和node2一起往后跑
        //当node2跑到结尾的时候，node1即为倒数第k个了
        while (node2.next != null){
            node1 = node1.next;
            node2 = node2.next;
        }

        return node1;
    }
}

当然这边也可以再优化下，写到一个while循环里，通过条件判断让node2先跑k个，双指针的思路和上次LeetCode刷题【876】链表的中间结点有点类似，都是通过控制两个指针之间的相对距离，找出链表中间的某个节点。