59~69 on building…

59 - I. 滑动窗口的最大值

难度困难474

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

  • 暴力解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length==0||k==0) return new int[0]; // 数组为null 的情况
        int []res=new int[nums.length-k+1]; // 滑动窗口的数量
        int pre=0; // 滑动窗口左下标
        while(pre+k<=nums.length){
            int max=nums[pre]; // 窗口最左边的元素
            for (int i  = pre+1; i < pre+k; i++) {// 循环窗口
                max=Math.max(max,nums[i]);
            }
            res[pre++]=max;// 移动窗口并赋值
        }
        return res;
    }
}
  • 单调队列

59 - II. 队列的最大值

难度中等403

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

对于入队操作以及出队操作, 直接使用Queue 的API即可

对于MAX_VALUE,如果要实现O(1)的复杂度, 需要使用Deque

  • 使用辅助队列Deque , 用来储存最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class MaxQueue {
    Deque<Integer> deque=new LinkedList<>(); // 辅助队列, 储存最大值
    Queue<Integer> queue=new LinkedList<>();
    public MaxQueue() {

    }

    public int max_value() { //直接通过deque获取最大值
        return deque.size()==0?-1: deque.peekFirst();
    }
    
    public void push_back(int value) {
        queue.add(value);
        // 调整deque ,使其保持单调递减
        while(deque.size()!=0&&deque.peekLast()<value){
            deque.removeLast();
        }
        deque.addLast(value);
    }

    public int pop_front(){
        if(queue.size()==0) return -1;
        if(queue.peek().equals(deque.peekFirst())){ //如果需要出队的元素是最大值,那么出队,否则不用管
            deque.pollFirst();
        }
        return queue.poll();
    }
}
/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue obj = new MaxQueue();
 * int param_1 = obj.max_value();
 * obj.push_back(value);
 * int param_3 = obj.pop_front();
 */

60. n个骰子的点数

难度中等464

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

  • 动态规划
  • 在前面计算的dp数组的概率的基础上, 都添加6 个分支temp[j+k]+=dp[j]/6.0;,

通过子问题的解 f(n - 1) 可递推计算出 f(n) ，而输入一个骰子的解 f(1) 已知，因此可通过解 f(1)依次递推出任意解 f(n) 。

假设有两个骰子A、B，这两个骰子相互独立。
在仅有一个骰子A的情况下，6个点出现的概率都为1/6, 同时A的每个点搭配B的每个点的概率也是相同的，所以骰子A为1会分别乘6个1/6去搭配骰子B的1~6， 即这种搭配2~7的概率分别都为1/36; 骰子A的2也会分别去乘6个1/6去搭配骰子B的1~6, 即这种搭配3~8的概率也分别为1/36, 以此类推。
因为这是独立重复试验，所以之间的关系是相加，所有实验相加后，就得到了最终的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public double[] dicesProbability(int n) {
        double[] dp=new double[6];
        Arrays.fill(dp,1/6.0);
        for (int i = 2; i <= n; i++) {
            double temp[]=new double[i*5+1];
            for (int j = 0; j < dp.length; j++) { // 前面的数组的点数
                for (int k = 0; k < 6; k++) {   // 多了一个 骰子的点数
                    temp[j+k]+=dp[j]/6.0; // 可以理解为 前面的数组的点数, 要均匀分给后面的骰子六份
                    // 例如本来是x  , 那么新的点数列表就是 (x,1),(x,2),(x,3),(x,4),(x,5),(x,6)
                    // x可以是(1,2,6), x中的每一位都表示之前的那一次的骰子的点数
                }
            }
            dp=temp;
        }
        return dp;
    }
}

61. 扑克牌中的顺子

难度简单261

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isStraight(int[] nums) {
//1 2 3 4 5 6 7 8  9 10 11 12 13
        Arrays.sort(nums);
        int cnt=0; // 统计 joker 的数量
        for (int i = 0; i < 4; i++) {
            if (nums[i] == 0) cnt++;
            else if (nums[i] == nums[i + 1]) return false;// 有重复的 , 直接false
        }
        if(cnt==0&&nums[4]-nums[0]>=5){// 最大值比最小值相差 >5
            return false;
        }
        if(cnt!=0&&nums[4]-nums[cnt]>=5){  
            return false;
        }
        return true;
    }
}
  • 最后几行的返回可以 简写,
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isStraight(int[] nums) {
//1 2 3 4 5 6 7 8  9 10 11 12 13
        Arrays.sort(nums);
        int cnt=0; // 统计 joker 的数量
        for (int i = 0; i < 4; i++) {
            if (nums[i] == 0) cnt++;
            else if (nums[i] == nums[i + 1]) return false;// 有重复的 , 直接false
        }
        return nums[4]-nums[cnt]<5; //最大牌 - 最小牌 < 5 则可构成顺子 (这个与是否有joker无关 ,区别只在于cnt)
    }
}

