Blogz

LeetCode 17 电话号码的字母组合

题目:

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]
 

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解:

经典回溯算法求全组合
根据提示我们可以得到以下数字-字符数组的映射表: "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"

    

        
2
3
4
5
6
7
8
9
    
    

        
[a,b,c]
[d,e,f]
[g,h,i]
[j,k,l]
[m,n,o]
[p,q,r,s]
[t,u,v]
[w,x,y,z]
    

思路
1.拆分digits= "23" 得数字[2,3]
2.匹配字符数组 charList = [[a,b,c],[d,e,f]] 深度 depth = 2 
3.根据字符数组深度 depth 定义一个同样深度的栈 stack 存储组合的字符
4.对charList从深度0开始递归，递归方式:
    a.判断当前深度是否最深，最深则存储结果返回，否则继续
    b.遍历当前深度所有字符 
    c.每次遍历入栈当前字符
    d.进入下一深度递归
    e.出栈当前字符

图解:

例: digits = "23"
匹配可得字符数组为[[a,b,c],[d,e,f]]

定义字符数组 charList = [[a,b,c],[d,e,f]] 
定义栈深度 depth = 2
定义栈 stack 
定义结果集 list

递归第一层 
取字符 a 入栈
进入第二层递归

递归第二层 
取字符 d 入栈
此时到达底层，存储结果 "ad"
list = ["ad"]

字符 d 出栈
字符 e 入栈
此时到达底层，存储结果 "ae"
list = ["ad","ae"]

字符 e 出栈
字符 f 入栈
此时到达底层，存储结果 "af"
list = ["ad","ae","af"]

字符 f 出栈
第二层遍历结束，回退回第一层遍历
字符 a 出栈
字符 b 入栈
进入第二层递归

递归第二层 
取字符 d 入栈
此时到达底层，存储结果 "bd"
list = ["ad","ae","af","bd"]

字符 d 出栈
字符 e 入栈
此时到达底层，存储结果 "be"
list = ["ad","ae","af","bd","be"]

字符 e 出栈
字符 f 入栈
此时到达底层，存储结果 "bf"
list = ["ad","ae","af","bd","be","bf"]

字符 f 出栈
第二层遍历结束，回退回第一层遍历
字符 b 出栈
字符 c 入栈
进入第二层递归

递归第二层 
取字符 d 入栈
此时到达底层，存储结果 "cd"
list = ["ad","ae","af","bd","be","bf","cd"]

字符 d 出栈
字符 e 入栈
此时到达底层，存储结果 "ce"
list = ["ad","ae","af","bd","be","bf","cd","ce"]

字符 e 出栈
字符 f 入栈
此时到达底层，存储结果 "cf"
list = ["ad","ae","af","bd","be","bf","cd","ce","cf"]

字符 f 出栈
第二层遍历结束，回退回第一层遍历
字符 c 出栈
第一层遍历结束
返回结果 list = ["ad","ae","af","bd","be","bf","cd","ce","cf"]

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public List<String> letterCombinations(String digits) {
    return process(digits);
}

