往西汪

往西汪 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 个人简介什么都没有

个人动态

往西汪 发布了文章 · 2020-09-09

「面向 offer 学算法」笔面试大杀器 -- 单调栈

目录

  1. 前言
  2. 单调栈
  3. 初入茅庐
  4. 小试牛刀
  5. 打怪升级
  6. 出师试炼

前言

单调栈是一种比较简单的数据结构。虽然简单,但在某些题目中能发挥很好的作用。

最近很多大厂的笔试、面试中都出现了单调栈的题目,而还有不少小伙伴连单调栈是什么都不了解,因此老汪专门写了这篇文章,希望对你们有所帮助。

老规矩,先上一道题给大家看看单调栈能解决什么样的问题,这题是 2020 年猿辅导(K12 教育的独角兽,研发岗白菜价 40W 起步,不加班高福利,想要内推的可以私信老汪)的一道面试题。

给定一个二叉搜索树,并给出他的前序序列,要求输出中序序列,时间复杂度O(n),并给出证明。

单调栈

  • 是什么:单调栈是一种具有单调性的栈,任何时刻从栈顶到栈底的元素都是单调增/减的。
  • 干什么:

    • 单调栈可以找到从左/右遍历第一个比它大/小的元素的位置。
    • 单调栈也可以将某个元素左/右边所有比它小/大的元素按升/降序输出。
  • 怎么做:使用栈结构,在入栈的时候保持 id 和 val 的单调性即可。

翻译成大白话,凡是遇到题目中直接或间接要求查找某个元素左/右边第一个大于/小于它的元素,或者要求将某个元素左/右边所有小/大于它的元素按升/降序输出,就可以使用单调栈来解决。

具体怎么做你可能还有些迷糊,下面我们直接通过做题来加深对单调栈的理解。十分钟包教包会,当天就可以和面试官对线。

初入茅庐

给定数组 a,要求输出这样的数组 b,b[i] 是 a[i] 左边第一个比 a[i] 大的元素,若不存在则 b[i] = a[i]。

最暴力的解法,就是对每一个 a[i],遍历其左边的所有元素,这样所需的时间复杂度是 O(n^2)。如果使用单调栈,时间复杂度可以优化到 O(n)。

这是最基本、最直白的单调栈问题,所有单调栈问题都是在该问题上进行延伸、变种得来的,掌握了这个问题的解决方法,所有单调栈的问题都能迎刃而解

由于本问题过于简单、直白,就不多做讲解,直接上代码:

public int[] solve(int[] a){
  if(a == null) return null; //容错处理,越是简单的题越要注意细节
  int n = a.length;
  int[] b = new int[n];
  Stack<Integer> stack = new Stack(); //单调栈当然要用栈结构啦
  for(int i = 0; i < n; i++){
    while(!stack.isEmpty() && stack.peek() < a[i]) stack.pop(); //所有比 a[i] 小的元素都出栈,保证了从栈顶到栈底元素是单调增的,并且栈顶的元素是 a[i] 左边第一个比 a[i] 大的元素
    b[i] = stack.isEmpty() ? a[i] : stack.peek();
    stack.push(a[i]);
  }
  return b;
}

这代码也是单调栈问题的基本结构,所有单调栈问题的代码都基于此进行变种、扩展。小伙伴们可以多花两分钟好好消化上面的代码。

考虑到有些小伙伴不用 Java,老汪把上述代码抽象成伪代码,这也是单调栈的基本结构

背诵 + 套用,即可解决所有单调栈问题。

函数 solve (数组 a):
    新建数组 b;
    新建栈 stack;
    For i From 0 To n - 1:
        While 栈非空 且 栈顶元素 < a[i]:
            出栈;
        End While
        b[i] = 栈顶元素 IF 栈非空 ELSE 默认值;
        a[i] 入栈;
    End For
    return b;

小试牛刀

单调栈的最基本使用方式我们已经了解了,下面一起来解决文章开头提到的面试题。

给定一个二叉搜索树,并给出他的前序序列,要求输出中序序列,时间复杂度O(n),并给出证明。

最暴力的方法就是对前序序列进行排序,时间复杂度为 O(nlogn),使用单调栈可以优化到 O(n)。

思路分析:

对于二叉搜索树而言,给定其根节点 a[i],左子树里所有元素都比 a[i] 小,右子树里所有元素都比 a[i] 大。

回顾一下遍历顺序:

前序序列,先遍历根节点,再遍历左子树,最后遍历右子树;

中序序列,先遍历左子树,再遍历根节点,最后遍历右子树。

即,对于元素 a[i],以它为根节点的子树,

前序序列为,a[i], a[i] 的左子树序列, a[i] 的右子树序列

后序序列为,a[i] 的左子树序列, a[i]a[i] 的右子树序列

因此,当我们遍历前序序列,遇到右子树的第一个元素 a[j] 时,其左边所有元素都小于 a[j], 将其左边所有元素按升序输出,即可得到 a[i]a[i] 的左子树 的后序序列。

对于右子树再以上述步骤迭代,即可得到完整的后序序列。

显然,这是单调栈的第二种用法:单调栈可以将某个元素左边所有比它小的元素按升序输出。

下面直接上代码:

public int[] solve(int[] pre){
  if(pre == null) return null; //注意容错细节
  int n = pre.length;
  int[] infix = new int[n]; //中序序列
  Stack<Integer> stack = new Stack();
  int index = 0; // 指示中序序列的当前下标
  for(int i = 0; i < n; i++){
    while(!stack.isEmpty() && stack.peek() < pre[i]) infix[index++] = stack.pop(); //由于栈中元素是从栈顶到栈底单调增的,所以可以保证输出序列是单调增的
    stack.push(pre[i]);
  }
  while(!stack.isEmpty()) infix[index++] = stack.pop();
  return infix;
}

打怪升级

再来看一道题,这道题是 2020 年 9 月 6 日字节笔试的第二题。难度对标 leetcode 的 medium 级别。

给定一个长为 n 的序列 a。L[i] 表示第 i 个位置左边第一个大于 a[i] 的数的下标(从 1 开始),没有的话为 L[i] = 0。R[i] 表示第 i 个位置右边第一个大于 a[i] 的数的下标(从 1 开始),没有的话为 R[i] = 0。求 $max_{i = 1}^{n}L[i]·R[i]$。

思路分析:一看题目,就是单调栈的第一种用法。使用两次单调栈分别得到 L[i] 和 R[i],再遍历一遍即可。时间复杂度为 O(n)。

代码如下:

public int solve(int[] a){
  if(a == null) throw new RuntimeException("输入有误!"); //细节,一定要细
  int n = a.length;
  int[] L = new int[n], R = new int[n];
  // 这里分两次 for 循环来写,熟练的话可以放在同一个 for 循环里。
  Stack<Pair> stack = new Stack();
  for(int i = 0; i < n; i++){
    while(!stack.isEmpty() && stack.peek().val < a[i]) stack.pop();
    L[i] = stack.isEmpty() ? 0 : stack.peek().id + 1; //注意题目要求下标是从 1 开始的
    stack.push(new Pair(i, a[i]));
  }
  stack.clear();
  for(int i = n - 1; i >= 0; i--){
    while(!stack.isEmpty() && stack.peek().val < a[i]) stack.pop();
    R[i] = stack.isEmpty() ? 0 : stack.peek().id + 1; //注意题目要求下标是从 1 开始的
    stack.push(new Pair(i, a[i]));
  }
  // L[i] 和 R[i] 计算完毕,下面遍历一遍得到最大值即可
  int ans = 0;
  for(int i = 0; i < n; i++) ans = Math.max(ans, L[i] * R[i]);
  return ans;
}

class Pair{
  int id; // 下标
  int val;
  public Pair(int id, int val){
    this.id = id;
    this.val = val;
  }
}

出师试炼

关卡 1

给定一个整数数组,你需要验证它是否是一个二叉搜索树正确的先序遍历序列。

你可以假定该序列中的数都是不相同的。

关卡 2

给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。

关卡 3

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

PS:在公众号【往西汪】后台回复关键字【单调栈】,即可获得上述关卡的过关秘籍(代码实现)。

本期单调栈问题就分享到这,下一期你想看什么内容呢?单调队列?前缀和思想?还是老汪独家刷题秘籍?又或者有其他想看的,也可以在下方评论区告诉老汪。

我是往西汪,致力于面向 offer 分享算法知识,希望你早日收获心仪 offer。我们下期再见。

爱你们

查看原文

赞 2 收藏 2 评论 0

往西汪 发布了文章 · 2020-08-31

「面经」你可能需要的字节跳动三轮面经

目录

前言

七月收获了字节的意向书,今日得空把面经整理出来分享给大家,也借此把好运分享给大家

简单介绍下个人情况:

面试前:剑指 offer 刷完,Leetcode 大概 70 道。操作系统复习完毕,数据库不会,计网不会。

后来:一面前一周学了数据库,三面前三天学了计网。两周时间陆续刷了 80 道 Leetcode。

希望这篇文章能对大家有所帮助,祝各位 offer 多多!

三轮面经

本人无实习,故而没有被问到关于项目的问题。

问题构成:手撕代码、基础知识、场景题。

「基础知识」都是固定答案,因此本篇中只分享题目,不分享答案。

一面

  • 手撕代码
easy 题:中文字符串转成数字。例:“五百三十万六千零三” -> 5306003。约束:输入金额在一亿以内。要求:做一定的容错处理,bug free。

这题比较简单,方法大家应该都能想到。只是要求 bug free 和容错处理,因此写代码的时候要考虑完善点。比如说输入异常的情况(字符串是否合法,“五五百”这种就不合法,“3百五”也不合法)。

  • 手撕代码
leetcode medium 原题:判断字符串是否满足斐波那契规则,如:“199100199”。由于 1 + 99 = 100,99 + 100 = 199。

这题老汪是在面试官的引导下才一步一步想到最优解的。(吹爆面试体验,面试官很耐心的在引导,nice!)

这题的关键点就在于如何找到开头两个数字 n1, n2。找到了这两个数字,后面就可以用 n = n1 + n2 的规则通过一次遍历来判断是否符合斐波那契规则。找开头俩数字只能暴搜了,代码如下:

public boolean solve(String str){
 if(str == null) return false;
 int n = str.length();
 for(int i = 1; i < n; i++){
   int n1 = Integer.parseInt(str.substring(0, i)); //获得第一个数
   for(int j = i + 1; j < n; j++){
     int n2 = Integer.parseInt(str.substring(i, j)); //获得第二个数
     if(judege(str, n1, n2, start)) return true;//判断是否符合规则
   }
 }
 return false;
}

//给定 n1, n2,判断字符串是否符合斐波那契规则
boolean judge(String str, int n1, int n2, int start){
 int n = str.length();
 for(int i = start; i < n;){
   int n3 = n1 + n2;
   int len = (n3 + "").length();
   if(start + len > n || n3 != Integer.parseInt(str.substring(i, i + len))) return false; // 下标超了,或者后一个数字不等于 n3
   i += len;
 }
 return true;
}

时间复杂度:O(n^3),找到开头两个数字需要 O(n^2),判断字符串是否符合规则需要 O(n)。

这题可以剪枝来稍微降低一些时间消耗,大家可以自行优化。

  • 手撕代码
10亿个无序整数找出中位数。

