byu_rself

LC.P1039[多边形三角剖分的最低得分] 题目描述你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是第 i 个顶点的值（即 顺时针顺序 ）。 假设将多边形 剖分 为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。 返回 多边形进行三角剖分后可以得到的最低分 。 示例 1： 输入：values = [1,2,3]输出：6解释：多边形已经三角化，唯一三角形的分数为 6。 示例 2： 输入：values = [3,7,4,5]输出：144解释：有两种三角剖分，可能得分分别为：375 + 457 = 245，或 345 + 347 = 144。最低分数为 144。 示例 3： 输入：values = [1,3,1,4,1,5]输出：13解释：最低分数三角剖分的得分情况为 113 + 114 + 115 + 111 = 13。 提示： n == values.len ...

LC.P516[最长回文子序列] 题目描述给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 示例 1： 输入：s = “bbbab”输出：4解释：一个可能的最长回文子序列为 “bbbb” 。 示例 2： 输入：s = “cbbd”输出：2解释：一个可能的最长回文子序列为 “bb” 。 提示： 1 <= s.length <= 1000 s 仅由小写英文字母组成 方法一：区间DP+记忆化搜索123456789101112131415161718192021222324class Solution { String s; int[][] cache; public int longestPalindromeSubseq(String s) { this.s = s; int n = s.length(); cache = new int[n][n]; ...

LC.P831[隐藏个人信息] 题目描述给你一条个人信息字符串 s ，可能表示一个 邮箱地址 ，也可能表示一串 电话号码 。返回按如下规则 隐藏 个人信息后的结果： 电子邮件地址： 一个电子邮件地址由以下部分组成： 一个 名字 ，由大小写英文字母组成，后面跟着 一个 '@' 字符，后面跟着 一个 域名 ，由大小写英文字母和一个位于中间的 '.' 字符组成。'.' 不会是域名的第一个或者最后一个字符。 要想隐藏电子邮件地址中的个人信息： 名字 和 域名 部分的大写英文字母应当转换成小写英文字母。 名字 中间的字母（即，除第一个和最后一个字母外）必须用 5 个"*****"替换。 电话号码： 一个电话号码应当按下述格式组成： 电话号码可以由 10-13 位数字组成 后 10 位构成 本地号码 前面剩下的 0-3 位，构成 国家代码 利用 {'+', '-', '(', ')', ' '} 这些 分隔字符 按某种形式 ...

LC.P292[Nim游戏] 题目描述你和你的朋友，两个人一起玩 Nim 游戏： 桌子上有一堆石头。你们轮流进行自己的回合， 你作为先手 。每一回合，轮到的人拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。 示例 1： 输入：n = 4输出：false解释：以下是可能的结果: 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。在所有结果中，你的朋友是赢家。 示例 2： 输入：n = 1输出：true 示例 3： 输入：n = 2输出：true 提示： 1 <= n <= 2^31 - 1 方法一：博弈论12345class Solution { public boolean canWinNim(int n) ...

LC.P464[我能赢吗] 题目描述在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。 如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？ 例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。 给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。 示例 1： 输入：maxChoosableInteger = 10, desiredTotal = 11输出：false解释：无论第一个玩家选择哪个整数，他都会失败。第一个玩家可以选择从 1 到 10 的整数。如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal ...

LC.P2367[算数三元组的数目] 题目描述给你一个下标从 0 开始、严格递增 的整数数组 nums 和一个正整数 diff 。如果满足下述全部条件，则三元组 (i, j, k) 就是一个 算术三元组 ： i < j < k， nums[j] - nums[i] == diff 且 nums[k] - nums[j] == diff 返回不同 算术三元组 的数目。 示例 1： 输入：nums = [0,1,4,6,7,10], diff = 3输出：2解释：(1, 2, 4) 是算术三元组：7 - 4 == 3 且 4 - 1 == 3 。(2, 4, 5) 是算术三元组：10 - 7 == 3 且 7 - 4 == 3 。 示例 2： 输入：nums = [4,5,6,7,8,9], diff = 2输出：2解释：(0, 2, 4) 是算术三元组：8 - 6 == 2 且 6 - 4 == 2 。(1, ...

安装栅栏 题目描述给定一个数组 trees，其中 trees[i] = [xi, yi] 表示树在花园中的位置。 你被要求用最短长度的绳子把整个花园围起来，因为绳子很贵。只有把 所有的树都围起来，花园才围得很好。 返回恰好位于围栏周边的树木的坐标。 示例 1: 输入: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]输出: [[1,1],[2,0],[3,3],[2,4],[4,2]] 示例 2: 输入: points = [[1,2],[2,2],[4,2]]输出: [[4,2],[2,2],[1,2]] 注意: 1 <= points.length <= 3000 points[i].length == 2 0 <= xi, yi <= 100 所有给定的点都是 唯一 的。 方法一：二维凸包（Andrew算法）1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484 ...

LC.P1673[两点之间不包含任何点的最宽垂直区域] 题目描述给你 n 个二维平面上的点 points ，其中 points[i] = [xi, yi] ，请你返回两点之间内部不包含任何点的 最宽垂直区域 的宽度。 垂直区域 的定义是固定宽度，而 y 轴上无限延伸的一块区域（也就是高度为无穷大）。 最宽垂直区域 为宽度最大的一个垂直区域。 请注意，垂直区域 边上 的点 不在 区域内。 示例 1： 输入：points = [[8,7],[9,9],[7,4],[9,7]]输出：1 示例 2： 输入：points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]输出：3 提示： n == points.length 2 <= n <= 105 points[i].length == 2 0 <= xi, yi <= 109 方法一：排序将输入的坐标按照横坐标排序，然后依次求出所有相邻点的横坐标距离，返回最大值。 12345678910class Solution { public int ...

LC.P593[有效的正方形] 题目描述给定2D空间中四个点的坐标 p1, p2, p3 和 p4，如果这四个点构成一个正方形，则返回 true 。 点的坐标 pi 表示为 [xi, yi] 。 输入没有任何顺序 。 一个 有效的正方形 有四条等边和四个等角(90度角)。 示例 1: 输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]输出: True 示例 2: 输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]输出：false 示例 3: 输入：p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]输出：true 提示: p1.length == p2.length == p3.length == p4.length == 2 -104 <= xi, yi <= 104 方法一：数学任取四个点中的三 ...

LC.P1037[有效的回旋镖] 题目描述给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，如果这些点构成一个 回旋镖 则返回 true 。 回旋镖 定义为一组三个点，这些点 各不相同 且 不在一条直线上 。 示例 1： 输入：points = [[1,1],[2,3],[3,2]]输出：true 示例 2： 输入：points = [[1,1],[2,2],[3,3]]输出：false 提示： points.length == 3 points[i].length == 2 0 <= xi, yi <= 100 方法一：数学若三点共线，则任意组成的两个向量叉乘为0。 即若A,B,C三点共线，则向量ABX向量BC = 0。 12345678class Solution { public boolean isBoomerang(int[][] points) { // AB X BC = 0 int[] AB = new i ...