初级算法之字符串

た入场券 2024-03-30 08:44 83阅读 0赞

### [344. 反转字符串][344.] ###

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

#### 思路一: ####

从中间开始向两边遍历,然后两边交换位置,最终获得字符串的反转

//
    class Solution {
        public void reverseString(char[] s) {
            int len = s.length,size = len;
            for(int i = 0;i < len/2;i++){
                size--;
                char tmp = s[i];
                s[i] = s[size];
                s[size] = tmp;
            }
        }
    }

#### 思路二: ####

使用位运算,每次异或进行赋值

class Solution {
        public void reverseString(char[] s) {
            int l = 0;
            int r = s.length - 1;
            while (l < r) {
                s[l] ^= s[r];  //构造 a ^ b 的结果，并放在 a 中
                s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
                s[l] ^= s[r];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
                l++;
                r--;
            }
        }
    }

### [541. 反转字符串 II][541. _ II] ###

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

思路:

参考上面题目,其实思路差不多每次反抓2k字符里面的前k个,如果最后的字符少于k,则直接全部反转.

//解法一
    class Solution {
        public String reverseStr(String s, int k) {
            StringBuffer res = new StringBuffer();
            int length = s.length();
            int start = 0;
            while (start < length) {
                // 找到k处和2k处
                StringBuffer temp = new StringBuffer();
                // 与length进行判断，如果大于length了，那就将其置为length
                int firstK = (start + k > length) ? length : start + k;
                int secondK = (start + (2 * k) > length) ? length : start + (2 * k);
    
                //无论start所处位置，至少会反转一次
                temp.append(s.substring(start, firstK));
                res.append(temp.reverse());
    
                // 如果firstK到secondK之间有元素，这些元素直接放入res里即可。
                if (firstK < secondK) { //此时剩余长度一定大于k。
                    res.append(s.substring(firstK, secondK));
                }
                start += (2 * k);
            }
            return res.toString();
        }
    }
    
    //方法二
    class Solution {
        public String reverseStr(String s, int k) {
            char[] ch = s.toCharArray();
            for(int i = 0; i < ch.length; i += 2 * k){
                int start = i;
                //这里是判断尾数够不够k个来取决end指针的位置
                int end = Math.min(ch.length - 1, start + k - 1);
                //用异或运算反转 
                while(start < end){
                    ch[start] ^= ch[end];
                    ch[end] ^= ch[start];
                    ch[start] ^= ch[end];
                    start++;
                    end--;
                }
            }
            return new String(ch);
        }
    }
    
    //方法三
    class Solution {
        public String reverseStr(String s, int k) {
            char[] chars = s.toCharArray();
            for (int i = 0; i < chars.length; i+=2*k) {
                if(i+k<=chars.length){
                    reverse(chars,i,i+k-1);
                    continue;
                }
                reverse(chars,i,chars.length-1);
                
            }
            return new String(chars);   
    
        }
        public void reverse(char[] chars,int i,int j){
            for (;i<j;i++,j--) {
                char temp = chars[i];
                chars[i] = chars[j];
                chars[j] = temp;
            }
        }
    }

### [7. 整数反转][7.] ###

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 \[−231, 231 − 1\] ，就返回 0。

思路:

**可以直接存一个临时的翻转结果，如果这个翻转结果除以10不等于上一个结果，说明有溢出。**

class Solution {
        public int reverse(int x) {
            int res=0;
            while(x!=0){
                int temp=res*10+x%10;
                x=x/10;
                if(temp/10!=res){
                    return 0;
                }
                res=temp;
            }
            return res;
        }
    }

### [387. 字符串中的第一个唯一字符][387.] ###

给定一个字符串 s ，找到 *它的第一个不重复的字符，并返回它的索引* 。如果不存在，则返回 -1 。

思路:

定义一个大小26的字符数组,依此遍历字符串的每一个字符,遇到对应的就对对应的字符数组的数字加1,然后再次循环遍历,如果该值等于1,便返回该数组索引,否则返回-1.

class Solution {
        public int firstUniqChar(String s) {
            int[] freq = new int[26];
            char[] chars = s.toCharArray();
            for (char ch : chars) {
                freq[ch - 'a']++;
            }
            for (int i = 0; i < chars.length; i++) {
                if (freq[chars[i] - 'a'] == 1) {
                    return i;
                }
            }
            return -1;
        }
    }

### [剑指 Offer II 032. 有效的变位词][Offer II 032.] ###

给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。

注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）

#### 思路: ####

先定义一个大小26的数组,遍历第一个字符串的每一个字符,然后统计对应26个字符的出现的次数,然后对第二个字符串进行遍历,遇到了就减一,最后遍历该数组,如果每一个值都是0,则是有效的,否则不是.

class Solution {
        public boolean isAnagram(String s, String t) {
            int[] record = new int[26];
    
            for (int i = 0; i < s.length(); i++) {
                record[s.charAt(i) - 'a']++;
            }
    
            for (int i = 0; i < t.length(); i++) {
                record[t.charAt(i) - 'a']--;
            }
            
            for (int count: record) {
                if (count != 0) {
                    return false;
                }
            }
            return true;
        }
    }

### [125. 验证回文串][125.] ###

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false

**思路:**

