首页 > 其他 > 详细

[leetcode刷题]——字符串

时间:2021-01-18 22:23:46      阅读:3      评论:0      收藏:0      [点我收藏+]

一、两个字符串包含的字符是否完全相同

242.有效的字母异位词 (easy) 2021-01-18

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true
示例 2:

输入: s = "rat", t = "car"
输出: false

 

说明:
你可以假设字符串只包含小写字母。

 

进阶:
如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?

 

题解:如果只是26个小写字母,那么建立一个长度为26的数组记录每个字母出现的频次信息就够了。如果包含unicode字符,需要使用map来存储。

 

class Solution {
    public boolean isAnagram(String s, String t) {
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        if(sarr.length != tarr.length){
            return false;
        }
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < sarr.length; i++){
            map.put(sarr[i], map.getOrDefault(sarr[i], 0) + 1);
        }
        for(int i = 0; i < sarr.length; i++){
            if(!map.containsKey(tarr[i])){
                return false;
            }else if(map.get(tarr[i]) == 1){
                map.remove(tarr[i]);
            }else{
                map.put(tarr[i], map.get(tarr[i]) - 1);
            }
        }
        if(map.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}

 

 

二、计算一组字符集合可以组成回文字符串的最大长度

409.最长回文串  (easy) 2021-01-18

给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。

在构造过程中,请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例 1:

输入:
"abccccdd"

输出:
7

     这个题我的做法是将元素存放哈希表中,记录频次信息,然后取出所有的values值进行操作。

  这个题遇到了一个bug记录一下:

  map.values( )  返回的是Collection类型。Collection被定义为接口,需要进行实例化,但是将其强转成(List)又会报错。

  最后使用的是ArrayList的一个构造方法,ArrayList(Collection<? extends E> 。

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for(char i : s.toCharArray()){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        //Collection<Integer> coll = map.values(); //map的values值是以collection的形式返回
        List coll = new ArrayList<Integer>(map.values());
        Iterator iterator = coll.iterator();
        int flag = 0; //记录回文串是否为奇数的标志
        int sum = 0;
        while(iterator.hasNext()){
            int temp = (int)iterator.next();
            if(flag == 0 && temp % 2 != 0){
                flag = 1;
            }
            sum = sum + temp / 2;
        }
        return sum * 2 + flag;
    }
}

 

三、字符串同构

205.同构字符串

给定两个字符串 s 和 t,判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。

示例 1:

输入:s = "egg", t = "add"
输出:true

  

class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        Map<Character, Character> map = new HashMap<>();
        if(sarr.length != tarr.length) return false;
        for(int i = 0; i < sarr.length; i++){
            if(!map.containsKey(sarr[i]) && !map.containsValue(tarr[i])){
                map.put(sarr[i], tarr[i]);
            }else if((map.containsKey(sarr[i]) && map.get(sarr[i]) == tarr[i])){
                
            }else{
                return false;
            }
        }
        return true;
    }
}

  使用数组来记录好像更简单。

class Solution {
    public boolean isIsomorphic(String s, String t) {
    int[] preIndexOfS = new int[256];
    int[] preIndexOfT = new int[256];
    for (int i = 0; i < s.length(); i++) {
        char sc = s.charAt(i), tc = t.charAt(i);
        if (preIndexOfS[sc] != preIndexOfT[tc]) {
            return false;
        }
        preIndexOfS[sc] = i + 1;
        preIndexOfT[tc] = i + 1;
    }
    return true;
}
}

 

四、回文子字符串的个数

647.回文子串  (medium) 2021-01-18

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

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

示例 1:

输入:"abc"
输出:3
解释:三个回文子串: "a", "b", "c"

    感觉思路是一致的,我的代码四十多行,大佬的代码就十几行,我/(ㄒoㄒ)/~~

class Solution {
    public int countSubstrings(String s) {
        char[] arr = s.toCharArray();
        int sum = 0;
        for(int i = 0; i < arr.length; i++){
            sum += sum1(i, arr);
            sum += sum2(i, arr);
        }
        return sum;
    }

