初级算法之字符串

举报
林寻星辰 发表于 2023/03/22 15:05:59 2023/03/22
【摘要】 344. 反转字符串编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。思路一:从中间开始向两边遍历,然后两边交换位置,最终获得字符串的反转//class Solution { public void reverseString(char[] s) { int len = s.length,size = len; for(in...

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

给定一个字符串 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. 整数反转

给你一个 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. 字符串中的第一个唯一字符

给定一个字符串 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. 有效的变位词

给定两个字符串 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. 验证回文串

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

给你一个字符串 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)

请你来实现一个 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. 找出字符串中第一个匹配项的下标

给你两个字符串 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. 外观数列

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

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

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

countAndSay(1) = "1"

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

思路:

该题目说白了就是找某一个字符串的连续数字的个数,定义一个指针,先获得某个值,然后进行遍历,如果相等,指针++,然后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. 最长公共前缀

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

如果不存在公共前缀,返回空字符串 ""

思路:

获得首个字符作为指针

对数组进行遍历,如果有不是以该字符开始的就( 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. 最长公共子序列

给定两个字符串 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];
    }
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。