[左神面试指南] 字符串[上]篇

CD95 判断两个字符串是否互为变形词

/* 模拟 */
public class CD95_1
{
    public static boolean solution(String s1, String s2)
    {
        if (s1.length() != s2.length()) return false;
        int[] temp = new int[256];
        for (char ch : s1.toCharArray())
            temp[ch]++;
        for (char ch : s2.toCharArray())
            if (--temp[ch] < 0)
                return false;
        return true;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        in.nextLine();
        String s1, s2;
        s1 = in.nextLine();
        s2 = in.nextLine();
        System.out.println(solution(s1, s2));
    }
}

CD96 判断两个字符串是否互为旋转词

/* 模拟 */
public class CD96_1
{
    public static boolean solution(String s1, String s2)
    {
        if (s1.length() != s2.length()) return false;
        if (s1.equals(s2)) return true;
        return (s2 + s2).contains(s1);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        in.nextLine();
        String s1, s2;
        s1 = in.nextLine();
        s2 = in.nextLine();
        System.out.println(solution(s1, s2) ? "YES" : "NO");
    }
}

CD97 将整数字符串转成整数值⭐

/* ⭐模拟⭐ */
public class CD97_1
{
    public static int solution(String s)
    {
        if (!isValid(s)) return 0;
        boolean neg = false;
        int idx = 0, ans = 0;
        if (s.charAt(0) == '-')
        {
            neg = true;
            idx++;
        }
        for (int i = idx; i < s.length(); i++)
        {
            if ((neg || Integer.MAX_VALUE - ans * 10 < s.charAt(i) - '0') && (!neg || (ans != 0 && ans * 10 - Integer.MIN_VALUE < s.charAt(i) - '0')))
                return 0;
            if (neg)
                ans = ans * 10 - (s.charAt(i) - '0');
            else
                ans = ans * 10 + (s.charAt(i) - '0');
        }
        return ans;
    }

    public static boolean isValid(String s)
    {
        if (s == null || s.length() == 0) return false;
        if (s.charAt(0) != '-' && (s.charAt(0) < '0' || s.charAt(0) > '9')) return false;
        if (s.charAt(0) == '-' && (s.length() == 1 || s.charAt(1) == '0')) return false;
        if (s.charAt(0) == '0' && s.length() > 1) return false;
        for (int i = 1; i < s.length(); i++)
            if (s.charAt(i) < '0' || s.charAt(i) > '9')
                return false;
        return true;
    }

    public static void main(String[] args)
    {
        // 2147483647, -2147483648
        Scanner in = new Scanner(System.in);
        String s;
        s = in.nextLine();
        System.out.println(solution(s));
    }
}

CD98 字符串的统计字符串

/* 模拟 */
public class CD98_1
{
    public static String solution(String s)
    {
        if (s == null || s.length() == 0) return "";
        int cnt = 1;
        char cur = s.charAt(0);
        StringBuilder ans = new StringBuilder();
        for (int i = 1; i < s.length(); i++)
        {
            if (s.charAt(i) == cur)
                cnt++;
            else
            {
                ans.append(cur).append("_").append(cnt).append("_");
                cur = s.charAt(i);
                cnt = 1;
            }
        }
        ans.append(cur).append("_").append(cnt);
        return ans.toString();
    }

    // 补充问题
    private static boolean extraSolution(String res, String s)
    {
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < s.length(); i++)
            ans.append(solution2(res, i + 1));
        System.out.println(ans);
        return s.equals(ans.toString());
    }

    private static char solution2(String res, int idx)
    {
        int cnt = 0, sum = 0;
        boolean flag = false;
        char cur = 0;
        for (int i = 0; i < res.length(); i++)
        {
            if (res.charAt(i) == '_')
                flag = !flag;
            else
            {
                if (!flag)
                {
                    sum += cnt;
                    if (sum >= idx) return cur;
                    cnt = 0;
                    cur = res.charAt(i);
                }
                else
                    cnt = cnt * 10 + res.charAt(i) - '0';
            }
        }
        return cur;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s;
        s = in.nextLine();
        String res = solution(s);
        System.out.println(res);
        System.out.println(extraSolution(res, s));
    }
}

CD103 判断字符数组中是否所有的字符都只出现过一次