private List<String> process(String digits) {
    List<String> list = new ArrayList<>();
    if (digits.isEmpty()) return list;
    String[] allChars = new String[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    char [] nums = digits.toCharArray();
    dfs(allChars, nums, 0, new StringBuilder(), list);
    return list;
}

private void dfs(String[] allChars, char[] nums, int depth, StringBuilder s, List<String> list) {
    if (depth == nums.length) {
        list.add(s.toString());
        return;
    }
    int index = nums[depth] - 50;
    char[] chars = allChars[index].toCharArray();
    for (int i = 0; i < chars.length; i++) {
        s.append(chars[i]);
        dfs(allChars, nums, depth + 1, s, list);
        s.deleteCharAt(s.length() - 1);
    }
}

LeetCode 16 最接近的三数之和

题目:

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。


示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：

输入：nums = [0,0,0], target = 1
输出：0
 

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
通过次数413,132提交次数908,668

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解:

此题使用双指针法为最优方案
具体流程如下:

1.对数组排序

2.遍历数组[0,nums.length-2)，i为当前遍历的位置,
  定义L=i+1 R=nums.length-1，即L为i的下一位，R为数组末尾
  定义minClose为最接近Target的距离，
  定义sum为最接近Target的三数和
  然后我们按照以下步骤寻找:

    a.如果nums[i]+nums[L]+nums[R]-Target=0 直接返回结果

    b.如果nums[i]+nums[L]+nums[R]-Target>0 
      比较三数和与Target距离和minClose，如果更接近则更新minClose和sum，
      R左移使三数和与Target更接近

    c.如果nums[i]+nums[L]+nums[R]-Target<0 
      比较三数和与Target距离和minClose，如果更接近则更新minClose和sum，
      L右移使三数和与Target更接近

    d.一旦L，R相遇则此次循环结束

3.剪枝:

    a.如果某一次遍历中 nums[i]+nums[i+1]+nums[i+2] > Target，
      说明此次遍历的最小和sumTemp > Target
      那么我们可以断言，如果最小和sumTemp与Target之间的距离sumTemp-Target
      比当前记录的最小距离minClose还要大，那么后续无论怎么移动L和R和只会增大，
      sumTemp与Target的距离sumTemp-Target只会更大，
      并且下一次遍历i+1开始也是如此，
      因此后续所有遍历均没有必要，可以直接退出返回结果

    b.如果某一次遍历中 nums[i]+nums[nums.length-2]+nums[nums.length-1] < Target，
      说明此次遍历的最大和sumTemp < Target
      那么我们可以断言，如果最大和sumTemp与Target之间的距离Target-sumTemp
      比当前记录的最小距离minClose还要大，那么后续无论怎么移动L和R和只会减小，
      sumTemp与Target的距离Target-sumTemp只会更大，
      但是下一轮遍历i+1使得和会增大，因此后续遍历无法断言，
      只可以终止当前循环，直接进入下一轮循环

图解:

例：nums = [3,5,-2,-1,8,10,15]
   target = 9

定义变量如下:
sum = nums[0](-2)+nums[1](-1)+nums[2](3) = 0
minClose = |sum(0) - target(9)| = 9

第一轮遍历 [ i=0 minClose=9 sum=0 ]
首先判断不满足剪枝条件，开始循环

tempSum = nums[i](-2)+nums[L](-1)+nums[R](15) = 12
|tempSum(12) - target(9)| = 3 < minClose 替换原有的sum和minClose
此时 sum = 12  minClose = 3
由于tempSum > target R指针左移 ⬇

tempSum = nums[i](-2)+nums[L](-1)+nums[R](10) = 7
|tempSum(7) - target(9)| = 2 < minClose 替换原有的sum和minClose
此时 sum = 7  minClose = 2
由于tempSum < target L指针右移 ⬇

tempSum = nums[i](-2)+nums[L](3)+nums[R](10) = 11
|tempSum(11) - target(9)| = 2 = minClose 原有的sum和minClose不变
此时 sum = 7  minClose = 2
由于tempSum > target R指针左移 ⬇

tempSum = nums[i](-2)+nums[L](4)+nums[R](8) = 10
|tempSum(10) - target(9)| = 1 < minClose 替换原有的sum和minClose
此时 sum = 10  minClose = 1
由于tempSum > target R指针左移 ⬇

tempSum = nums[i](-2)+nums[L](4)+nums[R](5) = 7
|tempSum(7) - target(9)| = 2 > minClose 原有的sum和minClose不变
此时 sum = 10  minClose = 1
L,R相遇，此轮遍历结束

第二轮遍历 [ i=1 minClose=1 sum=10 ]
首先判断不满足剪枝条件，开始循环

tempSum = nums[i](-1)+nums[L](4)+nums[R](15) = 18
|tempSum(18) - target(9)| = 9 > minClose 原有的sum和minClose不变
此时 sum = 10  minClose = 1
由于tempSum > target R指针左移 ⬇

tempSum = nums[i](-1)+nums[L](4)+nums[R](10) = 13
|tempSum(13) - target(9)| = 4 > minClose 原有的sum和minClose不变
此时 sum = 10  minClose = 1
由于tempSum > target R指针左移 ⬇ 

tempSum = nums[i](-1)+nums[L](4)+nums[R](8) = 11
|tempSum(11) - target(9)| = 2 > minClose 原有的sum和minClose不变
此时 sum = 10  minClose = 1
由于tempSum > target R指针左移 ⬇   

tempSum = nums[i](-1)+nums[L](4)+nums[R](5) = 8
|tempSum(8) - target(9)| = 1 = minClose 原有的sum和minClose不变
此时 sum = 10  minClose = 1
L,R相遇，此轮遍历结束  

第三轮遍历 [ i=2 minClose=1 sum=10 ]

此时我们可以发现
最小和 minSum = nums[i](4)+nums[i+1](5)+nums[i+2](8) = 17 > target
并且最小和 minSum(17) - target(9) = 8 > minClose(1)
因此后续所有遍历和一定都大于17，直接返回结果即可

结果返回 sum=10

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public int threeSumClosest_02(int[] nums, int target) {
    int sumResult = nums[0] + nums[1] + nums[2];
    int minClose = Math.abs(sumResult - target);
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; i++) {
        //剪枝
        int maxV = nums[i] + nums[i + 1] + nums[i + 2];
        if (maxV > target && maxV - target > minClose) {
            break;
        }
        //剪枝
        int minV = nums[i] + nums[nums.length - 1] + nums[nums.length - 2];
        if (minV < target && target - minV > minClose) {
            continue;
        }

        int L = i + 1;
        int R = nums.length - 1;
        while (L < R) {
            int sum = nums[i] + nums[L] + nums[R];
            if (sum == target) {
                return sum;
            } else if (sum > target) {
                if (sum - target < minClose) {
                    minClose = sum - target;
                    sumResult = sum;
                }
                R--;
            } else {
                if (target - sum < minClose) {
                    minClose = target - sum;
                    sumResult = sum;
                }
                L++;
            }
        }
    }
    return sumResult;
}

