昨天完成了 leetcode 的三月度每日一题打卡，现将三月份的部分题目和大家分享
选题标准：与实际工作或生活场景贴近 or 有意思的题目
二进制数
知识点
任何进制表示的小数，乘上进制等价于小数点往右移一位
题目介绍
二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。
-
示例1: -
输入：0.625 -
输出：”0.101″
-
-
示例2: -
输入：0.1 -
输出：”ERROR” -
提示：0.1无法被二进制准确表示
-
题解
function printBin(num: number): string {
let result: string = '0.';
while (result.length <= 32 && num !== 0) {
num *= 2;
const digit: number = Math.floor(num);
result += digit;
num -= digit;
}
if (result.length > 32) {
return "ERROR";
}
return result;
};
保证文件名唯一
应用点
文件夹的自动重命名是我们很常见的一个操作，如果让你实现，你会怎么做呢？
题目介绍
给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹：在第 i 分钟，新建名为 names[i] 的文件夹。
由于两个文件 不能 共享相同的文件名，因此如果新建文件夹使用的文件名已经被占用，系统会以 (k) 的形式为新文件夹的文件名添加后缀，其中 k 是能保证文件名唯一的 最小正整数 。
返回长度为 n 的字符串数组，其中 ans[i] 是创建第 i 个文件夹时系统分配给该文件夹的实际名称。
-
示例1 -
输入：names = [“gta”,”gta(1)”,”gta”,”avalon”] -
输出：[“gta”,”gta(1)”,”gta(2)”,”avalon”] -
解释：文件系统将会这样创建文件名：
“gta” –> 之前未分配，仍为 “gta”
“gta(1)” –> 之前未分配，仍为 “gta(1)”
“gta” –> 文件名被占用，系统为该名称添加后缀 (k)，由于 “gta(1)” 也被占 用，所以 k = 2 。实际创建的文件名为 “gta(2)” 。
“avalon” –> 之前未分配，仍为 “avalon”
-
-
示例2 -
输入：names = [“kaido”,”kaido(1)”,”kaido”,”kaido(1)”] -
输出：[“kaido”,”kaido(1)”,”kaido(2)”,”kaido(1)(1)”] -
解释：注意，如果含后缀文件名被占用，那么系统也会按规则在名称后添加新的后缀 (k) 。
-
题解
function getFolderNames(names: string[]): string[] {
const map = new Map<string, number>();
const result = [];
for (const name of names) {
if (!map.has(name)) {
map.set(name, 1);
result.push(name);
} else {
let val = map.get(name);
let uniqueName = getName(name, val);
while (map.has(uniqueName)) {
val++;
uniqueName = getName(name, val);
}
map.set(uniqueName, 1);
map.set(name, val + 1);
result.push(uniqueName);
}
}
return result;
}
function getName(name: string, val: number): string {
return <span class="hljs-subst" style="color: #e06c75; line-height: 26px;">${name}</span>(<span class="hljs-subst" style="color: #e06c75; line-height: 26px;">${val}</span>);
}
礼物的最大价值（动态规划）
应用点
最大化似乎是人们一直以来的执念，比较没有谁不想最大化，特别是关乎个人利益选择时，试想，如果生活中真有一堆礼物等你去挑选，你可以最大化其价值吗？
题目介绍
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
-
示例 1:
-
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
] -
输出: 12 -
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
-
题解
function maxValue(grid: number[][]): number {
const numRows = grid.length;
const numCols = grid[0].length;
const dpTable = new Array(numRows).fill(0).map(() => new Array(numCols).fill(0));
for (let row = 0; row < numRows; row++) {
for (let col = 0; col < numCols; col++) {
const fromAbove = row > 0 ? dpTable[row - 1][col] : 0;
const fromLeft = col > 0 ? dpTable[row][col - 1] : 0;
dpTable[row][col] = Math.max(fromAbove, fromLeft) + grid[row][col];
}
}
return dpTable[numRows - 1][numCols - 1];
};
最大网络秩
应用点
条条大路通罗马，如今高铁线路贯通南北
你在云南大理
我在首都北京
我们去过很多城市
高铁有很多个班次
请你告诉我
我们去过的所有城市
最大的网络秩
/**
* @param {number} n
* @param {number[][]} roads
* @return {number}
*/
var maximalNetworkRank = function(n, roads) {
let arr = new Array(n).fill(0).map(() => new Array(n).fill(0))
let degree = new Array(n).fill(0)
let max = 0
for(let item of roads){
arr[item[0]][item[1]] = true
arr[item[1]][item[0]] = true
degree[item[0]]++
degree[item[1]]++
}
for(let i=0;i<n;i++){
for(let j=i+1;j<n;j++){
let count = degree[i] + degree[j] - (arr[i][j] ? 1 : 0)
max = Math.max(max, count)
}
}
return max
};
总结
以上所有，我们介绍了三月度 LC 每日一题的部分题目，它们分别涉及到了这些问题
-
小数的进制问题 -
文件名重名问题 -
最大礼物价值问题 -
网路线路的最大联通数问题
