剑指offer -- java题解

刷题地址

https://www.nowcoder.com/exam/oj/ta?tpId=13

1、数字在升序数组中出现的次数

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
[1,2,3,3,3,3,4,5],3
4

解析

用二分查找找到 k + 0.5 的位置(k的最后一位的后一位)和 k−0.5（k的第一位）的位置，二者相减就是k出现的次数。

代码

public class Solution {public int GetNumberOfK(int [] array , int k) {return binsearch(array, k + 0.5) - binsearch(array, k - 0.5);}private int binsearch(int [] array, double k){int l = 0;int r = array.length - 1;while(l <= r){int mid = l + (r - l) / 2;if(array[mid] < k){l = mid + 1;}else if(array[mid] > k){r = mid - 1;}}return l;}
}

2、二叉搜索树的第k个节点

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。
1.返回第k小的节点值即可
2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
3.保证n个节点的值不一样

解析

二叉搜索树中序遍历（左中右）序列正好是由小到大的次序，因此递归中序遍历，也就是从最小的一个节点开始，找到k个就是我们要找的目标

代码

public class Solution {int count = 0;public int KthNode (TreeNode proot, int k) {// write code hereTreeNode res = midOrder(proot, k);if(res != null) return res.val;return -1;}private TreeNode midOrder(TreeNode root, int k){if(root == null || count > k) return null;TreeNode left = midOrder(root.left, k);if(left != null) return left;count++;if(count == k) return root;return midOrder(root.right, k);}
}

3、二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1 。

解析

dfs

代码

public class Solution {public int TreeDepth(TreeNode root) {if(root == null) return 0;return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;}
}

4、数组中只出现一次的两个数字

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

解析

假设要找的两个数为a, b;数组中所有数逐个异或，即x1 ^ x2 ^ y1 ^ y2 ^ …… ^ a ^ b, 最终成对的数根据归零率变成0，再根据恒等率剩下的一定是a ^ b

从a ^ b中可以获得某种信息：因为a != b所以a ^ b一定不为0，它其中某一位为1，根据这一位可以把a和b区分开（因为异或是两个输入不同时为1，相同时为0）

a & (-a)可以找到最右侧的1

代码

public class Solution {public int[] FindNumsAppearOnce (int[] array) {int eor = 0;for(int num : array){eor ^= num;}int a_b = 0;//找到最右边第一个不相等的1int rightOne = eor & (~eor + 1);for(int num : array){if((num & rightOne) == 0){a_b ^= num;}}int min = a_b < (a_b ^ eor) ? a_b : (a_b ^ eor);int max = min ^ eor;return new int[]{min, max};}
}

5、和为S的两个数字

输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

解析

使用双指针指向数组第一个元素和最后一个元素，然后双指针对撞移动，如果两个指针下的和正好等于目标值sum，那我们肯定找到了，如果和小于sum，说明我们需要找到更大的，那只能增加左边的元素，如果和大于sum，说明我们需要找更小的，只能减小右边的元素。

代码

import java.util.ArrayList;
public class Solution {public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {ArrayList<Integer> res = new ArrayList<>();int l = 0, r = array.length - 1;while(l < r){int s = array[l] + array[r];if(s < sum){l++;}else if(s > sum){r--;}else{res.add(array[l]);res.add(array[r]);break;}}return res;}
}

6、左旋转字符串

解析

三次反转

代码

public class Solution {public String LeftRotateString(String str,int n) {if(str.isEmpty() || str.length() == 0)return "";int len = str.length();int m = n % len;char[] s = str.toCharArray();reverse(s, 0, len - 1);reverse(s, 0, len - 1 - m);reverse(s, len - m, len - 1);return new String(s);}private void reverse(char[] s, int l ,int r){while(l < r){char temp = s[l];s[l] = s[r];s[r] = temp;l++;r--;}}
}

7、滑动窗口的最大值

给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。

解析

单调队列维护窗口的最大值

代码

import java.util.*;
public class Solution {public ArrayList<Integer> maxInWindows(int [] num, int size) {ArrayList<Integer> res = new ArrayList<>();Deque<Integer> deque = new LinkedList<>();if(num == null || size == 0 || size > num.length) return res;for(int i = 0; i < num.length; i++){//单调队列while(!deque.isEmpty() && num[i] > num[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);//维护窗口while(!deque.isEmpty() && deque.peekFirst() < (i - size + 1)){deque.pollFirst();}if(i - size + 1 >= 0) res.add(num[deque.peekFirst()]);}return res;}
}

8、扑克牌顺子

现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：

1. A为1，J为11，Q为12，K为13，A不能视为14
2. 大、小王为 0，0可以看作任意牌
3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
   4.数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]

解析

创建一个哈希表，查找重复：遍历数组的同时，遇到非零牌重复，直接不行，若没有重复则加入到哈希表中，等待后续的查找。同时在遍历过程需要记录数组最大值与最小值，最后检查最大值与最小值的差是否大于4，小于4的话，在没有非零牌重复的情况下，最大值与最小值中间的牌加上0牌就可以填满这手顺子

代码

import java.util.*;
public class Solution {public boolean IsContinuous(int [] numbers) {HashMap<Integer, Integer> map = new HashMap<>();int max = -1;int min = 14;for(int i = 0; i < numbers.length; i++){if(numbers[i] == 0) continue;if(map.containsKey(numbers[i])) return false;map.put(numbers[i], i);if(numbers[i] > max) max = numbers[i];if(numbers[i] < min) min = numbers[i];}System.out.println(max);System.out.println(min);if(max - min > 4) return false;return true;}
}

9、孩子们的游戏(圆圈中最后剩下的数)

每年六一儿童节，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中，有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0… m-1报数…这样下去…直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？

解析

利用约瑟夫问题的递推公式 f(n,m) = (f(n-1,m) +m)%n)
公式递推：
令f(n,m)表示最后一个人的下标。

1. 假设有n个人，报数m， 从0 开始报数，易知出圈的人下标为 m-1。
2. m-1 出圈后，我们对剩余人重新编号 即 第m个人下标为0，第m+1 下标为1 …以此编号。 那么重新编号之后，那么最后一个人的下标为f(n-1,m)
   问题1： 在重新编号之后的f(n-1,m) 与 重新编号之前的f(n,m)有什么关系？
   重新编号之前 m, m+1,m+2,…
   重新编号之后 0 ，1 ，2，…
   可知 (新编号+m)%n = 旧编号
3. f(n,m) = (f(n-1,m)+m) %n;

代码

public class Solution {public int LastRemaining_Solution(int n, int m) {if(n == 0 || m == 0) return -1;return dfs(n, m);}private int dfs(int n, int m){if(n == 1) return 0;int x = dfs(n - 1, m);return (x + m) % n;}
}

10、买卖股票的最好时机(一)

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费

解析

贪心算法

代码

public class Solution {public int maxProfit (int[] prices) {int res = 0, min = prices[0];for(int i = 1; i < prices.length; i++){if(prices[i] < min){min = prices[i];}res = Math.max(res, prices[i] - min);}return res;}
}