算法|字符串

6. Z 字形变换

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        StringBuilder[] stringBuilder = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++){
            stringBuilder[i] = new StringBuilder();
        }
        int line = 0;
        int increase = 1;
        for (int i = 0; i < s.length(); i++){
            stringBuilder[line].append(s.charAt(i));
            if (line ==  numRows - 1) {
                increase = -1;
            } 
            if (line == 0) {
                increase = 1;
            }
            line += increase;
        }
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            result.append(stringBuilder[i]);
        }
        return result.toString();
    }
}

14. 最长公共前缀

class Solution {
    private String getCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = -1;
        for (int i = 0; i < length; i++){
            if (str1.charAt(i) == str2.charAt(i)) {
                index++;
            } else {
                break;
            }
        }
        return str1.substring(0, index + 1);
    }
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String str = strs[0];
        for (int i = 1; i < strs.length; i++){
            str = getCommonPrefix(str, strs[i]);
        }
        return str;
    }
}

43. 字符串相乘

class Solution {
    private String sum(String str1, String str2) {
        int i = str1.length() - 1;
        int j = str2.length() - 1;
        int add = 0;
        StringBuilder sb = new StringBuilder();
        while (i >= 0 || j >= 0) {
            int v1 = i < 0 ? 0 : str1.charAt(i) - '0';
            int v2 = j < 0 ? 0 : str2.charAt(j) - '0';
            int sum = v1 + v2 + add;
            sb.append(sum % 10);
            add = sum / 10;
            i--;
            j--;
        }
        if (add != 0) {
            sb.append(add % 10);
        }
        return sb.reverse().toString();
    }
    public String multiply(String num1, String num2) {
        if (num1 == null || "".equals(num1)) return num2;
        if (num2 == null || "".equals(num2)) return num1;
        if ("0".equals(num1) || "0".equals(num2)) return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        String result = "0";
        for (int i = len2 - 1; i >= 0; i--){
            StringBuilder sb = new StringBuilder();
            for (int j = len2 - 1; j > i; j--) {
                sb.append('0');
            }
            int n2 = num2.charAt(i) - '0';
            int add = 0;
            for (int j = len1 - 1; j >= 0; j--){
                int n1 = num1.charAt(j) - '0';
                int v = n2 * n1 + add;
                sb.append(v % 10);
                add = v / 10;
            }
            if (add != 0) {
                sb.append(add);
            }
            result = sum(result, sb.reverse().toString());
        } 
    
        return result;
    }
}

415. 字符串相加

