球球了给孩子一个offer吧

题解

/ 注册

全部文章 / 题解（共64篇）

题解 | #那些插队的人#

题意：你有一个长度为 n 的队伍，从左到右依次为 1~n，有 m 次插队行为，用数组 cutIn 进行表示，cutIn 的元素依次代表想要插队的人的编号，每次插队，这个人都会直接移动到队伍的最前方。你需要返回一个整数，代表这 m 次插队行为之后，有多少个人已经不在原来队伍的位置了。示例输入：3,...

双指针

2021-08-02

0 585

题解 | #牛能和牛可乐的礼物#

题目关键信息：给定一个数组，将数组分成两个部分，使得这两部分的和的差最小方法一：动态规划“数组”，“求最优值”显然这道题可以用动态规划解决，这是0-1背包的变形类题目，求数组两部分的和的差的最小值，假设数组的总和为，部分一的和为，部分二的和为，那么增加，就减小,减小,就增加,,因此背包的最大容量是...

动态规划

2021-08-02

0 602

题解 | #牛妹的礼物#

题意描述：有NxM大小的矩阵，从左上角走到右下角，只能向右，下，右下走，求到达右下角的最短带权路径长度方法一：动态规划采用递推的方式,定义一个二维数组，显然，的值就是从左上角走到的最短路径，要求从左上角到右下角的最短路径就是求的值状态转移方程： import java.util.*; p...

动态规划递归

2021-08-01

0 445

题解 | #牛妹的面试#

描述：众所周知，牛妹是一个offer收割姬，这次面试她遇到了这样的一个问题。给了一个序列，让找出最长的“凸子序列”何为“凸子序列”：数列中有一个xi,使得所有x0<x1<x2….xi-1<xi且xi>xi+1>xi+1>….>xneg：12345431,是山...

贪心二分动态规划

2021-07-31

0 534

题解 | #最长重复子串#

描述一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。给定一个字符串，请编写一个函数，返回其最长的重复字符子串。若不存在任何重复字符子串，则返回0。从题目中我们可以整理出以下关键点：1.一个重复字符串是由两个连续的相同的字符...

滑动窗口

2021-07-29

0 2007

题解 | #不相邻最大子序列和#

描述给你一个n（1≤n≤10^5），和一个长度为n的数组，在不同时选位置相邻的两个数的基础上，求该序列的最大子序列和（挑选出的子序列可以为空）。示例输入：3,[1,2,3]返回值：4说明：有[],[1],[2],[3],[1,3] 4种选取方式其中[1,3]选取最优，答案为4 这道题本质上是“...

记忆化搜索递归动态规划

2021-07-28

0 573

题解 | #01背包#

描述已知一个背包最多能容纳物体的体积为V现有n个物品第i个物品的体积为, 第i个物品的重量为求当前背包最多能装多大重量的物品示例输入：10,2,[[1,3],[10,4]]返回值：4说明：第一个物品的体积为1，重量为3，第二个物品的体积为10，重量为4。只取第二个物品可以达到最优方案，取物重量为...

动态规划

2021-07-26

2 736

题解 | #孩子们的游戏(圆圈中最后剩下的数)#

描述这是一道典型的约瑟夫环问题，我们可以这样理解：有n个人围成一圈，从第一个人开始报数，第m个将被杀掉，最后剩下一个，其余人都被杀掉，返回最后剩下的这个人的索引，如果没有人，则返回-1示例输入：5,3返回值：3 方法一：环形链表我们可以用环形链表来存储数字，每次找到被选中的元素将其移除，删除...

递归

2021-07-25

0 410

题解 | #矩阵乘法#

描述给定两个nxn的矩阵A和B，求AxB。示例输入：[[1,2],[3,2]],[[3,4],[2,1]]返回值：[[7,6],[13,14]] 方法一：数学模拟有两个矩阵：a和b（矩阵实际上就是二维数组） a矩阵和b矩阵可以做乘法运算必须满足a矩阵的列的数量等于b矩阵的行的数量运算规则：a...

数组

2021-07-23

1 752

题解 | #表达式求值#

描述请写一个整数计算器，支持加减乘三种运算和括号。示例输入："1+2"返回值：3 思路：题目给出了一个中缀表达式，要我们求表达式的结果，最直接的想法就是把中缀表达式转为后缀表达式，再利用一个栈完成后缀表达式的求值。方法一：中缀表达式转后缀表达式+后缀表达式求值中缀表达式转后...

2021-07-23

1 570