剑指 Offer 05. 替换空格

问题：请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

StringBuilder 解法

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder(s);
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (' ' == c) {
                sb.append("%20");
            }else {
                sb.append(c);
            }
        }
        return sb.toString()
    }
}

双指针 不用 StringBuilder 的解法
思路：

• 首先扩充数组到每个空格替换成 “%20” 之后的大小。
• 然后从后向前替换空格，也就是双指针法，过程如下：

class Solution {
    public String replaceSpace(String s) {
        char[] chars = s.toCharArray();
        int emptySize = 0;
        for (char c : chars) {
            if (' ' == c) {
                emptySize++;
            }
        }
        // 扩充数组到每个空格替换成 "%20" 之后的大小
        char[] newChars = Arrays.copyOf(chars, chars.length + 2 * emptySize);
        // ===============双指针的代码逻辑=================
        // newChars 数组中索引位置
        // [0, i] 为未处理的字符，
        // (i, j) 为不需要的字符，
        // [j,newChars.length - 1) 为处理后的字符
        int i = chars.length - 1;
        int j = newChars.length - 1;
        while (i >= 0) {
            if (newChars[i] == ' ') {
                newChars[j] = '0';
                newChars[j - 1] = '2';
                newChars[j - 2] = '%';
                j -= 3;
            } else {
                newChars[j] = newChars[i];
                j -= 1;
            }
            i--;
        }
        return new String(newChars);
    }
}

剑指 Offer 55 - II. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

思路：左程云的二叉树递归套路

class Solution {
    public boolean isBalanced(TreeNode root) {
        Info info = isBalanced1(root);
        return info.isBalanced;
    }
    public Info isBalanced1(TreeNode treeNode) {
        if (treeNode == null) {
            return new Info(true, 0);
        }
        Info lInfo = isBalanced1(treeNode.left);
        Info rInfo = isBalanced1(treeNode.right);
        //加工出以 treeNode 为头节点的树的 Info 信息返回
        Info info = new Info();
        info.height = Math.max(lInfo.height, rInfo.height) + 1;
        // 列出答案所有的可能性
        if (lInfo.isBalanced && rInfo.isBalanced && Math.abs(lInfo.height - rInfo.height) <= 1) {
            info.isBalanced = true;
        } else {
            info.isBalanced = false;
        }
        return info;
    }
    // 以 treeNode 为头节点的左子树和右子树需要提供的信息
    class Info {
        // 树是否平衡
        Boolean isBalanced;
        // 树的高度
        int height;
        public Info() {
        }
        public Info(Boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }
}

剑指 Offer 58 - II. 左旋转字符串

问题：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

在一个数组上操作字符解法
思路

1. 反转区间为前 n 的子串
2. 反转区间为 n 到末尾的子串

3. 反转整个字符串

   class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder(s);
        // 反转区间为前 n 的子串
        reverseString(sb, 0, n - 1);
        // 反转区间为 n 到末尾的子串
        reverseString(sb, n, s.length() - 1);
        // 反转整个字符串
        sb.reverse();
        return sb.toString();
    }
    public void reverseString(StringBuilder sb, int startIndex, int endIndex) {
        int i = startIndex;
        int j = endIndex;
        while (i < j) {
            char temp = sb.charAt(i);
            sb.setCharAt(i++, sb.charAt(j));
            sb.setCharAt(j--, temp);
        }
    }
   }