class Solution {
    public String addStrings(String num1, String num2) {
        if (num1 == null || "".equals(num1)) return num2;
        if (num2 == null || "".equals(num2)) return num2;
        if ("0".equals(num1)) return num2;
        if ("0".equals(num2)) return num1;
        int i = num1.length() - 1;
        int j = num2.length() - 1;
        int add = 0;
        StringBuilder sb = new StringBuilder();
        while (i >= 0 || j >= 0) {
            int v1 = i < 0 ? 0 : num1.charAt(i) - '0';
            int v2 = j < 0 ? 0 : num2.charAt(j) - '0';
            // System.out.println(v1 + " " + v2);
            int sum = v1 + v2 + add;
            sb.append(sum % 10);
            add = sum / 10;
            i--;
            j--;
        }
        if (add != 0) {
            sb.append(1);
        }

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

class Solution {
    public String multiply(String num1, String num2) {
        if (num1 == null || "".equals(num1)) return num2;
        if (num2 == null || "".equals(num2)) return num1;
        if ("0".equals(num1) || "0".equals(num2)) return "0";
        int len1 = num1.length();
        int len2 = num2.length();
        int[] result = new int[len1 + len2];
        for (int i = len2 - 1; i >= 0; i--){
            int x = num2.charAt(i) - '0';
            for (int j = len1 - 1; j >= 0; j--){
                int y = num1.charAt(j) - '0';
                int sum = result[i + j + 1] +  x * y;
                result[i + j + 1] = sum % 10;
                result[i + j] += sum / 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i  < result.length; i++){
            if (i == 0 && result[i] == 0) continue;
            sb.append(result[i]);
        }
        return sb.toString();
    }
}

151. 反转字符串中的单词

class Solution {
    private char[] removeSpace(char[] cs) {
        int len = cs.length;
        int j = 0;
        int i = 0;
        for (; i < len; i++){
            if (cs[i] != ' ') {
                if (j != 0) {
                    cs[j++] = ' '; 
                }
                while (i < len && cs[i] != ' '){
                    cs[j++] = cs[i++];
                }
            }
        }
        System.out.println(j + " " + cs.length);

        char[] newCs = new char[j];
        i = 0;
        while (i < newCs.length){
            newCs[i] = cs[i];
            i++;
        }
        return newCs;

    }
    private void reverse(char[] cs, int left, int right) {
        while (left < right) {
            char temp = cs[left];
            cs[left] = cs[right];
            cs[right] = temp;
            left++;
            right--;
        }
    }

    private void reverseEachWord(char[] cs) {
        int j = 0;
        for (int i = 0; i <= cs.length; i++){
            //最后一个或者碰到空格了翻转字符串
            if (i == cs.length || cs[i] == ' ') {
                reverse(cs, j, i - 1);
                j = i + 1;
            }
        }
    }
    public String reverseWords(String s) {
        char[] cs = s.toCharArray();
        //去除空格
        char[] newCs = removeSpace(cs); 
        System.out.println(new String(newCs));
        //翻转
        reverse(newCs, 0, newCs.length - 1);
        reverseEachWord(newCs);
        return new String(newCs);
    }
}

165. 比较版本号

class Solution {
    private int parseInt(String str) {
        int num = 0;
        for (int i = 0; i < str.length(); i++){
            num = num * 10 + str.charAt(i) - '0';
        }
        return num;
    }
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int len1 = v1.length;
        int len2 = v2.length;
        // System.out.println(len1 + " " + len2);
        int i = 0;
        int j = 0;
        while (i < len1 || j < len2){
            int vNum1 = parseInt(i < len1 ? v1[i] : "0");
            int vNum2 = parseInt(j < len2 ? v2[j] : "0");
            // System.out.println(vNum1 + " " +vNum2);
            if (vNum1 > vNum2) {
                return 1;
            } else if (vNum1 < vNum2) {
                return -1;
            }
            i++;
            j++;
        }
        return 0;
    }
}

class Solution {
    private int parseInt(String str) {
        int num = 0;
        for (int i = 0; i < str.length(); i++){
            num = num * 10 + (str.charAt(i) - '0');
        }
        return num;
    }
    public int compareVersion(String version1, String version2) {
        String[] vs1 = version1.split("\\.");
        String[] vs2 = version2.split("\\.");
        for (int i = 0; i < Math.max(vs1.length, vs2.length); i++){
            int v1 =  parseInt(i < vs1.length ? vs1[i] : "0");
            int v2 = parseInt(i < vs2.length ? vs2[i] : "0");
            if (v1 > v2) {
                return 1;
            } else if (v1 < v2) {
                return -1;
            }
        }
        return 0;
    }
}

恢复压缩文字

private String huifuStr(String str) {
        if (str == null || str.length() == 0) return  "";
        Stack<Character> stack = new Stack<>();
        int len = str.length();
        int i = 0;
        StringBuilder result = new StringBuilder();
        while (i < len) {
            char c = str.charAt(i);
            //是数字
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < len && Character.isDigit(str.charAt(i))) {
                    num = num * 10 + str.charAt(i) - '0';
                    i++;
                }
                if (!stack.isEmpty()) {
                    Character topChar = stack.pop();
                    int j = 0;
                    while (j < num) {
                        result.append(topChar);
                        j++;
                    }
                }
            } else {
                //是字符
                if (!stack.isEmpty()) {
                    result.append(stack.pop());
                }
                stack.push(c);
                i++;
             }
        }
        if (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        return  result.toString();
    }
    public static void main(String[] args) {
        Main main = new Main();
        String str = "a3bs18c10d";
        String result = main.huifuStr(str);
        System.out.println(result);
    }

443. 压缩字符串

class Solution {
    public int compress(char[] chars) {
        int left = 0;
        int right = 0;
        int index = 0;
        int length = chars.length;
        while (right < length) {
            while (right < length && chars[left] == chars[right]) {
                right++;
            }
            int num = right - left;
            if (num == 1) {
                chars[index++] = chars[right -1];
                left = right;
            } else {
                String numString = num + "";
                chars[index++] = chars[right - 1];
                for (int i = 0; i < numString.length(); i++) {
                    chars[index++] = numString.charAt(i);    
                }
                left = right;
            }
        }
        return index;
    }
}

468. 验证IP地址

class Solution {
    /**
    *判断是否为ipv4
     */
    private boolean isIPv4(String queryIP) {
        String[] ips = queryIP.split("\\.", -1);
        if (ips == null || ips.length != 4) return false;
        for (int i = 0; i < ips.length; i++) {
            String ip = ips[i];
            if (ip == null || ip.length() == 0 || ip.length() > 3) return false;
            int num = 0;
            for (int j = 0; j < ip.length(); j++) {
                char c = ip.charAt(j);
                if (!(c >= '0' && c <= '9')) return false;
                if (ip.length() > 1 && ip.charAt(0) == '0') return false;
                num = num * 10 + (c - '0');
            } 
            if (num > 255) return false;
        }
        return true;
    }
    private boolean isIPv6(String queryIP) {
        String[] ips = queryIP.split(":", -1);
        if (ips == null || ips.length != 8) return false;
        for (int i = 0; i < ips.length; i++) {
            String ip = ips[i];
            if (ip == null || ip.length() == 0 || ip.length() > 4) return false;
            for (int j = 0; j < ip.length(); j++) {
                char c = ip.charAt(j);
                if (!((c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F') || (c >= '0' && c <= '9'))) return false;
            }
        }
        return true;
    }
    public String validIPAddress(String queryIP) {
        if (queryIP == null || queryIP.length() == 0) return "Neither";
        if (queryIP.contains(".")) {
            //判断ipv4
            if (isIPv4(queryIP)) return "IPv4"; 
            return "Neither";
        } else {
            //判断ipv6
            if (isIPv6(queryIP)) return "IPv6";
            return "Neither";
        }
    }
}

557. 反转字符串中的单词 III

class Solution {
    private void reverse(char[] cs, int left, int rigth) {
        while (left < rigth) {
            char temp = cs[left];
            cs[left] = cs[rigth];
            cs[rigth] = temp;
            left++;
            rigth--;
        }
    }
    public String reverseWords(String s) {
        char[] cs = s.toCharArray();
        int length = cs.length;
        int j = 0;
        for (int i = 0; i <= length; i++) {
            if (i == length || cs[i] == ' ') {
                reverse(cs, j , i - 1);
                j = i + 1;
            }
        }
        return new String(cs);
    }
}

class Solution {
    private void reverse(char[] cs, int left, int right) {
        while (left < right) {
            char temp = cs[left];
            cs[left] = cs[right];
            cs[right] = temp;
            left++;
            right--;
        }
    }
    public String reverseWords(String s) {
        char[] cs = s.toCharArray();
        int length = cs.length;
        for (int i = 0; i < length; i++) {
            char c = cs[i];
            if (c != ' ') {
                int j = i;
                while (i < length && cs[i] != ' ') i++;
                reverse(cs, j, i - 1);
            }
        }
        return new String(cs);
    }
}

415. 字符串相加

class Solution {
    public String addStrings(String num1, String num2) {
        int length1 = num1.length();
        int length2 = num2.length();
        int i = length1 - 1;
        int j = length2 - 1;
        int add = 0;
        StringBuilder result = new StringBuilder();
        while (i >= 0 || j >= 0) {
            int v1 = i >= 0 ? num1.charAt(i) - '0': 0;
            int v2 = j >= 0 ? num2.charAt(j) - '0': 0;
            int sum = v1 + v2 + add;
            result.append(sum % 10);
            add = sum / 10;
            i--;
            j--;
        }
        if (add != 0) {
            result.append(add % 10);
        }
        return result.reverse().toString();
    }
}

58. 最后一个单词的长度

class Solution {
    public int lengthOfLastWord(String s) {
        int length = s.length();
        for (int i = length - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c != ' ') {
                int j = i;
                while (i >= 0 && s.charAt(i) != ' ') {
                    i--;
                }
                return j - i;
            }
        }
        return 0;
    }
}

434. 字符串中的单词数

class Solution {
    public int countSegments(String s) {
        if (s == null || s.length() == 0) return 0;
        int length = s.length();
        int result = 0;
        for (int i = 0; i < length; i++) {
            if (s.charAt(i) != ' ') {
                while (i < length && s.charAt(i) != ' ') i++;
                result++;
            }
        }
        return result;
    }
}

392. 判断子序列

class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s.length() == 0) return true;
        if (t.length() == 0) return false;
        int i = 0;
        int j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == s.length();
    }
}