62. 圆圈中最后剩下的数字

难度简单656

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

  • 约瑟夫环问题

暴力模拟时间复杂度*O(MN)*显然是不可取的image-20220809160509100image-20220809160509100

正确的做法是使用动态规划:

我们首先将这个问题 当做一个 「n, m 问题」

  • 由于删除的是第m个数字, 因此实际删除的数字是(m-1) , 又因为 m可能大于n , 所以实际删除的数字是 (m-1)%n

  • 删除后的数字环从下一个数字开始 (将这个数字视为第一个数字, ) ,即m%n, 设 t= m%n

  • 那么可以得到新的数字环是:

    t, t+1, t+2 , t+3 .......0 , 1 , t-3 ,t-2 , (t-1刚刚被删除了)

    「n -1 , m 问题」 的数字环是:

    0 , 1 , 2 , 3 , ...... t, t+1 ... n-2

  • 删除一轮后的数字环变为了一个「n -1 , m 问题」, 下面是数字的编号以及对应的关系:

    「n -1 , m 问题」 「n , m 问题」
    0 t+0
    1 t+1
    2 t+2
    … …
    n-2 t-2

  • 我们假设 **「n -1 , m 问题」**中的某一个数字为 x ,

    • 那么可以得到递推关系:

      x----> (x+t)%n

那么如果这个x 恰好是**「n -1 , m 问题」** 的解(记为f(n) , 由此我们可以得到:

f(n) = (f(n-1) + t) % n

= (f(n-1) + m%n ) % n

= (f(n-1) + m ) % n

因此, 我们可以通过f (1)来递推之任意的f(n),

  • 而「1,m 问题」的解 f(1) = 0恒成立，即无论 m 为何值，长度为 1 的数字环留下的是一定是数字 0 。

动态规划:

状态定义： 设**「i,m 问题」**的解为 dp[i]；
转移方程： 通过以下公式可从 dp[i - 1]递推得到 dp[i] ；

  • dp[i]=(dp[i−1]+m)%i

初始状态：「1, m1,m 问题」的解恒为 00 ，即 dp[1] = 0 ；
返回值： 返回「n, m问题」的解 dp[n] ；

时间复杂度: O(n)

空间复杂度: O(1)

根据状态转移方程的递推特性，无需建立状态列表 dp ，而使用一个变量 x 执行状态转移即可。

1
2
3
4
5
6
7
8
9
class Solution {
    public int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }
}

63. 股票的最大利润

难度中等278

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

题目示例

暴力解法时间复杂度 达到O(n2) ,舍弃

正确的做法是使用动态规划, 随着天数的增加获得最低价格以及最高的售价 , 然后每次统计利润是否增加

1
profit=Math.max(profit,price-cost);
1
2
3
4
5
6
7
8
9
10
class Solution {
    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

难度中等523

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

  • cpp 利用构造函数求解
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    static int sum,value;
    Solution(){
        sum+=++value;
    }
    static int getSum(){return sum;}
    int sumNums(int n) {
        Solution *ptr=new Solution[n-1];
        return Solution::getSum();
    }
};
int Solution::sum=0, Solution::value=0;
  • java利用 && 求解 , (递归)
1
2
3
4
5
6
7
8
class Solution {
    int res=0;
    public int sumNums(int n) {
        boolean x= n>1&&sumNums(n-1)>0;
        res+=n;
        return res;
    }
}

65. 不用加减乘除做加法

难度简单338

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

  • 利用^ 以及&, 巧妙的进行相加

首先 ,我们有两个数字,

  • 需要先获取 非进位的和 n (n= a^b)
  • 然后获取进位的和 : p (p=a&b<<1)
  • 然后我们 通过 n= n^p 就得到了和 ( 进位和 + 非进位和)

9 : 1001
26: 11010
n: 10011
p: 10000
n: 00011 , 可见, 如果仅仅是 n^p 可能存在新的进位的情况 ,
此时我们继续使用 p 来记录 n&p<<1 的结果 ,
p: 100000
这里需要用到一个新的数字(temp)来储存 n&p<<1 的结果, 因为如果先 异或再 & , 就会导致先相加, 再&, 相当于重复计算了
然后继续执行上一步类似的操作 也就是 n= n^p
n:100011 : 35 得到正确结果

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int add(int a, int b) {
        int n=a;
        int p=b; //存储上一轮的 进位和结果
        while(p!=0){
            int temp = (n&p)<<1;// 存储上一轮的进位和结果  ,如果还有进位那么就继续执行操作
            n=n^p; // 进位和+ 非进位和
            p=temp; //如果还有进位那么就继续执行操作
        }
        return n;
    }
}

