25 – 09 – 23 (补于 25 – 09 – 29)
今日份题面
给定两个整数，分别表示分数的分子
numerator和分母denominator，以 字符串形式返回小数 。如果小数部分为循环小数，则将循环的部分括在括号内。
如果存在多个答案，只需返回 任意一个 。
对于所有给定的输入，保证 答案字符串的长度小于
104。
思路上其实只有一个难点：我们如何知道当前的结果是否是循环小数？
但其实也很容易想出来，因为除数始终是固定的，那么出现循环时所得的结果必定会在前面出现过。
那么很容易就想到了我们可以开一个 HashSet 维护出现过的当前位结果(注意不含补充 0 ),只要出现过就遍历当前拼接串，将第一次出现该结果的左边插入 ‘(‘， 末尾不插入当前结果(因为重复)而是插入 ‘)’
pass 实现：
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) return "0";
StringBuilder res = new StringBuilder();
// 处理符号
if ((numerator < 0) ^ (denominator < 0)) res.append('-');
long num = Math.abs((long) numerator);
long den = Math.abs((long) denominator);
// 整数部分
res.append(num / den);
long remainder = num % den;
if (remainder == 0) return res.toString();
// 小数部分
res.append('.');
Map<Long, Integer> map = new HashMap<>();
while (remainder != 0) {
if (map.containsKey(remainder)) {
res.insert(map.get(remainder), "(");
res.append(')');
break;
}
map.put(remainder, res.length());
remainder *= 10;
res.append(remainder / den);
remainder %= den;
}
return res.toString();
}
}
三角周，启动！
25 – 09 – 24 (补于 25 – 09 – 30)
今日份题面
三角形最小路径和
给定一个三角形
triangle，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标
i，那么下一步可以移动到下一行的下标i或i + 1。
一道很经典的 DP 入门题，实际上是 IOI 的94年赛题变种，我们可以自顶向下 dp 也可以自底向上 dp，核心的状态方程可表示为：
dp[i][j] = Math.min(dp[i - 1][j - 1] + triangle.get(i - 1).get(j - 1), dp[i - 1][j] + triangle.get(i - 1).get(j));秒了
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int res = Integer.MAX_VALUE, l = triangle.size();
int [][] dp = new int [l][l];
for(int [] i : dp){
Arrays.fill(i, Integer.MAX_VALUE);
}
if(l <= 1) return triangle.get(0).get(0);
dp[0][0] = 0; dp[1][0] = triangle.get(0).get(0); dp[1][1] = triangle.get(0).get(0);
for(int i = 1; i < l; ++i){
for(int j = 0; j <= i; ++j){
if(j == i){
dp[i][j] = dp[i - 1][j - 1] + triangle.get(i - 1).get(j - 1);
continue;
}else if (j == 0){
dp[i][j] = dp[i - 1][j] + triangle.get(i - 1).get(j);
continue;
}
dp[i][j] = Math.min(dp[i - 1][j - 1] + triangle.get(i - 1).get(j - 1), dp[i - 1][j] + triangle.get(i - 1).get(j));
}
}
for(int i = 0; i < l; ++i){
res = Math.min(res, dp[l - 1][i] + triangle.get(l - 1).get(i));
}
return res;
}
}
25 – 09 – 25 (补于 25 – 10 – 01)
国庆快乐！
今日份题面
给定一个包含非负整数的数组
nums，返回其中可以组成三角形三条边的三元组个数。
简明，扼要，但是不好搞。
当然我们可以暴力 $O(n^3)$ 一组一组进行比对，但只要数据量稍微大那么一丢丢就炸了。
所有另选思路。
构成三角形的必要条件是两边之和大于第三边，那么在边数有序的情况下，我们只需要考虑最大边是否小于其余两边之和就行了
所有考虑一个双指针，快指针维护当前最大边，慢指针维护最短边，两指针之间是中间边，当最短边和中间边之和小于最大边时最大边移动，大于最大边时记录当前组数
class Solution {
public int triangleNumber(int[] nums) {
int res = 0;
Arrays.sort(nums);
for(int i = 0; i < nums.length; ++i){
if(nums[i] == 0) continue;
int k = i;
for(int j = i + 1; j < nums.length; ++j){
while(k + 1 < nums.length && nums[k + 1] - nums[j] < nums[i]){
++k;
}
res += Math.max(k - j, 0);
}
}
return res;
}
}
这样我们就相当于用一个不回头的隐形指针省去了一组遍历，实现了 $O(n^2)$ 的复杂度
以上
25 – 09 – 26 (补于 25 – 10 – 02)
今日份题面
给你一个由 X-Y 平面上的点组成的数组
points，其中points[i] = [xi, yi]。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在10-5内的答案将会视为正确答案。
我很难觉得这他妈是八(简)岁(单)？
后来一看数据范围，哦暴力吧
class Solution {
public double largestTriangleArea(int[][] points) {
int n = points.length;
double ret = 0.0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
ret = Math.max(ret, triangleArea(points[i][0], points[i][1], points[j][0], points[j][1], points[k][0], points[k][1]));
}
}
}
return ret;
}
public double triangleArea(int x1, int y1, int x2, int y2, int x3, int y3) {
return 0.5 * Math.abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2);
}
}
当然肯定不应该只用暴力，因为 $O(n^3)$ 再多一点就会爆炸(
凸包
咕咕
25 – 09 – 27 (补于 25 – 10 – 03)
今日份题面
给定由一些正数（代表长度）组成的数组
nums，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。如果不能形成任何面积不为零的三角形，返回0
在边长有序(升序)的情况，由贪心我们很容易想到最大边长一定出现在数组最右侧，此时最长的三条边 a, b, c(a>b>c) 如果不满足 a < (b + c) 那么必定无解
class Solution {
public int largestPerimeter(int[] nums) {
Arrays.sort(nums);
for (int i = nums.length - 1; i >= 2; i--) {
if (nums[i - 2] + nums[i - 1] > nums[i]) {
return nums[i - 2] + nums[i - 1] + nums[i];
}
}
return 0; // 无解
}
}
以上
25 – 09 – 28 (补于 25 – 10 – 04)
今日份题面
你有一个凸的
n边形，其每个顶点都有一个整数值。给定一个整数数组values，其中values[i]是第i个顶点的值（即 顺时针顺序 ）。假设将多边形 剖分 为
n - 2个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有n - 2个三角形的值之和。返回 多边形进行三角剖分后可以得到的最低分 。
爆搜吧哎呀
好久不写搜索又忘了…
class Solution {
public int minScoreTriangulation(int[] values) {
int l = values.length, numsOflinesLim = l - 3;
int [][] memo = new int [l][l];
for(int [] i :memo){
Arrays.fill(i, -1);
}
return dfs(0, l - 1, values, memo);
}
private int dfs(int i, int j, int [] values, int [][] memo){
if(i + 1 == j){
return 0;
}
if(memo[i][j] != -1){
return memo[i][j];
}
int res = Integer.MAX_VALUE;
for(int k = i + 1; k < j; k++){
int curRes = dfs(i, k ,values, memo) + dfs(k, j, values, memo) + values[i] * values[j] * values[k];
res = Math.min(res, curRes);
}
return memo[i][j] = res;
}
}
25 – 09 – 29 (补于 25 – 10 – 05)
今日份题面
给你一个下标从 0 开始的整数数组
nums，其中nums[i]是0到9之间（两者都包含）的一个数字。
nums的 三角和 是执行以下操作以后最后剩下元素的值：
nums初始包含n个元素。如果n == 1，终止 操作。否则，创建 一个新的下标从 0 开始的长度为n - 1的整数数组newNums。- 对于满足
0 <= i < n - 1的下标i，newNums[i]赋值 为(nums[i] + nums[i+1]) % 10，%表示取余运算。- 将
newNums替换 数组nums。- 从步骤 1 开始 重复 整个过程。
请你返回
nums的三角和。
考虑数组 $[i, j, k]$ ,那么在一次变换后数组为 $[(i + j) % 10, (j + k) % 10]$ ，显然 i 和 k 只用了一次，于是我们可以原地操作，将新生成的结果填充在前一个元素的位置，同时下一次循环的右边界左移一位。
class Solution {
public int triangularSum(int[] nums) {
int l = nums.length, res = 0;
int [] tempNums = new int [l];
System.arraycopy(nums, 0, tempNums, 0 ,l);
for(int i = 1; i < l; ++i){
for(int j = 0; j < l - i; ++j){
tempNums[j] = (tempNums[j] + tempNums[j + 1]) % 10;
}
}
return tempNums[0];
}
}
以上
发表回复