LeetCode 15 三数之和

题目:

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。


示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
 

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解:

此题可使用暴力递归和回溯算法都可以解出此题,但是时间复杂度高,此处不给出具体解法
我们使用双指针法巧妙解决此问题,具体流程如下:

例：nums = [-2,-1,0,1,2,2,-1,3]

1.对数组排序
2.出现以下情况直接返回
    a.数组为空
    b.数组最小值大于0
    c.数组最大值小于0
3.遍历数组，i为当前遍历的位置,定义L=i+1 R=数组长度-1，即L为i的下一位，R为数组末尾，然后我们按照以下步骤寻找:
    a.如果nums[i]+nums[L]+nums[R]=0 记录结果且R左移L右移直至与当前L、R所在位置值不同的位置(此步骤就是去重操作)
    b.如果nums[i]+nums[L]+nums[R]>0 说明和太大，R左移直至与当前R所在位置值不同的位置(此步骤就是去重操作)
    c.如果nums[i]+nums[L]+nums[R]<0 说明和太小，L右移直至与当前L所在位置值不同的位置(此步骤就是去重操作)
    d.一旦L，R相遇则此次循环结束
4.结果存储在数组list中

图解:

第一轮遍历

nums[i](-2)+nums[L](-1)+nums[R](3) = 0
记录下结果 [-2,-1,3]
此时list=[[-2,-1,3]]
L右移至与当前值不同的位置
R左移至与当前值不同的位置

nums[i](-2)+nums[L](0)+nums[R](2) = 0
记录下结果 [-2,0,2]
此时list=[[-2,-1,3],[-2,0,2]]
L右移至与当前值不同的位置
R左移至与当前值不同的位置

L,R相遇，循环结束，i右移至与当前位置值不同的位置开始下一轮循环

第二轮遍历