/* hashmap / 堆排序 */
public class CD103_1
{
    public static String solution1(int[] arr)
    {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr)
        {
            if (map.containsKey(num))
                return "NO";
            map.put(num, 1);
        }
        return "YES";
    }

    public static String solution2(int[] arr)
    {
        if (arr == null) return "YES";
        heapSort(arr);
        for (int i = 1; i < arr.length; i++)
            if (arr[i] == arr[i - 1])
                return "NO";
        return "YES";
    }

    public static void heapSort(int[] arr)
    {
        for (int i = (arr.length - 2) / 2; i >= 0; i--)
            heapAdjust(arr, i, arr.length - 1);
        for (int i = arr.length - 1; i > 0; i--)
        {
            swap(arr, 0, i);
            heapAdjust(arr, 0, i - 1);
        }
    }

    public static void heapAdjust(int[] arr, int idx, int l)
    {
        int i = idx;
        while (idx < l)
        {
            if (2 * i + 2 <= l && arr[2 * i + 1] < arr[2 * i + 2])
                i = 2 * i + 2;
            else
                i = 2 * i + 1;
            if (i <= l && arr[i] > arr[idx])
            {
                swap(arr, idx, i);
                idx = i;
            }
            else
                break;
        }
    }

    public static void swap(int[] arr, int idx1, int idx2)
    {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution2(arr));
    }
}

CD99 在有序但含有空的数组中查找字符串⭐

/* ⭐二分⭐ */
public class CD99_1
{

    public static int solution(String[] arr, String find)
    {
        int l = 0, r = arr.length - 1, mid, res = -1;
        while (l <= r)
        {
            mid = (l + r) / 2;
            if ("0".equals(arr[mid]))
            {
                int temp = mid;
                while (temp >= l && arr[temp].equals("0")) temp--;
                if (temp < l || arr[temp].compareTo(find) < 0)
                    l = mid + 1;
                else
                {
                    if (arr[temp].compareTo(find) == 0) res = temp;
                    r = temp - 1;
                }
            }
            else
            {
                int compare = arr[mid].compareTo(find);
                if (compare < 0)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
        }
        if (res != -1) return res;
        else return arr[l].equals(find) ? l : -1;
    }

    public static void main(String[] args) throws Exception
    {
        Scanner in = new Scanner(System.in);
        int n;
        String find;
        n = Integer.parseInt(in.nextLine());
        String[] arr = new String[n];
        find = in.nextLine();
        for (int i = 0; i < n; i++)
            arr[i] = in.nextLine();
        System.out.println(solution(arr, find));
    }
}

CD104 字符串的调整与替换

/* 模拟(原地修改) */
public class CD104_1
{

    private static String solution(char[] s)
    {
        int space = 0, len;
        for (len = 0; len < s.length && s[len] != 0; len++)
            if (s[len] == ' ')
                space++;
        int newLen = len + 2 * space - 1, idx = newLen;
        while (--len >= 0)
        {
            if (s[len] == ' ')
            {
                s[idx--] = '0';
                s[idx--] = '2';
                s[idx--] = '%';
            }
            else
                s[idx--] = s[len];
        }
        return new String(s, 0, newLen + 1);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s;
        s = in.nextLine();
        char[] arr = new char[s.length() * 3];
        System.arraycopy(s.toCharArray(), 0, arr, 0, s.length());
        arr[s.length()] = 0;
        System.out.println(solution(arr));
    }
}

CD115 字符串的调整与替换（补充）

/* 模拟 */
public class CD115_1
{

    public static String solution(String s)
    {
        char[] str = s.toCharArray();
        int len = str.length - 1, idx = str.length - 1;
        while (idx >= 0)
        {
            if (str[idx] != '*')
                str[len--] = str[idx];
            idx--;
        }
        while (len >= 0)
            str[len--] = '*';
        return new String(str);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s;
        s = in.nextLine();
        System.out.println(solution(s));
    }

}

CD116 翻转字符串

/* 模拟 */
public class CD116_1
{
    public static String solution(String s)
    {
        int l = 0, r = 0;
        char[] str = s.toCharArray();
        while (r < str.length)
        {
            while (r < str.length && str[r] != ' ')
                r++;
            reverseWord(str, l, r - 1);
            l = r + 1;
            r++;
        }
        return new String(str);
    }

    public static void reverseWord(char[] str, int l, int r)
    {
        while (l <= r)
        {
            char temp = str[l];
            str[l] = str[r];
            str[r] = temp;
            l++;
            r--;
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s;
        s = in.nextLine();
        System.out.println(solution(s));
    }
}

CD117 翻转字符串（补充）⭐

/* ⭐模拟⭐ */
public class CD117_1
{
    public static String solution1(char[] chas, int size)
    {
        reverseWord(chas, 0, size - 1);
        reverseWord(chas, size, chas.length - 1);
        reverseWord(chas, 0, chas.length - 1);
        return new String(chas);
    }

