1.数学（一）

题目汇总https://leetcode-cn.com/tag/math/

2. 两数相加中等

7. 整数反转简单

8. 字符串转换整数 (atoi)中等（不会做）

9. 回文数简单

12. 整数转罗马数字中等

13. 罗马数字转整数简单

29. 两数相除中等（不会）

43. 字符串相乘中等

50. Pow(x, n)（需要看题解还不太懂）

60. 第k个排列中等

2. 两数相加中等

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

思路：考虑进位

代码来自链接https://leetcode-cn.com/problems/add-two-numbers/solution/hua-jie-suan-fa-2-liang-shu-xiang-jia-by-guanpengc/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {//执行用时：3 ms, 在所有 Java 提交中击败了23.33%的用户
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);//设置预先指针
        ListNode cur = pre;
        int carry = 0;
        while(l1 != null || l2 != null){
            int x = (l1 == null ? 0 : l1.val);
            int y = (l2 == null ? 0 : l2.val);
            int sum = x + y + carry;

            carry = sum / 10;  //进位值
            sum = sum % 10;    //实际存入链表的值
            cur.next = new ListNode(sum);
            cur = cur.next;

            if(l1 != null)  l1 = l1.next;
            if(l2 != null)  l2 = l2.next;
        }

        if(carry == 1) {
            cur.next = new ListNode(carry);
        }
        return pre.next;

    }
}

7. 整数反转简单

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
** 示例 2:**
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2³¹, 2³¹− 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

思路：考虑溢出问题

https://leetcode-cn.com/problems/reverse-integer/solution/hua-jie-suan-fa-7-zheng-shu-fan-zhuan-by-guanpengc/
反转整数的过程需要 %10 取到这个整数的末尾数字

最大的值与最小的值为：[−2^31, 2^31 − 1]，即：[-2147483648, 2147483647]
最大的32位整数2147483647反转过来就会发生溢出问题，肯定要返回 0

class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
    public int reverse(int x) {
        int res = 0;
        while (x != 0) {
            int pop = x % 10;
            // 最大数 2147483647
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && pop > 7)) 
                return 0;
            // 最小数 -2147483648
            if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && pop < -8)) 
                return 0;
            res = res * 10 + pop;
            x /= 10;
        }
    return res;  
    }
}

8. 字符串转换整数 (atoi)中等

请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。

假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。

该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2³¹, 2³¹− 1]。如果数值超过这个范围，请返回 INT_MAX (2³¹− 1) 或 INT_MIN (−2³¹) 。
示例 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 (−2³¹) 。

思路：

9. 回文数简单

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗？

思路：取出后半段数字进行翻转

class Solution {//执行用时：9 ms, 在所有 Java 提交中击败了98.78%的用户
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) 
            return false;
        int revertedNumber = 0;
        while (x > revertedNumber)
        {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }   
        // x 是偶数，revertNum 和 x 相等
        // x 是奇数，最中间的数字就在 revertedNumber 的最低位上，将它除以 10 以后应该和 x 相等
        if(x == revertedNumber || x == revertedNumber / 10) 
            return true;
        return false;
    }
}

12. 整数转罗马数字中等

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。

X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。

C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
示例 1:输入: 3，输出: "III"
示例 2:输入: 4，输出: "IV"
示例 3:输入: 9，输出: "IX"
示例 4:输入: 58，输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:输入: 1994，输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

思路：贪心

class Solution {//执行用时：5 ms, 在所有 Java 提交中击败了84.69%的用户
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};    
    String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length && num >= 0; i++) {
            while (values[i] <= num) {
                num -= values[i];
                sb.append(symbols[i]);
            }
        }
        return sb.toString();
    }
}

13. 罗马数字转整数简单

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

思路：哈希表

https://leetcode-cn.com/problems/roman-to-integer/solution/hua-jie-suan-fa-13-luo-ma-shu-zi-zhuan-zheng-shu-b/
首先将所有的组合可能性列出并添加到哈希表中
然后对字符串进行遍历，由于组合只有两种，一种是 1 个字符，一种是 2 个字符，其中 2 个字符优先于 1 个字符。先判断两个字符的组合在哈希表中是否存在，存在则将值取出加到结果 ans 中，并向后移2个字符。不存在则将判断当前 1 个字符是否存在，存在则将值取出加到结果 ans 中，并向后移 1 个字符。遍历结束返回结果 ans。

