Leetcode Java

Leetcode Java

StringBuilder

• 686. 重复叠加字符串匹配
• 2109. 向字符串添加空格
• 481. 神奇字符串

686. 重复叠加字符串匹配

Leetcode
如果 a 不是 b 的子串并且 b 由 a 的前后两部分组成，则只需要两个 a 即可。
如：“abc” “ca” -> “abcabc” 即 x + 1，此时 x = 1
如果 a 是 b 的子串并且 b 的两端（或一端）可以组成 a，那么只需要最多拆分一个 a。
如：“abc” “abcabc” 不用拆分 a ; “abc” “cabca” b 两端拆分一个 a。即 x，此时 x >= 1

否则的话返回 -1

class Solution {
    public int repeatedStringMatch(String a, String b) {
        // 剪枝 b 中包含了不在 a 中的字符，返回 -1 
		// for (int i = 0; i < b.length(); i++){
        //     if (a.indexOf​(b.charAt(i)) == -1) return -1;
        // }

		boolean[] exist = new boolean[26];
		for (char ch : a.toCharArray())	exist[ch - 'a'] = true;
		for (char ch : b.toCharArray()) if (!exist[ch - 'a']) return -1;		
		
        int x = (int)Math.ceil((double)b.length() / a.length());
        if (a.repeat​(x).contains(b)) return x;
        if (a.repeat​(x + 1).contains(b)) return x + 1;

        // StringBuilder sb = new StringBuilder();
        // sb.append(a.repeat​(x));
        // if (sb.indexOf(b) > -1) return x;
        // sb.append(a);
        // if (sb.indexOf(b) > -1) return x + 1;
      
        return -1;
    }
}

2109. 向字符串添加空格

Leetcode

class Solution {
    public String addSpaces(String s, int[] spaces) {
    	// 方法一：String  + ，超时
        // String res = s.substring(0, spaces[0]);
        // int n = spaces.length;
        // for (int i = 1; i < n; i++){
        //     res += " " + s.substring(spaces[i - 1], spaces[i]);
        // }
        // res += " " + s.substring(spaces[n - 1]);
        // return res;
        
		// 方法二：改成 StringBuilder 
        // int n = spaces.length;
        // StringBuilder sb = new StringBuilder(s.substring(0, spaces[0]));
        // for (int i = 1; i < n; i++){
        //     sb.append(" ");
        //     sb.append(s.substring(spaces[i - 1], spaces[i]));        
        // }
        // sb.append(" ");
        // sb.append(s.substring(spaces[n - 1]));

        // return sb.toString();
        
        // 方法三：逆序 单个字符加入
        int k = spaces.length - 1, n = s.length() - 1;
        StringBuilder sb = new StringBuilder();
        for(int i = n; i >= 0; i--){
            sb.append(s.charAt(i));
            if(k >= 0 && i == spaces[k]){
                sb.append(" ");
                --k;
            }
        }

        return sb.reverse().toString();
    }
}

481. 神奇字符串

Leetcode
知识点： StringBuilder, charAt, append, repeat.

class Solution {
    public int magicalString(int n) {
        // “1221121221221121122 ......”
        StringBuilder sb = new StringBuilder("122");
        String end = "1"; // 1 和 2 交替
        for (int i = 2; sb.length() < n; i++){ // 从第三个数开始生成          
            int num = sb.charAt(i) - '0';
            sb.append(end.repeat(num));
            end = (end == "2") ? "1" : "2"; 
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            if (sb.charAt(i) == '1') res++;
        }
        return res;
    }
}