Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Sign up
Appearance settings

Commit 6447115

Browse files
feat: add some leetcode
1 parent d07b32b commit 6447115

9 files changed

+417
-0
lines changed
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
/*
2+
* @lc app=leetcode id=17 lang=typescript
3+
*
4+
* [17] Letter Combinations of a Phone Number
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* @description: 回溯的方式实现
10+
* 其中 m 是输入中对应 3 个字母的数字个数(包括数字 2、3、4、5、6、8),nn 是输入中对应 4 个字母的数字个数(包括数字 7、9)
11+
* 时间复杂度 O(3m * 4n)
12+
* 空间复杂度 O(m + n)
13+
* @param {string} digits
14+
* @return {string[]}
15+
*/
16+
function letterCombinations(digits: string): string[] {
17+
const map = {
18+
2: ['a', 'b', 'c'],
19+
3: ['d', 'e', 'f'],
20+
4: ['g', 'h', 'i'],
21+
5: ['j', 'k', 'l'],
22+
6: ['m', 'n', 'o'],
23+
7: ['p', 'q', 'r', 's'],
24+
8: ['t', 'u', 'v'],
25+
9: ['w', 'x', 'y', 'z'],
26+
};
27+
28+
const len = digits.length;
29+
// 特殊情况的处理
30+
if (len === 0) return [];
31+
32+
if (len === 1) return map[digits[0]];
33+
34+
const ans = [];
35+
/**
36+
* @description: 回溯函数
37+
* @param {string} str
38+
* @param {string[]} res
39+
* @param {number} len
40+
* @param {number} idx
41+
* @return {void}
42+
*/
43+
function backtrack(str: string, res: string[] = [], len: number, idx: number): void {
44+
if (str.length === len) {
45+
// 通过索引控制不同,因此不会有重复,可以直接添加
46+
res.push(str);
47+
return;
48+
}
49+
50+
for (let i = idx; i < len; i++) {
51+
const letterList = map[digits[i]];
52+
53+
// !回溯遍历,注意通过索引的变化来防止生成重复的结果
54+
letterList.forEach((letter) => {
55+
backtrack(str + letter, res, len, i + 1);
56+
});
57+
}
58+
}
59+
60+
// 执行回溯方法
61+
backtrack('', ans, len, 0);
62+
63+
return ans;
64+
}
65+
// @lc code=end

‎leetcode/401.binary-watch.ts

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/*
2+
* @lc app=leetcode id=401 lang=typescript
3+
*
4+
* [401] Binary Watch
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* @description: 其实也是回溯
10+
* 时间复杂度 O(1)
11+
* 空间复杂度 O(1)
12+
* @param {number} turnedOn
13+
* @return {string[]}
14+
*/
15+
function readBinaryWatch(turnedOn: number): string[] {
16+
/**
17+
* @description: 用转换二进制的方式得到开的灯的数量
18+
* @param {number} num
19+
* @return {number}
20+
*/
21+
function getTurnedOnLights(num: number): number {
22+
return num.toString(2).split('0').join('').length;
23+
}
24+
25+
const ans: string[] = [];
26+
27+
for (let h = 0; h < 12; h++) {
28+
for (let m = 0; m < 60; m++) {
29+
// !核心是想到这个方法
30+
if (getTurnedOnLights(h) + getTurnedOnLights(m) === turnedOn) {
31+
ans.push(h + ':' + (m < 10 ? '0' + m : m));
32+
}
33+
}
34+
}
35+
36+
return ans;
37+
}
38+
// @lc code=end
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/*
2+
* @lc app=leetcode id=435 lang=typescript
3+
*
4+
* [435] Non-overlapping Intervals
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* @description: 贪心算法的思路
10+
* @param {number[][]} intervals
11+
* @return {number}
12+
*/
13+
function eraseOverlapIntervals(intervals: number[][]): number {
14+
intervals.sort((a: number[], b: number[]) => {
15+
// 排序只需要排列右侧数,左侧数可以通过下面的遍历来排除
16+
return a[1] - b[1];
17+
});
18+
19+
let count = 1;
20+
let len = intervals.length;
21+
let i = 1;
22+
// 取出第一个右边的数
23+
let right = intervals[0][1];
24+
25+
while (i < len) {
26+
const [num, r] = intervals[i];
27+
// !如果左边的数比上一个右边数大或相等,就可以统计
28+
if (num >= right) {
29+
right = r;
30+
count++;
31+
}
32+
i++;
33+
}
34+
35+
return len - count;
36+
}
37+
// @lc code=end

‎leetcode/506.relative-ranks.ts

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
/*
2+
* @lc app=leetcode id=506 lang=typescript
3+
*
4+
* [506] Relative Ranks
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* @description: 排序并处理
10+
* @param {number} score
11+
* @return {string[]}
12+
*/
13+
function findRelativeRanks(score: number[]): string[] {
14+
const len = score.length;
15+
const rank = ['Gold Medal', 'Silver Medal', 'Bronze Medal'];
16+
const res = new Array(len);
17+
const arr = new Array(len).fill(0).map(() => new Array(2).fill(0));
18+
19+
// 保存索引和分值信息
20+
for (let i = 0; i < len; i++) {
21+
arr[i][0] = score[i];
22+
arr[i][1] = i;
23+
}
24+
25+
// 排序
26+
arr.sort((a, b) => b[0] - a[0]);
27+
28+
for (let i = 0; i < len; i++) {
29+
const [, idx] = arr[i];
30+
if (i <= 2) {
31+
res[idx] = rank[i];
32+
} else {
33+
res[idx] = i + 1 + '';
34+
}
35+
}
36+
37+
return res;
38+
}
39+
// @lc code=end