这题老汪也是在面试官的引导下才一步步想到最优解的。(再次吹爆面试体验)

由于是 10 亿个整数,因此无法在内存中处理。也就是说要采用合适的外排序算法。

这里可以使用桶排序,使用 n 个区间均匀的桶,遍历一遍整数,将它们存入对应区间的桶中,并统计桶中数字个数。这样就可以找到中位数所在的桶,如果桶中数字还是很多,再进行桶排序,否则进内存中排序即可。

二面

  1. 事务的 ACID 特性
  2. Innodb 使用的索引结构
  3. b+ tree 的优点,为什么要用它
  4. 给定复合索引 (a, b, c),查询语句中用 where a = 1 and c = 1,索引是否会失效?(最左前缀匹配的相关知识)
  5. 一条 SQL 语句的执行流程 (不会)
  6. 进程和线程的区别
  7. 并发和并行的区别
  8. 进程调度的策略
  9. 死锁发生的原因
  10. 手撕代码
  • leetcode 原题 41 (不会,换了一题)
给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。

思路:要找最小的正整数,数组中有 n 个数字,那么缺失的最小正整数一定在 [1, n + 1] 内。

因此可以利用数组本身做哈希,遍历一遍数组,将 [1, n] 内的数字 i 放到对应下标 i - 1 上。

再遍历一遍数组,第一个 nums[i] != i + 1 的数字 i + 1即为缺失的最小正整数。

代码如下:

public int firstMissingPositive(int[] nums) {
  int n = nums.length;
  for(int i = 0; i < n; i++){
    while(nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]){ //(0, n] 的数字放到对应下标上
      int temp = nums[i] - 1;
      nums[i] = nums[temp];
      nums[temp] = temp + 1;
    }
  }
  int i = 0;
  for(; i < n && nums[i] == i + 1; i++); // 找到第一个未出现的正整数
  return i + 1;
}

时间复杂度:O(n),虽然有 while 循环,但每个数字最多被交换一次即可到对应下标上。

  • leetcode 原题 3
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

思路:很经典的一道题了,滑动窗口即可解决。

代码如下:

public int lengthOfLongestSubstring(String s) {
  if(s == null) return 0;
  Map<Character, Integer> map = new HashMap<>();
  int start = 0, ans = 0;
  for(int i = 0; i < s.length(); i++){
    char c = s.charAt(i);
    if(map.getOrDefault(c, -1) >= start) start = map.get(c) + 1;
    map.put(c, i);
    ans = Math.max(ans, i - start + 1);
  }
  return ans;
}

三面

  • 手撕代码
算法题:二维数组,按行递增,按列递增,问是否能找到某个数字(剑指offer原题)

思路:利用递增的特性,从最左下角开始遍历(该列最大值,该行最小值)。和目标数字比较:

< 目标数,说明这一列都 < 目标数,因此列下标 + 1

> 目标数,说明这一行都 > 目标数,因此行下标 - 1

这样,每次比较都可以排除一行/一列。

代码如下:

public boolean canFind(int[][] matrix, int target){
 if(matrix == null || matrix.length == 0) return false;
 int rows = matrix.length, cols = matrix[0].length;
 int row = rows - 1, col = 0;
 while(row >= 0 && col < cols){
   if(matrix[row][col] == target) return true;
   if(matrix[row][col] > target) row--;
   else col++;
 }
 return false;
}
  • 手撕代码
算法题:2 * 1 的小矩形填充满 2 * n 的大矩形有多少种方案?

思路:挺简单的动态规划题

代码如下:

public int nums(int n){
 if(n < 0) return 0;
 int[] dp = new int[Math.max(n, 2)];
 dp[0] = 1;
 dp[1] = 1;
 for(int i = 2; i < n; i++) dp[i] = dp[i - 2] + dp[i - 1];
 return dp[n];
}

这里空间复杂度是 O(n),也可以通过 状压 dp 将空间复杂度降到 O(1)。

  • 场景设计
1000 亿个无符号整数,找最大的 100 个。内存不够的情况下用什么方案?内存充足的情况下呢? partition 的方案不稳定,有什么稳定的方法吗?

内存不够堆排序,内存够用计数排序。

  1. https 如何加密的
  2. os 中的 pagefault (缺页中断)
  3. mysql 中的底层索引结构?为什么用这个结构
  4. hashmap 是线程安全的吗?想要线程安全怎么办?
  5. 场景设计
大文件的断点续传

这题网上也有很多方案。老汪是参照 tcp 的滑动窗口和重传机制来回答的。

把大文件分块并打上编号,接收端对块进行有序确认,如果有某块没收到,就告知发送端让其重发。

发送端记录最后一次发送的编号,断点续传时从这个编号开始传。

因为负载均衡,续传的时候要确定从哪个服务器拿的,这个可以让接收端记录发送端的标识。

关于字节

  1. 工作强度:大小周,10 10 5.5。不强制加班,做完就可以走,但工作量一般要加班完成。因人而异,也有摸鱼的。
  2. 福利:三餐全包,下午茶,房补 1500,免费健身房(基本上工作一年后都会吃胖,hhh)
  3. 氛围:扁平化管理,网传风评都挺不错的。
  4. 新人培养:mentor 制,一对一带领新人熟悉。不过和老牌 BAT 相比,文档不够完善,新人培养流程还是有些欠缺的。
  5. 字节校招的考察重点:后端的话,基本上是要转 go/python 的,所以不怎么考察语言。

主要考察「操作系统」、「数据库原理」、「计网」和「手撕代码」,字节是非常重视手撕的,这个一定要好好准备。当然项目做得好的同学,也是有加分的。

老汪点评:工作强度大,面对的挑战多,薪酬也给力。适合能力强、抗压能力强的同学,扛得住压成长会很快。不过对新人确实有点考验,因人而异吧。

彩蛋

  1. 虽然字节的手撕代码比较难,但题库是有限的,多刷面经中的算法题,会有很大概率碰上原题。
  2. 有三面挂了的,想投上海 data 部门的,老汪可以帮忙联系 HR 直捞。
  3. 点赞的各位小伙伴 offer 多多。没点赞的小伙伴嘛,也 offer 多多吧。嘻嘻~
  4. 听说发一句 “一切都会好起来的!”,就真的一切都好起来了!

image

查看原文

赞 7 收藏 4 评论 4

往西汪 发布了文章 · 2020-08-18

遇到「最值问题」还在无脑动态规划?二分法考虑一下呗

目录

  1. 前言
  2. 二分法基础及变种结构
  3. 小试牛刀
  4. 打怪升级
  5. 出师试炼

前言

一般来说,遇到「最值问题」通用的方法都是动态规划,而有一类「最值问题」可以用其他方法更加巧妙、简单方便的解决,这类问题的常见问法是「使……最大值尽可能小」。

这类问题也是大厂笔试面试常见题型,2020 年美团笔试题、字节面试题中都出现过。

这类问题有三大特征:

  1. 求最值(一般是最小值)
  2. 值的搜索空间是线性的
  3. 对该值有一个限制条件,并且若 x 满足条件,则 [x, +∞) 都满足条件,反之 (-∞, x] 都不满足条件。

你说的我都懂,可问题是,这是啥意思呢?叉会腰,冷静一下
(你说的我都懂,可问题是,这是啥意思呢?叉会腰,冷静一下。)

为了方便大家理解这类问题到底是个什么玩意儿,本汪在这里列出 leetcode 上的一道题目作为例子:

给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

不熟悉二分法的同学初遇此题,看到关键词“分割成 m 份”、“最小”,就想到了动态规划。诚然此题具备了使用动态规划的一切前提条件,也确实可以通过动态规划做出来,但其时间复杂度为 O(n^2 * m) , 空间复杂度为 O(n * m).

如果你看了本汪的这篇文章,学会了用二分法解决这一类问题,那么时间复杂度可以优化到 O(n * logx), 空间复杂度可以优化到 O(1),并且思路非常简洁,代码实现也极其简单。

二分法基础及变种结构

在讲具体的方法之前,本汪先和大家一起回顾下二分法,熟悉二分法的同学可以直接跳过这部分。

最早接触二分思想的地方应该是在二分搜索中。(本质上类似快排中的 partition 思想)

二分法是在有序线性搜索空间内,利用有序性,每次搜索通过排除一半的剩余搜索空间,使 O(n) 级别的线性搜索优化到 O(logn) 级别的方法。

image
(二叉树:我都会二分,不会还有人不会二分法吧?不会就让往西汪那小子教你)

二分法的基本代码非常简单,这里就不多提了,下面用类 java 语言给出其针对「最值问题」的变种结构:

// nums 数组是搜索空间,m 是限制条件
// check(x, m) 表示在搜索空间 nums 中的点 x,满足了限制条件 m
public int binary(int[] nums, int m){  
      初始化 l, r 为搜索空间的起始点和终点
    while(l < r){
        int mid = (l + r) >> 1; //二分,一次搜索可以排除 mid 的左边或者右边(剩余搜索空间的一半)
        if(check(mid, m)) r = mid; //因为这一类最值问题要找的是最小,mid 满足条件了,(mid, r] 就不是最小的答案了
        else l = mid + 1; // mid 不满足条件,根据有序性,[l, mid] 里的数全不满足条件
    }
    return r;
}

根据结构我们可以看出,遇到这类问题的时候只需要找到「搜索空间」、「检查条件」,然后套用结构就能轻轻松松地解决问题。

下面就让我们来用二分法解决刚刚提到的问题。

小试牛刀

题目

给定一个非负整数数组和一个整数 m,你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

思路

前文提及,解决本题只需要找到「搜索空间」、「检查条件」,剩下的就是闭着眼睛套结构的事儿了。

先找「搜索空间」,因为此类问题的搜索空间都是线性的,所以找到了起始点终点,也就找到了搜索空间。

看问题描述 “子数组各自和的最大值最小”,也就是说我们搜索的点是 "子数组各自和的最大值",那么搜索空间的起始点是数组 nums 中的最大值,即 min(nums),搜索空间的终点是数组 nums 中的所有元素之和,即 sum(nums)。因此我们找到了搜索空间,为 [min(nums), sum(nums)].

再看「检查条件」。给定搜索空间 nums,和点 x,判断 x 是否满足限制条件 m。

本题的条件是“子数组各自和的最大值”,也就是说 x 和 m 个子数组各自和相比较,都要大于或者等于它们。

「搜索空间」、「检查条件」都找到了,下面闭着眼睛套结构吧~

image
((瑟瑟发抖.jpg) 好的,这就上代码)

代码

class Solution {
      // 这个方法就是直接套结构
    public int splitArray(int[] nums, int m) {
        long l = 0, r = 0;
        for(int num: nums) {r += num; l = Math.max(l, num);} // 初始化 l 和 r
        while(l < r) {
            long mid = (l + r) >> 1;
            if(check(nums, mid, m)) r = mid;
            else l = mid + 1;
        }
        return (int)r;
    }
    
    public boolean check(int[] nums, long a, int m) { // 给定搜索空间中的点 a,看它是否大于等于所有子数组的各自和
        int cnt = 1;
        long sum = 0;
        for(int n: nums) {
            sum += n;
            if(sum > a) {
                sum = n;
                cnt ++;
                if(cnt > m) return false;
            }
        }
        return true;
    }
}

打怪升级

