• 字符串习题总结2

    目录

    一.最长回文子串

     1.题目

    2.图解

    3.代码

    二.求数组所有集合的全排列（和求字符串的所有子串方法相同）

    1.题目

    2.图解

    3.代码

    三.求一个字符串的所有回文子串（中心扩展法）

    1.题目

    2.思路图解

    （1）方法1

     （2）方法2

    3.代码

    （1）方法1

    （2）方法2 

    四.求二进制和

    1.题目

    2.思路图解

    3.代码

    五.分割回文串（分割后的字符串全为回文）

    1.题目

    2.思路图解

    3.代码

    六.复原IP地址

    1.题目

    2.思路图解

    3.代码

    七.最小覆盖子串

    1.题目

    2.思路图解

    3.代码

    八.电话号码的字母组合

    1.题目

    2.图解思路

    3.代码

    一.最长回文子串

     1.题目

    给你一个字符串 s，找到 s 中最长的回文子串。

    示例：

    输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

    2.图解

    3.代码

    1. public String longestPalindrome(String s) {
    2.         //设置两个指针保存回文串的开始和结束位置
    3.         int begin = 0;
    4.         int end = 0;
    5.         for(int i=0; i<s.length(); i++) {
    6.             //字符串长度有奇偶，所以需要求奇偶中的最大值
    7.             int len1 = huiWenLen(s, i, i);
    8.             int len2 = huiWenLen(s, i, i+1);
    9.             int len = Math.max(len1, len2);
    10.             if(len>end-begin) {
    11.                 //当为偶数的时候，如abb（结果为bb）这时候就会多算如果begin=i-len/2就会减一个，导致错误
    12.                 begin = i-(len-1)/2;
    13.                 end = i+len/2;
    14.             }
    15.         }
    16.         //字符串截取的是从begin开始，到end+1结束（不包含end+1）
    17.         return s.substring(begin, end+1);
    18.     }
    19.     //从当前元素开始向两边开始查找是否为回文串
    20.     public int huiWenLen(String str, int left, int right) {
    21.         int l = left, r = right;
    22.         while(l>=0 && r<str.length() && str.charAt(l)==str.charAt(r)) {
    23.             l--;
    24.             r++;
    25.         }
    26.         return r-l-1;
    27.     }

    二.求数组所有集合的全排列（和求字符串的所有子串方法相同）

    1.题目

    现在有一个没有重复元素的整数集合S，求S的所有子集
    注意：
    你给出的子集中的元素必须按升序排列

    给出的解集中不能出现重复的元素

    示例：

    输入：[1,2,3]

    返回值：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

    2.图解

    3.代码

    1.  public ArrayList<ArrayList<Integer>> subsets(int[] S) {
    2.         ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    3.         if(S==null || S.length==0) {
    4.             return res;
    5.         }
    6.         for(int i=0; i<=S.length; i++) {
    7.             //控制长度，调用递归函数依次查找
    8.             dfsColl(S, 0, i, res, new ArrayList<>());
    9.         }
    10.         return res;
    11.     }
    12.     public void dfsColl(int[] arr, int begin,int len , ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list) {
    13.         //满足指定长度，就添加到结果集中
    14.         if(len == list.size()) {
    15.             res.add(new ArrayList<>(list));
    16.         }
    17.         //从开始位置一直向后寻找
    18.         for(int i=begin; i<arr.length; i++) {
    19.             //将当前元素添加到list中
    20.             list.add(arr[i]);
    21.             //然后递归再向后查找
    22.             dfsColl(arr, i+1, len, res, list);
    23.             //当前元素的指定长度查找完后，删除当前元素
    24.             list.remove(list.size()-1);
    25.         }
    26.     }

    三.求一个字符串的所有回文子串（中心扩展法）

    1.题目

    给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

    回文字符串 是正着读和倒过来读一样的字符串。

    子字符串 是字符串中的由连续字符组成的一个序列。

    具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串

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

    示例：s="aaba"

    输出res= 6 ，其中回文串有a ,a ,b ,a ,aa ,aba

    2.思路图解

    （1）方法1

    首先一个字符肯定是回文的，当以该字符为中心时，继续分别以left和right向两边扩展并验证为子串时，这时候就是一种思路，但是存在一种情况，那就是相同的两个字符也可以组成作为一个中心向外扩散，例如aa,这时候我们就要根据奇偶来进行区分（可能会有一个疑问，那也可能会有3个或4个作为回文中心；因为3个就是1个的扩展，4个就是2个的扩展，所以我们就只根据奇偶讨论2个和1个）；使用2个字符作为中心进行扩展时，需要判断这2个字符相等才能接着进行扩展。

     （2）方法2

    思路和方法1相同，只不过在对于根据奇偶个数进行扩展的时候合并到了一起，减小了代码量。

    首先通过上面处理的结果可以看出，总共有s.length*2-1个中心需要进行扩展；然后再找关系，然后可以总结出，从【0，s.length*2-1】之间，所有的左边界left=i/2；所有的右边界right=left+i%2;

    之后还是通过中心扩展的方法进行求解（在扩展的过程中也判断了为偶数的2个字符作为中心是否相等）。

    3.代码

    （1）方法1

    1.   public int countSubstrings(String s) {
    2.         //这里自身就是回文，所以先统计自身
    3.       int res = s.length();
    4.       //以奇数进行扩展
    5.       for(int i=0; i<s.length(); i++) {
    6.           int left = i-1;
    7.           int right = i+1;
    8.           while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
    9.               res++;
    10.               left--;
    11.               right++;
    12.           } 
    13.       }
    14.       //以偶数进行扩展
    15.       for(int i=0; i<s.length()-1; i++) {
    16.           //说明2个字符可以作为扩展中心
    17.           if(s.charAt(i)==s.charAt(i+1)) {
    18.             res++;
    19.             int left = i-1;
    20.             int right = i+2;
    21.             while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
    22.                 res++;
    23.                 left--;
    24.                 right++;
    25.             }
    26.           }
    27.       }
    28.       return res;
    29.     }

    （2）方法2 

    1.     public int countSubstrings(String s) {
    2.         int res = 0;
    3.         //总共需要匹配len*2-1次，之后会根据奇偶向两边扩展，如果是回文
    4.         //res++,否则就判断下一个（判断过程中注意边界问题）
    5.         for(int i=0; i<s.length()*2-1; i++) {
    6.             int left = i/2;
    7.             int right = left+i%2;
    8.             while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
    9.                 res++;
    10.                 left--;
    11.                 right++;
    12.             }
    13.         }
    14.         return res;
    15.     }

    四.求二进制和

    1.题目

    给定两个用字符串表示的二进制数，返回他们的和。

    数据范围：字符串长度满足 1\le n \le 10^5 \1≤n≤105  ，字符串中只含有 0 和 1，且保证除 0 以外的二进制数没有前导零的情况。

    示例：

    输入："101","1"

    返回值："110"

    2.思路图解

    思路：

    思路：
    首先需要一个保存需要进位的数命名为carry（初始值为0），
    然后计算当前位置的和(包含进位的值), sum=A.charAt(i)+B.charAt(i)，
    求当前位置和的时候还需要每次判断是否超过了源字符串的长度，如果超出，当前结果位置就为0
    下一步是保存进位的值，为了下一位求和使用
    再保存当前位置的和

    图解：

    3.代码

    1.  public String binaryAdd (String A, String B) {
    2.         // write code here
    3.         int aL = A.length()-1;
    4.         int bL = B.length()-1;
    5.         //表示进位
    6.         int carry = 0;
    7.         StringBuilder sb = new StringBuilder();
    8.         while(aL>=0 || bL>=0 || carry>0) {
    9.             //获取每个字符串的当前结果
    10.             int a = (aL<0?'0':A.charAt(aL--))-'0';
    11.             int b = (bL<0?'0':B.charAt(bL--))-'0';
    12.             //求总和（包含低位的进位和高位的和）
    13.             int sum = a+b+carry;
    14.             //保存进位结果
    15.             carry = sum/2;
    16.             //保存进位之后的当前位置的结果
    17.             sb.append(sum%2);
    18.         }
    19.         //最后将拼接好的结果进行反转
    20.         return sb.reverse().toString();
    21.     }

    五.分割回文串（分割后的字符串全为回文）

    1.题目

    给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

    示例：

    输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

    2.思路图解

    3.代码

    1.  List<List<String>> res = new ArrayList<>();
    2.     public List<List<String>> partition(String s) {
    3.         char[] charArray = s.toCharArray();
    4.         dfs(charArray, 0, s.length(), new ArrayList<>());
    5.         return res;
    6.     }
    7.     //求所有回文子串
    8.     public void dfs(char[] charArray, int index, int len, ArrayList<String> list) {
    9.         //说明字符串已经处理完成
    10.         if(index == len) {
    11.             res.add(new ArrayList<>(list));
    12.             return;
    13.         }
    14.         //依次取一部分，先判断是否为回文，是回文就向下处理，如果不是回文，跳过当前循环
    15.         for(int i=index; i<len; i++){
    16.             if(!isPartion(charArray, index, i)) {
    17.                 continue;
    18.             }
    19.             list.add(new String(charArray, index, i-index+1));
    20.             dfs(charArray, i+1, len, list);
    21.             //处理完当前层的子字符串，删除掉，再处理当前层的后面子字符串
    22.             list.remove(list.size()-1);
    23.         }
    24.      }
    25.  
    26.     //判断是否为回文串
    27.     public boolean isPartion(char[] charArray, int left, int right) {
    28.         while(left < right) {
    29.             if(charArray[left++] != charArray[right--]) {
    30.                 return false;
    31.             }
    32.         }
    33.         return true;
    34.     }

     

    六.复原IP地址

    1.题目

    有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

    例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
    给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

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

    2.思路图解

    3.代码

    1. List<String> res = new ArrayList<>();
    2.     public List<String> restoreIpAddresses(String s) {
    3.         int len = s.length();
    4.         dfs(s, 0, 0, len, new ArrayList<String>());
    5.         return res;
    6.     }
    7.     //进行深度搜索进行处理
    8.     public void dfs(String s, int beign, int count, int len, ArrayList<String> list) {
    9.         //处理到了结尾，就直接保存并返回
    10.         if(beign == len) {
    11.             if(count==4)
    12.             res.add(String.join(".", list));
    13.             return;
    14.         }
    15.         //剪枝（字符长度小于之后截取的个数，字符长度大于截取个数的3倍）
    16.         if(len-beign<(4-count) || len-beign>3*(4-count)) {
    17.             return;
    18.         }
    19.         //处理当前的3个字符（1,2,3个分别连起来）
    20.         for(int i=0; i<3; i++) {
    21.             if(i+beign>=len) {
    22.                 break;
    23.             }
    24.             int tmp = segment(s, beign,beign+i+1);
    25.             if(tmp != -1){
    26.                 list.add(""+tmp);
    27.                 dfs(s, beign+i+1, count+1, len, list);
    28.                 //回溯
    29.                 list.remove(list.size()-1);
    30.             }
    31.         }
    32.     }
    33.  
    34.     //判断截取的字符串是否符合ip地址的规范，符合就转化为数字
    35.     public int segment(String s, int left, int right) {
    36.         //当第一长度大于1且第一位是0时就直接返回
    37.         if(right-left>1 && s.charAt(left)=='0') {
    38.             return -1;
    39.         }
    40.         //求字符串的10进制结果
    41.         int res = 0;
    42.         for(int i=left; i<right; i++) {
    43.             res = res*10+s.charAt(i)-'0';
    44.         }
    45.         //说明超过ip长度
    46.         if(res>255) {
    47.             return -1;
    48.         }
    49.         return res;
    50.     }

    七.最小覆盖子串

    1.题目

    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

    示例：

    2.思路图解

    求解思路就是使用两个hash表来存储字符串s和t中字符出现的次数，先统计字符串t，之后再通过滑动窗口的思想来将s中的字符添加到hash中，相当于是扩大窗口，在统计过程中如果窗口左边的元素没有在t中包含或者包含但重复较多，这时候就需要减小窗口的大小，这些操作都是基于hash表来操作。中间还需要一个count标记窗口中的元素是否已经包含了t中的所有字符，还需要一个len来标识是否是最小的覆盖子串。

    3.代码

    1.  public String minWindow(String s, String t) {
    2.         HashMap<Character,Integer> ms = new HashMap<>();
    3.         HashMap<Character,Integer> mt = new HashMap<>();
    4.         //先统计t中字符出现的次数
    5.         for(int i=0; i<t.length(); i++) {
    6.             mt.put(t.charAt(i), mt.getOrDefault(t.charAt(i), 0)+1);
    7.         }
    8.         //保存结果值
    9.         String res="";
    10.         //记录当前长度，之后根据该长度要进行缩短字符串
    11.         int len = Integer.MAX_VALUE;
    12.         //left 和 right 表示滑动窗口的左右边界;count记录t在s中已经存在的个数
    13.         for(int left=0,right=0,count=0; right<s.length(); right++) {
    14.             //先将元素放到ms中
    15.             ms.put(s.charAt(right), ms.getOrDefault(s.charAt(right), 0)+1);
    16.             //判断该字符是否也出现在t中
    17.             if(mt.containsKey(s.charAt(right))) {
    18.                 //还需要判断当前字符是否是t必须的（避免多个重复没用的字符）
    19.                 if(ms.get(s.charAt(right))<=mt.get(s.charAt(right))) {
    20.                     count++;
    21.                 }
    22.             }
    23.             //如果s的left位置的元素不包含在t中 或 字符个数多余指定个数，那么就将该字符删除
    24.             while(left<right && (!mt.containsKey(s.charAt(left)) ||
    25.                     ms.get(s.charAt(left))>mt.get(s.charAt(left)))) {
    26.                 ms.put(s.charAt(left), ms.get(s.charAt(left))-1);
    27.                 left++;
    28.             }
    29.             //满足count长度 然后 （根据len）判断是否需要缩短区间，若缩短，修改res
    30.             if(count==t.length() && right-left+1<len) {
    31.                 len = right-left+1;
    32.                 res = s.substring(left, right+1);
    33.             }
    34.         }
    35.         return res;
    36.     }

    八.电话号码的字母组合

    1.题目

    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

     示例：

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

    2.图解思路

    通过递归回溯去处理每一个数字对应的字符，当递归处理到数字串的末端时，就保存结果，结束递归。

     

    3.代码

    1. public List<String> letterCombinations(String digits) {
    2.       List<String> res = new ArrayList<>();  
    3.         if(digits.length()==0) {
    4.             return  res;
    5.         }
    6.       Map<Character, String> map = new HashMap<>(); 
    7.         map.put('2', "abc");
    8.         map.put('3', "def");
    9.         map.put('4', "ghi");
    10.         map.put('5', "jkl");
    11.         map.put('6', "mno");
    12.         map.put('7', "pqrs");
    13.         map.put('8', "tuv");
    14.         map.put('9', "wxyz");
    15.         dfs(0, digits, new StringBuilder(), map, res);
    16.         return res;
    17.     }
    18.     public void dfs(int index, String digits, StringBuilder sb, Map<Character, String> map, List<String> res) {
    19.         if(index==digits.length()) {
    20.             //说明数字已经处理到尾部
    21.             res.add(new String(sb));
    22.             return;
    23.         }
    24.         //没有处理完，就处理当前位置的数字(获取当前数字所对应的所有字符)
    25.         String str = map.get(digits.charAt(index));
    26.         //循环遍历当前字符并递归处理下一个数字
    27.         for(int i=0; i<str.length(); i++) {
    28.             sb.append(str.charAt(i));
    29.             //递归
    30.             dfs(index+1, digits, sb, map, res);
    31.             //回溯
    32.             sb.deleteCharAt(sb.length()-1);
    33.         }
    34.  
    35.     }

  • 相关阅读:
    Transformers入门：实战Ubuntu使用huggingface上的语句情感分类模型+配环境（2024.02.20）
    Maven
    阿里云服务器企业级和入门级实例规格有何区别？如何选择？
    Connor学JVM - 类加载机制
    Deep Learning for Anomaly Detection: A Review
    商标注册初审公告后可以使用吗？
    孔松（信通院）-数字化时代云安全能力建设及趋势
    Linux：CentOS7 开启路由转发
    PS-滤镜
    关于标准IO缓冲区的问题
  • 原文地址：https://blog.csdn.net/weixin_47651920/article/details/124227200