nums[i](-1)+nums[L](-1)+nums[R](3) = 1
和大于0，R左移至与当前值不同的位置

nums[i](-1)+nums[L](-1)+nums[R](2) = 0
记录下结果 [-1,-1,2]
此时list=[[-2,-1,3],[-2,0,2],[-1,-1,2]]
L右移至与当前值不同的位置
R左移至与当前值不同的位置

nums[i](-1)+nums[L](0)+nums[R](1) = 0
记录下结果 [-1,0,1]
此时list=[[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]
L右移至与当前值不同的位置
R左移至与当前值不同的位置
L,R相遇，循环结束，i右移至与当前位置值不同的位置开始下一轮循环

第三轮遍历

注意此时 nums[i](0)+nums[L](1) = 1
后续无论如何移动R将值减少也无法使和等于0，因此结束流程
返回结果 
list=[[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> listResult = new ArrayList<>();
    Arrays.sort(nums);
    if (nums.length <= 2 || nums[0] > 0 || nums[nums.length - 1] < 0) return listResult;
    int preI = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) return listResult;
        if (nums[i] == preI) continue;
        preI = nums[i];
        int L = i + 1;
        int R = nums.length - 1;
        while (L < R) {
            if (nums[i] + nums[L] > 0) break;
            int sum = nums[i] + nums[L] + nums[R];
            if (sum == 0) {
                listResult.add(Arrays.asList(nums[i], nums[L], nums[R]));
                do {
                    L++;
                } while (L < R && nums[L] == nums[L - 1]);
                do {
                    R--;
                } while (L < R && nums[R] == nums[R + 1]);
            } else if (sum < 0) {
                while (L < R && nums[i] + nums[L] + nums[R] < 0) {
                    L++;
                }
            } else {
                while (L < R && nums[i] + nums[L] + nums[R] > 0) {
                    R--;
                }
            }
        }
    }
    return listResult;
}

LeetCode 14 最长公共前缀

题目:

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
 

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解:

思路
1.如果字符串数组为空，返回空
2.任取字符串数组中一个字符串,从长到短取自身前缀去和数组其他字符串比较
3.如果某个前缀同时也是其他字符串前缀则此前缀为最长公共前缀

图解:

例: strs = ["flower","flow","flight"]
我们取第一个字符串"flower"作为比较对象

返回结果 "fl" 即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

public String longestCommonPrefix(String[] strs) {
    String result = "";
    if (strs.length == 0) return result;
    result = strs[0];
    for (int i = 1; i < strs.length; i++) {
        int n = result.length();
        while (!strs[i].startsWith(result)) {
            result = result.substring(0, --n);
        }
        if (result.length() == 0) break;
    }
    return result;
}

LeetCode 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:

输入: s = "III"
输出: 3
示例 2:

输入: s = "IV"
输出: 4
示例 3:

输入: s = "IX"
输出: 9
示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
 

提示：

1 <= s.length <= 15
s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。
通过次数720,508提交次数1,156,547

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/roman-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解:

思路:
1.分析可知罗马数字字符串一定从大到小排列组合
2.直接生成所有可能的罗马数字对应的数字的表如下:
reps  =  [ "M",  "CM",  "D",  "CD",  "C",  "XC",  "L",  "XL",  "X",  "IX",  "V",  "IV",  "I"]
values = [1000,   900,  500,   400,  100,   90,   50,    40,   10,     9,    5,    4,     1]
3.从头开始遍历罗马数字字符串取对应的数相加即可，我们可用字符串函数startWith(s,offset)方法

图解:

例: s="MCMXCIV"  设总和sum=0  字符头部偏移量 offset=0

1.s="MCMXCIV"  offset=0  sum=0  
2.此时判断头部是否是字符"M"
3.判断 s.startWith("M",0)=true
4.求和 sum = sum+1000 = 1000
5.偏移 offset偏移字符"M"的长度 offset = offset+1 = 1
6.继续判断offset为1 startWith("M",1)=false
7.判断下一个罗马数字⬇

