未命名分组 - 字符串 - 《数据结构 · Leetcode · SQL · 刷题笔记》

字符串

字符串

925. 长按键入

思路：使用两个指针判断当前的字符，如果一样的话两个都+1 如果不一样的话看看是不是和前一位一样，一样的话跳过

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int len1 = name.length();
        int len2 = typed.length();
        if(len2<len1){return false;}
        int i=0,j=0;
        while(i<len1 && j<len2){
            if(name.charAt(i)== typed.charAt(j)){
                i++;
                j++;
            }else if(j>0 && typed.charAt(j-1)== typed.charAt(j)){
                j++;
            }else{
                return false;
            }
        }
        if(i<len1){
            return false;
        }else{
            while(j<len2){
                if(i>0 && name.charAt(i-1)==typed.charAt(j)){
                    j++;
                }else{
                    return false;
                }
            }
            return true;
        }
    }
}

1002. 查找常用字符

这道题需要我们求的是，在这个数组里面，每一个str里面，每一个字符出现的次数。这个出现的次数是所有的共同次数。就用一个freq 和当前的str里面的频率。取得里面的最小值

class Solution {
    public List<String> commonChars(String[] A) {
        int[] freq = new int[26];
        List<String> res = new LinkedList<>();
        Arrays.fill(freq,Integer.MAX_VALUE);
        for(String str:A){
            int[] fre = new int[26];
            for (int i = 0; i < str.length(); i++) {
                fre[str.charAt(i)-'a']++;
            }
            for (int i = 0; i < 26; i++) {
                freq[i] = Math.min(fre[i],freq[i]);
            }
        }
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < freq[i]; j++) {
                res.add(String.valueOf((char)(i+'a')));
            }
        }
        return res;
    }
}

402. 移掉K位数字

扫描k次，每次找到后面比前面大的数，删掉，不然的话就删除最前面的数字。

class Solution {
    public String removeKdigits(String num, int k) {
        StringBuilder sb = new StringBuilder(num);
        if (num.length() == k) return "0";
        for (int i = 0; i < k; i++) {
            int index = 0;
            for (int j = 1; j < sb.length()&& sb.charAt(j)>=sb.charAt(j-1); j++) {
                index = j;
            }
            sb.delete(index,index+1);
            while (sb.length()>1&& sb.charAt(0)=='0'){
                sb.delete(0,1);
            }
        }
        return sb.toString();
    }
}

647. 回文子串

最简单的暴力的方法，遍历整个长度，截取里面的每一段，去判断一下。

class Solution {
    int res =  0;
    public int countSubstrings(String s) {
        for (int i = 0; i < s.length(); i++) {
            count(s,i,i);
            count(s,i,i+1);
        }
        return res;
    }
    private void count(String s, int start, int end) {
        while (start>=0&& end<s.length() && s.charAt(start) == s.charAt(end)){
            res++;
            start --;
            end++;
        }
    }
}

解法二：对于每一个位置的i，判断i开始的和i，i+1开始的。里面投几个回文串

class Solution {
    int res =  0;
    public int countSubstrings(String s) {
        for (int i = 0; i < s.length(); i++) {
            count(s,i,i);
            count(s,i,i+1);
        }
        return res;
    }
    private void count(String s, int start, int end) {
        while (start>=0&& end<s.length() && s.charAt(start) == s.charAt(end)){
            res++;
            start --;
            end++;
        }
    }
}

14. 最长公共前缀

思路：
先把里面的字符串拆分出来看一下，对于两个字符串我们怎么进行一个匹配？
用两个指针分别指向头，开始循环，遇到不一样的时候就break，记录相同的位置，做一个切片。
基本的操作就是这样的，加上列表的循环就是答案了。

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String ans = "";
        if(strs.length<1)return ans;

        ans = strs[0];

        for (int i=0;i<strs.length;i++){
            int j=0;
            for (int g=0;j<ans.length() && g<strs[i].length();j++,g++){
                if(ans.charAt(j)!=strs[i].charAt(g)){
                    break;
                }
            }
            ans = ans.substring(0,j);
        }
        return ans;
    }
}

