字符串

文章目录

1. 1. 字符串反转1(344)
2. 2. 字符串反转2(541)
3. 3. 字符串反转3(557)
4. 4. 字符串反转4(917)
5. 5. 字符串反转5(345)
6. 6. 报数问题(38)
7. 7. 二进制求和(67)
8. 8. 验证回文串(125)
9. 9. 有效括号(20)
10. 10. 无重复字符的最长子串(3)
11. 11. 最长回文子串(5)
12. 12. 压缩字符串(443)
13. 13. 字符串中的第一个唯一字符(387)
14. 14. 赎金信(383)

题目来自leetcode

字符串反转1(344)

/*
题目要求：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出。
*/
public void reverseString(char[] s) {
    int low = 0;
    int high = s.length - 1;
    while (low < high) {
        char temp = s[low];
        s[low++] = s[high];
        s[high--] = temp;
    }
}

字符串反转2(541)

/*
题目要求:给定一个字符串和一个整数 k，你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符，则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符，则反转前 k 个字符，并将剩余的字符保持原样。
示例：输入: s = "abcdefg", k = 2 输出: "bacdfeg"
*/
public String reverseStr(String s, int k) {
    // 计算长度 整数遍历次数 剩余元素个数
    int len = s.length();
    int lastNum = len % (2 * k);
    int num = len / (2 * k);
    char[] chars = s.toCharArray();
    // 先将前2*k*num个元素做反转
    for (int i = 1; i < 2 * num; i += 2) {
        int low = (i - 1) * k;
        int high = i * k - 1;
        reverseChar(chars, low, high);
    }
    // 将剩余的不到2*k个元素反转
    if (lastNum > k) {
        reverseChar(chars, 2*k*num, 2*k*num+k-1);
    } else {
        reverseChar(chars, 2*k*num, len-1);
    }
    return new String(chars);
}

// 字符数组反转函数
public void reverseChar(char[] chars, int low, int high) {
    while (low < high) {
        char temp = chars[low];
        chars[low ++] = chars[high];
        chars[high --] = temp;
    }
}

字符串反转3(557)

/*
题目要求: 给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。
示例 1:
	输入: "Let's take LeetCode contest"
	输出: "s'teL ekat edoCteeL tsetnoc" 
*/
// 解法：将字符串按照空格拆分成为字符串数组，然后将每一个字符串翻转，最后将反转的字符串拼接到一起。
// 其中字符串的反转采用的方式为先转换为字符数组，然后反转字符数组。
public String reverseWords(String s) {
    StringBuilder sb = new StringBuilder();
    String[] split = s.split("\\s+");
    for (int i = 0; i < split.length ; i++) {
        char[] chars = split[i].toCharArray();
        int low = 0;
        int hig = chars.length - 1;
        while (low < hig) {
            char temp = chars[low];
            chars[low ++] = chars[hig];
            chars[hig --] = temp;
        }
        sb.append(chars);
        if (i != split.length - 1) {
            sb.append(" ");
        }
    }
    return sb.toString();
}

字符串反转4(917)

/*
题目要求:给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。
示例 1：输入："ab-cd"  输出："dc-ba"
示例 2：输入："a-bC-dEf-ghIj" 输出："j-Ih-gfE-dCba"
*/
public String reverseOnlyLetters(String S) {
     // 双指针
    StringBuffer buf = new StringBuffer();
    int j = S.length() - 1;
    for (int i = 0; i < S.length(); i ++) {
        // 位置i上的字符为字母时，可以做交换
        if (Character.isLetter(S.charAt(i))) {
            while(!Character.isLetter(S.charAt(j))) {
                j --;
            }
            buf.append(S.charAt(j --));
        } else {
            buf.append(S.charAt(i));
        }
    }
    return buf.toString();
}

字符串反转5(345)

/*
题目要求:编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1: 输入: "hello" 输出: "holle"
示例 2: 输入: "leetcode" 输出: "leotcede"
说明: 元音字母不包含字母"y"。
*/

