第一题√ 题库错误

1.2 4分
image.png

题意

  • 题目的意思是 一个数轴有n个节点 数组每个下标表示一个节点 然后数组的值 代表它在数轴上的位置 从0 - ?

    贪心解法（+二分法变种）

  • 贪心策略意味着 绳子的右端点必须落在有点的位置 没有点没有必要

  • 我们假设绳子的长度为5 然后数轴的点如下图所示 假设绳子右端点落在第三个点的位置 那么绳子左端点落在 8-5 = 3 的位置
  • 用二分法找第一个大于等于 3的位置 ，这个代表绳子左面占到第一个端点的信息 这个点的下标表示它是第几个端点
  • 然后用绳子右端点 的 下标 减去左面端点的下标 + 1 表示绳子在这个右端点 得到最多几个端点
  • 把结果保存在结果数组里 时间复杂度为O(nlogn)

image.png

滑动窗口解法

  • 用一个滑动窗口 首先让L 和 R在 第一个节点 然后让R往右移动 如果R不能往右移了记录一下当前覆盖到几个点 然后l往左面移一个点 R继续往右移 重复上面过程

image.png

代码

image.png

第二题√

1.2 20分
image.png

  • 普通解法 ： 首先观察 发现奇数不可能凑够 只有偶数才行 所以用贪心优先凑更多8类型的袋子 剩下的为6类型
  • 优化解法 ： 8类型的袋子不用一直枚举 如果剩余数量超过24 则不可能 原因如图 他俩最小公倍数是24 大于24的，24的部分用8装比6装好

image.png

代码

image.png

打表法

1.2 39分

  • 适用于输入是一个整数 输出是一个整数 求解分布规律的问题
  • 例如上题 我们可以让他测试从1到100个苹果 结果的规律

image.png

下节课的题

1.2 43分 58秒
image.png

  • 递归代码如下 n代表草份数 如果小于5的话用分支判断 如果大于5 先手从1 4 16。。。开始尝试所有可能，如果吃掉base份草 那么子过程草的份数就是N-base份 子过程返回后手意味着父过程先手赢了，如果循环结束还没返回 则后手赢 （防止溢出 ）

image.png

第三题√

  • 涂颜色 给你一个乱序颜色块 比如 RGGRGR 可以把每个涂成红色或绿色 要求最左面是绿色 请问涂最少的办法
  • 枚举左侧部分的大小 从0到L 右侧部分的大小N-L 特殊情况用分支处理如下图所示，一般情况需要知道左侧部分多少个R 和 右侧部分有多少个G 才能知道染色块数 可以采用遍历的办法 也可以把情况保存在预处理数组中

image.png

预处理

  • 预处理数组就是保存 从从左侧部分起有多少个R 从右侧部分起有多少个G

image.png

第四题√

image.png

思考部分

  1. 首先这种问题 要思考 怎么确定正方形这个切入点 不要一上来直接想遍历
  2. 可以想一下怎么在矩阵中确定一个长方形 需要左上角和右下角两个点 时间复杂度是 N4
  3. 那确定正方形 只能用一个左上角的点 用其他点就构不成正方形了 然后就是确定边的大小 只要不超过边界即可 复杂度是 N3

image.png

实现部分

image.png

  1. 首先枚举左上角的两个点 只需要两个for循环即可
  2. 其次是枚举边 因为左上角节点可能距离右面或者下面更近 所以border的边界不能大于离矩阵边的最近距离
  3. 最后用四个for循环 来验证边上的值是不是都是1 这样时间复杂度为 N4

    矩阵预处理 x

  • 把N4 优化 成N3算法
  • 用两个矩阵 down 和 right 保存 这个点到右面连续的1有多少 down表示 这个点到下面连续的1有多少
  • 这样在判断边的时候 只需要判断三个点 在这两个矩阵是否等于border即可

image.png

第五题 x

思路

image.png

  1. 这样的题可以用二进制位来做 首先定义等概率返回0,1函数 如果给你的函数范围是奇数 可以一个数 1-5 保留12 45 如果返回 1 2 代表二进制位为0 ，返回4 5代表二进制位为1 如果为3 重新生成。
  2. 然后主函数可以准备三个二进制位 ，每个二进制位调用上面的步骤1， 然后右移 ，把每个二进制位相加，结果不为7返回结果+1，为7重新循环生成

  • 第三题 可以用2个位 等概率为p*1-p 可以返回 01 10 (01代表0 ，10代表1) 11 00 这两个数舍弃

    代码

    image.png
    image.png

    第六题（动态规划）x

    2.2 2分
    image.png

  • 如果给0 有一种结构 1 有一个节点 2 有两种可能 如果给n 就要讨论一下左子树有多少种情况

  • 那么dp[i] = dp[0]dp[i-1] + … + dp[j]dp[i-j-1]

    代码

    1. //二叉树节点个数
    2.     int problem = 3;
    3.     int[] dp = new int[problem+1];
    4.     dp[0] = 1;dp[1]=1;dp[2]=2;
    5.     for (int i = 3; i < problem+1; i++) {
    6.         for (int j = 0; j < i; j++) {
    7.             dp[i]+=dp[j]*dp[i-1-j];
    8.         }
    9.     }
    10.     System.out.println(dp[problem]);

    第七题 x

    2.2 8分
    image.png

    思路

  • 怎么判断括号的数量是否匹配 用一个变量count 来保存遍历时的情况 遇到左括号就++ 遇到右括号就—，当count<0时说明右括号多了 返回false，遍历结束时count>0说明左括号多了返回false。

  • 理解至少需要多少个，可能有这样的情况 )(，左括号的数量和右括号相等但是并不匹配，所以需要考虑每个右括号要在遍历括号的时候就匹配上
  • 这道题用两个变量 count 和 ans(answer) 在遍历的时候 如果遍历时 count小于0 说明缺左括号 把count置为0 然后ans++ ，最后遍历结束时如果count>0说明缺右括号 返回count+ans

    代码

    public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      String s = in.nextLine();
      char[] brackets = s.toCharArray();
      int cnt = 0,ans=0;
      for (int i = 0; i < brackets.length; i++) {
          if(brackets[i]=='(')cnt++;
          //右括号有左括号匹配
          else if(cnt>0) cnt--;
          //右括号没有左括号匹配
          else{
              ans++;
          }
      }
      System.out.println(cnt+ans);
  }

    总结

  1. 从左到右遍历 不往左走 滑动窗口
  2. 找规律 打表法
  3. 数组 和 矩阵 的预处理 查询代价可以降为O1