剑指offer刷题笔记（七）
剑指 Offer 53 - I. 在排序数组中查找数字 I
- 统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
二分查找，找出左边界和右边界即可。
class Solution {
public int search(int[] nums, int target) {
if(nums.length==0){
return 0;
}
return right(nums,target)-left(nums,target)+1;
}
private int left(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while (left<=right){
int mid=(left+right)>>>1;
if(nums[mid]<target){
left=mid+1;
}
else{
right=mid-1;
}
}
return left;
}
private int right(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while (left<=right){
int mid=(left+right)>>>1;
if(nums[mid]<=target){
left=mid+1;
}
else{
right=mid-1;
}
}
return right;
}
}
剑指 Offer 53 - II. 0～n-1中缺失的数字
- 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
二分
class Solution {
public int missingNumber(int[] nums) {
if(nums.length==0){
return -1;
}
return getNumber(nums,0,nums.length-1);
}
public int getNumber(int[]nums,int left,int right){
while(left<=right){
int mid=(left+right)>>>1;
if(nums[mid]==mid){
left=mid+1;
}
else if(nums[mid]>mid){
right=mid-1;
}
}
return left;
}
}
剑指 Offer 54. 二叉搜索树的第k大节点
- 给定一棵二叉搜索树，请找出其中第k大的节点。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4
中序遍历倒序排布，就是一个递增的序列。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int res;
int k;
public int kthLargest(TreeNode root, int k) {
this.k=k;
dfs(root);
return res;
}
private void dfs(TreeNode root) {
if(root==null){
return;
}
dfs(root.right);
if(k==0){
return;
}
if(--k==0){
res=root.val;
}
dfs(root.left);
}
}
剑指 Offer 55 - I. 二叉树的深度
- 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度
例如：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
int left=maxDepth(root.left);
int right=maxDepth(root.right);
return left>right?left+1:right+1;
}
}
剑指 Offer 55 - II. 平衡二叉树
- 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
后序遍历，自底向上，不会遍历重复节点。看了评论区大佬才想到剪枝，直接筛去不符合条件的不在继续往下遍历。
class Solution {
public boolean isBalanced(TreeNode root) {
return balanced(root)!=-1;
}
private int balanced(TreeNode root) {
if(root==null){
return 0;
}
int left=balanced(root.left);
if(left==-1){
return -1;
}
int right=balanced(root.right);
if(right==-1){
return -1;
}
return Math.abs(left-right)<2?Math.max(left,right)+1:-1;
}
}
剑指 Offer 56 - I. 数组中数字出现的次数
- 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/solution/jie-di-qi-jiang-jie-fen-zu-wei-yun-suan-by-eddievi/
异或，找到两个不同的数，然后分组异或
class Solution {
public int[] singleNumbers(int[] nums) {
int k=0;
for (int num:nums
) {
k^=num;
}
k=k&(-k);
int a=0;
int b=0;
for (int num:nums
) {
if((k&num)==0){
a^=num;
}
else{
b^=num;
}
}
return new int[]{a,b};
}
}
剑指 Offer 56 - II. 数组中数字出现的次数 II
- 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
异或操作，全体相加，对3取余。
class Solution {
public int singleNumber(int[] nums) {
if(nums.length==0){
return -1;
}
int res=0;
int[] b=new int[32];
for(int num:nums){
int bit=1;
for(int i=31;i>=0;i--){
if((num&bit)!=0){
b[i]++;
}
bit=bit<<1;
}
}
for(int i=0;i<32;i++){
res=res<<1;
res+=b[i]%3;
}
return res;
}
}
剑指 Offer 57. 和为s的两个数字
- 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
双指针移动
class Solution {
public int[] twoSum(int[] nums, int target) {
int i=0;
int j=nums.length-1;
while(i<j){
if(nums[i]+nums[j]>target){
j--;
}
else if(nums[i]+nums[j]<target){
i++;
}
else{
return new int[]{nums[i],nums[j]};
}
}
return new int[0];
}
}
剑指 Offer 57 - II. 和为s的连续正数序列
- 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
双指针移动，滑动窗口
class Solution {
List<int[]> list=new ArrayList<>();
public int[][] findContinuousSequence(int target) {
if(target==1||target==2){
return new int[][]{};
}
int small=1;
int big=2;
int sum=big+small;
int middle=(1+target)/2;
while(small<middle){
if(sum>target){
sum-=small;
small++;
}
else if(sum<target){
big++;
sum+=big;
}
else{
//存储
int[] r=new int[big-small+1];
for (int i = small; i <big+1; i++) {
r[i-small]=i;
}
list.add(r);
sum-=small;
small++;
}
}
return list.toArray(new int[list.size()][]);
}
}
剑指 Offer 58 - I. 翻转单词顺序
- 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
示例 1：
输入: "the sky is blue"
输出: "blue is sky the"
示例 2：
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3：
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
从尾向前遍历，遍历完一个单词添加入结果字符串中。
class Solution {
public String reverseWords(String s) {
s=s.trim();
int i=s.length()-1;
int j=i;
StringBuilder res=new StringBuilder();
while(j>=0){
while(j>=0&&s.charAt(j)!=' ')j--;
res.append(s.substring(j+1,i+1)+" ");
while(j>=0&&s.charAt(j)==' ')j--;
i=j;
}
return res.toString().trim();
}
}
剑指 Offer 58 - II. 左旋转字符串
- 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
字符串切片，拼接
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n)+s.substring(0,n);
}
}
剑指 Offer 59 - I. 滑动窗口的最大值
- 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length==0||k<1||nums.length<k){
return new int[]{};
}
int p=0;
LinkedList<Integer> list=new LinkedList<>();
int[] res=new int[nums.length-k+1];
for (int i = 0; i <nums.length ; i++) {
//必须是<=，更新索引
while(!list.isEmpty()&&nums[list.peekLast()]<=nums[i]){
list.pollLast();
}
list.addLast(i);
//当最大值索引不在窗口中时，弹出
if(list.peekFirst()==i-k){
list.pollFirst();
}
if(i>=k-1){
res[p++]=nums[list.peekFirst()];
}
}
return res;
}
}
剑指 Offer 59 - II. 队列的最大值
- 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]
与上一题基本类似，构建一个单向递减队列
class MaxQueue {
private LinkedList<Integer> max;
private LinkedList<Integer> list;
public MaxQueue() {
max=new LinkedList<>();
list=new LinkedList<>();
}
public int max_value() {
if(max.isEmpty()){
return -1;
}
return max.peekFirst();
}
public void push_back(int value) {
list.add(value);
while(!max.isEmpty()&&max.peekLast()<value)
max.removeLast();
max.add(value);
}
public int pop_front() {
if(list.isEmpty()){
return -1;
}
if(max.peekFirst().equals(list.peek()))
max.removeFirst();
return list.poll();
}
}
