刷题
- 【最大化控制资源成本】公司创新实验室正在研究如何最小化资源成本，最大化资源利用率，请你设计算法帮他们解决一个任务混部问题：有taskNum项任务，每个任务有开始时间（startTime），结束时间（endTime）,并行度（parallelism）三个属性，并行度是指这个任务运行时将会占用的服务器数量，一个服务器在每个时刻可以被任意任务使用但最多被一个任务占用，任务运行完成立即释放（结束时刻不占用）。任务混部问题是指给定一批任务，让这批任务由同一批服务器承载运行，请你计算完成这批任务混部最少需要多少服务器，从而最大最大化控制资源成本。
- 输入描述：第一行输入为taskNum，表示有taskNum项任务，接下来taskNum行，每行三个整数，表示每个任务的开始时间，（startTime ），结束时间（endTime ），并行度（parallelism）
- 输出描述：一个整数，表示最少需要的服务器数量
- 输入
- 3
- 2 3 1
- 6 9 2
- 0 5 1
- 输出 2js
let arr = [[0, 1, 2],[0, 5, 1],[2, 3, 1],[6, 9, 2],[1, 7, 1]] let setArr = Array.from(new Set(arr.flat())).sort((a, b) => a - b) let setLen = setArr.length let arrLen = arr.length let resArr = new Array() for (let i = 0; i < setLen - 1; i++) { let sum = 0 for (let j = 0; j < arrLen; j++) { if (arr[j][1] <= setArr[i]) continue //如果结束时间过了 跳过 if (arr[j][0] <= setArr[i]) { sum += arr[j][2] //在区间内 } } resArr.push(sum) } console.log(resArr) //服务器时间
- 【完美走位】输入一个长度为4的倍数的字符串，字符串中仅包含WASD四个字母。将这个字符串中的连续子串用同等长度的仅包含WASD的字符串替换，如果替换后整个字符串中WASD四个字母出现的频数相同，那么我们称替换后的字符串是“完美走位”。求子串的最小长度。如果输入字符串已经平衡则输出0。
- 输入：一行字符表示给定的字符串s WASDAASD
- 输出：一个整数表示答案 1js
let str = 'WASDAASDDDSS' getPerfectWays(str) function getMap(v) { //获取映射 let map = new Map() for (const item of v) { map.set(item, (map.get(item) || 0) + 1) } return map } function getPerfectWays(str) { let strMap = getMap(str) //获取词频表 //特殊情况，已经完美走位 if (strMap.get('W') == strMap.get('S') && strMap.get('W') == strMap.get('A') && strMap.get('W') == strMap.get( 'D')) { console.log(0); } let left = 0 let right = 0 let len = 0 let maxNums = 0 // 出现次数最多的字母 let res = str.length //记录最小的长度 // 可替换字母个数, freeNums大于0且能被4整除，当前范围满足条件，左指针右移一格，否则右指针右移 let freeNums = 0 while (right < str.length) { //获取剩余部分的映射关系 console.log(left, right) let restMap = getMap((str.slice(0, left) || '') + (str.slice(right + 1) || '')) //找到剩余部分映射中的最大长度 maxNums = Math.max(Math.max(Math.max((restMap.get('W') || 0), (restMap.get('A') || 0)), (restMap.get('S') || 0)), (restMap.get('D') || 0)) len = right - left + 1 //获取窗口长度 freeNums = len - ((maxNums - (restMap.get('W') || 0)) + (maxNums - (restMap.get('A') || 0)) + (maxNums - ( restMap.get( 'S') || 0)) + (maxNums - (restMap.get('D') || 0))) //如果用来替换的部分足够，并且超出的部分是4的倍数 console.log(restMap, maxNums, freeNums); if (freeNums >= 0 && freeNums % 4 == 0) { if (len < res || res == str.length) { res = len // 更新最短值 } left++ //尝试是否可以更短 } else { right++ //扩大窗口 } if (right >= str.length) { // 越界即结束 console.log(res); return res }; } }
- 【羊、狼、农夫过河】羊、狼、农夫都在岸边，当羊的数量小于狼的数量时，狼会攻击羊，农夫则会损失羊。农夫有一艘容量固定的船，能够承载固定数量的动物。要求求出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。只计算农夫去对岸的次数，回程时农夫不会运送羊和狼。备注：农夫在或农夫离开后羊的数量大于狼的数量时狼不会攻击羊。农夫自身不占用船的容量。
- 输入描述:第一行输入为M，N，X， 分别代表羊的数量，狼的数量，小船的容量。
- 输出描述:输出不损失羊情况下将全部羊和狼运到对岸需要的最小次数。（若无法满足条件则输出0）js
- 【字符串重新排列】给定一个字符串s，s包括以空格分隔的若干个单词，请对s进行如下处理后输出：
- 单词内部调整：对每个单词字母重新按字典序排序
- 单词间顺序调整：
- 统计每个单词出现的次数，并按次数降序排列
- 次数相同，按单词长度升序排列
- 次数和单词长度均相同，按字典升序排列
- 请输出处理后的字符串，每个单词以一个空格分隔。
- 输入描述：一行字符串，每个字符取值范围：【a-zA-z0-9】以及空格，字符串长度范围：【1，1000】
- 输入: This is an apple My sister is in the house not in the yard
- 输出: an is This aelpp in in eht eht My is not adry ehosu eirsstjs
function sortStr(s) { let sArr = s.split(' ') //单词内部排序 let resArr = sArr.map((item) => item.split('').sort((a, b) => a.charCodeAt() - b.charCodeAt()).join('')) //统计词频 //A--65 Z--90 a--97 z--122 let strMap = new Map() for (let i = 0; i < resArr.length; i++) { strMap.set(resArr[i], (strMap.get(resArr[i]) || 0) + 1) } //单词之间排序 for (let i = 0; i < resArr.length; i++) { for (let j = 0; j < resArr.length - 1; j++) { //词频高的放前面 if (strMap.get(resArr[j]) < strMap.get(resArr[j + 1])) { let temp temp = resArr[j] resArr[j] = resArr[j + 1] resArr[j + 1] = temp } else if (strMap.get(resArr[j]) = strMap.get(resArr[j + 1])) { if (resArr[j + 1].length < resArr[j].length) { let temp temp = resArr[j] resArr[j] = resArr[j + 1] resArr[j + 1] = temp } else if (resArr[j + 1].length = resArr[j].length) { // console.log(resArr[j + 1] - resArr[j]) } } } // resArr.sort((a, b) => strMap.get(b) - strMap.get(a)) } }
- 【租车骑绿岛】部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，做最大载重M。给出部门每个人的体重，请问最少需要租用多少双人自行车。
- 输入描述：
- 第一行两个数字m、n，分别代表自行车限重，部门总人数。
- 第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。
- 输出描述：
- 最小需要的双人自行车数量。
- 输入
- 3 4
- 3 2 2 1
- 输出
- 3
js//双指针+贪心 function min(arr) { let sortArr = arr.sort((a, b) => a - b) let limit = 3 console.log(sortArr, limit) let left = 0 let right = sortArr.length - 1 let count = 0 while (left <= right) { if (sortArr[left] + sortArr[right] <= limit) { count++ left++ right-- } else { count++ right-- } } console.log(count); //6 }
- 【无向图染色】给一个无向图染色，可以填红黑两种颜色，必须保证相邻两个节点不能同时为红色，输出有多少种不同的染色方案？
- 输入描述：第一行输入M(图中节点数) N(边数),后续N行格式为：V1 V2表示一个V1到V2的边,不能保证所有节点都是连通的
- 输出描述：输出一个数字表示染色方案的个数。
- 输入
- 4 4
- 1 2
- 2 4
- 3 4
- 1 3
- 输出：7js
- 【单向链表中间节点】求单向链表中间的节点值，如果奇数个节点取中间，偶数个取偏右边的那个值。
- 输入描述：第一行 链表头节点地址path 后续输入的节点数n 后续输入每行表示一个节点，格式: "节点地址 节点值 下一个节点地址(-1表示空指针)“ 输入保证链表不会出现环，并且可能存在一些节点不属于链表。
- 输出描述：链表中间节点值。
- 输入:
- 00010 4
- 00000 3 -1
- 00010 5 12309
- 11451 6 00000
- 12309 7 11451
- 输出：6js
//快慢指针：注意业务要求，偶数的时候取右侧的值，可以让慢指针先走 //map存储：遍历一遍并获取长度，取size/2的位置值
- 【等和子数组最小和】给定一个数组nums,将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，组内元素和的最小值js
//求分成k个等和子数组，再找最小的 - 【最多颜色的车辆】在一个狭小的路口，每秒只能通过一辆车，假好车辆的颜色只有 3 种，找出 N 秒内经过的最多颜色的车辆数量。三种颜色编号为0 ，1 ，2js
//滑动窗口 var uniquePaths = function (nums, window) { let left = 0 let right = 0 let map = new Map() let max = 0 while (right < nums.length) { let rNum = nums[right] right++ //窗口右移 map.set(rNum, (map.get(rNum) || 0) + 1) console.log(map, '1111') max = Math.max(max, map.get(rNum)) while (right - left == window && right < nums.length) { let r = nums[right] let l = nums[left] right++ left++ map.set(r, (map.get(r) || 0) + 1) map.set(l, map.get(l) - 1) console.log(map, '2222') max = Math.max(max, Math.max(map.get(r), map.get(l))) } } console.log(max) } - 【不含 101 的数】小明在学习二进制时，发现了一类不含 101的数，也就是：将数字用二进制表示，不能出现 101 。现在给定一个整数区间 [l,r] ，请问这个区间包含了多少个不含101 的数？js
var uniquePaths = function (left, right) { let count = 0 for (let i = left; i <= right; i++) { let str = i.toString(2) if (str.indexOf('101') != -1) { count++ } } return count } - 【过滤组合字符串】数字0、1、2、3、4、5、6、7、8、9分别关联 a~z 26个英文字母js
var uniquePaths = function (num, str) { let strArr = ['abc', 'def', 'ghi', 'jkl', 'mno', 'prq', 'st', 'uv', 'wx', 'yz'] let path = [] let resArr = [] let backTracking = function (index) { if (path.length == num.length) { resArr.push(path.slice()) return } let current = num[index] //获取对应到编号 let s = strArr[current] //拿到对应编号的字符串 for (let i = 0; i < s.length; i++) { path.push(s[i]) // backTracking(index + 1) path.pop() } } backTracking(0) console.log(resArr) } - 【真正的密码】在一行中输入一个字符串数组，如果其中一个字符串的所有以索引0开头的子串在数组中都有，那么这个字符串就是潜在密码，在所有潜在密码中最长的是真正的密码，如果有多个长度相同的真正的密码，那么取字典序最大的为唯一的真正的密码，求唯一的真正的密码。
- 【最小调整顺序次数】给定一个队列，但是这个队列比较特殊，可以从头部添加数据，也可以从尾部添加数据，但是只能从头部删除数据。输入一个数字n，会依次添加数字1~n（也就是添加n次）。
- 【探索地块建立】给一块nm的地块，相当于nm的二维数组，每个元素的值表示这个小地块的发电量；求在这块地上建立正方形的边长为c的发电站，发电量满足目标电量k的地块数量。js
//构建二维前缀和数组 按照边长遍历一遍，统计符合条件的子矩阵 - 【模拟商场优惠打折】 暴力遍历模拟
- 【区间交叠问题】给定坐标轴上的一组线段，线段的起点和终点均为整数并且长度不小于1，请你从中找到最少数量的线段，这些线段可以覆盖住所有线段。 扫描线js
//区间重叠合并问题 - 【二元组个数】给定两个数组a，b，若a[i] == b[j] 则称 [i, j] 为一个二元组，求在给定的两个数组中，二元组的个数。
- 【最大平分数组】给定一个数组nums，可以将元素分为若干个组，使得每组和相等，求出满足条件的所有分组中，最大的平分组个数。js
//回溯、动态规划问题 - 【连接器问题】有一组区间[a0，b0]，[a1，b1]，…（a，b表示起点，终点），区间有可能重叠、相邻，重叠或相邻则可以合并为更大的区间；给定一组连接器[x1，x2，x3，…]（x表示连接器的最大可连接长度，即x>=gap），可用于将分离的区间连接起来，但两个分离区间之间只能使用1个连接器；请编程实现使用连接器后，最少的区间数结果。js
//区间重叠合并问题 - 【打印机队列】
- 【处理器问题】 阅读理解
- 【日志首次上报最多积分】
- 【简单的自动曝光】
- 【获取最大软件版本号】
- 【二进制差异数】 30%
- 【Excel单元格数值统计】
- 【相同数字的积木游戏】
- 【开放日活动】
- 【投篮大赛】
- 【开心消消乐】js
//类似岛屿问题，BFS+感染 - 【通信误码】
- 【最大报酬】js
//动态规划 、回溯、背包问题，求最大价值 - 【机器人】js
//BFS - 【新学校选址】js
//排序后中位数求解 - 【寻找路径】js
//1: 理解了题意之后还是比较简单的。 //2：第一步找到数组中的最小值，当作为最小叶子节点。 //3：后面就是根据这个最小值的index，去上层找它的直接父节点。（对应关系就是 / 2） - 【任务调度】
- 【匿名信】
- 【密室逃生游戏】
- 【快递业务站】js
//图的遍历 - 【对称美学】
- 【箱子之字形摆放】js
//1：可以设置一个大小为n的数组，这样需要做的就变成了怎么把对应的字母放到指定的数组中去。 //2：设置一个flag变量，这样的话就可以控制在转弯的时候放到哪个数组中去了。 - 【数组合并】
- 【挑选字符串】
- 【优选核酸检测点】
- 【最短木板长度】js
//贪心的思想，遍历给的木料长度，每次都补一下最短的木板（只拿出1m的长度），每次补完之后重新排序，找到最短继续补1m, - 【最多获得的短信条数】js
//贪心算法 可以算出平均每一块钱对应多少条来排序 - 【星际篮球争霸赛】js
//等和子数组问题 - 【最左侧冗余覆盖子串】
- 【端口合并】js
//区间合并类的题目 双层循环合并即可，唯一需要注意的是判断两个区间相同元素的个数可以用set来加个速 - 【最大利润】js
//股票买卖的最佳时机 - 【最长的密码】
- 【计算数组中心位置】js
//预处理数组 - 【积木最远距离】
- 【区间交叠问题】
- 【整理扑克牌】
- 【分奖金】js
//单调栈 - 【计算快递业务主站点】js
//类似岛屿个数的那种DFS 题目 - 【去除多余空格】
- 【最差产品奖】js
//固定长度滑动窗口 - 【最多等和不相交连续子序列】js
//可以利用前缀和获取对应子数组的和 - 【货币单位换算】
- 【查找单入口空闲区域】js
//类似岛屿问题,多入口不算 - 【预订酒店】
- 【基站维护最短距离】
- 【士兵过河】js
1：出这种hard题，感觉想招ACM选手。。。 2：类似一个经典的过桥问题，但是有变种，手电筒换成了小船，过桥也变化了过河。。。 3：最关键的目标就是在过河过程中，让最慢的两个人消耗的时间最短。 具体的方法就是让最慢的两个一起过河，然后让对岸快的人回来送船。（其实从题目给出的示例的说明中，也能发现符合这个逻辑） 1、让用时最短的两个士兵a[0], a[1]划船过河到对岸，用时a[1] 2、然后让a[1]留在对岸，让最快的士兵a[0]划船回来本岸，用时a[0] 3、然后让本岸用时最长的两个士兵划船过河到对岸 4、然后再让对岸用时最短的士兵a[1]划船回来本岸 按照上述步骤进行循环，直到用时达到上限T，或者士兵全部运完。 5：有重复的子问题，那么动态规划也就顺势而出： 定义：dp[i] 为 第 0~i 士兵全部过河所需的最短时间。（首先肯定要对耗时数组 a 进行升序排序） 初始状态： 士兵总数为1，只能走到第1步：dp[0] = a[0] 士兵总数为2，只能走到第1步：dp[0] = a[1] 转移方程： dp[i] = min(dp[i - 1] + a[0] + get_shorter_time(a[0], a[i]), dp[i - 2] + a[0] + get_shorter_time(a[i - 1], a[i]) + a[1] + get_shorter_time(a[0], a[1])) 转义方程解释： 方案1：本岸剩余士兵个数为奇数，0~i-1 士兵都已经过河(dp[i - 1] )，此时让对岸最快的士兵回来，也就是a[0]，然后0号士兵和第 i 号士兵一起过河，用时a[i]。但是题目中有一个特殊条件：当2个士兵坐船1个士兵划船时，用时为 a[i]*10；a[i]为划船士兵用时。如果a[0] = 1, a[i] = 20, 那么a[0] 自己划船更快a[0]*10 < a[i]，所以需要判断一下。 因此：dp[i - 1] + a[0] + get_shorter_time(a[0], a[i]) 方案2：本岸剩余士兵个数为偶数，方案1就不成立了，需要回退一步，0~i-2 士兵都已经过河(dp[i - 2] )，此时让对岸最快的士兵回来，也就是a[0]，然后 i-1 号士兵 和i 号士兵划船过河（最慢的两个士兵），用时a[i]，然后对岸最快的a[1]划船回来，用时a[1]，然后0号士兵和1号士兵划到对岸，用时a[1]。同时考虑题目中的特殊条件，每次两个人过河的时候，都需要考两次一下是否一个人划船更快。 因此：dp[i - 2] + a[0] + get_shorter_time(a[i - 1], a[i]) + a[1] + get_shorter_time(a[0], a[1]) 6：OK，说明到此结束，考试出这题，能做出来的凤毛麟角吧。我想了很久，网上也各种搜博客和相关的答案才理解的。 - 【查找二叉树节点】
- 【硬件产品销售方案】js
//leetcode40 组合总和2 - 【核酸最快检测效率】
- 【计算网络信号】
- 【异常的打卡记录】
- 【删除重复数字后的最大数字】js
//贪心+单调栈 - 【字符串解密】
- 【找等值元素】
- 【任务总执行时长】
- 【水库蓄水问题】js
//1：leetcode 原题， 设两指针 i , j，指向的水槽板高度分别为 h[i] , h[j] ，此状态下水槽面积为 S(i, j)。由于可容纳水的高度由两板中的 短板 决定，因此可得如下 面积公式 ： S(i, j) = min(h[i], h[j]) × (j - i) 在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 -1−1 变短： 若向内 移动短板 ，水槽的短板 min(h[i], h[j])可能变大，因此下个水槽的面积 可能增大 。 若向内 移动长板 ，水槽的短板 min(h[i], h[j])不变或变小，因此下个水槽的面积 一定变小 。 因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。 - 【单词倒序】
- 【找出重复代码】js
//最长公共子串 var maxLengthLCS = function (s1, s2) { //dp[i][j]表示s1[..i]与s2[...j]的最长公共子串长度 let m = s1.length, n = s2.length let dp = Array.from(new Array(m + 1), () => new Array(n + 1).fill(0)) for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (s1[i] == s2[j]) { dp[i][j] = dp[i - 1][j - 1] + 1 } else { dp[i][j] = 0 } } } console.log(dp) }; - 【优雅子数组】js
//1：直接上暴力法吧，感觉这题如果有什么特殊的解法，应该是要难倒一大片人。 2：唯一找到一个类似的题目：1157. 子数组中占绝大多数的元素 - 力扣（LeetCode） 但是感觉考这种hard中的hard真的有用吗。。。暴力能做一点是一点吧。 3：上一个稍微取巧一点的方法，用数组的下标代表数字的大小，数组的值代表下标数字出现的个数。这样不用使用map来统计每个数字出现的次数。 - 【数字加减游戏】js
1：题目说可以加也能减，如果+a和-a同时存在，则正负相抵，啥都没做但已经使用了2次，所以可得-a和+a只能有一个存在。 2：存在下面三种情况: a、s-a*i+b*j=t -> t-(s-a*i)=b*j -> (t-(s-a*i))%b=0 b、s+a*i+b*j=t >t-(s+a*i)=b*j-> (t-(s+a*i))%b=0 c、s+a*i- b*j=t - t-(s +a*i) =-b*j -> (t-(s+a*i))%b=0这样一来就很清楚了。 t减去 s对a的递增或者递减 整除 b，增或者递减的次数则是a的使用次数。递增递减同时进行，先整除b的则是最小使用次数。 3：所以b是加还是减，应该都没有影响，主要起作用的是a是+ 还是-。 - 【猜字谜】