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
思路：考虑进位
/**
* 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 位的有符号整数，则其数值范围为 [−231, 231 − 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 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 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) 。
思路：
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/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 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
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;
}
}
