LeetCode刷题第八周

喜欢ヅ旅行 2022-11-26 07:39 137阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70]

> 咕咕咕

### 文章目录 ###

*  字符串专题
 *   *  简单
     *   *  13. 罗马数字转整数
         *  14. 最长公共前缀
     *  中等
     *   *  3. 无重复字符的最长子串
         *  5. 最长回文子串
         *  6. Z 字形变换
         *  8. 字符串转换整数 (atoi)
         *  12. 整数转罗马数字

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70_pic_center]

# 字符串专题 #

## 简单 ##

### 13. 罗马数字转整数 ###

**题目链接：** [点击跳转至本题][Link 1]

**题目大意：给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。**

*  I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
 *  X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
 *  C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70_pic_center 1]

**解题思路：`switch运用`**  
使用switch-case编写一个getValue函数，将阿拉伯数字与罗马字符对应起来。主函数中从第一个字符开始遍历，比较当前字符对应的数字与下一字符对应数字大小，大于等于则加，否则减，最后一个字符直接加。

class Solution { 
        public int romanToInt(String s) { 
            int result = 0,i=0,n =s.length();
            while(i < n){ 
                int current = getValue(s.charAt(i));
                //比较当前字符与下一个字符，大于等于则加到result，小于则减。最后一个字符直接加
                if(i==n-1 || current >= getValue(s.charAt(i+1))){ 
                    result += current;
                }else{ 
                    result -= current;
                }
                i++;
            }
            return result;
        }
        private static int getValue(char c){ 
            switch(c){ 
                case 'I':
                    return 1;
                case 'V':
                    return 5;
                case 'X':
                    return 10;
                case 'L':
                    return 50;
                case 'C':
                    return 100;
                case 'D':
                    return 500;
                case 'M':
                    return 1000;
                default:
                    throw new IllegalArgumentException("不合法的参数异常");
            }
        }
    }

### 14. 最长公共前缀 ###

**题目链接：** [点击跳转至本题][Link 2]

**题目大意：编写一个函数查找字符串数组中的最长公共前缀。  
如果不存在公共前缀，返回空字符串 “”。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70_pic_center 2]

**解题思路：`横向扫描`**  
取第一个字符串,与后面的每一个但字符串进行比较，使用indexOf(String s)函数，如果字符串包含第一个字符串时返回0，否则将第一个字符串末尾去掉，继续比较，直到字符串包含了第一个字符串为止。遍历结束后，第一个字符串已经变成了最长的公共前缀。双层while循环，外层控制遍历，内层负责比较。

class Solution { 
        public String longestCommonPrefix(String[] strs) { 
            //特判:如果字符串数组为空或长度为0,返回空字符串
            if(strs == null || strs.length == 0){ 
                return "";
            }
            //取第一个字符串
            String res = strs[0];
            int i = 1;
            //遍历字符串数组
            while(i < strs.length){ 
                while(strs[i].indexOf(res) != 0){ 
                    //删除res的最后一个字符
                    res = res.substring(0,res.length()-1);
                }
                i++;
            }
            return res;
        }
    }

## 中等 ##

### 3. 无重复字符的最长子串 ###

**题目链接：** [点击跳转至本题][Link 3]

**题目大意：给定一个字符串，要求找出其中不含有重复字符的 最长子串 的长度。**  
![在这里插入图片描述][20200812172214321.png_pic_center]

**解题思路：`滑动窗口`**  
HashMap是键不可以重复，值可以重复的集合。我们创建map集合，用键存储字符，用值存储对应的下标（人为规定为从1开始）。  
在遍历字符串时，定义start作为滑动窗口的起始点，end作为滑动窗口的结束点。则每个滑动窗口的长度为end-start+1。实际情况是滑动窗口是不停的改变，当集合中没有出现过某个元素时，就将其加入集合，并且更新依次滑动窗口的长度；当集合中出现过某个元素时，就将滑动窗口的左边收缩，此时也会做添加和更新操作，但由于更新是和旧值的比较，此时并不会更新。

class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            int n = s.length();
            int ans = 0;
            Map<Character,Integer> map = new HashMap<>();
            //start作为滑动窗口的起始，end作为结尾
            int start = 0;
            for(int end = 0;end < n;end++){ 
                char c = s.charAt(end);
                if(map.containsKey(c)){ 
                    //如果集合中出现过，滑动窗口的左边就向右收缩
                    start = Math.max(map.get(c),start);
                }
                //如果集合中没有出现过，就将其加入集合,并计算滑动窗口的长度
                map.put(c,end+1);
                ans = Math.max(ans,end-start+1);
            }
            return ans;
        }
    }

### 5. 最长回文子串 ###

**题目链接：** [点击跳转至本题][Link 4]

**题目大意：给定一个字符串 s，找到 s 中最长的回文子串。可以假设 s 的最大长度为 1000。**  
![在这里插入图片描述][20200813001109395.png_pic_center]

**解题思路：`中心扩展`**  
考虑从回文子串的中心开始向两边展开搜索匹配。我们需要遍历`2n - 1`个中心，这是因为当回文的中心为双数时，有n-1种划分；当回文的中心为单数时，有 n 种划分。