383. 赎金信

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] letters = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            letters[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            letters[ransomNote.charAt(i) - 'a']--;
            if (letters[ransomNote.charAt(i) - 'a'] < 0) return false;
        }
        return true;
    }
}

205. 同构字符串

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        HashMap<Character, Character> sHashMap = new HashMap<>();
        HashMap<Character, Character> tHashMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char x = s.charAt(i);
            char y = t.charAt(i);
            if (sHashMap.containsKey(x) && sHashMap.get(x) != y) return false;
            if (tHashMap.containsKey(y) && tHashMap.get(y) != x) return false; 
            sHashMap.put(x, y);
            tHashMap.put(y, x);
        }
        return true;
    }
}

290. 单词规律

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] ss = s.split(" ");
        if (ss.length != pattern.length()) return false;
        HashMap<String, Character> sHashMap = new HashMap<>();
        HashMap<Character, String> pHashMap = new HashMap<>();
        for (int i = 0; i < ss.length; i++) {
            String x = ss[i];
            char y = pattern.charAt(i);
            if ((sHashMap.containsKey(x) && sHashMap.get(x) != y) 
            || (pHashMap.containsKey(y) && !pHashMap.get(y).equals(x))) return false;
            sHashMap.put(x, y);
            pHashMap.put(y, x);
        }
        return true;
    }
}