咱们再来看一道题,小伙伴们可以先自己思考,有思路的话自己动手实现下。再看看本汪给出的思路,加深理解。

题目

珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

image

(往西汪:我请你们吃香蕉,可以给我点个赞吗)

思路

老规矩,先找「搜索空间」,再找「检查条件」,最后闭着眼睛套结构。

「搜索空间」:H 小时内必须吃完 sum(piles) 根香蕉,所以初始点为 sum(piles) / H,一次最多只能吃一堆,所以终点为 max(piles)。因此,搜索空间为 [sum(piles) / H, max(piles)]

「检查条件」:“在 H 小时内吃掉所有香蕉”,因此以 K 个 / 小时 的速度吃完香蕉的用时要小于等于 H。

下面就闭着眼睛套结构吧。

代码

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int l = 1, r = 0; // 这里本汪为了代码的简洁性,在不影响时间复杂度的情况下,直接让初始点为 1
        for(int i: piles) r = Math.max(r, i); // 一次最多吃一堆
        while(l < r){
            int mid = (l + r) >> 1;
            if(check(piles, mid, H)) r = mid;
            else l = mid + 1;
        }
        return r;
    }

    boolean check(int[] piles, int K, int H){
        int t = 0;
        for(double i: piles){
            t += Math.ceil(i / K); // 一堆香蕉共计 i 个,需要 ⌈i / K⌉ 个小时吃完
            if(t > H) return false; // 警卫回来了还没吃完
        }
        return true;
    }
}

出师试炼

我非常喜欢看我文章的小伙伴,个个都是人才,说话又好听,脑瓜子又聪明,还很主动的给我文章点赞。我相信砍翻两个小怪之后,你们已经是这类问题的专家了,下面就给几道题目供大伙随便玩玩。

image
(超喜欢往西汪的文章的)

关卡 1

你将会获得一系列视频片段,这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠,也可能长度不一。

视频片段 clips[i] 都用区间进行表示:开始于 clips[i][0]并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑,例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成覆盖整个运动过程的片段([0, T])。返回所需片段的最小数目,如果无法完成该任务,则返回 -1 。

关卡 2

牛牛有 n 件带水的衣服,干燥衣服有两种方式。

一、是用烘干机,可以每分钟烤干衣服的 k 滴水。

二、是自然烘干,每分钟衣服会自然烘干 1 滴水。

烘干机比较小,每次只能放进一件衣服。

注意,使用烘干机的时候,其他衣服仍然可以保持自然烘干状态,现在牛牛想知道最少要多少时间可以把衣服全烘干。

关卡 3

你太强了!我已经没有更多的题目给你玩了。你可以凭借这套武功闯荡江湖了!

……

……

……

等等,我说笑呢。你这小身板,要不先进我的其他训练营再练练呗?

啥,你问我的其他训练营在哪里?动动小手,点个关注,新的训练营已经在建设了,嘿嘿。

咳咳,暗示的很明显了
(咳咳,暗示的很明显了)

查看原文

赞 6 收藏 5 评论 3

往西汪 发布了文章 · 2020-07-27

算法题解 - 牛客编程巅峰赛S1第6场 - 黄金&钻石&王者组

A. 牛牛爱奇数

题目描述

在牛牛面前放着 n 个数,这些数字既有奇数也有偶数,只不过牛牛对奇数情有独钟,他特别想让这些数都变成奇数。

现在牛牛获得了一种能力,他可以执行一种操作:每次选中一个偶数,然后把这些数中与该数相等的数都除以 2,例如现在有一个数组为 [2, 2, 3],那么牛牛可以执行一次操作,使得这个数组变为 [1, 1, 3]。

牛牛现在想知道,对于任意的 n 个数,他最少需要操作多少次,使得这些数都变成奇数?

备注:

1 ≤ n ≤ 10^6,代表一个有多少数字
a1, a2, a3 ... an(1 ≤ ai ≤ 10^9)代表数字的大小

示例1

输入

3,[2,2,3]

输出

1

说明

只需做一次操作,会将其中的偶数2都变成1,满足了所有的数都是奇数的要求。

示例2

输入

3,[1,3,7]

输出

0

说明

不需要做任何操作,因为所有的数原本就是奇数。

解法:大顶堆 + 哈希集合

思路分析

每次可以让所有相同的偶数变成一半,问最少操作次数。

一次操作所有相同数,显然要使用哈希集合进行去重。

而要使得操作次数最少,必然对偶数从大到小进行操作,这样才可以避免对某个偶数进行重复的操作。

想要从大到小操作,显然使用大顶堆保存偶数。每次从堆顶取一个数字进行操作,若得到的新的数字是偶数并且未在哈希集合中出现过,就把它再加入大顶堆中。

时间复杂度:O(max(n, logm))。这里的 m 是最大的偶数。遍历一遍数字需要 O(n),把偶数全变成奇数需要 O(logm)。

空间复杂度:O(n)。

代码实现

public int solve (int n, int[] a) {
  Set<Integer> set = new HashSet();
  int ans = 0;
  for(int i: a)
    if((i & 1) == 0) set.add(i);
  Queue<Integer> q = new PriorityQueue<Integer>((x,y) -> y - x);
  q.addAll(set);
  while(!q.isEmpty()) {
    int num = q.poll() >> 1;
    ans++;
    if((num & 1) == 0 && !set.contains(num)) q.add(num);
  }
  return ans;
}

B. 牛牛摆放花

题目描述

牛牛有 n 朵需要摆放的花,但是每朵花呢,高度都不一样,牛牛不喜欢相邻的花高度相差太多,这样会影响美感。

所以牛牛提出了一个“丑陋度”的概念,“丑陋度”意思为在一个摆放序列中,相邻花高度差的最大值。而且牛牛是一个完美主义者,所以他希望:

1.将这些花摆成首尾相接的圆形

2.为了美观,他希望摆放的花“丑陋度”最小

程序应返回:按照这些花排成一个圆的顺序,输出在多个摆放花的序列中,最小的“丑陋度”。

备注:

第一个参数为一个整数 n(2 ≤ n ≤ 10^5),代表花的数量。
第二个参数为包含 a1, a2, a3 ... an(1 ≤ ai ≤ 10^9) 的数组,代表每朵花的高度。

示例1

输入

5,[2,1,1,3,2]

输出

1

说明

可以摆成 1 2 3 2 1这样的序列,最小的“丑陋度”为1

示例2

输入

3,[30,10,20]

输出

20

说明

可以摆成10 30 20这样的序列,最小的“丑陋度”为20

解法:排序

思路分析

如果不考虑首尾相接的话,要想丑陋度最小,显然摆放序列为升序/降序。

现在要求首尾相接,因此首尾的高度差也要小一些,显然 V 型 序列或者 ^ 型 序列满足要求。

故而进行排序,升序/降序都可以。这里以升序为例,高度差 = arr[i] - arr[i - 2]。首尾高度差 = arr[1] - arr[0]。

时间复杂度:O(nlogn)。

空间复杂度:O(1)。

代码实现

public int solve (int n, int[] array) {
  Arrays.sort(array);
  int ans = array[1] - array[0];
  for(int i = 2; i < n; i++) 
    ans = Math.max(ans, array[i] - array[i - 2]);
  return ans;
}

C. 星球游戏

题目描述

牛牛和牛妹在进行一场星球模拟游戏,游戏规则如下:

游戏地图内共有 n 个星球,共有 m 条隧道连接这些星球。每条隧道都是双向的,每两个星球间不一定只有一条隧道。现在牛牛占领了这 n 个星球中的 p 个星球,牛妹占领了这 n 个星球中的 q 的星球(每个星球最多只能被一个人占领)。现在牛牛想知道他占领的 p 个星球中任意一个星球,到牛妹占领的 q 个星球中任意一个星球,这两个星球的最短距离是多少。

备注:

2 ≤ n ≤ 1e5, 0 ≤ m ≤ 2e5, 1 ≤ p ≤ 1e5, 1 ≤ q ≤ 1e5, p + q ≤ n, min(p, q) ≤ 10, 1 ≤ wi ≤ 1e4
  相关参数意义如下
  niuniu 牛牛占领的p个星球的编号
  niumei 牛妹占领的q个星球的编号
  path  m条隧道,每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号,wi是它们之间的距离
  nn int整型 星球个数n

示例1

输入

[1],[3,4],[[1,2,7],[2,3,6],[3,4,2],[1,3,11],[2,4,3]],4

输出

10

说明

距离最近的牛牛星和牛妹星是 1 和 4,他们之间的距离为 10

示例2

输入

[1],[2],[],2

输出

-1

说明

所有的牛牛星和牛妹星都不联通,故输出 -1

解法:dijkstra算法

思路分析

显然这题是单源最短路问题,直接使用 dijkstra 算法可解。

有人可能要问了:“汪汪,牛牛不是占领了 p 个星球吗,怎么会是单源最短路问题?”

注意到题目中说的是 p 个星球中任意一个,所以法力无边的本汪创造了一个超级星球 X,从 X 出发可以瞬移到牛牛的 p 个星球,因此本题就等价于问从星球 X 出发,到牛妹占领的星球中最近距离是多少。就这样轻轻松松地变成一个单源最短路问题了。

本汪默认聪明博学的小伙伴们都会 dijkstra 算法,在这就不多赘述了。(才不是因为我懒)

如果有小伙伴对 dijkstra 算法还有疑问,可以在下方留言,有需求的话本汪就专门出一期 dijkstra 算法的博客。

代码实现

public class Solution {
    /**
     * 
     * @param niuniu int整型一维数组 牛牛占领的p个星球的编号
     * @param niumei int整型一维数组 牛妹占领的q个星球的编号
     * @param path int整型二维数组 m条隧道,每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号,wi是它们之间的距离
     * @param nn int整型 星球个数n
     * @return int整型
     */
    final int INF = 10001;
    public int Length (int[] niuniu, int[] niumei, int[][] path, int nn) {
        List<Pair>[] edges = new List[nn + 1];
        int[] dis = new int[nn + 1];
        Arrays.fill(dis, INF);
        boolean[] vis = new boolean[nn + 1];
        for(int i = 0; i <= nn; i++) edges[i] = new ArrayList();
        for(int[] edge: path) {
            edges[edge[0]].add(new Pair(edge[2],edge[1]));
            edges[edge[1]].add(new Pair(edge[2],edge[0]));
        }
        Queue<Pair> q = new PriorityQueue<Pair>((a, b) -> a.d - b.d);
        for(int u: niuniu) {
            dis[u] = 0;
            q.add(new Pair(0, u));
        }
        while(!q.isEmpty()) {
            Pair p = q.poll();
            if(vis[p.v]) continue;
            vis[p.v] = true;
            for(Pair e: edges[p.v]) {
                if(dis[e.v] > dis[p.v] + e.d) {
                    dis[e.v] = dis[p.v] + e.d;
                    q.offer(new Pair(dis[e.v],e.v));
                }
            }
        }
        int ans = INF;
        for(int u: niumei) ans = Math.min(ans, dis[u]);
        return ans == INF ? -1 : ans;
    }
}

class Pair{
    int d; //距离
    int v; //另一个顶点
    public Pair(int d, int v) {
        this.d = d;
        this.v = v;
    }
}

写在最后

