实习面试之算法准备:数学题

目录

  • 1 技巧
  • 2 例题
    • 2.1 Nim 游戏
    • 2.2 石子游戏
    • 2.3 灯泡开关

1 技巧

稍加思考,找到规律

2 例题

2.1 Nim 游戏

你和你的朋友,两个人一起玩 Nim 游戏:
桌子上有一堆石头。
你们轮流进行自己的回合, 你作为先手 。
每一回合,轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数,来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢,返回 true;否则,返回 false 。

示例 1:
输入:n = 4
输出:false
解释:以下是可能的结果:

  1. 移除1颗石头。你的朋友移走了3块石头,包括最后一块。你的朋友赢了。
  2. 移除2个石子。你的朋友移走2块石头,包括最后一块。你的朋友赢了。
    3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
    在所有结果中,你的朋友是赢家。

示例 2:
输入:n = 1
输出:true

示例 3:
输入:n = 2
输出:true

思路以及代码:
我们解决这种问题的思路一般都是反着思考:
如果我能赢,那么最后轮到我取石子的时候必须要剩下 1~3 颗石子,这样我才能一把拿完。

如何营造这样的一个局面呢?显然,如果对手拿的时候只剩 4 颗石子,那么无论他怎么拿,总会剩下 1~3 颗石子,我就能赢。

如何逼迫对手面对 4 颗石子呢?要想办法,让我选择的时候还有 5~7 颗石子,这样的话我就有把握让对方不得不面对 4 颗石子。

如何营造 5~7 颗石子的局面呢?让对手面对 8 颗石子,无论他怎么拿,都会给我剩下 5~7 颗,我就能赢。

这样一直循环下去,我们发现只要踩到 4 的倍数,就落入了圈套,永远逃不出 4 的倍数,而且一定会输。所以这道题的解法非常简单:

class Solution {
boolean canWinNim(int n) {// 如果上来就踩到 4 的倍数,那就认输吧// 否则,可以把对方控制在 4 的倍数,必胜return n % 4 != 0;}
}

2.2 石子游戏

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子,排成一行;每堆都有 正 整数颗石子,数目为 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ,所以没有平局。
Alice 和 Bob 轮流进行,Alice 先开始 。 每回合,玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中 石子最多 的玩家 获胜 。
假设 Alice 和 Bob 都发挥出最佳水平,当 Alice 赢得比赛时返回 true ,当 Bob 赢得比赛时返回 false 。

示例 1:
输入:piles = [5,3,4,5]
输出:true
解释:
Alice 先开始,只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗,这一行就变成了 [3,4,5] 。
如果 Bob 拿走前 3 颗,那么剩下的是 [4,5],Alice 拿走后 5 颗赢得 10 分。
如果 Bob 拿走后 5 颗,那么剩下的是 [3,4],Alice 拿走后 4 颗赢得 9 分。
这表明,取前 5 颗石子对 Alice 来说是一个胜利的举动,所以返回 true 。

示例 2:
输入:piles = [3,7,2,3]
输出:true

思路以及代码:
注意,石头的堆的数量为偶数,所以你们两人拿走的堆数一定是相同的。石头的总数为奇数,也就是你们最后不可能拥有相同多的石头,一定有胜负之分。
而且注意,并不是简单的挑数字大的选
这道题又涉及到两人的博弈,也可以用动态规划算法暴力试,比较麻烦。但我们只要对规则深入思考,就会大惊失色:只要你足够聪明,你是必胜无疑的,因为你是先手。

class Solution {public boolean stoneGame(int[] piles) {return true;}
}

动态规划解法:
dp[i][j] 表示当剩下的石子堆为下标 i到下标 j时,即在下标范围 [i,j] 中,在双方都做最好选择的情况下,先手与后手的最大得分差值为多少。

那么 f[1][n]为考虑所有石子,先手与后手的得分差值:
f[1][n]>0,则先手必胜,返回 True
f[1][n]<0,则先手必败,返回 False

不失一般性的考虑 f[l][r] 如何转移,根据题意,只能从两端取石子(令 piles 下标从 1 开始),共两种情况:
1.Alice从左端取,那么取到的价值为piles[l-1],这时,Alice变为了后手,Bob为先手,从f[l-1][r]之间做决策,那么基于这种情况,双方差值为:piles[l−1]−f[l+1][r]
2.Alice从右端取,同理,双方的差值为:piles[r−1]−f[l][r−1]

好,在双方都做出最优决策的情况下,f[l][r]为上述两种情况中的最大值。
因此,我们可以的到状态转移方程为
dp[i][j]=max(piles[i]−dp[i+1][j],piles[j]−dp[i][j−1])

对于区间 dp 来说,将 i 从 n−1 往前遍历到 0,而 j从 i 位置往后遍历到 n−1,这样能够方便 i<j ,将大区间划分成小区间。从小区间开始判断,不断的扩大我们的判断范围看会不会赢

class Solution {public boolean stoneGame(int[] piles) {int n = piles.length;if (n == 0) return false;int[][] dp = new int[n][n];for (int i=0;i<n;i++) {dp[i][i] = piles[i];}for (int i=n-1;i>=0;i--) {for (int j=i+1;j<n;j++) {dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);}}return dp[0][n - 1] >= 0;}
}