125. 验证回文串

class Solution {
    private boolean isLetter(char c) {
        if (c >= 'a' && c <= 'z') return true;
        if (c >= '0' && c <= '9') return true;
        return false;
    };
    public boolean isPalindrome(String s) {
        int length  = s.length();
        s = s.toLowerCase();
        int left = 0;
        int right = length - 1;
        while (left < right) {
            if (!isLetter(s.charAt(left))) {
                left++;
                continue;
            }
            if (!isLetter(s.charAt(right))) {
                right--;
                continue;
            }
            // System.out.print(s.charAt(left) + " " + s.charAt(right));
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

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

class Solution {
    public int myAtoi(String s) {
        if (s.length() == 0) return 0;
        
        int i = 0;
        int length = s.length();
        int sign = 1;
        //略过空格
        while (i < length && s.charAt(i) == ' ') i++;
        if (i == length) return 0;
        //有符号判断符号
        if (s.charAt(i) == '+' || s.charAt(i) == '-') {
            sign = s.charAt(i) == '+' ? 1 : -1;
            i++;
        }
        long num = 0;
        while (i < length && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            num = num * 10 + (s.charAt(i) - '0');
            if (num * sign > Integer.MAX_VALUE) return Integer.MAX_VALUE;
            if (num * sign < Integer.MIN_VALUE) return Integer.MIN_VALUE;
            i++;
        }
        return (int)num * sign;
    }
}

49. 字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<>();
        HashMap<String, ArrayList<String>> hashMap = new HashMap<>();
        for (String str:strs) {
            char[] cs  = str.toCharArray();
            Arrays.sort(cs);
            String newStr = new String(cs);
            if (!hashMap.containsKey(newStr)) {
                hashMap.put(newStr, new ArrayList<>());
            }
            hashMap.get(newStr).add(str);
        }
        return new ArrayList<>(hashMap.values());
    }
}

65. 有效数字

class Solution {
    private boolean isInt(String str) {
        
        if (str == null || str.length() == 0) return false;
        int index = 0;
        if (str.charAt(0) == '+' || str.charAt(0) == '-')  index++;
        if (index >= str.length()) return false;
        for (;index < str.length(); index++) {
            char c = str.charAt(index);
            //不是数字
            if (!(c >= '0' && c <= '9')) return false;
        }
        return true;
    }
    private boolean isDes(String str) {
        if (str == null || str.length() == 0) return false;
        int index = 0;
        if (str.charAt(0) == '+' || str.charAt(0) == '-') index++;
        if (index >= str.length() || (index + 1 >= str.length() && str.charAt(index) == '.')) return false;
        boolean isHaveDot = false;
        for (;index < str.length(); index++) {
            char c = str.charAt(index);
            if (c >= '0' && c <= '9') {
                continue;
            } else if (!isHaveDot && c == '.') {
                isHaveDot = true;
                continue;
            } else {
                return false;
            }
        }
        return true;
        
        
    }
    public boolean isNumber(String s) {
        if (s == null || s.length() == 0) return false;
        int ie = s.indexOf('e');
        int iE = s.indexOf('E');
        if (ie != -1 && iE != -1) return false;
        else if (ie == -1 && iE == -1) {
            //没有ie
        
            return isInt(s) || isDes(s);
        } else {
            //有一个ie iE或者
            ie = (ie == -1) ? iE : ie;
            String prexSub = s.substring(0, ie);
            String afterSub = s.substring(ie + 1, s.length());
            // System.out.println(prexSub + " " + afterSub);
            return (isInt(prexSub) || isDes(prexSub)) && isInt(afterSub);
        }
        
    }
}

299. 猜数字游戏

class Solution {
    public String getHint(String secret, String guess) {
        int aCount = 0;
        int[] aArr = new int[10];
        int[] bArr = new int[10];
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i) == guess.charAt(i)) {
                aCount++;
            } else {
                aArr[secret.charAt(i) - '0']++;
                bArr[guess.charAt(i) - '0']++;
            }
        }
        int bCount = 0;
        for (int i = 0; i < bArr.length; i++) {
            bCount += Math.min(aArr[i], bArr[i]);
        }
        StringBuilder result = new StringBuilder();
        result.append(aCount);
        result.append('A');
        result.append(bCount);
        result.append('B');

        return result.toString();
    }
}

1332. 删除回文子序列

class Solution {
    public int removePalindromeSub(String s) {
        int left = 0;
        int rigth = s.length() - 1;
        while (left < rigth) {
            if (s.charAt(left) != s.charAt(rigth)) return 2;
            left++;
            rigth--;
        }
        return 1;
    }
}

2423. 删除字符使频率相同

class Solution {
    private boolean isSameFreque(int[] letters) {
        int pre = -1;
        for (int i = 0; i < letters.length; i++) {
            if (pre == -1 && letters[i] != 0) {
                pre = letters[i];
            }  else if (letters[i] != 0) {
                if (pre != letters[i]) return false;
            }
        }
        return true;
    }
    public boolean equalFrequency(String word) {
        int[] letters = new int[26];
        for (int i = 0 ; i < word.length(); i++) {
            letters[word.charAt(i) - 'a']++;
        }

        for (int i = 0; i < letters.length; i++) {
            if (letters[i] != 0) {
                letters[i] -= 1;
                if (isSameFreque(letters)) return true;
                letters[i] += 1;
            }
        }
        return false;
    }
}