「牛客编程巅峰赛系列题解」也写了八期了,每篇文章都要耗费大量的时间进行撰写、排版、纠错。但对小伙伴们的帮助却不大,本汪 也是产生了一丢丢的挫败感。
暂不打算继续更新这个系列的文章了。
新的计划是更新「解题方法系列」的文章。第一期的标题我都想好了:【遇到「最值问题」无脑动态规划?二分法考虑一下呗】。预计一周内更新。
如果小伙伴想了解其他方面的知识,可以在下方评论区留言哦。本汪 会视情况决定是否新开这个系列。

查看原文

赞 0 收藏 0 评论 0

往西汪 发布了文章 · 2020-07-27

算法题解 - 牛客编程巅峰赛S1第5场 - 黄金&钻石&王者组

A. 完全平方数的尾巴

题目描述

我们把一个能被表示成某个整数的平方的数称为完全平方数。

例如 4 = 2 ∗ 2,16 = 4 ∗ 4,所以4,16是完全平方数。

现在输入一个整数为 x (0 ≤ x ≤ 999),请聪明的你判断它是不是由某个完全平方数对 1000 取模得到的呢。

示例1

输入

24

输出

true

说明

1024 = 32 ∗ 32
24 = 1024 mod 1000

解法:暴力搜索

思路分析

我们知道完全平方数对 k 取模的值,是 k 个一循环的。即对于 f(x) = (x * x) % k,函数值 k 个一循环。

本题对 1000 取模,因此遍历 1 - 999 的完全平方数模 1000 的值,若都不为 x,则返回 false。

代码实现

public boolean solve (int x) {
  for(int i = 1; i < 1000; i++) {
    if(i * i % 1000 == x) return true;
  }
  return false;
}

B. 牛牛的字符串

题目描述

牛牛有一个长度为 N 的由小写字母组成的字符串 S,还有一个整数 K。在每一步中,牛牛都可以选择一个位置 i,并在 i 和 i + K 处交换字符(i + K < N)并且 $S_i <S_{i+k}$,即交换之后,新形成的字符串应字典序大于旧字符串。牛牛想尽可能交换尽量多的步数。他想知道最多可以交换多少步呢。

备注:

1 ≤ N ≤ 1e5, 1 ≤ k ≤ N

示例1

输入

"cbexa",2

输出

2

说明

cbexa -> cxeba -> excba 步数为2

解法:分组求解

思路分析

我们看一下交换条件:$S_i <S_{i+k}$。即前一个字符小于后一个字符。

因此对于序列: i, i + k, i + 2k, …。可以交换的次数 = 顺序对的个数。

而字符串中总共有 k 个上述序列。故而求解这 k 个序列的顺序对的个数 之和,即可得出答案。

顺序对个数的求解方法和逆序对个数的求解方法相同,经典的方法有归并排序和离散化树状数组。不过本题是求字符数组的顺序对,因此可以利用 26 大小的哈希数组来求解。

代码分析

public int turn (String s, int k) {
  int ans = 0;
  List<Character>[] group = new List[k];
  for (int i = 0; i < k; i++) group[i] = new ArrayList<Character>();
  for (int i = 0; i < s.length(); i++) group[i % k].add(s.charAt(i));
  for (List<Character> list: group) {
    int[] arr = new int[26];
    for (char c : list) {
      int index = c - 'a';
      for(int i = 0; i < index; i++) ans += arr[i]; //找到字符 c 之前比字符 c 小的字符的个数
      arr[index]++;
    }
  }
  return ans;
}

C. 下棋

题目描述

牛牛做了一个 $n*n$ 的棋盘,棋盘每个格子有一个编号(从 1 到 $n * n$),编号是成螺旋形状的,下面给出 $3*3$ 的棋盘编号的例子。

123
894
765

由于隔离在家,牛牛只能自己一个人玩游戏。一开始棋子在 1 号格子上,分数为 0。
每次牛牛会用骰子掷出 1 - 6 中的一个数字 j (1 ≤ j ≤ 6),然后棋子会沿编号向前移动 j 步(n 号格子后面到 1 号格子),
且分数加上所有行号或者列号与当前格子相差小于 j 的所有格子的编号。

严格来说,函数 f(x, y) = 第 x 行第 y 列的格子的编号。比如 n = 3 时,f(2, 2) = 9;n = 4 时,f(3, 1) = 11。
假设当前棋子在 i 号格子上,移动 j 步,那么棋子将移动到 i' 号格子上,其中 i' = (i + j - 1 ) % (n * n) + 1。且分数加上
$∑_{1≤x,y≤n,\\f(x_0,y_0)=i′,\\min(∣x−x_0∣,∣y−y_0∣)<j}f(x,y)$
牛牛想让你帮他写个程序,计算出每次移动完累计得到的分数。 为了防止输出过大,请返回分数对 1,000,000,007 取模后的值。

备注:

对于30%数据,1 ≤ n ≤ 100,1 ≤ q ≤ 1000(q为询问次数)
对于100%数据,1 ≤ n ≤ 2000,1 ≤ q ≤ 100000(q为询问次数)

示例1

输入

4,[1,2,5,6,2]

输出

[48,138,274,410,510]

解法:前缀和

思路分析

$∑_{1≤x,y≤n,\\f(x_0,y_0)=i′,\\min(∣x−x_0∣,∣y−y_0∣)<j}f(x,y)$ 在图上来看,其实就是一个以 $f(x, y)$ 为中心的一个十字形框内的编号之和,如图所示。
在这里插入图片描述

因为查询的次数很多,所以我们希望在常数时间内求解出答案。

如果我们能在常数时间内得到某个矩形内的编号和,那么答案 = 红色矩形 + 绿色矩形 - 蓝色矩形 内编号之和。

如何在常数时间内得到某个矩形内的编号之和呢?显然我们可以利用前缀和保存一个大矩形的编号和,大矩形 - 小矩形 = 我们要求的矩形。

定义前缀和 preSum[i][j] 表示以 (i, j) 为右下角的矩形的编号和。显然前缀和可以通过公式 preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + chessboard[i][j] 来迭代求解。

时间复杂度:$O(n*n)$。初始化棋盘和前缀和的时间复杂度为 $O(n * n)$, 每一次查询分数的时间复杂度为 $O(1)$。

空间复杂度:$O(n * n)$

代码实现

public int[] getScores (int n, int[] query) {
  int[] ans = new int[query.length];
  int[][] chessboard = new int[n + 1][n + 1]; //棋盘,chessboard[x][y] 表示第 x 行 第 y 列的编号
  int[][] coordinates = new int[n * n + 1][2]; //编号对应的下标
  long[][] preSum = new long[n + 1][n + 1]; //前缀和,preSum[i][j] 表示以 (i,j) 为右下角的矩形内所有编号之和
  init(n, chessboard, coordinates, preSum);
  int now = 1;
  long score = 0;
  for(int i = 0; i < query.length; i++) {
    int j = query[i];
    now = (now + j - 1) % (n * n) + 1;
    int x = coordinates[now][0], y = coordinates[now][1];
    score += recSum(n, preSum, 1, y - j + 1, n, y + j - 1) + recSum(n, preSum, x - j + 1, 1, x + j - 1, n) - recSum(n, preSum, x - j + 1, y - j + 1, x + j - 1, y + j - 1);
    score %= 1e9 + 7;
    ans[i] = (int)score;
  }
  return ans;
}

//初始化棋盘,编号对应的坐标,前缀和
void init(int n, int[][] chessboard, int[][] coordinates, long[][] preSum){
  int[] fx = new int[]{0,1,0,-1};
  int[] fy = new int[]{1,0,-1,0};
  int x = 1, y = 1, opt = 0;
  for(int i = 1; i <= n * n; i++){
    chessboard[x][y] = i;
    coordinates[i] = new int[]{x, y};
    int x1 = x + fx[opt], y1 = y + fy[opt];
    if(x1 < 1 || x1 > n || y1 < 1 || y1 > n || chessboard[x1][y1] != 0) opt = (opt + 1) % 4;
    x = x + fx[opt]; 
    y = y + fy[opt];
  }
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + chessboard[i][j];
}

long recSum(int n, long[][] preSum, int x1, int y1, int x2, int y2) {
  if(x1 < 1) x1 = 1;
  if(y1 < 1) y1 = 1;
  if(x2 > n) x2 = n;
  if(y2 > n) y2 = n;
  return preSum[x2][y2] - preSum[x1 - 1][y2] - preSum[x2][y1 - 1] + preSum[x1 - 1][y1 - 1]; 
}

写在最后

大家好,我是往西汪,一位坚持原创的新人博主。
如果本文对你有帮助,请动动小手指点个赞?。你的支持是我创作路上的最大动力。谢谢大家!
也欢迎来微信公众号【往西汪】找我玩耍~以后会陆续在公众号里更新学习路线、基础知识和技术文章。

查看原文

赞 0 收藏 0 评论 0

往西汪 发布了文章 · 2020-07-23

算法题解 - 牛客编程巅峰赛S1第4场 - 黄金&钻石组

A. 牛牛分蛋糕

题目描述

牛牛今天家里要来客人,所以牛牛今天特意做了他最拿手的两种蛋糕,但是他是一个有洁癖的人,所以他在分蛋糕时,有如下几个原则:

  1. 他不希望一个盘子里出现两种蛋糕
  2. 他希望每个盘子中都有蛋糕
  3. 他想让装有最少蛋糕数量的盘子中装有的蛋糕数量尽可能多

备注:

n, a, b(1 ≤ a, b ≤ 10^5, 2 ≤ n ≤ a + b)
第一个参数代表盘子的数量
第二个参数代表第一种蛋糕的数量
第三个参数代表第二种蛋糕的数量。
程序应返回:在所有分法中,蛋糕数量最少的盘子中分到最多的蛋糕数量。

示例1

输入

5, 2, 3

输出

1

说明

只有一种方法把蛋糕分配到盘子里,即所有的盘子上都有一个蛋糕。

示例2

输入

4, 7, 10

输出

3

说明

第一个盘子中装有第一种蛋糕三个,第二个盘子中装有第一种蛋糕四个,第三个、第四个盘子中各装有第二种蛋糕五个。

解法一:暴力搜盘子

思路分析

要想装最少蛋糕数量的盘子中装的蛋糕最多,必定是均匀分配蛋糕。因此可以搜索所有的盘子分配方案,看哪种情况下均匀分配到的蛋糕最多。

时间复杂度:$O(n)$。总共有 $n - 1$ 种盘子分配方案。

空间复杂度:$O(1)$。

代码实现

public int solve (int n, int a, int b) {
  int res = 0;
  for(int i = 1; i < n; i++) {
    int min = Math.min(a / i, b / (n - i));
    res = Math.max(res, min);
  }
  return res;
}

解法二:二分搜蛋糕

思路分析

每个盘子都分配 $c$ 块蛋糕,若 $a / c + b / c \ge n$ 说明这样分配能使 $n$ 个盘子中都有蛋糕。二分搜索寻找最大的 $c$ 即可。

时间复杂度:$O(log(min(a,b)))$。

空间复杂度:$O(1)$

代码实现

public int solve (int n, int a, int b) {
  int l = 1, r = Math.min(a, b);
  while(l < r){
    int mid = (l + r + 1) >> 1;
    if(a / mid + b / mid < n) r = mid - 1;
    else l = mid;
  }
  return l;
}

B. 牛牛凑数字

题目描述