// 元音字母集合
final static Set<Character> sets = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

// 使用双指针,当两端同时为元音字母时,交换两个位置的字符。
public String reverseVowels(String s) {
    int left = 0;
    int right = s.length() - 1;
    char[] chars = s.toCharArray();
    while (left <= right) {
        while (!judgeVowel(chars[left])) {
            left ++;
            if (left > s.length() -1) {
                break;
            }
        }
        while (!judgeVowel(chars[right])) {
            right --;
            if (right < 0) {
                break;
            }
        }
        if (left > right) {
            break;
        }
        char temp = chars[left];
        chars[left++] = chars[right];
        chars[right--] = temp;
    }
    return new String(chars);
}

报数问题(38)

/*
题目要求：
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1.     1
2.     11
3.     21
4.     1211
5.     111221
说明：上一项报前一项，报数时是按照各数+数字报的。比如：给1报数的是2，报数时时1个1，即为11。给2报数的是3，报的数是11，2个1，即为21。报21时，1个2，1个1，即为1211
*/
// 解法：就是按照规律统计前一项的数字，直到第n项统计出n-1为止。
public String countAndSay(int n) {
    String res = "1";
    for (int i = 2; i <= n; i ++) {
        StringBuffer buf = new StringBuffer();
        char ch = res.charAt(0);
        int num = 0;
        for (int j = 0; j < res.length(); j ++) {
            if (ch == res.charAt(j)) {
                num ++;
            } else {
                buf.append(num).append(ch);
                ch = res.charAt(j);
                num = 1;
            }
        }
        buf.append(num).append(ch);
        res = buf.toString();
    }
    return res;
}

二进制求和(67)

/*
题目要求：
    给定两个二进制字符串，返回他们的和（用二进制表示）。
    输入为非空字符串且只包含数字 1 和 0。
示例:
   输入: a = "11", b = "1"    输出: "100"
   输入: a = "1010", b = "1011"    输出: "10101"
*/
// 从后往前遍历计算，将计算结果拼接到字符串后面，最后将字符串反转
public String addBinaryA(String a, String b) {
    StringBuffer buf = new StringBuffer();
    int ans = 0;
    for (int i = a.length() - 1, j  = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
        int sum = ans;
        // 两个字符串长度可能不同，故先遍历完毕的字符串计算值用0代替
        sum += (i >= 0 ? a.charAt(i) - '0' : 0);
        sum += (j >= 0 ? b.charAt(j) - '0' : 0);
        // 拼接
        buf.append(sum % 2);
        // 进位
        ans = sum / 2;
    }
    buf.append(ans == 1 ? ans : "");
    return buf.reverse().toString();
}

验证回文串(125)

/*
题目要求： 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例：
  输入: "A man, a plan, a canal: Panama"    输出: true
  输入: "race a car"    输出: false
*/
public boolean isPalindromeA(String s) {
    if (s == null || s.trim().length() == 0) {
        return true;
    }
    // 将字符串转小写
    String param = s.toLowerCase();
    int length = param.length();
    int left = 0;
    int right = length - 1;
    // 左右两个指针遍历，相遇结束
    while (left < right) {
        // 从左起，定位到第一个字母或是数字
        while (left < right && !isSuitable(param.charAt(left))) {
            left ++;
        }
        // 从右起，定位到第一个字母或是数字
        while (left < right && !isSuitable(param.charAt(right))) {
            right --;
        }
        if (left >= right) {
            return true;
        }
        // 不符合条件，返回false
        if (param.charAt(left ++) != param.charAt(right --)) {
            return false;
        }
    }
    return true;
}
// 判定给定的字符是否为字母或数字
public boolean isSuitable(char c) {
    return Character.isLetter(c) || Character.isDigit(c);
}

有效括号(20)