‎leetcode/680.valid-palindrome-ii.ts

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/*
2+
* @lc app=leetcode id=680 lang=typescript
3+
*
4+
* [680] Valid Palindrome II
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* @description: 贪心算法
10+
* 时间复杂度 O(n)
11+
* 空间复杂度 O(1)
12+
* @param {string} s
13+
* @return {boolean}
14+
*/
15+
function validPalindrome(s: string): boolean {
16+
/**
17+
* @description: 双指针检查是否是回文串
18+
* @param {string} str
19+
* @param {number} left
20+
* @param {number} right
21+
* @return {boolean}
22+
*/
23+
function checkPalindrome(str: string, left: number, right: number): boolean {
24+
for (let i = left, j = right; i < j; i++, j--) {
25+
if (str[i] !== str[j]) return false;
26+
}
27+
return true;
28+
}
29+
30+
// 双指针检查
31+
for (let i = 0, j = s.length - 1; i < j; i++, j--) {
32+
// !如果外侧两个不等而且内侧删除左边的字符或者右边的字符也不构成回文串就说明无法构成
33+
// 重点就是发现这个规律
34+
if (s[i] !== s[j]) {
35+
return checkPalindrome(s, i + 1, j) || checkPalindrome(s, i, j - 1);
36+
}
37+
}
38+
return true;
39+
}
40+
// @lc code=end
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
/*
2+
* @lc app=leetcode id=720 lang=javascript
3+
*
4+
* [720] Longest Word in Dictionary
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* @param {string[]} words
10+
* @return {string}
11+
*/
12+
var longestWord = function (words) {
13+
words.sort((a, b) => {
14+
if (a.length !== b.length) {
15+
return a.length - b.length;
16+
}
17+
return b.localeCompare(a);
18+
});
19+
20+
// 使用自动去重的 set 来保存对应字符
21+
const candidate = new Set();
22+
candidate.add('');
23+
let longest = '';
24+
25+
for (const word of words) {
26+
// 如果包含前面的字符,就加入
27+
if (candidate.has(word.slice(0, word.length - 1))) {
28+
candidate.add(word);
29+
longest = word;
30+
}
31+
}
32+
33+
return longest;
34+
};
35+
// @lc code=end
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/*
2+
* @lc app=leetcode id=720 lang=typescript
3+
*
4+
* [720] Longest Word in Dictionary
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* @description: 字典的方式
10+
* 也可以使用前缀表但实现起来代码量较多
11+
* @param {string[]} words
12+
* @return {string}
13+
*/
14+
function longestWord(words: string[]): string {
15+
// 让词组数组内的所有单词按照字符数和字母顺序排序
16+
words.sort((a: string, b: string) => {
17+
if (a.length !== b.length) {
18+
return a.length - b.length;
19+
}
20+
return b.localeCompare(a);
21+
});
22+
23+
// 使用自动去重的 set 来保存对应字符
24+
const candidate: Set<string> = new Set();
25+
candidate.add('');
26+
let longest = '';
27+
28+
for (const word of words) {
29+
// 如果包含前面的字符,就加入
30+
if (candidate.has(word.slice(0, word.length - 1))) {
31+
candidate.add(word);
32+
longest = word;
33+
}
34+
}
35+
36+
return longest;
37+
}
38+
// @lc code=end

‎leetcode/79.word-search.ts

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
/*
2+
* @lc app=leetcode id=79 lang=typescript
3+
*
4+
* [79] Word Search
5+
*/
6+
7+
// @lc code=start
8+
/**
9+
* @description: 回溯算法
10+
* 时间复杂度 O(MN*3L)
11+
* 空间复杂度 O(MN)
12+
* @param {string[][]} board
13+
* @param {string} word
14+
* @return {boolean}
15+
*/
16+
function exist(board: string[][], word: string): boolean {
17+
const DERICTIONS = [
18+
[1, 0],
19+
[-1, 0],
20+
[0, 1],
21+
[0, -1],
22+
];
23+
const m = board.length;
24+
const n = board[0].length;
25+
const len = word.length;
26+
// 存储访问的当前字母位置;
27+
const visited = new Array(m).fill(null).map(() => new Array(n));
28+
29+
/**
30+
* @description: 判断字符是否匹配
31+
* @param {number} i 遍历的行
32+
* @param {number} j 遍历的列
33+
* @param {number} k 匹配的字符长度
34+
* @return {boolean}
35+
*/
36+
function check(i: number, j: number, k: number): boolean {
37+
// 剔除两种特殊的场景,判定否和判断完全相等
38+
if (board[i][j] !== word[k]) return false;
39+
else if (k === len - 1) return true;
40+
41+
// 标记当前访问的字母,因为不允许重复使用
42+
visited[i][j] = true;
43+
44+
for (const [dx, dy] of DERICTIONS) {
45+
const newI = dx + i;
46+
const newJ = dy + j;
47+
48+
// 考虑矩形的边界场景,数组的界限
49+
if (newI >= 0 && newI < m && newJ >= 0 && newJ < n) {
50+
if (!visited[newI][newJ]) {
51+
// 如果没有标记过,检查四个方向上的字符是否满足
52+
const checked = check(newI, newJ, k + 1);
53+
// 如果满足,就可以直接返回结果
54+
if (checked) return checked;
55+
}
56+
}
57+
}
58+
59+
visited[i][j] = false;
60+
61+
return false;
62+
}
63+
64+
// 遍历每行每列,找出是否能够匹配的字符
65+
for (let i = 0; i < m; i++) {
66+
for (let j = 0; j < n; j++) {
67+
const checked = check(i, j, 0);
68+
if (checked) return true;
69+
}
70+
}
71+
72+
return false;
73+
}
74+
// @lc code=end

0 commit comments

Comments
(0)

AltStyle によって変換されたページ (->オリジナル) /