牛牛今天逛商店,看到商店里摆着一些很漂亮的数字,牛牛非常喜欢,想买一些数字带回家。

数字一共有九种类型,分别是 1 - 9 这九个数字,每个数字的价钱都不一样,而且每个数字的货源都非常充足。

牛牛是个完美主义者,他希望用自己的能够承受的价格,从这些数字里面购买,并且凑到最大的数字带回家。

备注:

第一个参数为一个整数 n(0 ≤ n ≤ 10^6),代表牛牛所能承受的价格。
第二个参数为 1 - 9 这九个数字的价格数组,a1, a2, ……, a9(1 ≤ ai ≤ 10^5)。
程序应返回:一个数字,代表牛牛能凑到的最大的数字。当然,如果牛牛一个数字都买不起,返回 "-1" 即可。
注意,由于数字可能会很大,所以程序中需要处理成 string 类型进行返回。

示例1

输入

5,[5,4,3,2,1,2,3,4,5]

输出

"55555"

说明

第 5 个数字只需要花费 1,所以买 5 个第 5 个数字可以凑到最大值 55555。

示例2

输入

2,[9,11,1,12,5,8,9,10,6]

输出

"33"

说明

购买 2 个第 3 个数字,可以凑到最大值为 33。

解法:贪心

思路分析

要想数字最大,首先得数字的数量最多。其次,在相同数量的数字时,应尽可能买最大的数字。

如果每一个都买花费最少的数字 $a$,那么数字的数量 $cnt$ 必定是最多的。

找到这个最多的数量后,从大到小搜寻数字,若不减少数量的情况下能买到更大的数字,则用它替换掉 $a$。

时间复杂度:$O(\frac n {min(a_i)})$。最多买 $\frac n {min(a_i)}$ 个数字,因此最多搜寻这么多次。

空间复杂度:$O(1)$。

代码实现

public String solve (int n, int[] a) {
  StringBuilder res = new StringBuilder();
  int min = Integer.MAX_VALUE;
  int minNum = 0;
  for(int i = 0; i < 9; i++ ) {
    if(a[i] <= min) {
      min = a[i];
      minNum = i + 1;
    }
  }
  if(n < min) return "-1";
  boolean incre = true;
  while(incre && n > min) {
    incre = false;
    for(int i = 8; i >= minNum; i--) {
      if(n >= a[i] && ((n - a[i]) / min == n / min - 1)) {
        res.append(i + 1);
        n -= a[i];
        incre = true;
        break;
      }
    }
  }
  for(int i = 1; i <= n / min; i++) res.append(minNum);
  return res.toString();
}

另一种写法(时间复杂度没变,只是降低了代码量)

public String solve (int n, int[] a) {
  StringBuilder res = new StringBuilder();
  int minCost = Integer.MAX_VALUE;
  for(int i = 0; i < 9; i++ ) minCost = Math.min(minCost, a[i]);
  if(n < minCost) return "-1";
  int cnt = n / minCost;
  for(int i = 8; i >= 0 && res.length() < cnt; i--){
    while(n - a[i] >= minCost * (cnt - res.length() -1)){
      res.append(i + 1);
      n -= a[i];
      if(res.length() == cnt) break;
    }
  }
  return res.toString();
}

C. 牛妹的野菜

题目描述

书接上回,牛妹组织春游,有一个有趣的项目是挖番薯。聪明的牛妹拿到了一个标明了番薯洞的地图,每个番薯洞中有一定数量的番薯。同时,我们知道番薯洞的连接路径,并规定路径是单向且小序号指向大序号,也无环。可以从任意一处开始挖,然后沿着连接往下挖(仅能选择一条路径),当无连接时,结束。

设计一种挖番薯的方案,使得可以挖到更多的番薯。

输出路径。

备注:

总番薯数量不超过1000000,番薯洞数量不超过250.

示例1

输入

[5,10,20,5,4,5],[[1,2],[1,4],[2,4],[3,4],[4,5],[4,6],[5,6]]

输出

"3-4-5-6"

说明

很明显 先去第三点拿20个番薯,再去第四个点拿5个,再去第五个点拿4个,再去第六个点拿5个。这个方案最优

解法: 回溯

思路分析

(内心 os: 作为成年人,所有番薯我全要。一条路径上的番薯只够牛妹一个人吃!)

当我们处于洞口 $a$ 时,如果我们知道了每一个洞口 $b (b \in next(a))$ 的最优方案,那么可以直接比较集合 $next(a)$ 的各个方案,选择其中最优的作为下一个洞口。

依照这个思路,我们只要从路径的底部往头搜寻,就可以一次遍历得到所有洞口的最优方案。那么如何找到路径的底部呢?答案就是利用回溯。从入口递归的往下搜寻洞口,然后回溯中返回下一个洞口的最优方案。

时间复杂度:$O(n)$。每个洞口最多搜寻一次

空间复杂度:$O(n^2)$。对于 $n$ 个洞口,需要记录它们的下一个洞口。

代码实现

List<Integer>[] next; // 从 i 出发的下一个洞口
String[] path; // 从 i 出发的最优方案路径
int[] potatoMaxNum; //从 i 出发可以挖到番薯的最大数量
int[] potatoNum;
public String digSum (int[] potatoNum, int[][] connectRoad) {
  int n = potatoNum.length;
  next = new List[n + 1];
  path = new String[n + 1];
  potatoMaxNum = new int[n + 1];
  this.potatoNum = potatoNum;
  for(int i = 1; i <= n; i++) next[i] = new ArrayList<Integer>(250);
  for(int[] path: connectRoad){
    next[path[0]].add(path[1]);
  }
  String res = "";
  int maxNum = 0;
  for(int i = 1; i <= n; i++) {//遍历 n 个洞口,看看哪个洞口出发得到的番薯最多
    dfs(i);
    if(potatoMaxNum[i] > maxNum) {
      maxNum = potatoMaxNum[i];
      res = path[i];
    }
  }
  return res;
}

public int dfs(int d){//返回洞口 d 出发得到的最大番薯数量
  if(potatoMaxNum[d] != 0) return potatoMaxNum[d];
  if(next[d].isEmpty()) {//最后一个洞口了
    path[d] = "" + d;
    return potatoMaxNum[d] = potatoNum[d - 1];
  }
  int maxd = d;
  for(Integer nextd: next[d]) {//看看下一步去哪个洞口得到的番薯最多
    int num = dfs(nextd);
    if(num > potatoMaxNum[maxd]) maxd = nextd;
  }
  potatoMaxNum[d] = potatoNum[d - 1] + potatoMaxNum[maxd];
  path[d] = d + "-" + path[maxd];
  return potatoMaxNum[d];
}

写在最后

大家好,我是往西汪,一位坚持原创的新人博主。
如果本文对你有帮助,请动动你的小手指点个赞👍。你的支持是我创作路上的最大动力。谢谢大家!
也欢迎来公众号【往西汪】找我玩耍~

查看原文

赞 0 收藏 0 评论 0

往西汪 发布了文章 · 2020-07-23

算法题解 - 牛客编程巅峰赛S1第3场 - 黄金&钻石组

A. 找卧底

题目描述

牛牛今天和大家玩了一个新游戏,除了牛牛以外还有 n 个人参加游戏,现在这 n 个人中的每个人从 [1, n] 中选择一个数字,保证选出的数字均不重复。牛牛作为第 n + 1 个人,充当卧底的角色,要求卧底从 1 到 n 中选择一个数字,现在将 n + 1 个数字重新打乱顺序,请找出卧底选择的数字是多少。

备注:

其中1 <= n <= 100000。
要求时间复杂度为 O(n),额外空间复杂度为 O(1)。

示例1

输入

4,[1,2,1,4,3]

输出

1

解法一:原地哈希

思路分析

这种找重复数字的题目还挺常见的。最直接的方法是用哈希表存储数字,遇到新数字判断它是否在哈希表里,若在就说明重复。

不过题目要求空间复杂度为 $O(1)$。那么就不能用内置哈希表了。

注意到数字范围是 [1, n],并且数组长度为 n + 1,因此我们可以把原数组当成哈希表,通过交换,将数字放到对应下标的位置即可。

例如:遇到了数字10,那么我们就去看看下标为 10 的数字是不是 10,是的话说明数字重复了,否则交换这两个数字。

代码实现

public int search (int n, int[] a) {
  while(a[0] != a[a[0]]){
    int temp = a[0];
    a[0] = a[a[0]];
    a[temp] = temp;
  }
  return a[0];
}

解法二:求和相减

思路分析

记卧底选的数字是 b,那么 $\sum_{i \in [0,n]} a[i] = \sum_{x \in [1,n]} x + b$。显然求出两个求和的结果,相减即可得到答案。

代码实现

public int search (int n, int[] a) {
  int sum = 0;
  for(int i = 0; i <= n; i++) sum += a[i];
  for(int i = 1; i <= n; i++) sum -= i;
  return sum;
}

解法三:位运算

思路分析

剑指 offer 里有一道很经典的题:给一个数组,只有一个数字仅出现一次,其他数字都出现了两次,问如何找到这个数字。

那题是利用了异或运算得到答案的。并且我们知道异或的结果与奇偶次有关,并不局限于一次两次的限定。

这题是只有一个数字出现了两次,其他数字都仅出现一次。如何与那题关联起来呢?

很简单,就让 1 ~ n 再出现一次,这样只有一个数字出现了三次,其他数字都出现了两次。这样就可以用异或来解决啦。

代码实现

public int search (int n, int[] a) {
  int x = 0;
  for(int i = 1; i <= n; i++) x ^= i;
  for(int i = 0; i <= n; i++) x ^= a[i];
  return x;
}

B. 父子情深

题目描述

在一颗有 n 个结点且以 1 为根节点树上,起初每个结点的初始权值为 0 。

现在有 q 次操作,每次操作选择将以 $r_i$ 为根节点的子树上的所有结点权值增加 $x_i$ 。

求 q 次操作后从 1 到 n 每个结点的权值。

输入

第一个参数为 n,1 ≤ n ≤ 100,000

第二个参数为边 $(u_i, v_i)$ 的集合,其中 $(u_i, v_i)$ 表示结点 $u_i$ 与结点 $v_i$ 之间有一条边,$1 ≤ u_i, v_i ≤ n$

第三个参数为 q,1 ≤ q ≤ 100,000

第四个参数为 q 次询问的 $(r_i,v_i)$ 的集合,$1≤r_i≤n,0≤∣v_i∣≤1000,000$

返回

从 1 到 n 每个结点的权值。

示例1

输入

5,[(2,5),(5,3),(5,4),(5,1)],2,[(1, 3), (2, -1)]

输出

[3,2,3,3,3]

说明

第一次操作,将以 1 为根节点的子树上的所有结点权值增加 3,此时结点的权值分别为 [3, 3, 3, 3, 3] ;
第二次操作,将以 2 为根节点的子树上的所有结点权值增加 -1,此时结点的权值分别为 [3, 2, 3, 3, 3] ;

解法:BFS

思路分析

本题难点在于:

  1. 输入中给的边是无向边,如何简便的分辨出父节点与子节点
  2. 如何在线性复杂度内计算出所有节点的权值

对于第一点,由于是树结构,遍历的时候肯定是从根节点往子节点遍历,因此可以用布尔数组 visited 记录访问过的节点,用列表数组 next记录节点 i 的相邻节点。若 next[i] 中的某节点 node 已访问,说明 nodei 的父节点。

