算法——字符串（一）

1、给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

 1 class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         int len=s.length();
 4         int max=0;
 5         int right=0;
 6         Set<Character> set=new HashSet<>();
 7         for(int i=0;i<len;i++){//左边界
 8             if(i!=0)set.remove(s.charAt(i-1));
 9             while(right<len&&!set.contains(s.charAt(right))){
10                 set.add(s.charAt(right));
11                 right++;
12 
13             }
14             max=Math.max(max,right-i);
15         }
16         return max;
17     }
18 }

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

 1 //中心扩散法
 2 class Solution {
 3     public String longestPalindrome(String s) {
 4         if (s == null || s.length() < 1) {
 5             return "";
 6         }
 7         int start = 0, end = 0;
 8         for (int i = 0; i < s.length(); i++) {
 9             int len1 = expandAroundCenter(s, i, i);
10             int len2 = expandAroundCenter(s, i, i + 1);
11             int len = Math.max(len1, len2);
12             if (len > end - start) {
13                 start = i - (len - 1) / 2;
14                 end = i + len / 2;
15             }
16         }
17         return s.substring(start, end + 1);
18     }
19 
20     public int expandAroundCenter(String s, int left, int right) {
21         while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
22             --left;
23             ++right;
24         }
25         return right - left - 1;
26     }
27 }

3、字符串转整数

 1 class Solution {
 2     public int myAtoi(String str) {
 3         int len = str.length();
 4         // str.charAt(i) 方法回去检查下标的合法性，一般先转换成字符数组
 5         char[] charArray = str.toCharArray();
 6 
 7         // 1、去除前导空格
 8         int index = 0;
 9         while (index < len && charArray[index] == ' ') {
10             index++;
11         }
12 
13         // 2、如果已经遍历完成（针对极端用例 "      "）
14         if (index == len) {
15             return 0;
16         }
17 
18         // 3、如果出现符号字符，仅第 1 个有效，并记录正负
19         int sign = 1;
20         char firstChar = charArray[index];
21         if (firstChar == '+') {
22             index++;
23         } else if (firstChar == '-') {
24             index++;
25             sign = -1;
26         }
27 
28         // 4、将后续出现的数字字符进行转换
29         // 不能使用 long 类型，这是题目说的
30         int res = 0;
31         while (index < len) {
32             char currChar = charArray[index];
33             // 4.1 先判断不合法的情况
34             if (currChar > '9' || currChar < '0') {
35                 break;
36             }
37 
38             // 题目中说：环境只能存储 32 位大小的有符号整数，因此，需要提前判：断乘以 10 以后是否越界
39             if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && (currChar - '0') > Integer.MAX_VALUE % 10)) {
40                 return Integer.MAX_VALUE;
41             }
42             if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (currChar - '0') > -(Integer.MIN_VALUE % 10))) {
43                 return Integer.MIN_VALUE;
44             }
45 
46             // 4.2 合法的情况下，才考虑转换，每一步都把符号位乘进去
47             res = res * 10 + sign * (currChar - '0');
48             index++;
49         }
50         return res;
51     }
52 }

4、最长公共前缀

 1 //纵向扫描
 2 class Solution {
 3     public String longestCommonPrefix(String[] strs) {
 4         if (strs == null || strs.length == 0) {
 5             return "";
 6         }
 7         int length = strs[0].length();//第一个字符串的长度
 8         int count = strs.length;
 9         for (int i = 0; i < length; i++) {
10             char c = strs[0].charAt(i);
11             for (int j = 1; j < count; j++) {
12                 if (i == strs[j].length() || strs[j].charAt(i) != c) {
13                     return strs[0].substring(0, i);
14                 }
15             }
16         }
17         return strs[0];
18     }
19 }