/*
题目要求：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
  左括号必须用相同类型的右括号闭合。
  左括号必须以正确的顺序闭合。
  注意空字符串可被认为是有效字符串。
示例:  输入: "()"  输出: true
      输入: "()[]{}" 输出: true
      输入: "(]"   输出: false
      输入: "([)]"  输出: false
      输入: "{[]}"  输出: true 
*/
// 解法：使用栈来操作
public boolean isValid(String s) {
    // 规律：对应的括号只有可能在紧邻的一位或者对称的位置找到
    // 空字符串直接返回 true
    if (s == null || s.trim().length() == 0) {
        return true;
    }
    int length = s.length();
    // 非2的偶数倍，直接返回false
    if (length % 2 != 0) {
        return false;
    }
    // 通过定义stack来实现，遇到左括号放入到stack中，遇到右括号从stack中弹出元素与之对比
    // 这种的扩展性较好，但是要引入HashMap,并且要匹配key,所以时间复杂度和空间复杂度都没下面的好
    Stack<Character> stack = new Stack<Character>();
    Map<Character, Character> map = new HashMap<Character, Character>();
    map.put('(', ')');
    map.put('{', '}');
    map.put('[', ']');
    Set<Character> keys = map.keySet();
    for (int j = 0; j < length; j ++) {
        char c = s.charAt(j);
        if (keys.contains(c)) {
            stack.push(c);
        } else {
            if (stack.isEmpty() ||  map.get(stack.pop()) != c) {
                return false;
            }
        }
    }
    // 下面这种时间复杂度和空间复杂度都要由于上面的，但是扩展性不好
    /*
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < length; i ++) {
            char c = s.charAt(i);
            switch(c) {
                case '(':
                case '{':
                case '[':
                    stack.push(c);
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') {
                        return false;
                    }
                    continue;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') {
                        return false;
                    }
                    continue;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') {
                        return false;
                    }
                    continue;

            } 
        }
        */
    return stack.isEmpty();
}

无重复字符的最长子串(3)

// 滑动窗口解法
public int lengthOfLongestSubstring(String s) {
    int length = s.length();
    int ans = 0;
    int left = 0;
    int right = 0;
    Set<Character> set = new HashSet<Character>();
    while(left < length && right < length) {
        if (!set.contains(s.charAt(right))) {
            set.add(s.charAt(right ++));
            ans = Math.max(ans, right - left);
        } else {
            set.remove(s.charAt(left ++));
        }
    }
    return ans;
}

最长回文子串(5)

// 题目要求:给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
// 1.要判断一个字符串是否为回文字符串，可以通过下面几种方式来实现
// 第一种:通过栈的后进先出原理，将字符串翻转来对比前后两个字符串是否一致
public static boolean isHuiWen1(String str) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
        stack.push(str.charAt(i));
    }
    StringBuffer buf = new StringBuffer();
    while (!stack.isEmpty()) {
        buf.append(stack.pop());
    }
    if (str.equals(buf.toString())) {
        return true;
    }
    return false;
}
// 第二种: 取消栈的引入，直接通过逆序输出拼接字符串(减少了额外的空间Stack)
public static boolean isHuiWen2(String str) {
    StringBuffer buf = new StringBuffer();
    for (int i = str.length() - 1; i >= 0 ; i--) {
        buf.append(str.charAt(i));
    }
    if (buf.toString().equals(str)) {
        return true;
    }
    return false;
}
// 第三中: 基于回文串左右两边两个字符相等的规律，定义两个变量做对比(优势是减少了字符串str的遍历次数，时间复杂度降低)
public static boolean isHuiWen3(String str) {
    int length = str.length();
    int left = 0;
    int right = length - 1;
    while (left <= right) {
        if (!(str.charAt(left) == str.charAt(right))) {
            return false;
        }
        left ++;
        right --;
    }
    return true;
}