66. 构建乘积数组

难度中等257

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

  • 使用 BigInteger.divide()方法 ,显然不行, 题目说了不可以使除法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.math.BigInteger;
class Solution {
    public int[] constructArr(int[] a) {
        BigInteger big=new BigInteger("1");
        int cnt=0;
        for (int i : a) {
            big=big.multiply(new BigInteger(String.valueOf(i)));
            if(i==0){
                break;
            }
            cnt++;
        }
        if (big.intValue()==0){
            int mul=1;
            for (int i = 0; i < a.length; i++) {
                if(i!=cnt){
                    mul*=a[i];
                }
            }
            int []res=new int[a.length];
            res[cnt]=mul;
            return res;
        }
        for (int i = 0; i < a.length; i++) {
            a[i]=big.divide(new BigInteger(String.valueOf(a[i]))).intValue();
        }
        return a;
    }
}
  • 左右累乘, 通过 b[]来记录左边的累乘的结果, 通过temp 来记录右边的累乘的结果,
  • 注意temp计算的时候是从右下角开始累乘
  • 计算过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] constructArr( int []a){
        int len =a.length;
        if(len==0) return new int[0];
        int[]b =new int[len];
        int temp=1;
        b[0]=1;
        for (int i = 1; i < b.length; i++) {
                b[i]=a[i-1]*b[i-1]; // a[i] 表示当前的元素, b[i-1] 表示的是前面的元素的累乘的结果
        }
        for (int i =len-2 ; i >=0 ; i--) { // 由于 a[n] 不需要乘以他本身, 因此 少循环一次, --> i=len-2;
            temp*=a[i+1];
            b[i]*=temp;
        }
        return b;
    }
}

67. 把字符串转换成整数

难度中等179

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0

image-20220811100252623image-20220811100252623

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    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. 二叉搜索树的最近公共祖先

难度简单252

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

举例

对于两个节点, 他们的对于祖先的分布有三种情况:

  1. 两个子节点都在左子树
  2. 两个子节点都在右子树
  3. 两个子节点一左一右分布在子树
    • 这种情况, 对应的最近公共祖先就是当前的节点( 在深入的话就没有公共祖先了)

由于题目给的是二叉搜索树 , 那么可以直接利用 特性比较即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val>p.val&&root.val>q.val)// 两个子节点都在左子树
            return lowestCommonAncestor(root.left,p,q);
        if(root.val<p.val&&root.val<q.val)
            return  lowestCommonAncestor(root.right,p,q);
        return root;
    }
}

68 - II. 二叉树的最近公共祖先

难度简单470

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

其实思路跟上一题一样, 区别在于判断节点位于根节点的左右子树的方法不同

  • 通过递归判断节点是否是当前的节点的子节点
    • 时间复杂度很高
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null) return null;
        if(root.val==p.val||root.val==q.val) return root;
        if(isSon(root.left,p)&&isSon(root.left,q))// 两个子节点都在左子树
            return  lowestCommonAncestor(root.left,p,q); 
        if(isSon(root.right,p)&&isSon(root.right,q)) // 两个子节点都在右子树
            return  lowestCommonAncestor(root.right,p,q);
        return root;
    }

    public boolean isSon(TreeNode root, TreeNode t){
        if(root==null) return false;
        if(root.val==t.val) return true;
        return isSon(root.left,t)||isSon(root.right,t);
    }
}

通过递归对二叉树进行先序遍历, 当遇到节点 p或 q 时返回。从底至顶回溯，当节点 p,q 在节点 root的异侧时，节点 root即为最近公共祖先，则向上返回 root。

递推过程

分别递归左右子树, 如果遇到了p q 节点就返回,

对于left 以及right 共有三种情况

  1. 都不为null , 说明当前的root 就是最近的公共祖先(return root)
  2. 如果都为null , 说明左右子树中都没有p ,q , 返回null ( return right )
  3. left和right中只有一个不为null, 说明两个节点在左右子树的同一侧
    • left为null : 说明p q 都在根节点的右子树中, 直接返回 right
      • p, q其中一个在root 的右子树中 , 此时right指向p , q其中一个
      • p, q都在root 的右子树中, 此时right指向两个节点的最近公共祖先
      • 如下图中的 0 8 , 由于left!=null&&right!=null ==> return root : 1
    • right为null:
      • 同理, 不再赘述

案例图

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==q||root==p) return root;
        // 那么分成三种情况, root 是公共祖先, 公共祖先位于 root的左子树, 公共祖先位于root的右子树
        TreeNode left= lowestCommonAncestor(root.left, p,q);
        TreeNode right= lowestCommonAncestor(root.right, p,q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }
}