    public static void reverseWord(char[] str, int l, int r)
    {
        while (l <= r)
        {
            char temp = str[l];
            str[l] = str[r];
            str[r] = temp;
            l++;
            r--;
        }
    }

    public static String solution2(char[] chas, int size)
    {
        exchange(chas, size, 0, chas.length - 1);
        return new String(chas);
    }

    public static void exchange(char[] chas, int size, int l, int r)
    {
        if (l == r) return;
        int len = r - l + 1, lp = size, rp = len - size;
        if (lp <= rp)
        {
            int rr = r;
            for (int s = l + lp - 1; s >= l; s--)
            {
                char t = chas[s];
                chas[s] = chas[rr];
                chas[rr] = t;
                rr--;
            }
            if (lp != rp)
                exchange(chas, lp, l, rr);
        }
        else
        {
            int ll = l;
            for (int s = l + lp; s <= r; s++)
            {
                char t = chas[s];
                chas[s] = chas[ll];
                chas[ll] = t;
                ll++;
            }
            exchange(chas, lp - rp, ll, r);
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        String s;
        n = Integer.parseInt(in.nextLine());
        s = in.nextLine();
        System.out.println(solution2(s.toCharArray(), n));
    }
}

CD118 完美洗牌问题❗

/* ❗
 * 如果数组长度为 2*N == (3^k)-1, 那么出发位置有 k 个, 依次为 1,3,9,..3^(k-1), k≥1。
 * 长度为一个任意的偶数, 都一定可以把这个偶数拆成一块块长度满足 3^(k-1) 的部分。
 */
public class CD118_1
{
    public static void solution(int[] arr)
    {
        if (arr != null && arr.length != 0 && (arr.length & 1) == 0)
            shuffle(arr, 0, arr.length - 1);
    }

    public static void shuffle(int[] arr, int L, int R)
    {
        while (R - L + 1 > 0)
        {
            int len = R - L + 1;
            int base = 1;
            int k = 0;
            while (base - 1 <= len)
            {
                base *= 3;
                k++;
            }
            k--;
            base /= 3;
            int half = (base - 1) / 2;
            int mid = (L + R) / 2;
            rotate(arr, L + half, mid, mid + half);
            cycles(arr, L, base - 1, k);
            L = L + base - 1;
        }
    }


    public static void cycles(int[] arr, int start, int len, int k)
    {
        for (int i = 0, trigger = 1; i < k; i++, trigger *= 3)
        {
            int preValue = arr[trigger + start - 1];
            int cur = modifyIndex2(trigger, len);
            while (cur != trigger)
            {
                int tmp = arr[cur + start - 1];
                arr[cur + start - 1] = preValue;
                preValue = tmp;
                cur = modifyIndex2(cur, len);
            }
            arr[cur + start - 1] = preValue;
        }
    }

    public static int modifyIndex2(int i, int len)
    {
        return (2 * i) % (len + 1);
    }

    public static void rotate(int[] arr, int L, int M, int R)
    {
        reverse(arr, L, M);
        reverse(arr, M + 1, R);
        reverse(arr, L, R);
    }