1.s="MCMXCIV"  offset=1  sum=1000
2.此时判断头部是否是字符"CM"
3.判断 s.startWith("CM",1)=true
4.求和 sum = sum+900 = 1900
5.偏移 offset偏移字符"CM"的长度 offset = offset+2 = 3
6.继续判断offset为3 startWith("CM",3)=false
7.判断下一个罗马数字⬇

1.s="MCMXCIV"  offset=3  sum=1900
2.此时判断头部是否是字符"D"
3.判断 s.startWith("D",3)=false
4.判断下一个罗马数字⬇

1.s="MCMXCIV"  offset=3  sum=1900
2.此时判断头部是否是字符"CD"
3.判断 s.startWith("CD",3)=false
4.判断下一个罗马数字⬇

1.s="MCMXCIV"  offset=3  sum=1900
2.此时判断头部是否是字符"C"
3.判断 s.startWith("C",3)=false
4.判断下一个罗马数字⬇

1.s="MCMXCIV"  offset=3  sum=1900
2.此时判断头部是否是字符"XC"
3.判断 s.startWith("XC",3)=true
4.求和 sum = sum+90 = 1990
5.偏移 offset偏移字符"CM"的长度 offset = offset+2 = 5
6.继续判断offset为5 startWith("XC",5)=false
7.判断下一个罗马数字⬇

依次类推,下一个罗马数字为 "IV"
1.s="MCMXCIV"  offset=5  sum=1990
2.此时判断头部是否是字符"IV"
3.判断 s.startWith("IV",5)=true
4.求和 sum = sum+4 = 1994
5.偏移 offset偏移字符"CM"的长度 offset = offset+2 = 7
6.全部判断完毕结束 

返回结果为 sum = 1994

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

public int romanToInt(String s) {
    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] reps = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    int result = 0;
    int offset = 0;
    for (int i = 0; i < 13; i++) {
        while (s.startsWith(reps[i], offset)) {
            result += values[i];
            offset += reps[i].length();
        }
    }
    return result;
}

LeetCode 12 整数转罗马数字

题目:

罗马数字包含以下七种字符： 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:

输入: num = 3
输出: "III"
示例 2:

输入: num = 4
输出: "IV"
示例 3:

输入: num = 9
输出: "IX"
示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：
1 <= num <= 3999

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/integer-to-roman
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

思路:

1.首先直接生成个位，十位，百位，千位上0-10的表示数组如下:
chars0 = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
chars1 = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
chars2 = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
chars3 = ["", "M", "MM", "MMM"]

2.数字从最低位到最高位依次取出，然后对应表中相应罗马数字即可

图解：

例: num = 1994 则对应表中位置如下:

得出结果  MCMXCIV

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public String intToRoman(int num) {
    String[] chars0 = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
    String[] chars1 = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
    String[] chars2 = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
    String[] chars3 = {"", "M", "MM", "MMM"};
    String[][] chars = new String[][]{chars0, chars1, chars2, chars3};
    String result = "";
    int d = 0;
    while (num > 0) {
        int n = num % 10;
        result = chars[d][n] + result;
        num = num/10;
        d++;
    }
    return result;
}

LeetCode 11 盛最多水的容器

题目：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：
输入：height = [1,1]
输出：1
 