class Solution {//执行用时：11 ms, 在所有 Java 提交中击败了13.32%的用户
    public int romanToInt(String s) {
        Map<String,Integer> map = new HashMap<>();
        map.put("I",1);
        map.put("IV",4);
        map.put("V", 5);
        map.put("IX", 9);
        map.put("X", 10);
        map.put("XL", 40);
        map.put("L", 50);
        map.put("XC", 90);
        map.put("C", 100);
        map.put("CD", 400);
        map.put("D", 500);
        map.put("CM", 900);
        map.put("M", 1000);
        
        int ans = 0;
        for(int i = 0; i<s.length(); ){
            if(i + 1 < s.length() && map.containsKey(s.substring(i,i+2))){
                ans += map.get(s.substring(i,i+2));
                i+=2;
            }
            else{
                ans += map.get(s.substring(i,i+1));
                i+=1;
            }
        }
        return ans;     
    }
}

43. 字符串相乘中等

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：

num1 和 num2 的长度小于110。

num1 和 num2 只包含数字 0-9。

num1 和 num2 均不以零开头，除非是数字 0 本身。

不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

class Solution {//执行用时：5 ms, 在所有 Java 提交中击败了66.74%的用户
    public String multiply(String num1, String num2) {
        int n1 = num1.length() - 1;
        int n2 = num2.length() - 1;
        if(n1 < 0 || n2 < 0)    return "";
        int[] mul = new int[n1 + n2 + 2];

        for(int i = n1; i >= 0; i--){
            for(int j = n2; j >= 0; j--){
                int bitmul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                bitmul += mul[i + j + 1];// 先加低位判断是否有新的进位
                mul[i + j] += bitmul / 10;
                mul[i + j + 1] = bitmul % 10;
            }
        }

        StringBuilder sb = new StringBuilder();
        int i = 0;
        while(i < mul.length - 1 && mul[i] == 0)
            i++;
        for(; i < mul.length; i++){
            sb.append(mul[i]);
        }
        return sb.toString();
    }
}

50. Pow(x, n)中等

实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10，输出: 1024.00000
示例 2:
输入: 2.10000, 3，输出: 9.26100
示例 3:
输入: 2.00000, -2，输出: 0.25000
解释: 2^-2 = 1/2² = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2³¹, 2³¹− 1]

思路：快速幂分治

代码来自题解https://leetcode-cn.com/problems/powx-n/solution/50-powx-n-kuai-su-mi-qing-xi-tu-jie-by-jyd/

class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了94.48%的用户
    public double myPow(double x, int n) {
        if(x == 0.0f)   return 0.0d;
        long b = n;
        double res = 1.0;
        if(b < 0){   //考虑负数情况
            x = 1 / x;
            b = - b;
        }
        while(b > 0){
            if(b % 2 == 1)  res *= x;  //每当 b 为奇数时，将多出的一项 x 乘入 res 
            x *= x;//执行x = x^2
            b >>= 1;//右移一位
        }
    return res;
    }
}

60. 第k个排列中等

给出集合 [1,2,3,…,n]，其所有元素共有 n ! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"

"132"

"213"

"231"

"312"

"321"
给定 n 和 k，返回第 k 个排列。
说明：
给定n 的范围是 [1, 9]。
给定 k的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"

思路：DFS

代码是这个题解的，搬运工https://leetcode-cn.com/problems/permutation-sequence/solution/pai-lie-zu-he-zhi-di-kge-pai-lie-golden-monkey-by-/

class Solution {//执行用时：8 ms, 在所有 Java 提交中击败了33.77%的用户
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for(int i=0;i<n;i++){
            nums[i] = i + 1;//生成nums数组
        }
        boolean[] used = new boolean[n];//记录当前的索引的数是否被使用过
        return dfs(nums,  new ArrayList<String>(), used, 0, n, k);
    }

     /**
     * @param nums      源数组
     * @param levelList 每一层的选择
     * @param used      数组的元素是否被使用过
     * @param depth     深度，也就是当前使用的元素的索引
     * @param n         上限值
     * @param k         第k个
     * @return 第k个排列
     */

    private String dfs(int[] nums, List<String> levelList, boolean[] used, int depth, int n, int k){
        if(depth == n){//触发出口条件，开始收集结果集
            StringBuilder res = new StringBuilder();
            for (String s : levelList) res.append(s);
            return res.toString();
        }
        int cur = factorial(n - depth - 1);//当前的depth也就是索引，有多少排列数
        for(int i=0;i<n;i++){
            if (used[i]) continue;//当前元素被使用过，做剪枝
            if (cur < k) {//当前的排列组合数小于k，说明就算这一层排完了，也到不了第k个，剪枝
                k -= cur;
                continue;
            }
            levelList.add(nums[i] + "");//list收的是string类型
            used[i] = true;//当前元素被使用过标记
            return dfs(nums, levelList, used, depth + 1, n, k);
        }
        return null;
    }


     //返回n的阶乘，如3!=3*2*1=6
    private int factorial(int n) {
        int res = 1;
        while (n > 0) {
            res *= n--;
        }
        return res;
    }

}