关于leetcode:leetcode-字符串

@TOC

字符串循环移位蕴含

编程之美 3.1

s1 = AABCD, s2 = CDAA
Return : true

题解: 给定两个字符串 s1 和 s2,要求断定 s2 是否可能被 s1 做循环移位失去的字符串蕴含。
s1 进行循环移位的后果是 s1s1 的子字符串,因而只有判断 s2 是否是 s1s1 的子字符串即可。

字符串循环移位

编程之美 2.17

s = "abcd123" k = 3
Return "123abcd"

题解:
将字符串向右循环挪动 k 位。
将 abcd123 中的 abcd 和 123 独自翻转,失去 dcba321,而后对整个字符串进行翻转,失去 123abcd。

字符串中单词的翻转

程序员代码面试指南

s = "I am a student"
Return "student a am I"

题解:
将每个单词翻转,而后将整个字符串翻转。


242. 无效的字母异位词* (简略)

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

示例 1:

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

示例 2:

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

阐明:
你能够假如字符串只蕴含小写字母。
进阶:
如果输出字符串蕴含 unicode 字符怎么办?你是否调整你的解法来应答这种状况?

题解:
1.转换为数组再排序
将两个字符串排序,字母异位词排序后截然不同。
首先判断长度是否相等,不相等间接返回false;

class Solution {
   public boolean isAnagram(String s, String t) {
    //长度不相等,立刻返回false
    if (s.length() != t.length()) {
        return false;
    }
    //字符串转化为数组
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    //数组排序
    Arrays.sort(str1);
    Arrays.sort(str2);
    //数组比拟
    return Arrays.equals(str1, str2);
    }
}

工夫复杂度O(nlogn)
空间复杂度O(1): 空间取决于排序实现,如果应用 heapsort,通常须要O(1) 辅助空间。留神,在 Java 中,toCharArray() 制作了一个字符串的拷贝,所以它破费 O(n) 额定的空间,然而咱们疏忽了这一复杂性剖析,因为:这依赖于语言的细节。 这取决于函数的设计形式。例如,能够将函数参数类型更改为 char[]。

2. 桶计数

// 字母桶计数ver1:
// 若两个字符串长度不等,立刻返回false
// 先对s中字符计数
// 对t中字符计数,t中相应字符计数减1,若某个字母计数小于0,立刻返回false
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] table = new int[26];
        if (s.length() != t.length()){
            return false;
        }
        //s中的字符计数
        for (int i= 0; i<s.length(); i++){
            table[s.charAt(i)-'a']++;   
        }
        
        //s计数根底上,t中相应字符计数减1
        for (int i = 0; i<t.length(); i++){
            table[t.charAt(i) - 'a']--;
            if (table[t.charAt(i) - 'a'] < 0)   //若某一个字符计数小于0时,立刻返回false
                return false;
        }
        return true;
    }
}
// 字母桶计数ver2:
// 若两个字符串长度不等,立刻返回false
// 先对s中字符计数
// 查看字母表是否每个字符计数为0,不是返回false
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] table = new int[26];
        if (s.length() != t.length()){
            return false;
        }
        //s中的字符计数
        for (int i= 0; i<s.length(); i++){
            table[s.charAt(i)-'a']++;   
            table[t.charAt(i)-'a']--;
        }
        
        //s计数根底上,t中相应字符计数减1
        for (int i = 0; i<26; i++){
            if (table[i]!=0)
                return false;
        }
        return true;
    }
}

工夫复杂度O(n)
空间复杂度O(1)


409. 最长回文串

给定一个蕴含大写字母和小写字母的字符串,找到通过这些字母结构成的最长的回文串。
在结构过程中,请留神辨别大小写。比方 “Aa” 不能当做一个回文字符串。
留神:
假如字符串的长度不会超过 1010。

示例 1:

输出:
"abccccdd"
输入:
7

解释:
咱们能够结构的最长的回文串是”dccaccd”, 它的长度是 7。

题解:
对于回文字符串,最多只有一个字符的个数是1个,其余字符必为偶数个
用一个桶统计每个呈现的字符的个数。
某字母个数为偶数个,加上该字母个数
某字母个数为奇数个,加上该字母的个数再减1
若后果长度小于原字符串长度:后果长度再加1