对于第二点,用数组 ans 保存每个节点的权值:

  1. 先遍历一次询问集合 Query, 并仅记录子树根节点 $r_i$ 的权值,不对其子树进行操作。
  2. 我们发现,节点 $r_i$ 的最终权值 $ans[r_i] = ans[r_i] + ans[fa(i)]$。$fa(i)$ 是 节点 $r_i$ 的父节点。因此可以通过一次遍历完成权值的计算。

用 Java 的小伙伴们注意,树的遍历通常用 BFS 或 DFS。但是这里的节点是十万个,如果最坏情况下树退化成了单链表,使用 DFS 意味着需要十万个栈空间,显然会栈溢出。因此我们使用 BFS 来进行遍历。

时间复杂度:$O(n)$

空间复杂度:$O(n)$

代码实现

public long[] solve (int n, Point[] Edge, int q, Point[] Query) {
  long[] ans = new long[n];
  List<Integer>[] next = new List[n];
  boolean[] visited = new boolean[n];
  for(int i = 0; i < n; i++) next[i] = new LinkedList<Integer>();
  for(Point p: Edge){
    next[p.x - 1].add(p.y - 1);
    next[p.y - 1].add(p.x - 1);
  }
  for(Point p: Query) ans[p.x - 1] += p.y;
  Queue<Integer> queue = new LinkedList();
  queue.offer(0);
  while(!queue.isEmpty()){
    int root = queue.poll();
    visited[root] = true;
    for(Integer node: next[root]){
      if(visited[node]) continue;
      ans[node] += ans[root];
      queue.offer(node);
    }
  }
  return ans;
}

C. 旋转跳跃

题目描述

牛牛有一个长为 n 的排列 p ,与 m 对 $(x_i,y_i)$.

每对 $(x_i,y_i)$ 表示可以将 $p_{x_i}$ 的值与 $p_{y_i}$ 的值互换。

m 对 $(x_i,y_i)$ 的使用顺序与次数不限。

牛牛想知道,任意次操作之后他能得到的字典序最小的排列是什么

字典序定义:对于数字 1、2、3......n 的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354 和 12345,排列 12345 在前,排列 12354 在后。按照这样的规定,5 个数字的所有的排列中最前面的是 12345,最后面的是 54321。(来自百度百科)

输入

第一个参数为 n,1 ≤ n ≤ 100,000

第二个参数为 m,1 ≤ m ≤ 100,000

第三个参数为初始排列 p,$1 ≤p_i≤n$

第四个参数为 m 对 $(x_i,y_i)$, $1≤x_i,y_i≤n,x_i≠y_i$

返回

字典序最小的排列

示例1

输入

5,3,[5,2,3,4,1],[(2,4),(1,4),(3,4)]

输出

[2,3,4,5,1]

说明

1. 交换 (3, 4), 交换后的序列为: 5, 2, 4, 3, 1
2. 交换 (2, 4), 交换后的序列为: 5, 3, 4, 2, 1
3. 交换 (1, 4), 交换后的序列为: 2, 3, 4, 5, 1

解法:并查集

思路分析

把下标看作图中的节点, $(x_i,y_i)$ 表示节点 $p_{x_i}$ 和 $p_{y_i}$ 直接相连。由于 m 对 $(x_i,y_i)$ 的使用顺序与次数不限,因此同一连通分量中的节点可以任意排列。

例如:对原排列 a, b, c, 给定 (a, b), (b, c) ,我可以排列成 b, a, c(仅用到 (a, b)),也可以排列成 a, c, b(仅用到 (b, c))。

显然使用并查集可以方便的得到所有的连通分量。之后对每一个连通分量内部进行排序,小的值放在小的下标上。

时间复杂度:$O(nlogn)$.

空间复杂度:$O(n)$.

代码实现

class Solution {
    public int[] solve (int n, int m, int[] perm, Point[] Pair) {
        int[] ans = new int[n];
        Union un = new Union(n);
        for(Point p: Pair) un.union(p.x - 1, p.y - 1);
        Map<Integer, Queue<Integer>> valueMap = new HashMap();
        for(int i = 0; i < n; i++){
            int fa = un.find(i);
            if(!valueMap.containsKey(fa)) valueMap.put(fa, new PriorityQueue());
            valueMap.get(fa).add(perm[i]);
        }
        for(int i = 0; i < n; i++){
            Queue<Integer> valueSet = valueMap.get(un.find(i));
            ans[i] = valueSet.poll();
        }
        return ans;
    }
}

class Union{
    private int[] parent;
    
    public Union(int size){
        parent = new int[size];
        for(int i = 0; i < size; i++) parent[i] = i;
    }
    
    public int find(int x){
        if(x != parent[x]) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    public void union(int x, int y){
        parent[find(x)] = find(y);
    }
}

写在最后

大家好,我是往西汪,一位坚持原创的新人博主。
如果本文对你有帮助,请动动小手指点个赞👍。你的支持是我创作路上的最大动力。谢谢大家!
也欢迎来公众号【往西汪】找我玩耍~

查看原文

赞 0 收藏 0 评论 0

往西汪 发布了文章 · 2020-07-23

算法题解 - 牛客编程巅峰赛S1第3场 - 青铜&白银组

A. 位数求和

题目描述

牛牛想知道所有的长度为 n 的数中,各个位上的数字之和为 m 的这些数的和是多少呢。给定 n 和 m,求这些数的和。

备注:

1 ≤ n ≤ 6,1 ≤ m ≤ 9 ∗ n

示例1

输入

2, 3

输出

63

说明

12 + 21 + 30 = 63

解法一:暴力枚举

思路分析

由于范围很小,所以可以暴力枚举每一个长度为 n 的数,看其是否符合条件。

时间复杂度:$O(10^n)$。总共枚举 $10^n - 10^{n-1}$ 个数字。

空间复杂度:$O(1)$。

代码实现

public long sum (int n, int m) {
  long res = 0;
  int max = (int)Math.pow(10, n);
  for(int i = (int)Math.pow(10, n - 1); i < max; i++){
    int j = i, sum = 0;
    while(j > 0) {sum += j % 10; j /= 10;}
    if(sum == m) res += i;
  }
  return res;
}

解法二:DFS

思路分析

从前到后依次枚举每一位上的数字,到第 $n$ 位时停止,若此时的数满足条件,则计入总和中。

可以加入剪枝操作,记前面的位上数字之和为 a,若 $a + b = m (b \in [1,9])$ 则只需枚举 $[1, b]$ 即可。

时间复杂度:$O(10^n)$。递归 $n$ 层,每层循环 10 次。但加入了剪枝策略,因此时间开销比解法一要小一些。

空间复杂度:$O(n)$。需要递归 $n$ 层。

代码实现

long res = 0;

public long sum(int n, int m) {
  for (int i = 1; i <= 9 && i <= m; i++) dfs(n - 1, m - i, i);
  return res;
}

public void dfs(int n, int m, int num) {
  if(n == 0 && m == 0) res += num;
  if(n == 0) return;
  for (int i = 0; i <= 9 && i <= m; i++) dfs(n - 1, m - i, num * 10 + i);
}

B. 不可思议

题目描述

给定一颗节点编号为 1 ~ n​ 的,且以 1 为根的树,给出 n 组询问,每次询问给定一个数对 (x, y),求 i 为 x 到根路径上的点(包括 x 和根) $∑_i(y+2i)xor(y+i)$.

对于这 n 组询问的答案,不需要依次输出 n 个数,你只需要输出他们的和对 998244353 的取模即可。

树的信息以及询问不会直接给出,输入数据只包含随机种子,具体生成方式请仔细阅读备注内容。

备注:

输入数据包含5个整数,n,seed1,seed2,seed3,x.
树的信息生成伪代码如下
//////////////////////1/////////////////////
定义边集数组u[],v[]     //u[i],v[i]表示第i条边的两个端点
定义变量seed4
定义循环变量i从1到n-1
循环体开始
        seed4=(seed1+seed2)%998244353*seed3%998244353;

        u[i]=i+1;

        v[i]=(seed4%i)+1;