    public static void reverse(int[] arr, int L, int R)
    {
        while (L < R)
        {
            int tmp = arr[L];
            arr[L++] = arr[R];
            arr[R--] = tmp;
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        solution(arr);
        System.out.println(Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}

CD120 完美洗牌问题（进阶）❗

/*❗*/
public class CD120_1
{
    public static void solution(int[] arr)
    {
        if (arr == null || arr.length == 0) return;
        Arrays.sort(arr);
        if ((arr.length & 1) == 1)
            shuffle(arr, 1, arr.length - 1);
        else
        {
            shuffle(arr, 0, arr.length - 1);
            for (int i = 0; i < arr.length; i += 2)
            {
                int tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
            }
        }
    }

    public static void shuffle(int[] arr, int L, int R)
    {
        while (R - L + 1 > 0)
        {
            int len = R - L + 1;
            int base = 1;
            int k = 0;
            while (base - 1 <= len)
            {
                base *= 3;
                k++;
            }
            k--;
            base /= 3;
            int half = (base - 1) / 2;
            int mid = (L + R) / 2;
            rotate(arr, L + half, mid, mid + half);
            cycles(arr, L, base - 1, k);
            L = L + base - 1;
        }
    }


    public static void cycles(int[] arr, int start, int len, int k)
    {
        for (int i = 0, trigger = 1; i < k; i++, trigger *= 3)
        {
            int preValue = arr[trigger + start - 1];
            int cur = modifyIndex2(trigger, len);
            while (cur != trigger)
            {
                int tmp = arr[cur + start - 1];
                arr[cur + start - 1] = preValue;
                preValue = tmp;
                cur = modifyIndex2(cur, len);
            }
            arr[cur + start - 1] = preValue;
        }
    }

    public static int modifyIndex2(int i, int len)
    {
        return (2 * i) % (len + 1);
    }

    public static void rotate(int[] arr, int L, int M, int R)
    {
        reverse(arr, L, M);
        reverse(arr, M + 1, R);
        reverse(arr, L, R);
    }

    public static void reverse(int[] arr, int L, int R)
    {
        while (L < R)
        {
            int tmp = arr[L];
            arr[L++] = arr[R];
            arr[R--] = tmp;
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        solution(arr);
        System.out.println(Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}

CD121 删除多余字符得到字典序最小的字符串⭐

/*⭐⭐*/
public class CD121_1
{
    public static String solution(String s)
    {
        Stack<Character> sta = new Stack<>();
        int[] cnt = new int[500];
        int[] vis = new int[500];
        Arrays.fill(cnt, 0);
        Arrays.fill(vis, 0);
        for (char ch : s.toCharArray())
            cnt[ch]++;
        for (char ch : s.toCharArray())
        {
            cnt[ch]--;
            if (vis[ch] == 1) continue;
            while (!sta.empty() && ch < sta.peek())
            {
                if (cnt[sta.peek()] != 0)
                {
                    vis[sta.peek()] = 0;
                    sta.pop();
                }
                else break;
            }
            sta.push(ch);
            vis[ch] = 1;
        }

        StringBuilder res = new StringBuilder();
        while (!sta.empty())
            res.append(sta.pop());
        return res.reverse().toString();
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s;
        s = in.nextLine();
        System.out.println(solution(s));
    }
}

CD122 数组中两个字符串的最小距离

/* 模拟 */
public class CD122_1
{

    public static int solution(String[] arr, String s1, String s2)
    {
        int ans = Integer.MAX_VALUE, idx1 = -1, idx2 = -1;
        for (int i = 0; i < arr.length; i++)
        {
            if (s1.equals(arr[i]))
            {
                idx1 = i;
                if (idx2 != -1)
                    ans = Math.min(ans, idx1 - idx2);
            }
            if (s2.equals(arr[i]))
            {
                idx2 = i;
                if (idx1 != -1)
                    ans = Math.min(ans, idx2 - idx1);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        String s1, s2;
        n = Integer.parseInt(in.nextLine());
        String[] temp = in.nextLine().split(" ");
        s1 = temp[0];
        s2 = temp[1];
        String[] arr = new String[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextLine();
        System.out.println(solution(arr, s1, s2));
    }
}

CD123 字符串的转换路径问题

public class CD123_1
{

    public static void solution(String from, String to, ArrayList<String> list)
    {
        HashMap<String, ArrayList<String>> paths = new HashMap<>();
        ArrayList<ArrayList<String>> res = new ArrayList<>();
        list.add(from);
        createPath(list, paths);
        int shortestLen = BFS(from, to, paths);
        if (shortestLen == -1) System.out.println("NO");
        else
        {
            DFS(from, to, shortestLen, paths, res, new ArrayList<String>(), new HashMap<String, Integer>());
            System.out.println("YES");
            for (ArrayList<String> temp : res)
                System.out.println(temp.stream().collect(Collectors.joining(" -> ")));
        }
    }

    public static void DFS(String from, String target, int shortestLen, HashMap<String, ArrayList<String>> paths,
                           ArrayList<ArrayList<String>> res, ArrayList<String> path, HashMap<String, Integer> vis)
    {
        path.add(from);
        if (path.size() > shortestLen + 1) return;
        if (path.size() == shortestLen + 1 && path.get(shortestLen).equals(target))
        {
            res.add(new ArrayList<>(path));
            return;
        }
        if (!paths.containsKey(from)) return;
        for (String to : paths.get(from))
        {
            if (vis.containsKey(to)) continue;
            vis.put(to, 1);
            DFS(to, target, shortestLen, paths, res, path, vis);
            path.remove(path.size() - 1);
            vis.remove(to);
        }
    }

    public static int BFS(String from, String to, HashMap<String, ArrayList<String>> paths)
    {
        if (from.equals(to)) return 0;
        int cnt = 0;
        Queue<String> que = new LinkedList<>();
        que.add(from);
        while (!que.isEmpty())
        {
            int size = que.size();
            cnt++;
            while (size-- > 0)
            {
                String pollString = que.poll();
                if (!paths.containsKey(pollString)) continue;
                ArrayList<String> path = paths.get(pollString);
                for (String s : path)
                {
                    if (to.equals(s)) return cnt;
                    que.add(s);
                }
            }
        }
        return -1;
    }

    public static void createPath(ArrayList<String> list, HashMap<String, ArrayList<String>> paths)
    {
        HashSet<String> map = new HashSet<>();
        for (String t : list) map.add(t);
        for (String s : list)
        {
            ArrayList<String> path = new ArrayList<>();
            for (char alpha = 'a'; alpha <= 'z'; alpha++)
            {
                char[] str = s.toCharArray();
                for (int j = 0; j < str.length; j++)
                {
                    if (alpha == str[j]) continue;
                    char temp = str[j];
                    str[j] = alpha;
                    if (map.contains(String.valueOf(str)))
                        path.add(String.valueOf(str));
                    str[j] = temp;
                }
            }
            Collections.sort(path);
            paths.put(s, path);
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n;
        String from, to;
        ArrayList<String> list = new ArrayList<String>();
        n = Integer.parseInt(in.nextLine());
        String[] temp = in.nextLine().split(" ");
        from = temp[0];
        to = temp[1];
        while (n-- > 0)
            list.add(in.nextLine());
        solution(from, to, list);
    }
}

CD124 添加最少字符使字符串整体都是回文字符串⭐

/* ⭐DP⭐
 * dp[i][j]表示为子串str[i..j]最少添加几个字符可以使其为回文串
 */
public class CD124_1
{
    public static String solution(String s)
    {
        int len = s.length();
        int[][] dp = new int[len][len];
        for (int i = 0; i < len; i++)
        {
            for (int j = i - 1; j >= 0; j--)
            {
                if (s.charAt(j) == s.charAt(i))
                    dp[j][i] = dp[j + 1][i - 1];
                else
                    dp[j][i] = Math.min(dp[j][i - 1], dp[j + 1][i]) + 1;
            }
        }
        char[] chas = s.toCharArray();
        char[] res = new char[len + dp[0][len - 1]];
        int i = 0, j = len - 1, resl = 0, resr = res.length - 1;
        while (i <= j)
        {
            if (chas[i] == chas[j])
            {
                res[resl++] = chas[i++];
                res[resr--] = chas[j--];
            }
            else if (dp[i][j - 1] < dp[i + 1][j])
            {
                res[resl++] = chas[j];
                res[resr--] = chas[j--];
            }
            else
            {
                res[resl++] = chas[i];
                res[resr--] = chas[i++];
            }
        }
        return String.valueOf(res);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s;
        s = in.nextLine();
        System.out.println(solution(s));
    }
}

CD125 添加最少字符使字符串整体都是回文字符串（进阶）

/* 模拟 */
public class CD125_1
{
    public static String solution(String s1, String s2)
    {
        char[] ans = new char[2 * s1.length() - s2.length()];
        int s1L = 0, s1R = s1.length() - 1, s2L = 0, s2R = s2.length() - 1, ansL = 0, ansR = ans.length - 1;
        while (ansL <= ansR)
        {
            if (s1.charAt(s1L) != s2.charAt(s2L))
            {
                ans[ansL++] = s1.charAt(s1L);
                ans[ansR--] = s1.charAt(s1L++);
            }
            else if (s1.charAt(s1R) != s2.charAt(s2R))
            {
                ans[ansL++] = s1.charAt(s1R);
                ans[ansR--] = s1.charAt(s1R--);
            }
            else
            {
                ans[ansL++] = s1.charAt(s1L);
                ans[ansR--] = s1.charAt(s1L);
                s1L++;
                s1R--;
                s2L++;
                s2R--;
            }
        }
        return new String(ans);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        String s1, s2;
        s1 = in.nextLine();
        s2 = in.nextLine();
        System.out.println(solution(s1, s2));
    }
}