数据结构类题目
Array
- 面试题3: 数组中重复的数字
- 面试题4: 二维数组中的查找
- 面试题11: 旋转数组中的最小数字
- 面试题21: 调整数组顺序使奇数位于偶数前面
- 面试题29: 顺时针打印矩阵
- 面试题39: 数组中出现次数操作一半的数字
- 面试题42: 连续子数组的最大和
- 面试题45: 把数组排成最小的数
- 面试题47: 礼物的最大值
- 面试题51: 数组中的逆序对
- 面试题53: 在排序数组中查找数字
- 面试题53-I: 在排序数组中查找数字I
- 面试题53-II: 0 ~ n-1 中缺失的数字
- 面试题56: 数组中数字出现的次数
- 面试题66: 构建乘积数组
LinkedList
- 面试题6：从尾到头打印链表
- 面试题18：删除链表的节点
- 面试题22：链表中倒数第k个结点
- 面试题23：链表中环的入口节点
- 面试题24：反转链表
- 面试题25：合并两个或k个有序链表
- 面试题35：复杂链表的复制
- 面试题36： 二叉搜索树与双向链表
- 面试题52：两个链表的第一个公共结点
- 面试题56：删除链表中重复的结点
Tree
- 面试题7：重建二叉树
- 面试题26：树的子结构
- 面试题27：二叉树的镜像
- 面试题28：对称的二叉树
- 面试题32-I：从上到下打印二叉树
- 面试题32-II：从上到下打印二叉树 II
- 面试题32-III：从上到下打印二叉树 III
- 面试题33：二叉搜索树的后序遍历序列
- 面试题34： 二叉树中和为某一值的路径
- 面试题36：二叉搜索树与双向链表
- 面试题37：序列化二叉树
- 面试题54：二叉搜索树的第k大节点
- 面试题55-I： 二叉树的深度
- 面试题55-II：平衡二叉树
- 面试题68-I：二叉搜索树的最近公共祖先
- 面试题68-II：二叉树的最近公共祖先
Stack & Queue
Heap
Hash Table
- 面试题3: 数组中重复的数字
图
具体算法类题目
搜索算法
- 面试题4: 二维数组中的查找
- 面试题11: 旋转数组的最小数字
- 面试题39: 数组中出现次数超过一半的数字
动态规划
面试题10-I: 10- I. 斐波那契数列
面试题10-II: 10- II. 青蛙跳台阶问题
面试题19: 19. 正则表达式匹配
面试题42: 42. 连续子数组的最大和
面试题46: 46. 把数字翻译成字符串
面试题47: 47. 礼物的最大价值
面试题48: 48. 最长不含重复字符的子字符串
面试题49: 49. 丑数
面试题60: 60. n 个骰子的点数
面试题63: 63. 股票的最大利润
回溯
- 面试题12: 矩阵中的路径
- 面试题13: 机器人的运动范围
排序
- 面试题29: 最小的k个数 (堆排序)
- 面试题39: 数组中出现次数超过一半的数字 (快排序)
- 面试题51: 数组中的逆序对(归并排序)
位运算
- 面试题15: 二进制中1的个数
- 面试题56-I: 数组中数字出现的次数
- 面试题56-II: 数组中数字出现的次数 II
刷题记录
面试题3-I：数组中重复的数字
题目一：找出数组中的重复数字
方法一: 排序之后 查找
排序，之后遇到有重复的返回该数字即可
时间复杂度： O(nlogn)
空间复杂度：O(1)
// 内置排序算法
public int findRepeatNumber(int[] arrays) {
Arrays.sort(arrays);
int t = 0;
for (int i = 0; i < arrays.length-1; i++) {
if (arrays[i] == arrays[i + 1]) {
t = arrays[i];
}
}
return t;
}
// 使用快排
public int findRepeatNumber(int[] nums) {
quickSort(nums);
for(int i = 1; i<nums.length; i++){
if(nums[i] == nums[i-1]){
return nums[i];
}
}
return -1;
}
private void quickSort(int[] nums){
quickSort(nums, 0, nums.length-1);
}
private void quickSort(int[] nums, int low, int high){
if(low > high){
return;
}
else{
int position = patition(nums, low, high);
quickSort(nums, low, position-1);
quickSort(nums, position+1, high);
}
}
private int patition(int[] nums, int low, int high){
int position = nums[low];
while(low < high){
while(low < high && nums[high] >= position){
high--;
}
nums[low] = nums[high];
while(low < high && nums[low] <= position){
low++;
}
nums[high] = nums[low];
}
nums[low] = position;
return low;
}
方法二: 散列表
将所有的元素当做key存如散列表，value表示key出现的个数
public int findRepeatNumber(int[] nums) {
int a = 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i : nums) {
if (map.containsKey(i)) {
Integer integer = map.get(i);
integer += 1;
a = i;
} else {
map.put(i, 0);
}
}
return a;
}
方法三: 位图
具体可参见编程珠玑或算法新解
面试题3-II：不修改数组，找出重复的数字
二分查找287. 寻找重复数
public int findDuplicate(int[] nums) {
int i = 0;
int j = nums.length - 1;
while( i < j ){
// j = mid
// 所以 mid = (i+j)/2
// 若果i = mid
// 则 mid = (i + j + 1)/2
int mid = (i + j) /2;
int count = 0;
// 统计小于中值的数量
for(int num : nums){
if(num <= mid){
count++;
}
}
// 如果统计出的数量>中值
// 重复的元素可定出现在i~mid区间, 所以mid+1~j区间就可以不用考虑了
if(count > mid){
j = mid;
}else {
i = mid + 1;
}
}
return i;
}
面试题4：二维数组查找
从左下角开始
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int m = matrix.length -1;
int n = 0;
while(m >= 0 && n<=matrix[0].length-1){
if(matrix[m][n] < target){
n++;
}else if(matrix[m][n] > target){
m--;
}
else {
return true;
}
}
return false;
}
面试题5：替换空格
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == ' '){
sb.append("%20");
}
else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
面试题6：从尾到头打印链表
public int[] reversePrint(ListNode head) {
// 使用栈
ListNode p = head;
Stack<ListNode> stack = new Stack<>();
while (p != null){
stack.push(p);
p = p.next;
}
int[] res = new int[stack.size()];
int i = 0;
while (!stack.isEmpty()){
res[i++] = stack.pop().val;
}
return res;
}
// 头插法重新构造链表 然后依次放入
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ListNode dummy = new ListNode(-1);
ArrayList<Integer> list = new ArrayList<>();
while(listNode != null){
ListNode temp = listNode.next;
listNode.next = dummy.next;
dummy.next = listNode;
listNode = temp;
}
listNode = dummy.next;
while(listNode != null){
list.add(listNode.val);
listNode = listNode.next;
}
return list;
}
面试题7： 重建二叉树
public static TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> inMap = new HashMap<Integer, Integer>();
for (int i = 0; i < inorder.length; i++) {
inMap.put(inorder[i], i);
}
TreeNode root = buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
return root;
}
public static TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {
if (preStart > preEnd) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
// 当前根节点所在中序遍历位置
int inRoot = inMap.get(root.val);
// 该根节点左边子节点的个数
int numsLeft = inRoot - inStart;
root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorder, inStart, inRoot - 1, inMap);
root.right = buildTree(preorder, preStart + numsLeft + 1 , preEnd, inorder, inRoot + 1, inEnd, inMap);
return root;
}
面试题8： 二叉树的下一个节点
面试题9： 两个栈实现队列
// 使用两个栈实现队列
Deque<Integer> A, B;
public interview9() {
A = new ArrayDeque<>();
B = new ArrayDeque<>();
}
public void appendTail(int value) {
A.push(value);
}
public int deleteHead() {
if (!B.isEmpty()) {
return B.removeLast();
}
// 表明两个栈都为空了, 所以没有能返回的值了
if (A.isEmpty()) {
return -1;
}
while (!A.isEmpty()) {
B.addLast(A.removeLast());
}
return B.removeLast();
}
面试题10： 斐波那契数列
方法一：递归
方法二：DP
题目二：青蛙跳台阶
题目三： 矩阵覆盖
面试题11： 旋转数组中的最小数字
二分查找, 注意元素会重复
public int minArray(int[] numbers) {
int i = 0;
int j = numbers.length -1;
while(i < j){
int mid = (i + j )/2;
if(numbers[mid] > numbers[j]){
i = mid + 1;
}else if(numbers[mid] < numbers[j]){
j = mid;
}else {
j -= 1;
}
}
return numbers[i];
}
面试题12：矩阵中的路径
public boolean exist(char[][] matrix, String str) {
int n = matrix.length;
int m = matrix[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (hasPathCore(matrix, str, 0, i, j)) {
return true;
}
}
}
return false;
}
public boolean hasPathCore(char[][] matrix, String str, int start, int row, int col) {
int n = matrix.length;
int m = matrix[0].length;
if (start == str.length()) {
return true;
}
if (row < 0 || row >= n || col < 0 || col >= m || matrix[row][col] != str.charAt(start)) {
return false;
}
char c = matrix[row][col];
matrix[row][col] = ' ';
boolean result = hasPathCore(matrix, str, start + 1, row + 1, col)
|| hasPathCore(matrix, str, start + 1, row - 1, col)
|| hasPathCore(matrix, str, start + 1, row, col + 1)
|| hasPathCore(matrix, str, start + 1, row, col - 1);
matrix[row][col] = c;
return result;
}
面试题13：机器人的运动范围
private int count = 0;
public int movingCount(int m, int n, int k) {
boolean[][] vistied = new boolean[m][n];
visit(vistied, k, m, n, 0, 0);
return count;
}
public void visit(boolean visited[][], int k , int m, int n, int i, int j){
if(i <0 || i>=m || j < 0 || j>= n || visited[i][j] || cal(i, j) > k){
return;
}
visited[i][j] = true;
count++;
visit(visited, k, m, n, i+1, j);
visit(visited, k, m, n, i-1, j);
visit(visited, k, m, n, i, j+1);
visit(visited, k, m, n, i, j -1);
}
private int cal(int i, int j) {
int calI = calculate(i);
int calJ = calculate(j);
return calI + calJ;
}
private int calculate(int num){
int sum = 0;
while (num != 0){
sum += (num%10);
num /= 10;
}
return sum;
}
面试题14：剪绳子
动态规划
//理解不好
public int cuttingRope(int n) {
if (n <= 3) {
return n - 1;
}
int a = n / 3;
int b = n % 3;
if (b == 0) {
return (int) Math.pow(3, a);
} else if (b == 1) {
return (int) (Math.pow(3, a - 1) * 4);
}
return (int) Math.pow(3, a) * 2;
}
public int cuttingRopeII(int n) {
int[] dp = new int[n+1];
if(n<=1){
return 0;
}
if(n==2){
return 1;
}
if(n==3){
return 2;
}
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
int max = 0;
int temp = 0;
for(int i = 4; i<=n; i++){
for(int k=1; k<=i/2; k++){
temp = dp[k] * dp[i-k];
if(max < temp){
max = temp;
}
}
dp[i] = max;
}
return dp[n];
}
面试题15：二进制中1个个数
public static int numberOf2(int n){
// n & (n - 1) 会消除 n 中最后一位中的 1。
int res = 0;
while (n != 0){
n &= (n-1);
res++;
}
return res;
}
面试题16：数值的整数次方
面试题17：打印从1到最大的n位整数
public int[] printNumbers(int n ){
int nums = (int) Math.pow(10, n);
int[] res = new int[nums-1];
for (int i = 0; i < nums-1; i++) {
res[i] = i+1;
}
return res;
}
面试题18：删除链表的节点
public static ListNode deleteNode(ListNode head, ListNode q) {
ListNode dummy = new ListNode(-1);
if (head == null) {
return null;
}
dummy.next = head;
ListNode pre = dummy;
ListNode p = head;
while (p != null) {
if (p == q) {
pre.next = p.next;
p = pre.next;
}
else {
pre = p;
p = p.next;
}
}
return dummy.next;
}
面试题19：正则表达式匹配
还没理好
面试题20：表示数值的字符串
按照题目提示写就是了
.:.之前不能出现.和ee:e之前不能出现e, 且前一位必须是数字,且后面必须还要有数字+/-:+/-只能出现在0位置或者e后面
public static boolean isNumber(String s) {
if(s == null || s.length() == 0){
return false;
}
boolean res = true;
boolean isNums = false;
boolean isDot = false;
boolean isE = false;
String trim = s.trim();
for (int i = 0; i < trim.length(); i++) {
if (trim.charAt(i) <= '9' && trim.charAt(i) >= '0') {
isNums = true;
} else if (trim.charAt(i) == 'e' || trim.charAt(i) == 'E') {
if (!isNums || isE) {
return false;
}
isE = true;
// 防止出现12e的情况(不能表示数字)
isNums = false;
} else if (trim.charAt(i) == '.') {
if (isE || isDot) {
return false;
}
isDot = true;
} else if (trim.charAt(i) == '+' || trim.charAt(i) == '-') {
if (i != 0 && trim.charAt(i - 1) != 'E' && trim.charAt(i - 1) != 'e') {
return false;
}
} else {
return false;
}
}
return isNums;
}
面试题21：调整数组顺序使奇数位于偶数前面
// 最直白的做法，依次遍历，然后遇到偶数的时候
// 后面的元素调前面，该元素放置末尾
public int[] exchange(int[] nums) {
if (nums == null || nums.length < 2) {
return nums;
}
int left = 0;
int right = nums.length - 1;
int temp[] = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if ((nums[i] & 1) == 0) {//偶数
temp[right--] = nums[i];
} else {//奇数
temp[left++] = nums[i];
}
}
return temp;
}
// 双指针方法
public static int[] exchangeII(int[] nums) {
int p = 0;
int q = nums.length - 1;
while (p < q) {
while (p < q && nums[p] % 2 == 0) {
if(nums[q] %2 == 1){
int temp = nums[p];
nums[p] = nums[q];
nums[q] = temp;
p++;
q--;
}else if(nums[q] %2 == 0){
q--;
}
}
while (p < q && nums[p]%2 == 1){
p++;
}
}
return nums;
}
// 上面的逻辑 是基于正常交换逻辑
// 但是是依次处理， 可以先假设符合条件， 之后将不符合条件的一一处理
// 类似快排的枢轴处理
// 代码的可读性更高
public static int[] exchangeIII(int[] nums){
int pBegin = 0;
int pRear = nums.length-1;
while (pBegin < pRear){
while (pBegin < pRear && nums[pBegin]%2 == 1){
pBegin ++;
}
while (pBegin < pRear && nums[pRear] %2 == 0){
pRear--;
}
if(pBegin < pRear){
int temp = nums[pBegin];
nums[pBegin] = nums[pRear];
nums[pRear] = temp;
}
}
return nums;
}
面试题22：链表中倒数第K个节点
// 遍历两次链表
public static ListNode getKthFromEnd(ListNode head, int k){
if(head==null){
return null;
}
int length = getLength(head);
if(k>length){
return null;
}
if(k==length){
return head;
}
ListNode preNode = getPreNode(head, length - k);
return preNode.next;
}
private static ListNode getPreNode(ListNode head, int preK){
while (preK > 1){
head = head.next;
preK--;
}
return head;
}
private static int getLength(ListNode head){
int length = 0;
while (head != null){
head = head.next;
length ++;
}
return length;
}
// 双指针解决
public static ListNode getKthFromEndII(ListNode head, int k){
if(head == null || k==0){
return null;
}
ListNode fast = head;
ListNode slow = head;
while (k-1 > 0){
fast = fast.next;
k--;
}
while (fast.next != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
面试题23：链表中环的入口节点
双指针之快慢指针
public ListNode meetingNode(ListNode head) {
ListNode entry = null;
if (head == null) {
return entry;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
ListNode slowII = head;
while (slow != slowII) {
slowII = slowII.next;
slow = slowII.next;
}
return slow;
}
}
return null;
}
面试题24：反转链表
头插法
public static ListNode reverseList(ListNode head){
ListNode dummmy = new ListNode(-1);
ListNode p = head;
while (p != null){
ListNode temp = p.next;
p.next = dummmy.next;
dummmy.next = p;
p = temp;
}
return dummmy.next;
}
面试题25： 合并两个排序的链表
// 尾插法
public ListNode mergeTwoLists(ListNode l1, ListNode l2){
ListNode dummy = new ListNode(-1);
ListNode rear = dummy;
while (l1!= null && l2!= null){
if(l1.value <= l2.value){
rear.next = l1;
l1 = l1.next;
}else {
rear.next = l2;
l2 = l2.next;
}
rear = rear.next;
}
if (l1 != null){
rear.next = l1;
}
if (l2!= null) {
rear.next = l2;
}
return dummy.next;
}
面试题26：树的子结构
public boolean isSubStructure(TreeNode A, TreeNode B){
boolean res = false;
if(A!=null && B!=null){
if(A.val == B.val){
res = doesHaveTree2(A, B);
}if(!res){
res = isSubStructure(A.left, B);
}if(!res){
res = isSubStructure(A.right, B);
}
}
return res;
}
private boolean doesHaveTree2(TreeNode A, TreeNode B){
if(B == null) {
return true;
}
if(A == null){
return false;
}
if(A.val != B.val){
return false;
}
return doesHaveTree2(A.left, B.left) && doesHaveTree2(A.right, B.right);
}
面试题27：二叉树的镜像
public TreeNode mirrorTree(TreeNode root) {
if (root != null) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirrorTree(root.left);
mirrorTree(root.right);
}
return root;
}
面试题28：对称二叉树
// 递归
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetric(root.left, root.right);
}
private boolean isSymmetric(TreeNode left, TreeNode right) {
if (left == null && right == null) {
return true;
}
if ((left != null && right == null) || (left == null && right != null)
|| (left.value != right.value)){
return false;
}
return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}
面试题29： 顺时针打印矩阵
打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。基础点为（0,0）
流程
空值处理
初始化， 初始化 上下左右的四个边界
t、b、l、r循环打印
根据边界依次添加到
res尾部边界修改（内缩1）
边界是否相遇，若相遇则打印完毕
| 打印方向 | 根据边界打印 | 边界内缩 | 是否打印完毕 |
| :———: | :—————————: | :———: | :—————: |
| 从左到右 | 左边界：l，右边界: r | t+1 | 是否t+1>b |
| 从上到下 | 上边界: t，下边界: b | r-1 | 是否r-1r |
public int[] spiralOrderII(int[][] martix){
if(martix.length == 0){
return new int[0];
}
int l, r, t, b, x=0;
l = 0;
r = martix[0].length-1;
t = 0;
b = martix.length-1;
int[] res = new int[(r + 1) * (b + 1)];
while (true){
// 从左到右
for (int i = l; i <= r; i++) {
res[x++] = martix[t][i];
}
if(++t > b){
break;
}
// 从上到下
for (int i = t; i <= b; i++) {
res[x++] = martix[i][r];
}
if(--r < l){
break;
}
// 从右到左
for (int i = r; i >= l; i--) {
res[x++] = martix[b][i];
}
if(--b < t){
break;
}
// 从下到上
for (int i = b; i >= t; i--) {
res[x++] = martix[i][l];
}
if(++l > r){
break;
}
}
return res;
}
面试题30： 包含min函数的栈
函数设计：
- push(x) 函数： 重点为保持栈 B 的元素是 非严格降序 的。
- 将 x 压入栈 A （即 A.add(x) ）
- 若栈 B 为空 或 x 小于等于 栈 B 的栈顶元素，则将 x 压入栈 B（即 B.add(x) ）。
- pop() 函数： 重点为保持栈 A, B 的 元素一致性 。
- 执行栈 AA 出栈（即 A.pop() ），将出栈元素记为 yy ；
- 若 y 等于栈 B 的栈顶元素，则执行栈 B 出栈（即 B.pop() ）。
- top() 函数： 直接返回栈 A 的栈顶元素即可，即返回 A.peek() 。
- min() 函数： 直接返回栈 BB 的栈顶元素即可，即返回 B.peek() 。
private Stack<Integer> stackA, stackB;
public Interview30() {
stackA = new Stack<>();
stackB = new Stack<>();
}
public void push(int x) {
stackA.push(x);
if(stackB.isEmpty() || x <= stackB.peek()){
stackB.push(x);
}
}
public void pop() {
if(stackA.pop().equals(stackB.peek())){
stackB.pop();
}
}
public int top() {
return stackA.peek();
}
public int min() {
return stackB.peek();
}
面试题31：栈的压入、弹出序列
建立一个辅助栈，只有给定了一个压入和弹出序列，才能确定栈的压入和弹出的顺序。按照题目给的入栈序列[1,2,3,4,5] 和出栈序列[4,5,3,2,1]为例
| 步骤 | 压入操作 | 辅助栈 | 弹出数字 |
|---|---|---|---|
| 1 | 压入1 | 1 | |
| 2 | 压入2 | 1、2 | |
| 3 | 压入3 | 1、 2、 3 | |
| 4 | 压入4 | 1、 2、 3、4 | |
| 5 | 弹出 | 1、 2、 3 | 4 |
| 6 | 压入5 | 1、2、 3、 5 | |
| 7 | 弹出 | 1、 2、 3 | 5 |
| 8 | 弹出 | 1、 2 | 3 |
| 9 | 弹出 | 1 | 2 |
| 10 | 弹出 | 1 |
依次思路，实现如下：
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int i = 0;
for (int num : pushed) {
stack.push(num);
while (!stack.isEmpty() && stack.peek() == popped[i]){
stack.pop();
i++;
}
}
return stack.isEmpty();
}
面试题32：从上到下打印二叉树
层次遍历
public int[] levelOrder(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return new int[0];
}
Queue<TreeNode> queue = new LinkedList(){{add(root);}};
TreeNode q;
while (!queue.isEmpty()){
for (int i = 0; i < queue.size(); i++) {
q = queue.poll();
list.add(q.val);
if(q.left != null){
queue.add(q.left);
}
if(q.right!=null){
queue.add(q.right);
}
}
}
int[] res = new int[list.size()];
int i = 0;
for (Integer integer : list) {
res[i++] = integer;
}
return res;
}
面试题32-2：分行从上到下打印二叉树
每一层打印一行
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>();
List<Integer> out = new ArrayList<>();
if(root == null){
return lists;
}
Queue<TreeNode> queue = new LinkedList() {{
add(root);
}};
int preCount = 1;
int count = 0;
while (!queue.isEmpty()){
TreeNode p = queue.poll();
out.add(p.val);
preCount--;
if(p.left != null){
queue.add(p.left);
count++;
}
if (p.right != null) {
queue.add(p.right);
count++;
}
if(preCount == 0){
preCount = count;
count=0;
lists.add(out);
out = new ArrayList<>();
}
}
return lists;
}
面试题32-3：分行从上到下zigzag打印二叉树
判断当前行数为奇偶即可说白了就是通过层次遍历获取二叉树的高度。
public static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> out = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
int level = 0;
queue.add(root);
while (!queue.isEmpty()){
level ++;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode p = queue.poll();
if(level % 2 == 1){
out.add(p.val);
}else if(level % 2 == 0){
out.add(0, p.val);
}
if(p.left !=null){
queue.add(p.left);
}
if(p.right != null){
queue.add(p.right);
}
}
res.add(out);
out = new ArrayList<>();
}
return res;
}
面试题33：二叉搜索树的后序遍历序列
递归，还有一个辅助栈的解法，暂时还没看懂，就不贴了
递归的思想和书上一模一样，确定好递归的返回值、终止条件、当前层处理逻辑即可
public boolean verifyPostorder(int[] postorder) {
if(postorder == null || postorder.length == 0){
return true;
}
return verifyPostorder(postorder, 0, postorder.length-1);
}
private boolean verifyPostorder(int[] postorder, int start, int end){
// 终止条件
if(start>=end){
return true;
}
// 当前层处理逻辑
int p = start;
while (postorder[p] < postorder[end]) {
p++;
}
int m = p;
while (postorder[p] > postorder[end]){
p++;
}
// 返回值
return p == end && verifyPostorder(postorder, start, m-1) && verifyPostorder(postorder, m, end-1);
}
面试题34：二叉树中和为某一值的路径
这个，直接dfs吧
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> results = new ArrayList<>();
if(root == null){
return results;
}
List<Integer> out = new ArrayList<>();
backTrack(root , results, out, sum);
return results;
}
private void backTrack(TreeNode root, List<List<Integer>> lists, List<Integer> out, int ta
if(root == null){
return;
}
out.add(root.val);
if(root.left == null && root.right == null && root.val == target){
lists.add(new ArrayList<>(out));
}
backTrack(root.left, lists, out, target-root.val);
backTrack(root.right, lists, out, target-root.val);
out.remove(out.size()-1);
}
面试题35：复杂链表的复制
在复杂链表中，每个节点除了有一个
next指针指向下一个节点，还有一个random指针指向链表中的任意节点或者null。
方法1：
- 先复制链表上的每个节点，将创建的节点使用
next指针链接 - 在原链表上寻找
random指针指向的位置，然后新链表上找对应的位置即可
方法2：
- 先复制链表上的每个节点，将创建的节点使用
next指针链接，同时创建map，存储每个节点的random指向 - 新链表确定
random时，通过map查找
public Node copyRandomList(Node head) {
Map<Node, Node> map = new HashMap<>();
Node nodeNew = new Node(head.val);
map.put(head, nodeNew);
Node oldP = head;
Node newP = nodeNew;
// 第一步 复制节点&next指针
while (oldP.next != null){
newP.next = new Node(oldP.next.val);
newP = newP.next;
oldP = oldP.next;
map.put(oldP, newP);
}
// 第二步 复制random指针
oldP = head;
newP = nodeNew;
while (oldP != null){
if(oldP.random!=null){
newP.random = map.get(oldP.random);
}
newP = newP.next;
oldP = oldP.next;
}
return nodeNew;
}
方法3：
- 将复制的每个新节点插入原链表的原节点的后面(原节点奇数位置、复制节点偶数位置)
- 原链表的节点的
random指向S，对应的新节点指向S的复制节点S' - 按照奇偶位置拆分链表即可
面试题36：二叉搜索树与双向链表
不同思路:
和书上的思路略有不同，这道题的核心是中序遍历，书中是遍历到根节点的时候进行处理。我们可以直接进行构造双向链表，不用考虑是否为根节点。
构造双向链表的基础(当前遍历到的节点cur, 其前驱节点pre):
- 不仅要
cur.left = pre还要pre.right = cur - 最后，构造的双向链表的头结点
head和尾节点tail需要head.left = tail,tail.right = head
二叉树的中序遍历
void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
// 操作节点
dosomething();
inOrder(root.right);
}
实现
Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null){
return null;
}
recur(root);
head.left = pre;
pre.right = head;
return head;
}
private void recur(Node cur) {
if(cur == null){
return;
}
recur(cur.left);
if(pre != null){
pre.right = cur;
}else {
// 确定头节点
head = cur;
}
cur.left = pre;
pre = cur;
recur(cur.right);
}
面试题37：序列化二叉树
private final String delimiter = ",";
private final String emptyNode = "#";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
if (root == null) {
return emptyNode;
}
serialize(root, sb);
return sb.toString();
}
private void serialize(TreeNode cur, StringBuilder sb) {
if (cur == null) {
sb.append(emptyNode).append(delimiter);
return;
}
sb.append(cur.val).append(delimiter);
serialize(cur.left, sb);
serialize(cur.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Deque<String> nodes = new LinkedList<>();
nodes.addAll(Arrays.asList(data.split(delimiter)));
return deserialize(nodes);
}
private TreeNode deserialize(Deque<String> nodes) {
String s = nodes.pollFirst();
if(s.equalsIgnoreCase(emptyNode)){
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(s));
root.left = deserialize(nodes);
root.right = deserialize(nodes);
return root;
}
面试题38： 字符串的排列
排列问题，使用回溯
面试题39：数组中刚出现次数超过一半的数字
方法一: 使用map
public static int majorityElement(int[] nums) {
int ret = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.compute(num, (k, v) -> {
if (null == v) {
v = 0;
}
v = v + 1;
return v;
});
if (map.get(num) > nums.length / 2) {
ret = num;
break;
}
}
return ret;
}
方法二：快排枢轴思想
// 快排思想
// 枢轴的选择，若是选择start, 则从high开始while循环。若是选择high,则从low开始while循环
public static int majorityElementII(int[] nums) {
int middle = nums.length >> 1;
int len = nums.length;
int start = 0;
int end = nums.length - 1;
int partition = partition(nums, start, end, len);
while (partition != middle) {
if (partition < middle) {
start = partition + 1;
partition = partition(nums, start, end, len);
} else {
end = partition - 1;
partition = partition(nums, start, end, len);
}
}
if (isMoreThanHalf(nums, len, nums[middle])) {
return nums[middle];
}
return 0;
}
private static int partition(int[] nums, int i, int j, int length) {
if (nums == null || length == 0 || i < 0 || j >= length) {
throw new IllegalArgumentException("输入错误");
}
int partition = nums[j];
while (i < j) {
while (i < j && nums[i] <= partition) {
i++;
}
nums[j] = nums[i];
while (i < j && nums[j] >= partition) {
j--;
}
nums[i] = nums[j];
}
nums[j] = partition;
return i;
}
private static boolean isMoreThanHalf(int[] nums, int length, int num) {
int times = 0;
for (int i = 0; i < length; i++) {
if (nums[i] == num) {
times++;
}
}
boolean flag = true;
if (times * 2 <= length) {
flag = false;
}
return flag;
}
方法三：摩尔投票法
// 摩尔投票
public int majorityElementIII(int[] nums) {
int votes = 0;
int mark = 0;
for (int num : nums) {
if (votes == 0) {
mark = num;
}
votes += num == mark ? 1 : -1;
}
return mark;
}
面试题40：最小的k个数
public int[] getLeastNumbers(int[] arr, int k) {
if(k == arr.length){
return arr;
}
int start = 0;
int end = arr.length - 1;
int length = arr.length;
int partition = partition(arr, start, end, length);
while (partition != k) {
if (partition < k) {
start = partition + 1;
partition = partition(arr, start, end, length);
} else {
end = partition - 1;
partition = partition(arr, start, end, length);
}
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
private int partition(int[] nums, int start, int end, int length) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("参数错误");
}
int partition = nums[start];
while (start < end) {
while (start < end && nums[end] >= partition) {
end--;
}
nums[start] = nums[end];
while (start < end && nums[start] <= partition) {
start++;
}
nums[end] = nums[start];
}
nums[start] = partition;
return start;
}
面试题41：数据流中的中位数
class MedianFinder {
Queue<Integer> A, B;
/** initialize your data structure here. */
public MedianFinder() {
A = new PriorityQueue<>();
B = new PriorityQueue<>((x, y) -> (y - x));
}
public void addNum(int num) {
if(A.size() != B.size()) {
A.add(num);
B.add(A.poll());
} else {
B.add(num);
A.add(B.poll());
}
}
public double findMedian() {
return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
}
}
面试题42：连续数组的最大和
public static int maxSubArray(int[] nums) {
int sum = 0;
int maxSum = nums[0];
for (int num : nums) {
sum += num;
if (sum < 0) {
sum = 0;
}
if (maxSum < sum) {
maxSum = sum;
}
}
return maxSum;
}
面试题43：1~N整数中1出现的次数
首先想到的是最基础的算法，暴力枚举(当N非常大的时候，计算就会特别特别慢，时间复杂度 $O(NlogN)$)
public int countDigitOne(int n) {
int sum = 0;
for (int i = 1; i <=n; i++) {
int count = countNumberOf1(i);
sum += count;
}
return sum;
}
private int countNumberOf1(int n){
int count = 0;
while (n != 0){
if(n %10 == 1){
count++;
}
n /= 10;
}
return count;
}
第二种解法：
这个和剑指offer中的思想不太一样，但是也都是递归的思想，思路
简单总结：将 1 ~ n 的个位、十位、百位、…1 出现次数相加，即为 1 出现的总次数。
刚开始是分类讨论，当前位的出现1的次数：
- 当前位为1
- 当前位为0
- 当前位为2~9
public int countDigitOneII(int n){
int digits=1, res = 0;
int high = n / 10, cur = n%10, low = 0;
while (high != 0 || cur != 0){
if(cur == 1){
res += high*digits + low +1;
}else if(cur == 0){
res += high * digits;
}else {
res += (high+1) * digits;
}
low += cur * digits;
cur = high %10;
high = high/10;
digits *= 10;
}
return res;
}
面试题44：数字序列中某一位的数字
面试题45：把数组排成最小数
排序问题, 自定义比大小规则
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
int i = 0;
for (int num : nums) {
strs[i++] = String.valueOf(num);
}
Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str);
}
return sb.toString();
}
public String minNumberII(int[] nums) {
String[] strs = new String[nums.length];
int i = 0;
for (int num : nums) {
strs[i++] = String.valueOf(num);
}
StringBuilder stringBuilder = new StringBuilder();
// 快排
quickSort(strs, 0, strs.length-1);
for (String str : strs) {
stringBuilder.append(str);
}
return stringBuilder.toString();
}
private void quickSort(String[] strings, int low, int high){
if(low == high){
return;
}
if(low < high){
int pri = pri(strings, low, high);
quickSort(strings, low, pri-1);
quickSort(strings, pri+1, high);
}
}
private int position(String[] strs, int left, int right) {
String temp = strs[left];
while (left < right) {
while(left < right && (strs[right] + temp).compareTo((temp + strs[right])) >= 0) {
right--;
}
strs[left] = strs[right];
while(left < right && (strs[left] + temp).compareTo((temp + strs[left])) <= 0) {
left++;
}
strs[right] = strs[left];
}
strs[left] = temp;
return left;
}
面试题46: 把数字翻译成字符串
public int translateNum(int num) {
String s = String.valueOf(num);
int[] dp = new int[s.length()+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= s.length(); i ++){
String temp = s.substring(i-2, i);
if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
dp[i] = dp[i-1] + dp[i-2];
else
dp[i] = dp[i-1];
}
return dp[s.length()];
}
面试题47: 礼物的最大值
动态规划
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
continue;
}
if (i == 0) {
grid[i][j] += grid[i][j - 1];
} else if (j == 0) {
grid[i][j] += grid[i - 1][j];
} else {
grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
}
}
}
return grid[m - 1][n - 1];
}
面试题48: 最长不含重复字符串的子字符串
滑动窗口
// 滑动窗口
public static int lengthOfLongestSubstring(String s) {
if(s==null || s.length()==0){
return 0;
}
int low = 0;
int height = 0;
int maxSize = 0;
List<Character> list = new ArrayList<>();
while (height < s.length()){
while (height < s.length() && !list.contains(s.charAt(height))){
list.add(s.charAt(height));
height++;
maxSize = Math.max(maxSize, list.size());
}
while (height < s.length() && list.contains(s.charAt(height))){
list.remove(0);
}
}
return maxSize;
}
面试题49：丑数
最直白的方式超出了时间限制，所以使用动态规划
public static int nthUglyNumber(int n){
int a = 0, b = 0, c = 0;
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
dp[i] = Math.min(Math.min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
if(dp[i] == dp[a] *2){
a++;
}
if(dp[i] == dp[b] * 3){
b++;
}
if(dp[i] == dp[c] * 5){
c++;
}
}
return dp[n-1];
}
面试题50：第一只出现一次的字符
使用一个Map，利用空间换时间即可
public char firstUniqChar(String s) {
Map<Character, Boolean> map = new HashMap<>();
char[] sc = s.toCharArray();
for (char c : sc) {
map.put(c, !map.containsValue(c));
if(map.get(c)){
return c;
}
}
return ' ';
}
面试题51：数组中的逆序对
最基础的思路，暴力双for循环，不出意外，会超时
public int reversePairs(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length-1; i++) {
for (int j = i+1; j < nums.length; j++) {
if(nums[i] > nums[j]){
count++;
}
}
}
return count;
}
第二种思路：回溯
好吧，也超时了
public static int reversePairsII(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> out = new ArrayList<>();
backtrack(nums, res, out, 0);
return res.size();
}
private static void backtrack(int[] nums, List<List<Integer>> res, List<Integer> out, int start) {
if (out.size() == 2) {
res.add(new ArrayList<>(out));
}
for (int i = start; i < nums.length; i++) {
if(!out.isEmpty() && out.get(0) < nums[i]){
continue;
}
out.add(nums[i]);
backtrack(nums, res, out, i + 1);
out.remove(out.size() - 1);
}
}
第三种思路：归并思想（炸裂，写不出来）
public int reversePairsIII(int[] nums){
int length = nums.length;
if(length < 2){
return 0;
}
// copy数组，用于数组操作
int[] copy = new int[length];
int i = 0;
for (int num : nums) {
copy[i++] = num;
}
// 用于存储操作后的数据
int[] temp = new int[length];
return reversePairsIII(copy, 0, length-1, temp);
}
/**
* nums[left..right] 计算逆序对个数并且排序
* @param nums
* @param left
* @param right
* @param temp
* @return
*/
private int reversePairsIII(int[] nums, int left, int right, int[] temp) {
int mid = left + (right - left) / 2;
int leftPairs = reversePairsIII(nums, left, mid, temp);
int rightPairs = reversePairsIII(nums, mid + 1, right, temp);
if (nums[mid] <= nums[mid + 1]) {
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(nums, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}
private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
for (int i = 0; i < nums.length; i++) {
temp[i] = nums[i];
}
int i = left;
int j = mid + 1;
int count = 0;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
nums[k] = temp[j];
j++;
} else if (j == right + 1) {
nums[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i];
i++;
} else {
nums[k] = temp[j];
j++;
count += (mid - i + 1);
}
}
return count;
}
面试题52：两个链表的第一个公共节点
第一种思路：暴力双循环
第二种思路：构造一个环
环
一图胜万言，直接上代码
注意, 因为是自己构造的环, 所以需要在返回之前要将构造环的地方断开, 所以不能直接在循环中找到节点就断开
public static ListNode getIntersectionNode(ListNode headA, ListNode headB){
if (headA == null || headB == null) {
return null;
}
ListNode endA = headA;
while (endA.next != null) {
endA = endA.next;
}
endA.next = headA;
ListNode slowII = null;
// 快慢指针法
ListNode fast = headB;
ListNode slow = headB;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (slow == fast){
slowII = headB;
while (slowII != slow){
slowII = slowII.next;
slow = slow.next;
}
break;
}
}
endA.next = null;
return slowII;
}
面试题53: 在排序数组中查找数字
解题思路
排序数组中的搜索问题，首先想到 二分法 解决。
使用二分法分别找到 左边界 $left$ 和 右边界$right$ ，易得数字$target$的数量为 $right -left -1$
实现步骤
- 初始化左边界 left = 0, 右边界right = length-1;
- 循环$[left, right]$内无元素的时候退出
- 计算中点 $mid = \lfloor left+right \rfloor/2$
- nums[mid] < target, 则target在区间$[mid+1, right]$中
- nums[mid] > target, 则target在区间$[left, mid-1]$中
- nums[mid] = target, 则左边界在$[left, mid-1]$ 中, 右边界在$[mid+1, right]$
- 若查找 右边界 right ，则执行 left = mid + 1 ；（跳出时left指向右边界）
- 若查找 左边界 left，则执行 right = m id - 1 ；（跳出时right指向左边界)
代码
public static int search(int[] nums, int target) {
int i = 0;
int j = nums.length -1;
return helper(nums, target) - helper(nums, target-1);
}
private static int helper(int[] nums, int target) {
int i = 0;
int j = nums.length - 1;
while (i <= j) {
int mid = (i + j) / 2;
if (nums[mid] <= target) {
i = mid + 1;
} else {
j = mid - 1;
}
}
return i;
}
面试题53 - II. 0～n-1中缺失的数字
public int missingNumber(int[] nums) {
int i = 0;
int j = nums.length - 1;
while(i < j){
int mid = (i + j)/ 2;
if(mid == nums[mid]){
i = mid + 1;
}else {
j = mid;
}
}
if(nums[i] == i){
return i+1;
}
return i;
}
面试题54: 二叉搜索树的第K大节点
int res, k;
public int kthLargest(TreeNode root, int k) {
this.k = k;
inOrder(root);
return res;
}
private void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.right);
if(k == 0){
return;
}
if(--k == 0){
res = root.val;
}
inOrder(root.left);
}
非递归实现
第K小的节点, 寻找第K大的节点, 可以按照右根左遍历
public TreeNode kthNode(TreeNode pRoot, int k){
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = pRoot;
TreeNode res = null;
while(p != null || !stack.isEmpty()){
if(p != null){
stack.push(p);
p = p.left;
}
else {
p = stack.pop();
if(--k == 0){
res = p;
}
p = p.right;
}
}
return res;
}
面试题55-I: 二叉树的深度
树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；
常见的 DFS ： 先序遍历、中序遍历、后序遍历；
常见的 BFS ： 层序遍历（即按层遍历）。
求树的深度需要遍历树的所有节点
奉上三种解法:一种递归写法(DFS), 两种种借助队列的非递归写法(层次遍历)
递归
public int maxDepth(TreeNode root){
if(root == null){
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
非递归
public int maxDepth(TreeNode root) {
int level = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
TreeNode p = null;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
p = queue.poll();
if (p.left != null) {
queue.offer(p.left);
}
if (p.right != null) {
queue.offer(p.right);
}
}
level++;
}
return level;
}
public int maxDepthII(TreeNode root) {
int level = 0;
int preCount = 1;
int count = 0;
if (root == null){
return level;
}
Queue<TreeNode> queue = new LinkedList<>();
TreeNode p = null;
queue.offer(root);
while (!queue.isEmpty()){
preCount--;
p = queue.poll();
if(p.left != null){
queue.offer(p.left);
count++;
}
if(p.right != null){
queue.offer(p.right);
count++;
}
if(preCount == 0){
level++;
preCount = count;
count = 0;
}
}
return level;
}
面试题55-II: 平衡二叉树
解法一(自顶向下):
借助上一题, 判断当前节点左子树高度和右子树高度,若是绝对值差≤1则当前节点的子树平衡,然后递归的检测每一个子树即可
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
int left = helper(root.left);
int right = helper(root.right);
return Math.abs(left-right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int helper(TreeNode root){
if(root == null){
return 0;
}
return Math.max(helper(root.left), helper(root.right)) + 1;
}
解法二(自底向上):
但是,上述的解法,重复遍历了很多的节点, 导致性能降低.
public boolean isBalanced(TreeNode root) {
if(root == null){
return true;
}
return postOrder(root) != -1;
}
private int postOrder(TreeNode root){
if(root == null){
return 0;
}
int left = postOrder(root.left);
if(left == -1){
return -1;
}
int right = postOrder(root.right);
if(right == -1){
return -1;
}
return Math.abs(left-right) < 2? Math.max(left, right) + 1 : -1;
}
面试题56-I: 数组中数字出现的次数
和数组中数字出现一次的思路一样,使用异或操作,但是需要将现有数组分为两组
使得：
- 两个只出现一次的数字在不同的组中；
- 相同的数字会被分到相同的组中。
public static int[] singleNumbers(int[] nums) {
int[] resNum = new int[2];
int res = 0;
for (int num : nums) {
res ^= num;
}
int div = 1;
while ((div & res) == 0) {
div <<= 1;
}
int a = 0, b = 0;
for (int num : nums) {
if ((div & num) == 0) {
a ^= num;
}else {
b ^= num;
}
}
resNum[0] = a;
resNum[1] = b;
return resNum;
}
面试题56-II: 数组中唯一出现一次的数字
public int singleNumber(int[] nums) {
int[] counts = new int[32];
for(int num : nums) {
for(int j = 0; j < 32; j++) {
counts[j] += num & 1;
num >>>= 1;
}
}
int res = 0, m = 3;
for(int i = 0; i < 32; i++) {
res <<= 1;
res |= counts[31 - i] % m;
}
return res;
}
面试题57-I: 和为S的两个数字
双指针问题 while执行要比if效率高一些
public int[] twoSum(int[] nums, int target) {
int[] res = new int[]{-1, -1};
int i = 0;
int j = nums.length - 1;
while (i < j) {
int temp = nums[i] + nums[j];
if(temp == target){
res[0] = nums[i];
res[1] = nums[j];
break;
}
while (nums[i] + nums[j] > target){
j--;
}
while (nums[i] + nums[j] <target){
i++;
}
}
return res;
}
面试题57-II: 和为S的连续整数序列
滑动窗口问题
// 双指针 滑动窗口
public int[][] findContinuousSequenceII(int target) {
int small = 1;
int big = 1;
int curSum = 0;
List<int[]> res = new ArrayList<>();
while (small <= target/2){
while(curSum < target){
curSum += big;
big++;
}
while(curSum > target){
curSum -= small;
small++;
}
if(curSum == target){
int[] arr = new int[big - small];
for (int i = small; i < big; i++) {
arr[i-small] = i;
}
res.add(arr);
curSum -= small;
small++;
}
}
return res.toArray(new int[res.size()][]);
}
面试题58-I: 翻转字符串
循环执行部分
- 索引i从右向左移动 直到搜索到搜个空格
- 添加单词s[i+1, j+1]到sb中
- 索引跳过空格
- 执行j=i, 此时j指向下一个单词的尾字符
public String reverseWords(String s) {
int i = s.length()-1;
int j = i;
StringBuilder sb = new StringBuilder();
while (i >= 0){
while (i>=0 && s.charAt(i) != ' '){
i--;
}
sb.append(s.substring(i+1, j+1) + " ");
while (i>=0 && s.charAt(i) == ' '){
i--;
}
j = i;
}
return sb.toString().trim();
}
面试题58-II: 翻转字符串
“字符串切片” ， “列表遍历拼接” ， “字符串遍历拼接” 三种方法
字符串切片
字符串切片
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n, s.length()) + s.substring(0, n);
}
}
列表遍历拼接
列表遍历拼接
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
for (int i = n; i < s.length(); i++) {
sb.append(s.charAt(i));
}
for (int i = 0; i < n; i++) {
sb.append(s.charAt(i));
}
return sb.toString();
}
字符串遍历拼接
字符串遍历拼接
public String reverseLeftWords(String s, int n){
String res = "";
for (int i = n; i < s.length(); i++) {
res += s.charAt(i);
}
for (int i = 0; i < n; i++) {
res += s.charAt(i);
}
return res;
}
方法一不消耗额外的空间, 方法二需要创建一个StringBuilder对象, 方法三会创建n个String对象.
所以效率上:
方法一>方法二>方法三
面试题59-I: 滑动窗口的最大值
暴力法: 时间复杂度 $O(nk)$
public static int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || nums == null){
return new int[]{};
}
List<Integer> list = new ArrayList<>();
int slow = 0;
int hight = k - 1;
while (slow < nums.length - k + 1) {
int max = Integer.MIN_VALUE;
for (int i = slow; i <= hight; i++) {
if (nums[i] > max) {
max = nums[i];
}
}
list.add(max);
hight++;
slow++;
}
int[] res = new int[list.size()];
int j = 0;
for (Integer integer : list) {
res[j++] = integer;
}
return res;
}
面试题59-II: 队列的最大值
和30题的思路一样, 不过这里是维持一个非严格递增的最大双端队列
举例说明:
{2,3,4,2,6,2,5,1}
| 步骤 | 插入数字 | 正常队列值 | 双端队列值 | 最大值 |
|---|---|---|---|---|
| 1 | 2 | 2 | 2 | 2 |
| 2 | 3 | 2,3 | 3 | 3 |
| 3 | 4 | 2,3,4 | 4 | 4 |
| 4 | 2 | 2,3,4,2 | 4,2 | 4 |
| 5 | 6 | 2,3,4,2,6 | 6 | 6 |
| 6 | 2 | 2,3,4,2,6,2 | 6,2 | 6 |
| 7 | 5 | 2,3,4,2,6,2,5 | 6,5 | 6 |
| 8 | 1 | 2,3,4,2,6,2,5,1 | 6,5,1 | 6 |
在第四步的时候, 接下来如果4弹出之后, 2可能会是最大值, 所以需要入队
private Queue<Integer> queue1;
private Deque<Integer> queue2;
public MaxQueue() { {
this.queue1 = new LinkedList<>();
this.queue2 = new LinkedList<>();
}
public int max_value() {
return queue2.size()>0?queue2.peek():-1;
}
public void push_back(int value) {
queue1.offer(value);
while (!queue2.isEmpty() && queue2.peekLast() < value){
queue2.pollLast();
}
queue2.offer(value);
}
public int pop_front() {
int ans = queue1.isEmpty()?-1:queue1.poll();
if(!queue2.isEmpty() && queue2.peek().equals(ans)){
queue2.poll();
}
return ans;
}
面试题60: n个骰子的点数
面试题61: 扑克牌中的顺子
public boolean isStraight(int[] nums) {
Set<Integer> repeat = new HashSet<>();
int max = 0;
int min = 14;
for (int num : nums) {
if(num==0){
continue; // 跳过大小王
}
if(repeat.contains(num)){
return false;
}
max = Math.max(max, num);
min = Math.min(min, num);
repeat.add(num);
}
return max-min < 5;
}
面试题62: 圆圈中最后剩下的数字
构造环,然后按照题意解决
实践证明, 太繁琐了.复杂度为$O(nm) ≈ O(n^2)$ 会超时
public int lastRemainingII(int n, int m){
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(i);
}
int index = 0;
while (n > 1){
index = (index + m - 1) % n;
list.remove(index);
n--;
}
return list.get(0);
}
约瑟夫环——公式法（递推公式）
public int lastRemaining(int n, int m) {
if(n<1 || m < 1){
return -1;
}
int last = 0;
// 最后一轮剩下2个人，所以从2开始反推
for(int i =2; i<=n; i++){
last = (last+m)%i;
}
return last;
}
面试题63: 股票的最大利润
在卖出价格固定的时候, 买入价越低, 利润也就越高, 换成程序理解就是: 在扫描当前元素i的时候, 记住前面i-1个元素中最小的元素.就能在当前卖出的价格中最高
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int len = prices.length - 1;
int min = prices[0];
int diff = prices[1] - prices[0];
for (int k = 2; k <= len; k++) {
if (min > prices[k - 1]) {
min = prices[k - 1];
}
diff = Math.max(diff, (prices[k] - min));
}
return diff < 0 ? 0 : diff;
}
其实这道题也可以理解为动态规划问题
状态定义: 设置动态规划列表$dp$ , $dp[i]$表示以$prces[i]$为结尾的子数组的最大利润
转移方程: 由于题目限定 “买卖该 股票一次” ，因此前$i$日最大利润 $dp[i]$ 等于前$ i - 1$ 日最大利润 $dp[i-1]$ 和第 $i$ 日卖出的最大利润中的最大值。
$dp[i] = max(dp[i-1], (prices[i]- min(prices[0:i])))$
初始状态: $dp[0] = 0$
返回值: $dp[n-1]$
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, profit = 0;
for(int price : prices) {
cost = Math.min(cost, price);
profit = Math.max(profit, price - cost);
}
return profit;
}
面试题64: 求1+2+…+n的结果
public int sumNums(int n) {
return (1+n)*n/2;
}
面试题65: 不用加减乘除做加法
public int add(int a, int b) {
// 当进位为 0 时跳出
while(b != 0) {
// c = 进位
int c = (a & b) << 1;
// a = 非进位和
a ^= b;
// b = 进位
b = c;
}
return a;
}
面试题66: 构建乘积数组
public int[] constructArr(int[] a) {
if (a.length == 0) {
return new int[0];
}
int[] b = new int[a.length];
b[0] = 1;
for (int i = 1; i < a.length; i++) {
b[i] = a[i-1] * b[i-1];
}
int temp = 1;
for (int i = a.length-2; i>=0; i--){
temp *= a[i+1];
b[i] = b[i] * temp;
}
return b;
}
// 使用前缀数组和后缀数组
public int[] constructArrII(int[] nums){
int[] pre = new int[nums.length];
int[] post = new int[nums.length];
pre[0] = 1;
for(int i = 1; i < nums.length; i++){
pre[i] = nums[i-1] * pre[i-1];
}
post[nums.length-1] = 1;
for(int i = nums.length-2; i>=0; i--){
post[i] = post[i+1] * nums[i+1];
}
for(int i = 0; i< nums.length; i++){
pre[i] = pre[i] * post[i];
}
return pre;
}
面试题67: 把字符串转换成整数
public int strToInt(String str) {
char[] c = str.trim().toCharArray();
if(c.length == 0) return 0;
int res = 0, bndry = Integer.MAX_VALUE / 10;
int i = 1, sign = 1;
if(c[0] == '-') sign = -1;
else if(c[0] != '+') i = 0;
for(int j = i; j < c.length; j++) {
if(c[j] < '0' || c[j] > '9') break;
if(res > bndry || res == bndry && c[j] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
res = res * 10 + (c[j] - '0');
}
return sign * res;
}
面试题68-I: 二叉搜索树的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor(root.right, p, q);
}
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor(root.left, p, q);
}
return root;
}
面试题68-II: 二叉树的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root==p || root ==q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null && right==null){
return null;
}
if(left == null){
return right;
}
if(right == null){
return left;
}
return root;
}
References
剑指offer原解
- LeetCode官方题解
5