    //以i为中心的回文子串的个数
    public int sum1(int i, char[] arr){
        int k = 0;
        int sum = 0;
        boolean continual = true;  //判断是否连续地标志
        while(i - k >= 0 && i + k < arr.length){
            if(continual == true && arr[i - k] == arr[i + k]){
                sum++;
            }else{
                continual = false;
            }
            k++;
        }
        return sum;
    }

    //以i + 0.5为中心的回文子串的个数
    public int sum2(int i, char[] arr){
        int k = 1;
        int sum = 0;
        boolean continual = true;
        while(i + 1 - k >= 0 && i + k < arr.length){
            if(continual == true && arr[i + 1 - k] == arr[i + k]){
                sum++;
            }else{
                continual = false;
            }
            k++;
        }
        return sum ; 
    }
}

 

class Solution {
    private int cnt = 0;
    public int countSubstrings(String s) {
    for (int i = 0; i < s.length(); i++) {
        extendSubstrings(s, i, i);     // 奇数长度
        extendSubstrings(s, i, i + 1); // 偶数长度
    }
    return cnt;
}
private void extendSubstrings(String s, int start, int end) {
    while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
        start--;
        end++;
        cnt++;
    }
}
}

 

五、判断一个整数是否为回文数

9.回文数 (easy) 2021-01-18

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

你能不将整数转为字符串来解决这个问题吗?

     使用字符串确实简单。

class Solution {
    public boolean isPalindrome(int x) {
        String str = String.valueOf(x); 
        for(int i = 0 ; i < str.length() / 2; i++){
            if((int)str.charAt(i) != (int)str.charAt(str.length() - 1 - i)){
                return false;
            }
        }
        return true;
    }
}

  ·不使用字符串,更多的使用数学的方式。不停地使用余数成十以致两个数长度差在1以内。

class Solution {
    public boolean isPalindrome(int x) {
    if (x == 0) {
        return true;
    }
    if (x < 0 || x % 10 == 0) {
        return false;
    }
    int right = 0;
    while (x > right) {
        right = right * 10 + x % 10;
        x /= 10;
    }
    return x == right || x == right / 10;
}
}

 

 

六、统计二进制字符串中连续1和连续0数量相同地子字符串的个数

696.计数二进制子串  (easy) 2021-01-18

给定一个字符串 s,计算具有相同数量0和1的非空(连续)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的。

重复出现的子串要计算它们出现的次数。

示例 1 :

输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0:“0011”,“01”,“1100”,“10”,“0011” 和 “01”。

请注意,一些重复出现的子串要计算它们出现的次数。

另外,“00110011”不是有效的子串,因为所有的0(和1)没有组合在一起。

    

    这个题不容易,忙碌了几个小时的菜鸟程序员发现运行时间超出限制。

    写程序确实需要脑袋清醒,之前的思路正确但是嵌套循环太浪费运行时间。换换思路还是事半功倍。

class Solution {
    public int countBinarySubstrings(String s) {
        int sum = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != ‘0‘ && s.charAt(i) != ‘1‘){
                i++;
            }
            int k = 1;
            while(i - k + 1 >= 0 && i + k < s.length()){
                if(s.charAt(i - k + 1) == s.charAt(i) && s.charAt(i + k) !=  s.charAt(i) ){
                    sum++;
                    k++;
                }else{
                    break;
                }
            }
        }       
        return sum;
    }
}

   贴一个大佬的做法,算法确实妙。

class Solution {
    public int countBinarySubstrings(String s) {
    int preLen = 0, curLen = 1, count = 0;
    for (int i = 1; i < s.length(); i++) {
        if (s.charAt(i) == s.charAt(i - 1)) {
            curLen++;
        } else {
            preLen = curLen;
            curLen = 1;
        }
        if (preLen >= curLen) {
            count++;
        }
    }
    return count;
}
}

 

 

 

 

 

[leetcode刷题]——字符串

原文:https://www.cnblogs.com/nobita/p/14295200.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号