剑指offer 05
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = “We are happy.” 输出：“We%20are%20happy.”
class Solution {
public String replaceSpace(String s) {
if (s.length() == 0) {
return s;
}
char[] cs = new char[s.length() * 3];
int index = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ') {
cs[index] = '%';
cs[index + 1] = '2';
cs[index + 2] = '0';
index += 3;
} else {
cs[index++] = s.charAt(i);
}
}
return new String(cs, 0, index);
}
}
剑指offer 06
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
class Solution {
public int[] reversePrint(ListNode head) {
if (head == null) {
return new int[0];
}
Stack<Integer> stack = new Stack<>();
while (head != null) {
stack.push(head.val);
head = head.next;
}
int[] ans = new int[stack.size()];
for (int i = 0; i < ans.length; i++) {
ans[i] = stack.pop();
}
return ans;
}
}
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：
3
/ \
9 20
/ \
15 7
class Solution {
private Map<Integer, Integer> indexMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
indexMap = new HashMap<>();
for (int i = 0; i < n; i++) {
indexMap.put(inorder[i], i);
}
return myBuilder(preorder, inorder, 0, n - 1, 0, n - 1);
}
public TreeNode myBuilder(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
if (preorderLeft > preorderRight || inorderLeft > inorderRight) {
return null;
}
int preorderRoot = preorderLeft;
int inorderRoot = indexMap.get(preorder[preorderRoot]);
TreeNode root = new TreeNode(preorder[preorderRoot]);
int leftSize = inorderRoot - inorderLeft;
root.left = myBuilder(preorder, inorder, preorderLeft + 1, preorderLeft + leftSize, inorderLeft, inorderRoot - 1);
root.right = myBuilder(preorder, inorder, preorderLeft + leftSize + 1, preorderRight, inorderRoot + 1, inorderRight);
return root;
}
}