// 当前这道题如何实现
public String longestPalindrome(String s) {
    // 给定一个字符串s,找到s中最长的回文子串。你可以假设s的最大长度为1000。
    int len = s.length();
    if (len == 0) {
        return "";
    }
    int resultLen = 1;
    String resultStr = s.substring(0, 1);
    for (int i = 0; i < len; i ++) {
        // 从中间向两边查找对称的回文串
        String oddStr = spread(s, len, i, i);
        String evenStr = spread(s, len, i, i+1);
        String myStr = oddStr.length() >= evenStr.length() ? oddStr : evenStr;
        if (myStr.length() > resultLen) {
            resultStr = myStr;
            resultLen = resultStr.length();
        }
    }
    return resultStr;
}
    
public String spread(String s, int len, int left, int right) {
    int l = left;
    int r = right;
    while (l >= 0 && r < len && (s.charAt(l) == s.charAt(r))) {
        l --;
        r ++;
    }
    return s.substring(l+1, r);
}

压缩字符串(443)

// 题目要求: 给定一组字符串，使用原地算法将其压缩。
// 题目解法
public int compress(char[] chars) {
    int anchor = 0; // 描点，定位可以元素
    int write = 0; // 写下标，定位写的位置
    for (int read = 0; read < chars.length; read ++) {
        // 若是当前元素为最后一个元素或者是后一个元素与当前元素不相等，执行写入与统计写入操作
        if ((read == chars.length - 1) || (chars[read + 1] != chars[read])) {
            // 将anchor位置处的元素写入到write位置处
            chars[write ++] = chars[anchor];
            // 判断该元素是否需要压缩
            if (read > anchor) {
                String numStr = read - anchor + 1 + "";
                char[] numArr = numStr.toCharArray();
                for (char num : numArr) {
                    chars[write ++] = num;
                }
            }
            // 将锚点移动到下一个元素
            anchor = read + 1;
        }
    }
    // 返回覆盖的个数
    return write;
}

字符串中的第一个唯一字符(387)

/*
题目要求: 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
说明: 你可以假设字符串只含有小写字母。
示例: s = "leetcode" 返回 0.		s = "loveleetcode" 返回 2.
*/
// 第一中解法，遍历两次字符串，哈希表存储每个字符和其出现的个数
public int firstUniqCharA(String s) {
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    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);
        }
    }
    for (int j = 0; j < s.length(); j ++) {
        if (map.get(s.charAt(j)) == 1) {
            return j;
        }
    }
    return -1;
}

// 第二种解法: 仅遍历26个字母，唯一的特征：第一个字符和最后一个字符的index相同
public int firstUniqCharB(String s) {
    char[] originalChar = "abcdefghijklmnopqrstuvwxyz".toCharArray();
    int index = s.length();
    // 此处循环26次
    for (char c : originalChar) {
        int left = s.indexOf(c);
        if (left != -1 && left == s.lastIndexOf(c)) {
            index = Math.min(index, left);
        }
    }
    if(index != s.length()) {
        return index;
    }
    return -1;
}

赎金信(383)

/*
题目要求: 给出两个字符串，用第二个字符串中的字符拼接成为第一个字符串，每个字符只能使用一次。可以返回true，否则返回false。
说明: 你可以假设两个字符串均只含有小写字母。
实例：
	canConstruct("a", "b") -> false  
	canConstruct("aa", "ab") -> false
	canConstruct("aa", "aab") -> true
*/
public boolean canConstruct(String ransomNote, String magazine) {
    // 第一个字符串里面的字符能不能由第二个字符串里面的字符构成，若可以，返回true。否则返回false。
    // 将26 个字母个数映射到一个26大小的数组上
    int[] bucket = new int[26];
    for (int i = 0; i < magazine.length(); i ++) {
        bucket[magazine.charAt(i) - 'a'] ++;
    }
    for (int j = 0; j < ransomNote.length(); j ++) {
        if (-- bucket[ransomNote.charAt(j) - 'a'] < 0) {
            return false;
        }
    }
    return true;
}