        seed3=seed2;
        seed2=seed1;
        seed1=seed4;
循环体结束

//////////////////////1/////////////////////

询问信息生成伪代码如下,顺带一提,第一次询问的x会在输入中给出
//////////////////////2/////////////////////
定义变量lastans,初始值为0           
定义变量ret,初始值为0
定义变量y,初始值为0          //含义见题干
定义函数ans(x,y),返回值为对数对(x,y)这组询问的答案         //这里“询问”的含义见题干
定义变量z
定义循环变量i从1到n
循环体开始
        z=ans(x,y); 
        ret=(ret+z)%998244353;
        lastans=z;
        x=((x+lastans)^ret)%n+1;
        y=lastans;
循环体结束
//////////////////////2/////////////////////

输出一个整数,表示答案。
n<=10^5,seed1,seed2,seed3<=10^9,x<=n
保证构造出的数据合法。

示例1

输入

3,1,1,1,1

输出

7

示例2

输入

4,2,2,3,1

输出

119

解法:直观解法

思路分析

这题和它的名字一样,题目是 "不可思议" 的长,乍看会以为很难。看完题目后发现,只需要实现函数 ans 即可,“不可思议”的简单……

就是从 x 不断的往上找父亲节点 i 直到根节点,返回路径上 $(y+2*i) xor (y+i)$ 的总和。

可以用数学归纳法证明 $u[i]$ 的父节点是 $v[i]$。这个证明比较简单,就不多赘述了。

时间复杂度:$O(n*k)$。$k$ 是树的深度,总共 $n$ 组询问,每次询问最多循环计算 $k$ 次。

空间复杂度:$O(n)$。需要存储 $n - 1$ 个节点的父节点。

代码实现

int[] p; // p[i] 是 i 的父节点

public long work(int n, long seed1, long seed2, long seed3, int x) {
  // 生成树
  p = new int[n + 1];
  for (int i = 1; i < n; i++) {
    long seed4 = (seed1 + seed2) % 998244353 * seed3 % 998244353;
    p[i + 1] = (int) (seed4 % i) + 1;
    seed3 = seed2;
    seed2 = seed1;
    seed1 = seed4;
  }
  // 询问信息生成
  long lastans = 0, ret = 0, y = 0;
  for (int i = 1; i <= n; i++) {
    long z = ans(x, y);
    ret = (ret + z) % 998244353;
    lastans = z;
    x = (int) ((x + lastans) ^ ret) % n + 1;
    y = lastans;
  }
  return ret;
}

public long ans(int x, long y) {
  long ans = 0;
  while (x != 1) {
    ans += (y + 2 * x) ^ (y + x);
    x = p[x];
  }
  ans += (y + 2) ^ (y + 1);
  return ans;
}

C. 牛牛晾衣服

题目描述

牛牛有 n 件带水的衣服,干燥衣服有两种方式。

一、是用烘干机,可以每分钟烤干衣服的 k 滴水。

二、是自然烘干,每分钟衣服会自然烘干 1 滴水。

烘干机比较小,每次只能放进一件衣服。

注意,使用烘干机的时候,其他衣服仍然可以保持自然烘干状态,现在牛牛想知道最少要多少时间可以把衣服全烘干。

备注:

第一个参数n(1 ≤ n ≤ 105),代表一共有多少件衣服。
第二个参数为n个数(1 ≤ an ≤ 109)组成的数组,代表n件衣服分别有多少水滴水。
第三个参数k(1 ≤ k ≤ 109),代表烘干机每分钟能烘干k滴水。
程序应返回:一个整数,代表使n件衣服全部干燥所需要的最少的时间。

示例1

输入

3,[2,3,9],5

输出

3

说明

前两分钟对第三件衣服进行烘干机烘干,使得衣服的水份分别为0,1,0,所以最快三分钟可以烘干。

解法:二分法

思路分析

先不考虑怎么用程序实现,如果让你自己算最少烘干时间,你会怎么算?

是不是对直接算烘干时间毫无头绪?那如果给你个时间 t,让你判断 t 分钟后衣服是否全部烘干。这个问题是不是就简单很多了?

因此我们可以暴力遍历每一个时刻,看是否能烘干,最小的时刻就是题目要求的答案了。

但是暴力匹配耗时太多了啊,怎么办呢?

我们发现这是在线性连续区域内进行遍历的,显然使用二分法可以大大降低时间复杂度。

时间复杂度:$O(nlogn)$。二分搜索的复杂度是 $O(logn)$, 每次搜索时判断能否全部烘干需要 $O(n)$。

空间复杂度:$O(1)$。

代码实现

public int solve (int n, int[] a, int k) {
  Arrays.sort(a);
  int l = a[0], r= a[a.length - 1];
  while(l < r){
    int mid = (l + r) >> 1;
    if(check(mid, k, a)) r = mid;
    else l = mid + 1;
  }
  return r;
}

public boolean check(int t, int k, int[] a){
  int cnt = 0; //记录烘干机用时
  for(int i = a.length - 1; i >= 0 && cnt <= t; i--){
    if(a[i] <= t) break;
    cnt += (a[i] - t) / (k - 1);
    if(((a[i] - t) % (k - 1)) != 0) cnt++;
  }
  return cnt <= t;
}

写在最后

大家好,我是往西汪,一位坚持原创的新人博主。
如果本文对你有帮助,请动动小手指点个赞?。你的支持是我创作路上的最大动力。谢谢大家!
也欢迎来公众号【往西汪】找我玩耍~

查看原文

赞 0 收藏 0 评论 0

往西汪 发布了文章 · 2020-07-19

算法题解 - 牛客编程巅峰赛S1第2场 - 黄金&钻石组

A. 牛牛的 Fib 序列

题目描述

牛牛重新定义了斐波那契数列,牛牛定义 $f(n) = f(n-1) + f(n+1), f(1) = a, f(2) = b$,现在给定初始值 $a, b$,现在求第 $n$ 项 $f(n) \mod 1000000007$ 的值。

其中 $1 \le |a|, |b|, n \le 10^9$

输入

a,b,n

输出

f(n) % 1000000007

备注:

最终的答案应是一个非负整数,如 -1 % 1000000007 = 1000000006

示例1

输入

1, 2, 3

输出

1

说明

f(2) = f(3) + f(1), 所以 f(3) = f(2) - f(1) = 2 - 1 = 1

示例2

输入

-1, -2, 3

输出

1000000006

说明

同例1:f(3)= -1 % 1000000007 = 1000000006

解法

思路分析

手写一下前几个数,就会发现这个数列 6 个数一循环。

时间复杂度:O(1)

空间复杂度:O(1)

代码实现

public int solve (int a, int b, int n) {
  final int mod = 1000000007;
  int[] fib = new int[]{a, b, (b - a) % mod, -a, -b, (a - b) % mod};
  return (fib[(n - 1) % 6] + mod) % mod ;
}

B. 破译密码

题目描述

题面:

​ 牛牛收到了一个任务,任务要求牛牛破译一个密码。牛牛将被给予两个字符串 s1 和 s2,均由四个小写字母构成。需要破译的密码为从s1 变换到 s2 最少需要的变换次数。

​ 变换的方式是这样:每次变换可以选择当前字符串中的一个位置,然后剩下的三个位置的字符从左到右分别加上 2,3,5,若是超出 'z',则重新从 'a' 开始,例如:对于字符串 "abcd",我们选择 'c' 的位置进行变换,则变换之后的字符串为 "ceci"; 对于字符串 "qyzr", 我们选择 'r' 位置进行变换,则变换之后的字符串为 "sber"。

输入

s1, s2

输出

s1 变换到 s2 最少需要的变换次数

备注:

s1, s2 均由四个小写字母组成

示例1

输入

"aaaa", "ccgk"

输出

2

说明

第一次变换选择第一个'a',变成 "acdf",第二次变换选择第二个 'c',变成 "ccgk",故答案为2

解法一:BFS

思路分析

在之前的文章中,【魔法数字】一题也用到了 BFS。本题和那题的思路一致。穷举所有变换的可能性,通过备忘录剪枝来减少搜索空间。

对每一个字符串都有四种变换情况,即选择第 $i$ 位 $(0 \le i \le 3)$ 进行变换。

这里可以自行画一下四叉树,更能直观的体会这种方法的流程。(才不是因为我懒得画图,【逃】)

第一次变换到 s2 的那一层 j,即为最少变换次数。(根节点 s1 所在层为 0)

时间复杂度:$O(log_426^4)$. 最坏情况下把所有字符串 ($26^4$ 个) 都搜索了一遍。

空间复杂度:$O(26^4)$. 额外空间主要是备忘录和队列的空间开销,最坏情况下把所有字符串都存进去了。

代码实现

int[] add = new int[] {2,3,5};
public int solve(String s1, String s2) {
    Set<String> visited = new HashSet();
    Queue<String> q = new LinkedList();
    q.offer(s1);
    int res = 0;
    while(!q.isEmpty()) {
        int size = q.size();
        while(size-- > 0) {
            String cur = q.poll();
            if(cur.equals(s2)) return res;
            if(visited.contains(cur)) continue;
            visited.add(cur);
            for(int i = 0; i < 4; i++) q.offer(convert(cur,i));
        }
        res++;
    }
    return res;
}

public String convert(String s, int i) {
    char[] str = s.toCharArray();
    int index = 0;
    for(int j = 0; j < 4; j++) {
        if(j == i) continue;
        str[j] = (char)('a' + (str[j] - 'a' + add[index]) % 26);
        index++;
    }
    return String.valueOf(str);
}

解法二:数学方法

思路分析

因为 s1 到 s2 的距离为固定值,因此可以用数组 dis[4] 记录四位字符分别的距离。

记 a, b, c, d 分别为选择第 i (0 <= i <= 3) 位字符的次数。以下四个公式成立,即可说明这种情况下可以从 s1 变换到 s2:

$2 * (b + c + d) \mod 26 = dis[0]$

$(2 * a + 3* (c + d)) \mod 26 = dis[1]$

$(3 * (a + b) + 5 * d) \mod 26 = dis[2]$

$5 * (a + b + c) \mod 26 = dis[3]$

所需变换次数为 $cnt = a + b + c + d$,取其中结果最小的即可。

代码实现

public int solve (String s1, String s2) {
  int[] dis = new int[4];
  for(int i = 0; i < 4; i++) dis[i] = (s2.charAt(i) - s1.charAt(i) + 26) % 26;
  int res = 26 * 4;
  for(int a = 0; a < 26; a++)
    for(int b = 0; b < 26; b++)
      for(int c = 0; c < 26; c++)
        for(int d = 0; d < 26; d++)
          if(dis[0] == 2 * (b + c + d) % 26 && dis[1] == (2 * a + 3* (c + d)) % 26 && dis[2] == (3 * (a + b) + 5 * d) % 26 && dis[3] == 5 * (a + b + c) % 26)
            res = Math.min(res, a + b + c + d);
  return res;
}

C. 卡牌问题

问题描述

有 $n * m$ 张牌叠在一起,称之为旧牌库。

牌由旧牌库底部的第一张从 1 开始编号,旧牌库顶的牌编号就是 $n*m$.

每张牌上有一个数字,设编号为 $i$ 的牌上的数字为 $a[i]$, 保证满足 $a[i] = ((i - 1 ) \mod m) + 1$。

现给出 $a$ 和 $b$,进行两个操作:

1、每次将旧牌库最底下的一张牌拿出来,放到旧牌库顶,重复 $a$ 次。

2、建一个新牌库,初始新牌库没有卡牌,每次先将旧牌库最底下的牌拿出来,放在新牌库顶,再将旧牌库最顶上的牌拿出来,放到新牌库顶,重复 $b$ 次,保证 $2*b \le n*m$,最后将旧牌库所有剩余卡牌直接放到新牌库顶。

再给出数字 $x$ 和 $y$,求新牌库从牌库底起第 $x$ 张牌到第 $y$ 张牌上的数字之和。

这个答案可能很大,输出答案对 998244353 取模后的结果。

备注:

输入包含 6 个整数 n, m, a, b, x, y,且保证数据一定合法可行。
输出一行,一个整数。
n <= 1e9; m <= 1e5; a <= n * m; b * 2 <= n * m; x <= y <= n * m

示例1

输入

4, 5, 17, 6, 3, 14

输出

39

示例2

输入

2, 3, 4, 1, 2, 5

输出

7

解法:前缀和

思路分析

乍看本题的小伙伴可能一头雾水,待本汪花 3 分钟细细讲解之后,小学生也能做出来!

咱们先分析新牌堆是什么样的,知道它长啥样,之后的计算思路就一目了然了。

依题意,原牌堆自底向上看牌上数字是这样一个序列:$(1, 2, …, m)^n$。

经过操作 1 之后,变成了牌堆 A ,序列为:$s_1, s_1 + 1, …, m, (1, 2, …, m)^{n-1}, 1, 2, …, s_1-1$。其中 $s_1 = a \mod m + 1$。

对牌堆 A 进行操作 2 之后,得到新牌堆。新牌堆可分成两个序列:$B_1,B_2$。

首先看 $B_1$,它包含了 $2b$ 张牌,并且奇数牌和偶数牌的规律如下:

  1. 奇数牌:自底向上的第 $2k - 1$ 张牌,对应牌堆 A 自底向上的第 $k$ 张牌。
  2. 偶数牌:自底向上的第 $2k$ 张牌,对应牌堆 A 自顶向下的第 $k$ 张牌。

$B_2$ 就很简单了,序列为:$s_2, s_2 + 1, …, m, 1, 2, …, m, 1, 2, …$。其中 $s_2 = (s_1 - 1 + b) \mod m + 1$。

现在知道新牌堆长什么样了,很显然 $B_2$ 的部分和是很好计算的。

$B_1$ 相当于牌堆 A 前向和后向各数了 b 张牌。因此用前缀和+ 后缀和便可以计算出 $B_1$ 的部分和。

到这里,熟悉 前缀和 的小伙伴就可以自己动手写代码体验 AC 的快感了。不熟悉 前缀和 的小伙伴也别担心,贴心的往西汪只用 1 分钟就能给你讲的明明白白。

给定参数 $st, l$ ,分别代表序列的初始数字,和序列的长度。