class Solution {
    public int longestPalindrome(String s) {
        int res = 0;
        //大写和小写字母之间有6个其余字符,因而数组大小:52+6
        int[] bucket = new int[58];
        
        for (int i = 0; i<s.length(); i++){
            bucket[s.charAt(i) - 'A'] ++; 
        }
        int flag = 0;
        for (int x: bucket){
            res += x - (x & 1);  //取x的最大偶数个,若x为奇数,则减1
        }
        //若后果长度比s长度小,再加上一个字母的长度
        return res<s.length()? res+1: res;
    }
}

工夫复杂度O(n)
空间复杂度O(1)


5. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你能够假如 s 的最大长度为 1000。

示例 1:

输出: "babad"
输入: "bab"
留神: "aba" 也是一个无效答案。

示例 2:

输出: "cbbd"
输入: "bb"
// 核心扩大
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int max_len = 1;
        int start = 0;
        int n = s.length();
        for(int i = 0; i<n; i++){
            int left = i-1; 
            int right = i+1;
            while(left>=0 && s.charAt(left) == s.charAt(i)){
                left--;
            }
            while (right<n && s.charAt(right) == s.charAt(i)){
                right++;
            }
            while(left>=0 && right<n && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            if (right-left-1 > max_len){
                max_len = right-left-1;
                start = left+1;
            }
        }
        return s.substring(start, start+max_len);
    }
}

工夫复杂度O(n^2)
空间复杂度O(1)


647. 回文子串

给定一个字符串,你的工作是计算这个字符串中有多少个回文子串。
具备不同开始地位或完结地位的子串,即便是由雷同的字符组成,也会被视作不同的子串。

示例 1:

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

示例 2:

输出:"aaa"
输入:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提醒:
输出的字符串长度不会超过 1000 。


205. 同构字符串

给定两个字符串 s 和 t,判断它们是否是同构的。
如果 s 中的字符能够被替换失去 t ,那么这两个字符串是同构的。
所有呈现的字符都必须用另一个字符替换,同时保留字符的程序。两个字符不能映射到同一个字符上,但字符能够映射本人自身。

示例 1:

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

示例 2:

输出: s = "foo", t = "bar"
输入: false

示例 3:

输出: s = "paper", t = "title"
输入: true

阐明:
你能够假如 s 和 t 具备雷同的长度。

题解:
1. 两个哈希表
依据题意,s惟一地映射到t, 且t惟一地映射到s.

如 s = "foo", t = "bar" 不同构
o -> a
o -> r
o 映射到了两个字母
如s = "ab", t = "cc"不同构
a -> c
b -> c
c 被映射了两次
反过来由 t 映射到 s
c -> a 
c -> b
c 映射到了两个字母

因而须要验证 s->t 成立,且 t->s 成立

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> map1 = new HashMap<>();  //s->t
        Map<Character, Character> map2 = new HashMap<>();  //t->s
        
        for (int i = 0; i < s.length(); i++){
            //map1中不蕴含s[i]的映射, map2也不蕴含t[i]的映射,则将s[i]<->t[i] 退出映射表中
            if (!map1.containsKey(s.charAt(i)) && !map2.containsKey(t.charAt(i))){  
                map1.put(s.charAt(i), t.charAt(i));
                map2.put(t.charAt(i), s.charAt(i));
            }
            else{
                //若map1中存在s[i]的映射,但s[i]-/>t[i], 返回false
                if (map1.containsKey(s.charAt(i)) && map1.get(s.charAt(i)) != t.charAt(i))
                    return false;
                //若map1中存在t[i]的映射,但t[i]-/>t[i], 返回false
                else if (map2.containsKey(t.charAt(i)) && map2.get(t.charAt(i))!= s.charAt(i))
                    return false;
            } 
        }
        return true;
    }
}

工夫复杂度O(n)
空间复杂度O(n)

2. 一个哈希表
s -> t 与 t -> s 两个方向分次进行

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

工夫复杂度O(n)
空间复杂度O(n)


