6.27号刷题

第一题 344. Reverse String

题目描述

反转一个String

算法

public class reverseString344 {
    public String reverseString(String s) {
        StringBuilder sb = new StringBuilder();
        if (s.isEmpty()) return sb.toString();
        for (int i = s.length() - 1; i >= 0; i--) {
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

第二题 541. Reverse String II

题目描述

给定一个字符串和一个整数k，每2k个字符翻转前k个字符。如果剩余字符不足k个，则全部翻转。如果剩余字符在k到2k之间，则翻转前k个字符，剩余字符保持原样。

约束条件：

字符串只包含小写英文字母。
给定字符串长度和k在范围[1, 10000]之间。

算法

利用subString进行解决

public class Solution {
    public String reverseStr(String s, int k) {
        StringBuilder res = new StringBuilder();
        boolean flag = true;
        
        for (int i = 0; i < s.length();) {
            if (flag) {
                if (s.length() - i - k < 0) {
                    res.append(reverse(s.substring(i, s.length())));
                } else {
                    res.append(reverse(s.substring(i, i + k)));
                }
                i += k;
                flag = false;
            } else {
                if (s.length() - i - k < 0) {
                    res.append(s.substring(i, s.length()));
                } else {
                    res.append(s.substring(i, i + k));
                }
                i += k;
                flag = true;
            }
        }
        return res.toString();
    }
    public String reverse(String s) {
        StringBuilder sb = new StringBuilder();
        if (s.isEmpty()) return sb.toString();
        for (int i = s.length() - 1; i >= 0; i--) {
            sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

第三题 345. Reverse Vowels of a String

题目描述

编写函数输入一个字符串，将其中的元音字母逆置。

测试用例如题目描述。

算法

双指针

public class Solution {
    public String reverseVowels(String s) {
        if (s.isEmpty()) return "";
        Set<Character> vowels = new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
        char[] cha = s.toCharArray();
        int left = 0, right = s.length() - 1;
        while (left <= right) {
            if (vowels.contains(cha[left]) && vowels.contains(cha[right])) {
                char temp = cha[left];
                cha[left] = cha[right];
                cha[right] = temp;
                left++; right--;
            } else if (vowels.contains(cha[left])) {
                right--;
            } else if (vowels.contains(cha[right])) {
                left++;
            } else {
                left++; right--;
            }
        }
        return String.valueOf(cha);      
    }
}

第四题 557. Reverse Words in a String III

题目描述

给定字符串，将每个单词逐字符逆置，返回新字符串。

注意：字符串中单词之间有且只有1个空格分开

算法

public class reverseWords557 {
    public String reverseWords(String s) {
        char[] ch = s.toCharArray();
        int left = 0;
        for (int right = 0; right < ch.length; right++) {
            if (ch[right] == ' ') {
                reverse(ch, left, right - 1);
                left = right + 1;
            }
        }
        reverse(ch, left, ch.length - 1);
        return String.valueOf(ch);
    }
    public void reverse(char[] s, int l, int r) {
        while(l < r)
        {
            char temp = s[l];
            s[l] = s[r];
            s[r] = temp;
            l++; r--;
        }
    }
}

第五题 544. Output Contest Matches

题目描述

有n只队伍（n是2的幂，范围[2, 212]），顺序编号为1 ~ n。

队伍按照(1, n), (2, n - 1), (3, n - 2) … 的顺序两两配对进行比赛，胜者按照同样原则递归。

算法

利用数组，将字符串进行拼接

public class findContestMatch544 {
    public String findContestMatch(int n) {
        String[] res = new String[n];
        for (int i = 1; i <= n; i++) res[i - 1] = String.valueOf(i);
        while (n > 0) {
            for (int i = 0; i < n / 2; i++) {
                res[i] = "(" + res[i] + ","+ res[n - i - 1] + ")";
            }
            n /= 2;
        }
        return res[0];
    }
}

第六题 521. Longest Uncommon Subsequence I

题目描述

给定两个字符串，计算其“最长不公共子序列”。最长不公共子序列是指：两字符串中某一个的子序列，该子序列不是另一个字符串的子序列，并且长度最长。

子序列是指从一个序列中删除一些字符，剩余字符顺序保持不变得到的新序列。任何字符串都是其本身的子序列，空串不属于任意字符串的子序列。

返回最长不公共子序列，若不存在，返回-1。

注意：

两字符串长度均不超过100
输入字符串只包含小写字母a-z

算法

public class Solution {
    public int findLUSlength(String a, String b) {
        return a.equals(b) ? -1 : Math.max(a.length(), b.length());
    }
}