剑指 offer 53-I 在排序数组中查找数字 I
非常简单的一个题，二分查找一下，然后向左向右扩展遍历计数即可
class Solution {public int search(int[] nums, int target) {if(nums.length == 0) return 0;int r = nums.length - 1, l = 0;int count = 0;int mid = 0;while (l <= r){mid = (l+r) / 2;//查询到退出循环，此时 mid 指向的元素就是 target//但是并不能保证查找到的就一定是第一个为 target 的元素//所以在后面需要向前和向后遍历，找到所有相同的元素来计数if(nums[mid] == target){count++;break;}else if(nums[mid] < target){l = mid+1;}else{r = mid-1;}}//向前和向后查找相同大小的元素，避开已经计数的 midfor (int i = mid+1; i<nums.length && nums[i] == target; i++) {count++;}for (int i = mid-1; i >= 0 && nums[i] == target; i--) {count++;}return count;}}
但是思考一下，这种写法的最坏时间复杂度其实是 O(n) ( 全是相同的元素 )，为了不让时间复杂度下降，我们可以通过两次二分查找，分别查找出 target 的左右边界，然后相减即可
class Solution {
public int search(int[] nums, int target) {
int targetLeftEdgeIndex = binarySearchLeftEdge(nums, target);
int targetRightEdgeIndex = binarySearchRightEdge(nums, target);
return targetRightEdgeIndex-targetLeftEdgeIndex;
}
private int binarySearchLeftEdge(int[] nums, int target){
int left = 0;
int right = nums.length-1;
while(left <= right){
int mid = left+(right-left) / 2;
if(nums[mid] < target){
left = mid+1;
}else if(nums[mid] >= target){
right = mid-1;
}
}
if(left > nums.length-1 || nums[left] != target){
return -1;
}
return left;
}
private int binarySearchRightEdge(int[] nums, int target){
int left = 0;
int right = nums.length-1;
while(left <= right){
int mid = left+(right-left) / 2;
if(nums[mid] <= target){
left = mid+1;
}else if(nums[mid] > target){
right = mid-1;
}
}
if(right < 0 || nums[right] != target){
return -1;
}
//加 1 是为了把自身计算进去，因为是统计出现次数
return right+1;
}
}
这样的时间复杂度就始终是 O(log2n)
剑指 offer 04 二维数组中的查找
最简单的方法就是遍历这个二维数组，将所有元素加入到一个 list 中，然后返回 contains(target) 即可。但是这样的做法时间复杂度就是 O(n*m)，并且显然没有用到题目所给的行列有序这个条件
那要如何利用这个条件呢？
其实细心 (脑洞大) 一点的话不难发现，其实对于任何一个元素来说
- 同列中其上面的元素都比该元素小
- 同行中其右边的元素都比该元素大
因此我们可以这样解决这个问题
- 选取左下角或者右上角的元素 (这里以选取左下角元素为例)
- 当该元素大于 target 时，我们可以移动行指针，往上移动一行，因为当前行里面的元素都是比 target 大的，说明 target 在小的地方
- 当该元素小于 target 时，移动列指针，往左移动一行，因为当前列中的元素都是小于 target 的，说明 target 应该在左边列中更大的地方
- 否则当前元素等于 target，返回 true
这样我们就可以通过每次消除一行或一列，直到行指针或者列指针越界后返回 false
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix.length == 0) return false;
int i = matrix.length-1, j = 0;
while(j < matrix[0].length && i >=0){
if(matrix[i][j] > target){
i--;
}else if(matrix[i][j] < target){
j++;
}else{
return true;
}
}
return false;
}
}
剑指 offer 41 数据流中的中位数
真想偷懒的话，那么这一题就很简单，但是这样这题的定位就不会是 hard 了
我们的最终目的只有求出中位数这一个，但是在数组长度不同时，有两种情况
- 当数组长度为奇数时，中位数为中间那个数
- 当数组长度为偶数时，中位数为中间两个数 / 2
因此其实我们可以使用两个优先队列 (堆) 来实现这个需求
- 一个小顶堆：让其作为一个数组的后半段，但其实不需要有序，我们只要保证其第一个元素比前面的都大，而且是最小的即可，因此使用小顶堆
- 一个大顶堆：让其作为一个数组的前半段，同样不需要有序，我们只需要保证第一个元素是前半部分最大的元素即可
- 当大顶堆大小和小顶堆大小一样时，优先朝小顶堆插入，这样如果最后长度为奇数的话，直接返回小顶堆的首元素即是中位数
添加一个元素的具体过程是这样的
- 如果大顶堆大小 == 小顶堆大小，由于我们不知道这个新加入的元素是大还是小，因此我们先将这个元素加入大顶堆，然后从大顶堆中弹出最大的元素加入小顶堆。这样就保证了小顶堆中的元素都比大顶堆大
- 否则我们就反过来，将元素加入小顶堆后，弹出小顶堆中的最小的元素加入大顶堆
最后，我们的 find 方法，只需要判断两个堆长度是否相同并返回对应情况下的中位数即可
class MedianFinder {
/** initialize your data structure here. */
//用两个栈来实现
//一个大顶堆，一个小顶堆，小顶堆中保证所有的元素都比大顶堆大
//所以小顶堆的第一个就可以作为中位数 (奇数长度下)
//或者大顶堆的第一个+小顶堆的第一个 (前半段最大+后半段最小) 也可以构成中位数 (偶数长度下)
Queue<Integer> minStack;
Queue<Integer> maxStack;
public MedianFinder() {
minStack = new PriorityQueue<>();
maxStack = new PriorityQueue<>((o1, o2)->{return o2-o1;});
}
public void addNum(int num) {
//如果大顶堆和小顶堆的长度相等，则优先让元素加入小顶堆，
//但是需要先将元素加入到大顶堆中，然后再从大顶堆弹出当前最大的元素，加入小顶堆
if(maxStack.size() == minStack.size()){
maxStack.add(num);
minStack.add(maxStack.poll());
//否则长度不相等的话，从小顶堆中弹出最小的元素，加入大顶堆
}else{
minStack.add(num);
maxStack.add(minStack.poll());
}
}
public double findMedian() {
if(maxStack.size() == minStack.size()){
return (maxStack.peek()+minStack.peek())*1.0 / 2;
}
return minStack.peek();
}
}
剑指 offer 42 连续子数组的最大和
一道 ez 难度的 dp 题
设 dp[i] 表示纳入第 i 个数字时，即到 nums[i] 为止的子数组能够表示的最大值
且题目要求的是一个或多个连续的整数构成的子数组。则转移方程为：dp[i] = Math.max(dp[i-1]+nums[i], nums[i]) （之所以是 nums[i] 是因为要求的是连续的子数组，因此不能用 dp[i-1]；即每次必须选择当前的数，只不过看下当前的数和当前的数+dp[i-1] 谁更大而已）
每次选择完成后，代表找到了一个当前最大连续子数组，只不过这个子数组的大小需要和之前的连续子数组的最大值进行比较，选取最大的。即 max = Math.max(dp[i], max);
最后返回最大值 max 即可
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for(int i=1; i<nums.length; i++){
dp[i] = Math.max(nums[i]+dp[i-1], nums[i]);
max = Math.max(dp[i], max);
}
return max;
}
}
剑指 offer 45 把数组排成最小数
这道题如果找出规律的话其实非常简单
首选看一下示例1的情况，[10, 2] 有两种可能
- 102
- 210
可能看不出啥，再来看下 [10,11,2] 这种情况下的可能
- 10112
- 11102
- 11210
- 10211
- 21011
- 21110
其实不难看出本质了，如果我们想要拼接数组中的元素为一个数字，那么我们就需要保证两两数字之间拼接的结果是最小的，那该如何保证呢？
很简单，就是排序，比较两个数字组成的字符串的字典序，这样就可以使得可以组成更小字符串的数字在前了。最后拼接出来的数字也就是最小的
class Solution {
public String minNumber(int[] nums) {
//假设只有两个数，[100,1]，则可以组成 1001 和 1100，明显前者小于后者
//再来看 [100,101,2] 可以组成 1001012 1002101 1011002 1012100 2100101 2101100
//很明显，在 100 + 101 的组合中，100101 < 101100，所以我们选择前者
//在 100101 + 2 的组合中，很明显 1001012 < 2100101，所以我们选择前者，于是得到了结果
//所以这题的本质其实是排序，而排序的依据则是两个字符串拼接谁小
List<String> list = new LinkedList<>();
for (int num : nums) {
list.add(String.valueOf(num));
}
//能组成更小的字符串的排序方式，字符串 o1 和字符串 o2 的两种组合，谁更小谁就排在前面
list.sort((o1, o2) -> (o1+o2).compareTo(o2+o1));
return String.join("", list);
}
}
剑指 offer 07 重建二叉树
<br />在中序遍历中，可以根据根结点，将其划分为 **[左 | 根 | 右]**<br />根据中序遍历中的左子树和右子树的结点数，又可以将前序遍历划分为 **[ 根 | 左 | 右 ]**<br />对于一棵简单的，只有三个结点的二叉树，譬如下图来说
其先序遍历序列是 [1, 2, 3]，中序遍历序列是 [2, 1, 3]
如果想要重建这棵二叉树，我们可以经过以下几步
- 我们保存先序序列，并用 hashmap 保存中序序列中元素和下标的映射
- 我们从先序序列中取出首元素，将这个元素做为根结点，创建一个根结点
- 获得该元素在中序序列中的下标 i
- 根据下标，我们可以划分出左右子树，并获取当前根结点的左孩子和右孩子
通过以上几步，我们可以得到当前结点作为根结点的左子树的根结点和右子树的根结点。对着两个根结点进行递归重复上述步骤即可
对于更长的序列，我们可以得到以下规律 ( 图源 weiwei 哥的题解 )
我们来把上图简化一下
preL：根结点下标 —-> root：当前要构建的树的根结点在 preorder 数组中的下标
inL：左边界 ——> leftEdge：限定构建的左/右子树的起始
pivot：根结点在中序序列中的下标，用来参与左右子树的拆分
inR：右边界 ——> rightEdge：限定构建的左/右子树的终点
可以看见，我们每次需要链接的左右孩子的下标分别：
- 当前根结点的左孩子在 preorder 中的下标是 root+1。将其作为新的根结点传递，相当于对当前的根结点的左子树进行构建，范围是 [ leftEdge, pivot-1 ]
- 而当前根结点的右孩子在 preorder 中的下标则是 pivot-leftEdge+root+1。作为新的根结点进行传递，相当于对当前的 根结点的右子树进行构建，范围是 [ pivot+1, rightEdge ]
- 递归以上两步，就可以构建出完成的左右子树
class Solution {
int[] preorder;
HashMap<Integer, Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return builtTree(0, 0, inorder.length-1);
}
private TreeNode builtTree(int root, int leftEdge, int rightEdge){
if(leftEdge > rightEdge) return null;
TreeNode rootNode = new TreeNode(preorder[root]);
int pivot = map.get(preorder[root]);
// 根据当前的根结点，找到其左右孩子以及左右子树的范围，左右孩子就是左右子树的根结点，然后继续进行构建，递归该过程
rootNode.left = builtTree(root+1, leftEdge, pivot-1);
rootNode.right = builtTree(pivot-leftEdge+root+1, pivot+1, rightEdge);
return rootNode;
}
}
剑指 offer 47 礼物的最大价值
<br /> 一道基础的 dp 题<br />首先思考，截止到当前礼物 grid[i][j]，我们能获得的最大价值应该是 Math.max(grid[i][j-1], grid[i-1][j]) + grid[i][j]。即本身的价值加上左面/上面的两个礼物中价值最大的那个<br />对于第一列和第一行，我们应该特殊处理
- 当在起点时，没有可以选择的礼物，跳过
- 当在第一行时，没有上面的礼物可以选择，因此只能选择左面的礼物
- 当在第一列时，没有左面的礼物可以选择，因此只能选择上面的礼物
class Solution {
public int maxValue(int[][] grid) {
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if(j == 0 && i == 0){
continue;
}
if(j == 0){
grid[i][j] += grid[i-1][j];
}else if(i == 0){
grid[i][j] += grid[i][j-1];
}else{
grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
}
}
}
return grid[grid.length-1][grid[0].length-1];
}
}
剑指 offer 57-II 和为 s 的连续正数序列
一道滑动窗口问题，但是需要明白窗口的范围
首先对于一个 target，其取值区间是 [1, target]，要从中取出和为 target 的连续序列，且至少有两个值
所以我们可以将这个问题视作一般的滑动窗口问题
滑动窗口的左右边界指针为 l 和 r，初始值都为 1，表示窗口的最小取值，通过一个变量 sum 来记录滑动窗口的和。右边界不断扩大的过程中，如果 sum > target 了，就减少 sum 的值，减少的值也就是左边界 l 的值，并且 l 进行自增，表示窗口缩小
当 sum == target 时，说明我们找到一个 [l, r] 的区间，其和等于 target，这就是其中一个解，我们存储这个区间的数值，并加入到待返回的数组中
根据以上思路，代码如下
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> res = new LinkedList<>();
int sum = 0;
int r = 1, l = 1;
while (r < target) {
sum += r;
while (sum > target){
sum -= l;
l++;
}
if(sum == target){
int[] tmp = new int[r-l+1];
for (int i1 = 0; i1 < tmp.length; i1++) {
tmp[i1] = l+i1;
}
res.add(tmp);
}
r++;
}
int[][] ress = new int[res.size()][];
for (int i = 0; i < ress.length; i++) {
ress[i] = res.get(i);
}
return ress;
}
}
剑指 Offer 33 二叉搜索树的后序遍历序列
首先题目要求的只是判断该数组能不能是一棵二叉搜索树的后序遍历结果
那么一棵二叉树的后序遍历序列应该是：左 -> 右 -> 根
当翻转这个序列后，就应该是 根 -> 右 -> 左
根据二叉搜索树的性质，我们可以知道，在 根->右 这个序列中，结点大小是依次递增的
根据这个性质和序列
- 我们可以通过不断入栈递增的序列
- 当遇到比栈顶结点小的结点时，我们不断出栈比这个结点大的结点作为当前结点的 root ( 因为比当前节点大 )
- 直到遇到比当前结点小的结点，此时的 root 就是当前结点的根结点，当前结点就是 root 的左孩子，这样就构成了一棵二叉搜索树 ( 右孩子就是不断出栈的那些比 root 大的结点 )
- 此时栈中剩下的结点 (也可能没有剩下)，就可以构成其它的二叉搜索树
具体证明参考 k 神题解
class Solution {
public boolean verifyPostorder(int[] postorder) {
//1,2,3,6,5 倒序遍历序列为 5,6,2,3,1
//左孩子一定比右孩子和根结点小，因此当遇到比当前根结点小的值时，说明这个结点就是当前root的左孩子
//然后我们将栈中比当前这个结点大的元素依次出栈，这就代表了一棵合法的二叉搜索树
//(因为如果一直递增的话，就说明是当前结点的右子树，保证了大这一要求，题目只要求判断能否构成一棵二叉搜索树而已)
//在构成一棵二叉搜索树后，如果出现了比旧的root更大的结点，说明这不是一棵二叉搜索树
//(因为二叉搜索树的后序遍历序列的倒序是 根|右|左，我们保证了当前树中的根、右结点已经加入了栈中
//那么剩下的就是左子树上的结点，必然都比root小)
Deque<Integer> stack = new ArrayDeque<>();
int root = Integer.MAX_VALUE;
for (int i = postorder.length-1; i >=0 ; i--) {
if(postorder[i] > root) return false;
//更新root
while (!stack.isEmpty() && stack.peekFirst() > postorder[i]){
root = stack.pollFirst();
}
stack.addFirst(postorder[i]);
}
return true;
}
}
若有收获，就点个赞吧
0 人点赞