调用api方法把字符串转换成小写的,然后创建一个StringBuilder,如果遇到数字和字符,便加进去,最后比较该字符和反转后的字符

class Solution {
        public boolean isPalindrome(String s) {
            if (s == null) return true;
            s = s.toLowerCase();
            int l = s.length();
            StringBuilder str = new StringBuilder(l);
            for (char c : s.toCharArray()) {
                if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z')) {
                    str.append(c);
                }
            }
            return str.toString().equals(str.reverse().toString());
        }
    }

##### [8. 字符串转换整数 (atoi)][8. _ _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 。

返回整数作为最终结果。

public class Solution {
        public int myAtoi(String str) {
            char[] chars = str.toCharArray();
            int n = chars.length;
            int idx = 0;
            while (idx < n && chars[idx] == ' ') {
                // 去掉前导空格
                idx++;
            }
            if (idx == n) {
                //去掉前导空格以后到了末尾了
                return 0;
            }
            boolean negative = false;
            if (chars[idx] == '-') {
                //遇到负号
                negative = true;
                idx++;
            } else if (chars[idx] == '+') {
                // 遇到正号
                idx++;
            } else if (!Character.isDigit(chars[idx])) {
                // 其他符号
                return 0;
            }
            int ans = 0;
            while (idx < n && Character.isDigit(chars[idx])) {
                int digit = chars[idx] - '0';
                if (ans > (Integer.MAX_VALUE - digit) / 10) {
                    // 本来应该是 ans * 10 + digit > Integer.MAX_VALUE
                    // 但是 *10 和 + digit 都有可能越界，所有都移动到右边去就可以了。
                    return negative? Integer.MIN_VALUE : Integer.MAX_VALUE;
                }
                ans = ans * 10 + digit;
                idx++;
            }
            return negative? -ans : ans;
        }
    }

## [28. 找出字符串中第一个匹配项的下标][28.] ##

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

class Solution {
        public  int strStr(String haystack, String needle) {
            int num1=haystack.length(),num2=needle.length(),num=-1;
            if(num2==0)
                num=0;
            else
            for(int i=0;i<=num1-num2;i++){
                int j=0,k=i;
                while(j<num2){
                    if(haystack.charAt(k)==needle.charAt(j)){
                        k++;
                        j++;
                    }
                    else 
                        break;
                }
                if(j==num2){
                    num=i;
                    break;
                }
            }
            return num;
    
        }
    }

## [38. 外观数列][38.] ##

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”

countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

![a32ef27845dccdcba105a8df8334461a.png][]

思路:

该题目说白了就是找某一个字符串的连续数字的个数,定义一个指针,先获得某个值,然后进行遍历,如果相等,指针++,然后append差值同时append该值,反复遍历

class Solution {
        public String countAndSay(int n) {
            String str = "1";
            for (int i = 2; i <= n; ++i) {
                StringBuilder sb = new StringBuilder();
                int start = 0;
                int pos = 0;
    
                while (pos < str.length()) {
                    while (pos < str.length() && str.charAt(pos) == str.charAt(start)) {
                        pos++;
                    }
                    sb.append(Integer.toString(pos - start)).append(str.charAt(start));
                    start = pos;
                }
                str = sb.toString();
            }
            
            return str;
        }
    }

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

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

思路:

获得首个字符作为指针

对数组进行遍历,如果有不是以该字符开始的就( **startsWith() 方法用于检测字符串是否以指定的前缀开始)就进行分割**

class Solution {
        public String longestCommonPrefix(String[] strs) {
            if(strs.length==0) return "";
            String s=strs[0];
            for(String string:strs){
                while(!string.startsWith(s)){
                    if(s.length()==0) return "";
                    s=s.substring(0,s.length()-1);
    
                }
            }
            return s;
    
        }
    }

## [剑指 Offer II 095. 最长公共子序列][Offer II 095.] ##

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路:

典型的动态规划问题,

class Solution {
        public int longestCommonSubsequence(String text1, String text2) {
            int m = text1.length();
            int n = text2.length();
            int[][] dp = new int[m+1][n+1];
            for(int i=1; i<=m; i++){
                char ch1 = text1.charAt(i-1);
                for(int j=1; j<=n; j++){
                    char ch2 = text2.charAt(j-1);
                    if(ch1 == ch2) dp[i][j] = dp[i - 1][j - 1] + 1;
                    else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);               
                }
            }
            return dp[m][n];
        }
    }

[344.]: https://leetcode.cn/problems/reverse-string/
[541. _ II]: https://leetcode.cn/problems/reverse-string-ii/
[7.]: https://leetcode.cn/problems/reverse-integer/
[387.]: https://leetcode.cn/problems/first-unique-character-in-a-string/
[Offer II 032.]: https://leetcode.cn/problems/dKk3P7/
[125.]: https://leetcode.cn/problems/valid-palindrome/
[8. _ _atoi]: https://leetcode.cn/problems/string-to-integer-atoi/
[28.]: https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
[38.]: https://leetcode.cn/problems/count-and-say/
[a32ef27845dccdcba105a8df8334461a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a9ce5d57edef44428cd40c1789edc991.png
[14.]: https://leetcode.cn/problems/longest-common-prefix/
[Offer II 095.]: https://leetcode.cn/problems/qJnOS7/