8. 字符串转换整数 (atoi)

首先把空格给去掉，接着对正负号进行处理。最后是需要对溢出的情况做一个处理。在+和x10的情况里面都可能会出现溢出的情况。处理的方式 ans*10+tmp< Integer.MIN_VALUE ，做一个变化，就可以得到这个判断式子。

class Solution {
    public int myAtoi(String str) {
        char[] res = str.toCharArray();
        int i =0;
        while (i<res.length&&res[i]==' '){
            i++;
        }
        if(i == res.length) return 0;
        boolean isNagative = false;
        if(res[i] =='-'){
            isNagative =true;
            i++;
        }else if(res[i] =='+'){
            i++;
        }
        int ans = 0;
        while (i<res.length&&Character.isDigit(res[i])){
            int tmp = res[i] -'0';
            if(ans>(Integer.MAX_VALUE-tmp)/10){
                return isNagative?Integer.MIN_VALUE:Integer.MAX_VALUE;
            }
            ans=ans*10+tmp;
            i++;
        }
        return isNagative?-ans:ans;

    }
}

1071-字符串的最大公因数

思路：首先 str1+str2 ==str2+str1 然后使用辗转相除法

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        /*
        如果 str1 和 str2 存在最大公约数 str，那么就相当于 str1 和 str2 都是由 str 组成的，那么 str1 + str2 和 str2 + str1 应该是相等的
        如果不满足，那么不存在最大公约数

        我们可以通过 两个字符串的长度来求得最大公约数的长度
        比如 str1 = "ABABAB", str2 = "ABAB"
            len1 = 6         len2 = 4
            那么最大公约数 str = "AB"
                         len = 2
        */
        if(!(str1+str2).equals(str2+str1)){
            return "";
        }

        return str1.substring(0,gcd(str1.length(),str2.length()));

    }

    private int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
}

面试题 01.06. 字符串压缩

思路:
使用一个Stringbuilder来接受判断的字符。从头开始遍历，记录一下pre和cur，做一下比较。如果一致的话，次数加一。如果不是的话，将这个字符和次数添加到res里面。最终比较一下里面的大小。

class Solution {
    public String compressString(String S) {
        if(S ==null || S.length()==0){
            return S;
        }

        StringBuilder res = new StringBuilder();

        char pre = S.charAt(0);
        int times = 1;

        for(int i=1;i<S.length();i++){
            char cur = S.charAt(i);
            if(cur == pre){
                times++;
            }else{
                res.append(pre);
                res.append(times);
                pre = cur;
                times = 1;
            }
        }
        res.append(pre);
        res.append(times);

        if(res.length()>=S.length()){
            return S;
        }
        return res.toString();

    }
}

804. 唯一摩尔斯密码词

思路：
吧每一个单词转换为摩斯电码，加入到set中，最后取出size

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};

        Hash  Set<String> set = new HashSet<>();
        for(String word:words){
            StringBuilder res = new StringBuilder();
            for(int i=0;i<word.length();i++){
                res.append(codes[word.charAt(i)-'a']);
            }
            set.add(res.toString());
        }
        return set.size();
    }
}

409. 最长回文串

思路：
首先需要统计一下给定字符串的各个字母出现的次数。这里可以使用哈希表来做，也可以使用数组来做。统计完之后我们需要计算res。因为回文串中最多只有一个字母可以出现奇数次。假如a出现了3次我们需要res增加2次。如果是a出现了1次。不能增加。这里有一个好方法，res+=x-（x&1）。非常的漂亮。
ascii 码中 A是65 a是97

class Solution {
    public int longestPalindrome(String s) {
        if(s.length()<1) return 0;
        HashMap<Character,Integer> map = new HashMap<>();

        for(int i=0;i<s.length();i++){
            if(!map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),1);
            }else {
                map.put(s.charAt(i),map.get(s.charAt(i))+1);
            }
        }
        int res = 0;
        System.out.println(map.toString());
        for(Character c:map.keySet()){
           res += map.get(c)-(map.get(c)&1);
        }
        return res<s.length()?res+1:res;
    }
}