class Solution { 
        public String longestPalindrome(String s) { 
            if(s == null || s.length() < 1){ 
                return "";
            }
            //start和end分别作为扩展中心的左右边界
            int start = 0,end = 0;
            for(int i = 0;i < s.length();i++){ 
                //有一个扩展中心时
                int len1 = CenterExtension(s,i,i);
                //有两个扩展中心时
                int len2 = CenterExtension(s,i,i+1);
                //len表示扩展中心的大小
                int len = Math.max(len1,len2);
                //如果扩展中心的大小>前一个扩展中心的大小,就更新start和end
                if(len > end-start+1){ 
                    //start表示扩展中心左边界
                    start = i -(len-1)/2;
                    //end表示扩展中心右边界
                    end = i + len/2;
                }
            }
            //substring[a,b)是左闭右开区间
            return s.substring(start,end+1);
        }
        //中心扩展函数
        private int CenterExtension(String s,int left,int right){ 
            int L = left,R = right;
            while(L>=0 && R < s.length() && s.charAt(L) == s.charAt(R)){ 
                L--;
                R++;
            }
            //满足条件时就开始向左向右进位,相当于最后的边界多了左右两个值,因此不是R-L+1
            return R-L-1;
        }
    }

### 6. Z 字形变换 ###

**题目链接：** [点击跳转至本题][Link 5]

**题目大意：给定一个字符串，根据给定的行数，以从上往下、从左到右进行 Z 字形排列。要求输出需要从左往右逐行读取，产生出一个新的字符串。**  
![在这里插入图片描述][20200813135842786.png_pic_center]

**解题思路：`按行排序+标志变量`**

定义rows字符串，并将rows分隔成n份（n为行数numRows）。接着，遍历字符串 s 时把每个字符填到正确的行 rows\[i\]中 。遍历时标志变量在-1和1之间变换，从而控制了是向上遍历还是向下遍历。最终将n份结果合并到res返回。

class Solution { 
        public String convert(String s, int numRows) { 
            //特判:行数<2时直接返回原字符串
            if(numRows < 2){ 
                return s;
            }
            //定义字符串rows
            List<StringBuilder> rows = new ArrayList<StringBuilder>();
            //有多少行,就将rows分成多少份
            for(int i = 0;i < numRows;i++){ 
                rows.add(new StringBuilder());
            }
            int i = 0,flag = -1;
            for(char c :s.toCharArray()){ 
                rows.get(i).append(c);
                //到达转折点时,执行反向
                if(i==0 || i==numRows-1){ 
                    flag = -flag;
                }
                //向上或向下遍历
                i += flag;
            }
            //定义res,将多份的rows合并起来作为结果
            StringBuilder res = new StringBuilder();
            for(StringBuilder row:rows){ 
                res.append(row);
            }
            return res.toString();
        }
    }

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

**题目链接：** [点击跳转至本题][Link 6]

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

*  如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
 *  假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
 *  该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。

**解题思路：**  
注意考虑三点：①去掉前导空格 ②处理正负号 ③注意越界情况。实际上工作中建议直接调用写好的API，自定义轮子，此题比较无聊。

class Solution { 
        public int myAtoi(String str) { 
            //将字符串转化为字符串数组
            char[] chars = str.toCharArray();
            int n = chars.length;
            int i = 0;
            //去掉前导空格
            while(i < n && chars[i] == ' '){ 
                i++;
            }
            //去掉前导空格后到达末尾了
            if(i == n){ 
                return 0;
            }
            boolean flag = true;
            if(chars[i] == '-'){ 
                //遇到负号
                flag = false;
                i++;
            }else if(chars[i] == '+'){ 
                //遇到正号
                i++;
            }else if(!Character.isDigit(chars[i])){ 
                //其他符号
                return 0;
            }
            int ans = 0;
            while(i < n && Character.isDigit(chars[i])){ 
                int digit = chars[i] - '0';
                //应该是ans*10 +digit >Integer.MAX_VALUE,但*10和+digit可能越界,故移到右边
                if(ans >(Integer.MAX_VALUE - digit)/10){ 
                    //越界处理
                    return flag ? Integer.MAX_VALUE:Integer.MIN_VALUE;
                }
                ans = ans * 10 + digit;
                i++;
            }
            return flag ? ans : -ans;
        }
    }

### 12. 整数转罗马数字 ###

**题目链接：** [点击跳转至本题][Link 7]

**题目大意：给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70_pic_center 3]

**解题思路：`贪心算法`**  
使用可变字符串StringBuilder存储答案，将阿拉伯数字和罗马数字分别用数组装起来。遍历数字数组，每一个数字与num比较，如果小于等于num就将对应下标的字符串数组中的值添加到sb中。并将num的值对应减去相应的数字。

class Solution { 
        int[] digit ={ 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] Rome = { "M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        public String intToRoman(int num) { 
            //StringBuilder是可变字符
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i<digit.length;i++){ 
                while(digit[i] <= num){ 
                    num -= digit[i];
                    sb.append(Rome[i]);
                }
            }
            return sb.toString();
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70]: /images/20221124/f3c38f7c118a4494a3d43537caa592e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/303119dc3ff74bf195e1a4b8af39cc47.png
[Link 1]: https://leetcode-cn.com/problems/roman-to-integer/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/bfdb23ffe6df4e6996e5f43148f01c50.png
[Link 2]: https://leetcode-cn.com/problems/longest-common-prefix/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/2bb9d634a77146d7b0ae9bb329820277.png
[Link 3]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[20200812172214321.png_pic_center]: /images/20221124/3c8d1f5f0a6c49f5a251f05c9489c535.png
[Link 4]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[20200813001109395.png_pic_center]: /images/20221124/ade6e80f1a804a16aa4794e82acef524.png
[Link 5]: https://leetcode-cn.com/problems/zigzag-conversion/
[20200813135842786.png_pic_center]: /images/20221124/fde9c6a860f24ef19ee200f246dbc6db.png
[Link 6]: https://leetcode-cn.com/problems/string-to-integer-atoi/
[Link 7]: https://leetcode-cn.com/problems/integer-to-roman/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/b69a49ef0a514a37aa5e9a94edc9b0de.png