提示：
n == height.length
2 <= n <= 105
0 <= height[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

思路就按照一条原则，补短板，求面积
1.左右两边哪边短，就从那边开始收缩直至找到更高的边，才有可能比之前的面积更大

图解：

示例: [1,8,6,2,5,4,8,3,7] 定义i,j分别为左右边界,max为最大盛水量,初始值为0

此时最大盛水量=8*1  [8]  max=8
短板为左，i右移直至短板变长

此时最大盛水量=7*7  [8,49] max=49
短板为右，j左移直至短板变长

此时最大盛水量=8*5  [8,49,40] max=49
短板为左，i右移直至短板变长
i直至和j相遇短板也无法继续增高，因此返回结果 49

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int maxArea(int[] height){
    int res = 0;
    int i = 0;
    int j = height.length-1;
    while (i < j) {
        int min = Math.min(height[i], height[j]);
        res = Math.max(res, (j - i) * min);
        if (height[i] <= height[j]) {
            while (i < j && height[i] <= min) i++;
        } else {
            while (i < j && height[j] <= min) j--;
        }
    }
    return res;
}

LeetCode 09 回文数

题目：

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
 
示例 1：

输入：x = 121
输出：true
示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
 

提示：

-231 <= x <= 231 - 1

进阶：你能不将整数转为字符串来解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

思路很简单
1.负数直接返回False，一定不是回文数
2.每次去除原数A最低位加上新数✖️10，得新数B，判断A是否等于B即可

图解：

例：54345  步骤如下：

代码：

1
2
3
4
5
6
7
8
9
10
11

public boolean isPalindrome(int x) {
    if (x < 0) return false;
    int m = x;
    int n = 0;
    while (x > 0) {
        n = n * 10 + x % 10;
        x = x / 10;
    }
    if (n == m) return true;
    return false;
}

LeetCode 08 字符串转换整数 (atoi)

题目：

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 
如果两者都不存在，则假定结果为正。读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。
如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。
具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
 

示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
        ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
        ^
第 3 步："42"（读入 "42"）
        ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
            ^
第 3 步："   -42"（读入 "42"）
            ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
        ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
        ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
            ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
 

提示：

0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

字符串类型的题目需要判断的点较多，各种条件交错容易漏逻辑或者逻辑错误
最好的办法首先分析写出逻辑表，然后按照逻辑表依条写
此题我们可以将逻辑大体分为以下：

1.依次读入字符

2.如果字符不是 数字（0-9）、' '、'+'、'-' 这四种直接结束

3.如果字符是 ' ' 且此时即没有确认符号也没有读入任何数字，继续读入，否则结束

4.如果字符是 '+'、'-' 且此时没有确认符号，则确认符号，继续读入，否则结束

5.如果字符是 数字（0-9）且此时没有确认符号，自动确认符号为 '+',加入数字计算，
  计算按照公式 已经计算的数x10+新读入的数 = 新计算数 
  然后判断新计算数是否已经超过Int范围，如果超过则赋值最值后结束，否则继续读入
  
6.根据符号和最后计算数确认结果返回

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public int myAtoi(String s) {
    char[] chars = s.toCharArray();
    Boolean positive = null;
    long v = 0;
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] == 32) {
            if (positive == null) continue;
            break;
        } else if (chars[i] == 43 || chars[i] == 45) {
            if (positive != null) break;
            positive = chars[i] == 43;
        } else if (chars[i] >= 48 && chars[i] <= 57) {
            if (positive == null) positive = true;
            v = v * 10 + (chars[i] - '0');
            if (positive && v > Integer.MAX_VALUE) {
                v = Integer.MAX_VALUE;
                break;
            } else if (!positive && v > (long) Integer.MAX_VALUE + 1) {
                v = (long) Integer.MAX_VALUE + 1;
                break;
            }
        } else {
            break;
        }
    }
    return (int) (Boolean.TRUE.equals(positive) ?v:-v);
}

LeetCode 07 整数反转

题目：

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
 
示例 1：

输入：x = 123
输出：321
示例 2：

输入：x = -123
输出：-321
示例 3：

输入：x = 120
输出：21
示例 4：

输入：x = 0
输出：0
 

提示：

-231 <= x <= 231 - 1
通过次数1,087,516提交次数3,074,044

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

思路很简单，每次取原数最低位加上新数✖️10即可

图解：

例：12345  步骤如下：

需要注意的是反转后的数字可能超过Int类型数值范围，可巧妙利用Long类型存储后转换

代码：

1
2
3
4
5
6
7
8

public int reverse(int x) {
    long n = 0;
    while(x != 0) {
        n = n*10 + x%10;
        x = x/10;
    }
    return (int)n==n? (int)n:0;
}