2.3 灯泡开关

初始时有 n 个灯泡处于关闭状态。第一轮,你将会打开所有灯泡。接下来的第二轮,你将会每两个灯泡关闭第二个。
第三轮,你每三个灯泡就切换第三个灯泡的开关(即,打开变关闭,关闭变打开)。第 i 轮,你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮,你只需要切换最后一个灯泡的开关。
找出并返回 n 轮后有多少个亮着的灯泡。

示例1:
在这里插入图片描述
输入:n = 3
输出:1
解释:
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].
你应该返回 1,因为只有一个灯泡还亮着。

示例 2:
输入:n = 0
输出:0

示例 3:
输入:n = 1
输出:1

题目解读:

第 1 轮操作是把每一盏电灯的开关按一下(全部打开)。

第 2 轮操作是把每两盏灯的开关按一下(就是按第 2,4,6… 盏灯的开关,它们被关闭)。

第 3 轮操作是把每三盏灯的开关按一下(就是按第 3,6,9… 盏灯的开关,有的被关闭,比如 3,有的被打开,比如 6)…

如此往复,直到第 n 轮,即只按一下第 n 盏灯的开关。

代码以及思路:
首先,因为电灯一开始都是关闭的,所以某一盏灯最后如果是点亮的,必然要被按奇数次开关。
我们假设只有 6 盏灯,而且我们只看第 6 盏灯。需要进行 6 轮操作对吧,请问对于第 6 盏灯,会被按下几次开关呢?这不难得出,第 1 轮会被按,第 2 轮,第 3 轮,第 6 轮都会被按。

为什么第 1、2、3、6 轮会被按呢?因为 6=16=23

一般情况下,因子都是成对出现的,也就是说开关被按的次数一般是偶数次。

但是有特殊情况,比如说总共有 16 盏灯,那么第 16 盏灯会被按几次?

16 = 116 = 28 = 4*4

其中因子 4 重复出现,所以第 16 盏灯会被按 5 次,奇数次。现在你应该理解这个问题为什么和平方根有关了吧?

所以这道的base case就是找 1-n之间有多少个平方数

因此代码如下:

int bulbSwitch(int n) {return (int)Math.sqrt(n);
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1410169.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

查询每个部门工资最高的员工 sql

在线运行sql语句 CREATE TABLE dept (dno INT PRIMARY KEY AUTO_INCREMENT,dname VARCHAR(50) NOT NULL,dlocal VARCHAR(100) ); CREATE TABLE employee (eno INT PRIMARY KEY AUTO_INCREMENT,ename VARCHAR(50) NOT NULL,egender CHAR(2),deptno INT NOT NULL,ejob VARCHAR(5…

KindEditor 漏洞:历史与现状

零基础入门学习路线 视频配套资料&国内外网安书籍、文档 网络安全面试题 KindEditor 是一款开源的富文本编辑器&#xff0c;曾广泛应用于各种网站和 CMS 系统。 然而&#xff0c;它也曾曝出多个安全漏洞&#xff0c;对使用它的网站造成安全风险。 历史漏洞&#xff1a; 文…

ROS实操:通信机制的实现

最近闲来无事&#xff0c;打算重温了一下ROS方面的相关知识。先前的学习都是一带而过&#xff0c;发现差不多都忘了&#xff0c;学习的不够深入。因此&#xff0c;在重温的同时&#xff0c;写下了这篇关于ROS通信实操的学习博客。 上一篇博客的链接为&#xff1a;ROS架构的学习…

Android 开发部分基础工具使用

c调试 在NDK调试的时候&#xff0c;如果找不到 符号的话&#xff0c;我们可以在调试配置中添加符号地址的全路径一直到根目录&#xff1a;&#xff0c;xxx/armeabi-v7a&#xff1a; You must point the symbol search paths at the obj/local/ directory. This is also not a …

设计模式: 责任链模式

目录 一&#xff0c;责任链模式 二&#xff0c;特点 四&#xff0c;实现步骤 五&#xff0c;代码 一&#xff0c;责任链模式 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种软件设计模式&#xff0c;它属于行为型模式。在这种模式中&#xff0c…

华为云耀云服务器开放端口

博客主页&#xff1a;花果山~程序猿-CSDN博客 关注我一起学习&#xff0c;一起进步&#xff0c;一起探索编程的无限可能吧&#xff01;让我们一起努力&#xff0c;一起成长&#xff01; 目录 一.华为云控制台开放端口 寻找到安全组信息 2. 添加开放的端口信息 3. 检查是否成…

Python量化炒股的财务因子选股

Python量化炒股的财务因子选股-财务因子选股 选股是股市投资的第一步&#xff0c;是最基础的一步&#xff0c;也是最重要的一步。 初识财务因子选股 量化选股是利用数量化的方法选择股票组合&#xff0c;期望该股票组合能够获得超越基准收益率的投资行为。总的来说&#xff…

VBA技术资料MF147:从Excel运行PowerPoint演示文稿

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…

数组的扩容与缩容

数组的扩容与缩容 文章目录 数组的扩容与缩容数组的扩容内存分析 数组的缩容内存分析内存分析 数组的扩容 数组扩容是指当原有数组的空间不足以容纳更多的元素时&#xff0c;创建一个新的、长度更大的数组&#xff0c;并将原数组中的元素复制到新数组中&#xff0c;然后更新原…

《半小时漫画论语》读书笔记

站在几年前看现在的我&#xff0c;感觉多了几分犹豫、内耗&#xff0c;少了几分勇敢。 今天重新读下论语&#xff0c;矫正一下人生态度。 一、论语是什么 论语&#xff0c;主要记载了孔子和他弟子们日常说的话、做的事。 孔子&#xff0c;读书人心中的圣人&#xff0c;中国历…

数据通信-A

数据通信 一、数据通信网络基础二、VRP系统三、eNSP配置命令 不是从零开始&#xff0c;有一些基础&#xff0c;主要记录配置命令。一、数据通信网络基础 图标&#xff1a;主要是认识第一行。 常见术语&#xff1a;数据通信网络最基本的功能是实现数据互通。 数据载荷&#…

【C++】滑动窗口:长度最小的子数组

1.题目 2.算法分析 这种题目&#xff0c;首先想到的是暴力穷举法&#xff1a; 用两层循环取遍该数组的所有子数组&#xff0c;然后找到那个最短的就可以了。 我们的滑动窗口就是对这种暴力穷举法进行优化&#xff1a; 主要是舍弃的思想&#xff0c;舍弃那些一定不可能是最终…

jupyter notebook切换conda虚拟环境

首先&#xff0c;切换到某个虚拟环境&#xff0c;本人切换到了d2l环境&#xff1a; (d2l) C:\Users\10129>pip install ipykernel然后&#xff0c;如代码所示安装ipykernel包 最后&#xff0c;按下述代码执行&#xff1a; (d2l) C:\Users\10129>python -m ipykernel i…

857.雇佣K名工人的最低成本

题目说的其实是有点乱的,所以我们可能抓不住重点,甚至都不太清楚规则,比如 eg. quality[3,1,10,10,1] wage[4,8,200,200,7] 这里是选下标0,1,4 ->单价为8 但是想清楚其实就很easy. 就是 贪心(sort) 优先队列 梳理下我们发现其实要让每个人得到最低期望,就要按照当前最贵…

vue中配置 测试、准生产、生产环境

在package.json,scripts中配置 "dev": "vue-cli-service serve --open --mode dev",在项目根目录下配置 新建 .env.dev 和.env.development文件 //类似于title NODE_ENV "serve" //各环境API数据接口请求地址 VUE_APP_BASE_API "http:…

Python绘制的好看统计图

代码 sx [Accent, Accent_r, Blues, Blues_r, BrBG, BrBG_r, BuGn, BuGn_r, BuPu, BuPu_r, CMRmap, CMRmap_r, Dark2, Dark2_r, GnBu, GnBu_r, Greens, Greens_r, Greys, Greys_r, OrRd, OrRd_r, Oranges, Oranges_r, PRGn, PRGn_r, Paired, Paired_r, Pastel1, Pastel1_r, P…

DataTrove:一款针对大规模文本数据的处理、过滤和消除重复数据工具

关于DataTrove DataTrove是一款针对大规模文本数据的处理、过滤和消除重复数据工具&#xff0c;该工具可以通过提供一组平台无关的可定制管道处理块&#xff0c;帮助广大研究人员从各种复杂脚本中解放出来&#xff0c;同时还允许我们轻松添加自定义功能。 DataTrove所实现的数…

Linux内核之原子操作:atomic_long_inc用法实例(六十六)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

【C语言】atoi和atof函数的使用

人生应该树立目标&#xff0c;否则你的精力会白白浪费。&#x1f493;&#x1f493;&#x1f493; 目录 •&#x1f319;知识回顾 &#x1f34b;知识点一&#xff1a;atoi函数的使用和实现 • &#x1f330;1.函数介绍 • &#x1f330;2.代码演示 • &#x1f330;3.atoi函数的…

springboot + slf4j + log4j2

<!--Web依赖--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId><exclusions><exclusion><groupId>org.springframework.boot</groupId><artifact…