9. 回文数

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

示例 1:

输出: 121
输入: true

示例 2:

输出: -121
输入: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因而它不是一个回文数。

示例 3:

输出: 10
输入: false
解释: 从右向左读, 为 01 。因而它不是一个回文数。

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

题解:
1. 数字转化为字符串

2. 将整个数字翻转
回文数翻转后和原来的数相等。
翻转的形式:

revertedNum = revertedNum*10 + temp%10;
temp = temp/10;

class Solution {

public boolean isPalindrome(int x) {
    if (x<0 || ( x%10 == 0 && x!=0)){  //留神边界条件
        return false;
    }
    int temp = x;
    int revertedNum = 0;
    while (temp > 0){
        revertedNum = revertedNum*10 + temp%10;
        temp = temp/10;
    }
    return x == revertedNum;
}

}

工夫复杂度O(log10(n))
空间复杂度O(1)


**3. 翻转一半的数**
翻转了一半时: x < revertedNum
同时留神,当原数有奇数位数时,翻转后的数会多一位,只有再除以10而后比拟即可。
最初留神边界条件。
- 当x为正数时,不是回文数
- 当x非0,但最初一位为0时,不是回文数

class Solution {

public boolean isPalindrome(int x) {
    if (x<0 || ( x%10 == 0 && x!=0)){  //留神边界条件
        return false;
    }
    
    int revertedNum = 0;
    while (x > revertedNum){
        revertedNum = revertedNum*10 + x%10;
        x = x/10;
    }
    return x == revertedNum || x == revertedNum/10;
}

}

工夫复杂度O(log10(n))
空间复杂度O(1)

***

## 696. 计数二进制子串

>给定一个字符串 s,计算具备雷同数量0和1的非空(间断)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的。
反复呈现的子串要计算它们呈现的次数。

**示例 1 :**

输出: “00110011”
输入: 6
解释: 有6个子串具备雷同数量的间断1和0:“0011”,“01”,“1100”,“10”,“0011” 和 “01”。

>请留神,一些反复呈现的子串要计算它们呈现的次数。
另外,“00110011”不是无效的子串,因为所有的0(和1)没有组合在一起。

**示例 2 :**

输出: “10101”
输入: 4
解释: 有4个子串:“10”,“01”,“10”,“01”,它们具备雷同数量的间断1和0。


**留神:**
s.length 在1到50,000之间。
s 只蕴含“0”或“1”字符。

**题解:**
**1. 按字符分组**
将字符串 `s` 转换为 `arr` 数组示意字符串中雷同字符间断块的长度。例如,如果 s=“11000111000000”,则 arr=[2,3,3,6]。
-  `'0' * k + '1' * k` 或 `'1' * k + '0' * k` 模式的每个二进制字符串,有k个子串。
- 对于相邻的两个字符块,`arr[i-1]` 和`arr[i]`的子串个数为`min(arr[i-1], arr[i])`

//按字符分组
class Solution {

public int countBinarySubstrings(String s) {
    int res = 0;
    int n = s.length();
    if (n == 0 || n == 1){
        return res;
    }
    
    //按字符分组,寄存到arr中
    int[] arr = new int[n];
    arr[0] = 1;
    int index = 0;
    for (int i = 1; i < s.length(); i++){
        if (s.charAt(i) == s.charAt(i-1)){
            arr[index]++; 
        }else{
            arr[++index] = 1;
        }
    }
    //计算每个相邻字符块的字串个数
    for (int i = 1; i<n; i++){
        res += Math.min(arr[i], arr[i-1]);
    }
    return res;
}

}

工夫复杂度O(n)
空间复杂度O(n)

**2. 线性扫描**
时时记录后果

class Solution {

 public int countBinarySubstrings(String s) {
    int n = 0, pre = 0, curr = 1, len = s.length()-1;
    for (int i = 0; i < len; ++i) {
        if (s.charAt(i) == s.charAt(i+1)) 
            curr++;
        else{
            pre = curr; 
            curr = 1;
        }               
        if (pre >= curr)
            ++n;
    }
   return n;
}

}

工夫复杂度O(n)
空间复杂度O(1)

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据