面试题3：数组中重复的数字
题目一：长度为n的数组里的数字在0到n-1的范围
题目一：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。
- 算法
- 1.遍历数组，把所有数字归到原位，即使得nums[i] = i
- 2.当遇到nums[i] != i的数字时，判断nums[i]和nums[nums[i]]是否相等
- 2.1 如果相等，那它就是重复的数字
- 2.2 如果不相等，就把当前不应该在这个位置的数字归位，然后循环直到把应该在这个位置的数字归位
public int findRepeatNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return -1;
} 题目二：长度为n的数组里的数字在1到n-1的范围
题目二：在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。
- 算法
- 二分查找法
- 1.每次循环统计数组中值在[start middle]范围的元素的个数
- 2.如果范围大于 middle - start + 1，说明重复的数在左半部分，否则在右半部分；重复查找
public int findRepeatNumber(int[] nums) {
int start = 1;
int end = nums.length - 1;
while (start <= end) {
int middle = (start + end) >> 1;
int count = countRange(nums, start, middle);
if (start == end) {
if (count > 1) {
return start;
} else {
break;
}
}
if (count > (middle - start + 1)) {
end = middle;
} else {
start = middle + 1;
}
}
return -1;
}
private int countRange(int[] nums, int start, int end) {
int count = 0;
for(int i = 0; i < nums.length; i++) {
if (nums[i] >= start && nums[i] <= end) {
count++;
}
}
return count;
} 面试题4：二维数组中的查找
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20- 算法
- 1.从矩阵的右上角开始寻找而不是从矩阵的左上角开始寻找，便于判断下一步走向
- 2.大于target的话，列数减一
- 3.小于target的话，行数加一
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int rows = matrix.length, cols = matrix[0].length;
int row = 0, col = cols - 1;
while (row < rows && col >= 0) {
if (matrix[row][col] > target) {
col--;
} else if (matrix[row][col] < target) {
row++;
} else {
return true;
}
}
return false;
} 面试题5：替换空格
题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。
- 算法
- 先遍历一遍统计空格个数，分配替换空格后新的char数组
public String replaceSpace(String s) {
if (s == null) {
return s;
}
int oldLength = s.length();
int numberOfBlank = 0;
for (char c : s.toCharArray()) {
numberOfBlank += (c == ' ' ? 1 : 0);
}
if(numberOfBlank == 0) {
return s;
}
int newLength = oldLength + (numberOfBlank << 1);
int indexOfOld = oldLength-1;
int indexOfNew = newLength-1;
StringBuilder sb = new StringBuilder(newLength);
while (indexOfOld >= 0) {
if (s.charAt(indexOfOld) == ' ') {
sb.insert(0, '0');
sb.insert(0, '2');
sb.insert(0, '%');
indexOfNew -= 3;
} else {
sb.insert(0, s.charAt(indexOfOld));
}
indexOfOld--;
if (indexOfNew == indexOfOld) {
sb.insert(0, s.substring(0, indexOfNew+1));
break;
}
}
return sb.toString();
} 面试题6：从尾到头打印链表
题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。
- 算法
- 算法1.第一次遍历统计元素，第二次遍历保存到数组
- 算法2.使用栈保存元素，再逐个弹出
// 不使用栈
public int[] reversePrint(ListNode head) {
ListNode node = head;
int count = 0;
while (node != null) {
count++;
node = node.next;
}
int[] res = new int[count];
node = head;
for (int i = count - 1; i >= 0; --i) {
res[i] = node.val;
node = node.next;
}
return res;
}
// 使用栈
public int[] reversePrint(ListNode head) {
if (head == null) {
return new int[0];
}
Stack<Integer> stack = new Stack<Integer>();
while (head != null) {
stack.push(head.val);
head = head.next;
}
int[] res = new int[stack.size()];
int i = 0;
while (!stack.empty()) {
res[i++] = stack.pop();
}
return res;
}
// 使用栈或递归打印结果
public void reverseTraverseListNode(ListNode head) {
if (head == null) {
return;
}
Stack<Integer> stack = new Stack<>();
while (head != null) {
stack.push(head.val);
head = head.next;
}
while (!stack.empty()) {
System.out.print(stack.pop()+" ");
}
}
public void reverseTraverseListNode(ListNode head) {
if (head != null) {
reverseTraverseListNode(head.next);
System.out.print(head.val+" ");
}
} 面试题7：重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1, 2, 4, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建出图2.6所示的二叉树并输出它的头结点。
1
/ \
2 3
/ / \
4 5 6
\ /
7 8
图 2.6- 算法
- 类似重建二叉树的统一算法
- 1.找出根节点
- 2.利用根节点计算左子树和右子树中的节点个数
- 3.利用节点个数递归构建左子树和右子树
public TreeNode buildTreeByPreorderAndInorder(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {
return null;
}
if (preorder.length != inorder.length) {
throw new RuntimeException("Invalid input");
}
return buildTreeByPreorderAndInorder(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
private TreeNode buildTreeByPreorderAndInorder(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
TreeNode root = new TreeNode(preorder[preStart]);
if (preStart == preEnd) {
if (preorder[preStart] == inorder[inStart]) {
return root;
} else {
throw new RuntimeException("Invalid input");
}
}
int rootIndex = inStart;
while (rootIndex < inEnd && inorder[rootIndex] != preorder[preStart]) {
rootIndex++;
}
if (rootIndex == inEnd && inorder[rootIndex] != preorder[preStart]) {
throw new RuntimeException("Invalid input");
}
int leftLength = rootIndex - inStart;
int rightLength = inEnd - rootIndex;
if (leftLength > 0) {
root.left = buildTreeByPreorderAndInorder(preorder, preStart+1, preStart+leftLength, inorder, inStart, rootIndex-1);
}
if (rightLength > 0) {
root.right = buildTreeByPreorderAndInorder(preorder, preStart+leftLength+1, preEnd, inorder, rootIndex+1, inEnd);
}
return root;
} 面试题8：二叉树的下一个结点
题目：给定一棵二叉树和其中的一个结点，如何找出中序遍历顺序的下一个结点？树中的结点除了有两个分别指向左右子结点的指针以外，还有一个指向父结点的指针。
- 算法：结点有指向父结点的引用
- 1.如果右子树不为空，下一个结点就是右子树中最左下方的结点
- 2.如果右子树为空
- 2.1如果当前结点没有父结点，它就是根节点，下一个结点就是null
- 2.2如果当前结点是父结点的左子结点，加上本身右子树为空，下一个结点就是父结点
- 2.3如果当前结点是父结点的右子结点，需要向上追溯直到当前结点是父结点的左子结点
public class TreeNode2 {
public int val;
public TreeNode2 left;
public TreeNode2 right;
public TreeNode2 parent;
public TreeNode2(int x) { val = x; }
}
public TreeNode2 nextNodeOfInorder(TreeNode2 node) {
if (node == null) {
return null;
}
if (node.right != null) {
TreeNode2 rightTree = node.right;
while (rightTree.left != null) {
rightTree = rightTree.left;
}
return rightTree;
} else {
TreeNode2 cur = node;
TreeNode2 parent = node.parent;
while (parent != null && cur == parent.right) {
cur = parent;
parent = parent.parent;
}
return parent;
}
} - 算法：标准二叉树
- 1.如果右子树不为空，下一个结点就是右子树中最左下方的结点
- 2.如果右子树为空
- 2.1如果当前结点没有父结点，它就是根节点，下一个结点就是null
- 2.2如果当前结点是父结点的左子结点，加上本身右子树为空，下一个结点就是父结点
- 2.3如果当前结点是父结点的右子结点，需要向上追溯直到当前结点是父结点的左子结点
- ps：寻找父节点的算法
- 递归算法
- 1.当root的左子树和右子树都不是node时，递归到左右子树寻找，然后判断寻找到与否
- 2.当root的左子树和右子树有一个是node时，父节点就是root
public TreeNode nextNodeOfInorder(TreeNode root, TreeNode node) {
if (root == null || node == null) {
return null;
}
if (node.right != null) {
TreeNode rightTree = node.right;
while (rightTree.left != null) {
rightTree = rightTree.left;
}
return rightTree;
} else {
TreeNode cur = node;
TreeNode parent = parentNode(root, node);
while (parent != null && cur == parent.right) {
cur = parent;
parent = parentNode(root, parent);
}
return parent;
}
}
private TreeNode parentNode(TreeNode root, TreeNode node) {
if (root == null || root.left == null && root.right == null) {
return null;
}
TreeNode parent = root;
if (root.left != node && root.right != node) {
TreeNode leftTree = parentNode(root.left, node);
TreeNode rightTree = parentNode(root.right, node);
if (leftTree != null) {
parent = leftTree;
} else if (rightTree != null) {
parent = rightTree;
} else {
parent = null;
}
}
return parent;
} 面试题9：栈和队列相互实现
题目一：用两个栈实现一个队列
题目一：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。
- 算法
- 1.添加时向第一个栈添加
- 2.删除时从第二个栈删除，如果是空，全部元素换栈删除栈顶元素
class CQueue {
public CQueue() {
}
public void appendTail(int value) {
}
public int deleteHead() {
}
} class CQueue <T> {
Stack<T> stack1 = new Stack<>();
Stack<T> stack2 = new Stack<>();
public CQueue() {
}
public void appendTail(T value) {
stack1.push(value);
}
public T deleteHead() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
if (stack2.empty()) {
throw new RuntimeException("Empty Queue");
}
return stack2.pop();
}
} 题目二：用两个队列实现一个栈
- 算法
- 1.添加时向非空的那个队列添加
- 2.删除时全部元素改变队列，最后一个元素删除；所以任何时刻一定有一个队列为空
class CStack <T> {
Queue<T> queue1 = new LinkedList<>();
Queue<T> queue2 = new LinkedList<>();
public CStack() {
}
public void appendTail(T value) {
if (queue2.isEmpty()) {
queue1.add(value);
} else {
queue2.add(value);
}
}
public T deleteTop() {
if (queue1.isEmpty() && queue2.isEmpty()) {
throw new RuntimeException("Empty Stack");
} else if (queue1.isEmpty()) {
while (queue2.size() > 1) {
queue1.add(queue2.poll());
}
return queue2.poll();
} else {
while (queue1.size() > 1) {
queue2.add(queue1.poll());
}
return queue1.poll();
}
}
} 
京公网安备 11010502036488号