  1. 前缀和,计算序列 $st, st + 1, …, m, 1, 2, …, m, 1, 2, …$ 的和。
  2. 后缀和,计算序列 $st, st − 1, …, 1, m, m−1, …, 1, m, m−1, …$ 的和。

针对序列 $B_1$,记 $sum(x)$ 表示区间 $[1, x]$ 的牌的数字和,$sum(x) = 前缀和(st = s_1, l = ⌈r/2⌉) + 后缀和(st = s_1 - 1, l = ⌊r/2⌋)$ 。

区间 $[x_1, x_2]$ 的和为:$sum(x_2) - sum(x_1 - 1)$。

至此本题再无难度。

代码实现

class Solution {
    long m;
    final long mod = 998244353;
    public long work (long n, long m, long a, long b, long x, long y) {
        this.m = m;
        long res = 0;
        long s1 = a % m + 1, s2 = (s1 - 1 + b) % m + 1;
        if(x <= 2 * b){
            res = modAdd(res, mod - b1Sum(s1, x - 1));
            res = modAdd(res, b1Sum(s1, Math.min(2 * b, y)));
        }
        if(y > 2 * b){
            res = modAdd(res, mod - b2Sum(s2, Math.max(2 * b, x - 1) - 2 * b));
            res = modAdd(res, b2Sum(s2, y - 2 * b));
        }
        return res;
    }
    
    public long addTo(long l, long r){//计算[l, r]的区间和
        if(r < l) return 0;
        return ((l + r) * (r - l + 1) >> 1) % mod;
    }
    
    public long modAdd(long n1, long n2){
        return (n1 + n2) < mod ? (n1 + n2) : (n1 + n2 - mod);
    }
    
    public long preSum(long st, long l){//这里的 l 表示序列长度
        if(l <= 0) return 0;
        if(l <= m - st + 1) return addTo(st, st + l - 1);
        long k = (l - (m - st + 1)) / m;
        long end = (l - (m - st + 1)) % m;
        long res = modAdd(addTo(st, m), addTo(1, end));
        return modAdd(res, (k * addTo(1, m)) % mod);
    }
    
    public long backSum(long st, long l){
        if(l <= 0) return 0;
        if(l <= st) return addTo(st - l + 1, st);
        long k = (l - st) / m;
        long end = m - ((l - st) % m) + 1;
        long res = modAdd(addTo(1, st), addTo(end, m));
        return modAdd(res, (k * addTo(1, m)) % mod);
    }
    
    public long b1Sum(long s1, long l){// l 表示序列长度
        if(l <= 0) return 0;
        long half = l >> 1;
        return modAdd(preSum(s1, l - half), backSum(s1 - 1, half));
    }
    
    public long b2Sum(long s2, long l){
        if(l <= 0) return 0;
        return preSum(s2, l);
    }
}

写在最后

大家好,我是往西汪,一位坚持原创的新人博主。
如果本文对你有帮助,请点赞、评论二连。你的支持是我创作路上的最大动力。
谢谢大家!
也欢迎来公众号【往西汪】找我玩耍~

查看原文

赞 0 收藏 0 评论 0

往西汪 发布了文章 · 2020-07-17

算法题解 - 牛客编程巅峰赛S1第2场 - 青铜&白银组

A. 牛牛扔牌

题目描述

牛牛现在有 n 张扑克牌,每张扑克牌都有点数和花色两部分组成。点数为 ‘1’ - ‘9’ 的正整数,花色为 'C', 'D', 'H', 'S' 其中的一个,分别表示梅花、方块、红桃、黑桃。现在牛牛想按一定的顺序把这n张牌扔掉。扔牌顺序的规则如下:

  1. 如果现在还剩素数张牌,则将牌顶的牌扔掉
  2. 如果现在还剩非素数张牌,则将牌底的牌扔掉

牛牛想知道他的扔牌顺序是什么,请返回扔牌顺序的字符串

备注:

对于 100% 的数据,1 ≤ n ≤ 10。

示例1

输入

"3C8D6H3D"

输出

"3D3C8D6H"

说明

开始 n = 4,为非素数,扔掉牌底的牌 3D
n = 3,为素数,扔掉牌顶的牌 3C
n = 2,为素数,扔掉牌顶的牌 8D
n = 1,为非素数,扔掉牌底的牌 6H

示例2

输入

"8S8S8S8S8S8S8S"

输出

"8S8S8S8S8S8S8S"

说明

因为全是8S,所以扔牌顺序的每一张牌也都是8S

解法

思路分析

由于 n 在 [1, 10] 上,故本题直接把所有素数列出来即可。没什么难度。

时间复杂度:O(n)

空间复杂度:O(n)

代码实现

/**
 * 
 * @param x string字符串 字符串从前到后分别是从上到下排列的n张扑克牌
 * @return string字符串
 */
public String Orderofpoker (String x) {
    int n = x.length() / 2;
    int top = 0, bot = x.length() - 2;
    String res = "";
    while(n > 0){
        if(n == 2 || n == 3 || n == 5 || n == 7){
            res += x.substring(top, top + 2);
            top += 2;
        }else{
            res += x.substring(bot, bot + 2);
            bot -= 2;
        }
        n--;
    }
    return res;
}

B. 疯狂过山车

题目描述

今天牛牛去游乐园玩过山车项目,他觉得过山车在上坡下坡的过程是非常刺激的,回到家之后就受到启发,想到了一个问题。如果把整个过山车的轨道当作是一个长度为 n 的数组 num,那么在过山车上坡时数组中的值是呈现递增趋势的,到了最高点以后,数组中的值呈现递减的趋势,牛牛把符合这样先增后减规律的数组定义为金字塔数组,请你帮牛牛在整个 num 数组中找出长度最长的金字塔数组,如果金字塔数组不存在,请输出 0。

备注:

1 <= n <= 1000000,且 num 数组中的数 0 <= num[i] <= 1000000。

示例1

输入

4,[1,2,3,1]

输出

4

示例2

输入

5,[1,5,3,3,1]

输出

3

解法一:直观解法

思路分析

在遍历的时候判断是否是金字塔数组即可。当前数字 i 和前一个数字 j 比较有三种情况:

  1. i > j,说明数组处于爬升阶段,若 j 是低谷则对长度 len 初始化为 1。len++。
  2. i = j,必定不是金字塔,初始化 len 为 1。
  3. i < j,若之前处于爬升阶段,说明是金字塔,len++,并且和金字塔最大长度 res 作比较。

时间复杂度:O(n)

空间复杂度:O(1)

代码实现

/**
 * 
 * @param n int整型 
 * @param num int整型一维数组 
 * @return int整型
 */
public int getMaxLength (int n, int[] num) {
  // write code here
  int res = 0;
  int len = 1;
  boolean up = false;
  for(int i = 1; i < n; i++) {
    if(num[i] > num[i - 1]) {
      up = true;
      if(i > 1 && num[i - 1] < num[i - 2]) len = 1;
      len++;
    }else if(num[i] == num[i - 1]) {
      len = 1;
      up = false;
    }else {
      if(up) {
        len++;
        res = Math.max(len, res);
      }
    }
  }
  return res;
}

解法二:寻找金字塔顶法

思路分析

金字塔数组长度 = 爬升阶段长度 + 1 (塔顶) + 下降阶段长度。

下降阶段相当于从右往左遍历时的爬升阶段

因此分别用 l 数组r 数组记录从左到右从右到左的爬升阶段长度。

若 l[i] 和 r[i] 都不为 0,说明 i 是塔顶。

时间复杂度:O(n)

空间复杂度:O(n)

代码实现

/**
 * 
 * @param n int整型 
 * @param num int整型一维数组 
 * @return int整型
 */
public int getMaxLength (int n, int[] num) {
  int res = 0;
  int[] l = new int[n];
  int[] r = new int[n];
  for(int i = 1; i < n; i++){
    if(num[i] > num[i - 1]) l[i] = l[i - 1] + 1;
  }
  for(int i = n - 2; i >= 0; i--){
    if(num[i] > num[i + 1]) r[i] = r[i + 1] + 1;
  }
  for(int i = 0; i < n; i++){
    if(l[i] != 0 && r[i] != 0) res = Math.max(res, l[i] + r[i] + 1);
  }
  return res;
}

C. 牛牛的棋盘

题目描述

牛牛最近在家里看到一个棋盘,有 n m 个格子,在棋盘旁边还放着 k 颗棋子,牛牛想把这 k 颗棋子全部放在 n m 的棋盘上,但是有一个限制条件:棋盘的第一行、第一列、最后一行和最后一列都必须有棋子。牛牛想知道这样的棋子放法到底有多少种,答案需要对 1e9 + 7取模。

备注:

2 <= n, m <= 30; 1 <= k <=1000

示例1

输入

2,3,1

输出

0

说明

就1颗棋子,所以无法满足条件。

示例2

输入

2,2,2

输出

2

说明

我们可以把第1颗棋子放在左上角,第2颗棋子放在右下角;也可以把第1颗棋子放在右上角,第2颗棋子放在左下角。故而有2种放法。

解法:容斥原理

思路分析

本题需要具备高中的数学知识:容斥原理和排列组合数。涉及的数学公式会在题解中给出,如果有看不明白的地方可以自行查询相关数学概念。

记行 i 上无棋子的集合为 $S_{ri}$, 列 j 上无棋子的集合为 $S_{cj}$。根据容斥原理,有

$$ \begin{aligned} res &= ∣S_{r1} ∩ S_{rn} ∩ S_{c1} ∩ S_{cm}∣ \hspace{100cm}\\ &= all - |S_{r1} ∪ S_{rn} ∪ S_{c1} ∪ S_{cm}∣\\ &= all - \sum_{C \subseteq U}(-1)^{size(C) - 1}|\cap_{e \in C} e| \end{aligned} $$

其中, $U = \{S_{r1}, S_{rn}, S_{c1}, S_{cm}\}$。

由于 $U$ 中只包含四个集合,因此可以用 4 个 bit 分别表示是否交集合 $S_i$。

总共有 $2^4 - 1 = 15$ 种交集情况,再加上 all ,共计 16 种情况。

排列组合数可以利用公式 $C_m^n = C_{m - 1}^n + C_{m - 1}^{n - 1}$ 迭代计算得出。

代码实现

final int mod = (int)1e9 + 7;
/**
 * 
 * @param n int整型 
 * @param m int整型 
 * @param k int整型 
 * @return int整型
 */
public int solve (int n, int m, int k) {
  if(k < 2) return 0;
  int[][] C = initC();
  int res = 0;
  for(int i = 0; i < 16; i++){
    int r = n, c = m, cnt = 0;
    if((i & 1) != 0) {r--; cnt++;}
    if((i & 2) != 0) {r--; cnt++;}
    if((i & 4) != 0) {c--; cnt++;}
    if((i & 8) != 0) {c--; cnt++;}
    res = (res - ((cnt & 1) * 2 - 1) * C[r * c][k]) % mod;
  }
  return (res + mod) % mod;
}

public int[][] initC(){
  int n = 1000;
  int[][] C = new int[1001][1001];
  for(int i = 1; i <= n; i++) C[i][0] = C[i][i] = 1;
  for(int i = 2; i <= n; i++){
    for(int j = 1; j < i; j++){
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
  }
  return C;
}

写在最后

大家好,我是往西汪,一位坚持原创的新人博主。
如果本文对你有帮助,请点赞、评论二连。你的支持是我创作路上的最大动力。
谢谢大家!
也欢迎来公众号【往西汪】找我玩耍~

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 17 次点赞
  • 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2020-07-17
个人主页被 1.6k 人浏览