0%

233. 数字 1 的个数

难度困难303收藏分享切换为英文接收动态反馈

给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1:

1
2
输入:n = 13
输出:6

示例 2:

1
2
输入:n = 0
输出:0

提示:

  • 0 <= n <= 2 * 109

Solution

拿到题目很奇怪,这道题暴力解答也就是个稍稍大于o(n)的复杂度,作为hard题目出现,只能说明暴力会超时

那么先回顾一下整体的超时代码段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {number} n
* @return {number}
*/
var countDigitOne = function (n) {
let counter = 0;
for (let i = n; i > 0; i--) {
let num = i;
while (num > 0) {
if (num % 10 === 1) {
counter++;
}
num = Math.floor(num / 10);
}
}
return counter
};

超时之后我就开始找规律,个位1只会出现1次,十位只会出现10次,百位是100次,之后是数学方法就不解了(懒orz),答案的主要部分

1
2
3
4
for (let k = 0; n >= mulk; ++k) {
ans += (Math.floor(n / (mulk * 10))) * mulk + Math.min(Math.max(n % (mulk * 10) - mulk + 1, 0), mulk);
mulk *= 10;
}

133. 克隆图

难度中等390收藏分享切换为英文接收动态反馈

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 valint) 和其邻居的列表(list[Node])。

Solution

dfs就可以解决

题目提供了索引就是val,所以map的key可以使用val来简化体积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* // Definition for a Node.
* function Node(val, neighbors) {
* this.val = val === undefined ? 0 : val;
* this.neighbors = neighbors === undefined ? [] : neighbors;
* };
*/

/**
* @param {Node} node
* @return {Node}
*/
var cloneGraph = function (node) {
if (!node) return;
let isVisit = new Map();
//dfs
const dfs = function (item) {
const newNode = new Node(item.val);
isVisit.set(item.val, newNode);
// console.log('isVist===>',isVisit)
// deep clone
for (let neighbor of item.neighbors) {
if (!isVisit.has(neighbor.val)) {
dfs(neighbor);
}
newNode.neighbors.push(isVisit.get(neighbor.val))
}
}
dfs(node);
return isVisit.get(node.val);
};

611. 有效三角形的个数

难度中等230收藏分享切换为英文接收动态反馈

给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

1
2
3
4
5
6
7
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

  1. 数组长度不超过1000。
  2. 数组里整数的范围为 [0, 1000]。

Solution

排序后根据,a+b>c 套两层for循环确定ab,理论上还可以再套一层for循环确定c,但是复杂度太高,达到o(n^3)的复杂度,我们可以通过二分法,找到a+bc的极限值,极限左边都是符合要求的数据,从而n降为lgn的复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @param {number[]} nums
* @return {number}
*/
var triangleNumber = function(nums) {
if (nums.length < 3) return 0;
let ans = 0;
nums = nums.sort();
for (let i = 0; i < nums.length ; i++) {
for (let j = i + 1; j < nums.length ; j++) {
// 二分
let left = j + 1, right = nums.length - 1, k = j;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] < nums[i] + nums[j]) {
k = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
ans += k - j;
}
}
return ans;
};

581. 最短无序连续子数组

难度中等609收藏分享切换为英文接收动态反馈

给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组,并输出它的长度。

示例 1:

1
2
3
输入:nums = [2,6,4,8,10,9,15]
输出:5
解释:你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。

示例 2:

1
2
输入:nums = [1,2,3,4]
输出:0

示例 3:

1
2
输入:nums = [1]
输出:0

提示:

  • 1 <= nums.length <= 104
  • -105 <= nums[i] <= 105

进阶:你可以设计一个时间复杂度为 O(n) 的解决方案吗?

Solution

目前想到的方法

  • 偏数学,找到最大最小值为界
  • 排序找差别,确定子数组两边下标
  • 排序后用二分(稍微提升)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @return {number}
*/
var findUnsortedSubarray = function (nums) {
let start, end = -1, point = 0;
let max = -100000, min = 10000;//题目给的大小区间
while (point < nums.length) {
// 找分界点
max > nums[point] ? end = point : max = nums[point]
min < nums[nums.length - point - 1] ? start = nums.length - point - 1 : min = nums[nums.length - point - 1]
point++;
}
return end === -1 ? 0 : end - start + 1;
};

743. 网络延迟时间

难度中等371收藏分享切换为英文接收动态反馈

n 个网络节点,标记为 1n

给你一个列表 times,表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi),其中 ui 是源节点,vi 是目标节点, wi 是一个信号从源节点传递到目标节点的时间。

现在,从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1

示例 1:

img

1
2
输入:times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出:2

示例 2:

1
2
输入:times = [[1,2,1]], n = 2, k = 1
输出:1

示例 3:

1
2
输入:times = [[1,2,1]], n = 2, k = 2
输出:-1

提示:

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • 所有 (ui, vi) 对都 互不相同(即,不含重复边)

Solution

明显的思路,

  • Dijkstra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var networkDelayTime = function (times, n, k) {
const INF = Number.MAX_SAFE_INTEGER;// max value
const g = new Array(n).fill(INF).map(() => new Array(n).fill(INF));
for (const t of times) {
const x = t[0] - 1, y = t[1] - 1;
g[x][y] = t[2];// 赋值
}

const dist = new Array(n).fill(INF);//distance
dist[k - 1] = 0;//k 本身为0
const used = new Array(n).fill(false);//遍历标记
for (let i = 0; i < n; ++i) {//遍历每个顶点
let x = -1;
for (let y = 0; y < n; ++y) {
// 未标记过并且(x为-1 或者 y的距离小于x的距离) 准备需要更新的节点
if (!used[y] && (x === -1 || dist[y] < dist[x])) {
x = y;
}
}
used[x] = true;//遍历标记
for (let y = 0; y < n; ++y) {
// k到x的最小值
dist[y] = Math.min(dist[y], dist[x] + g[x][y]);
}
}

let ans = Math.max(...dist);//最小值的最大值
return ans === INF ? -1 : ans;
};
console.log(networkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2))

前几天面试官说mongodb5出了事务,就赶紧来看看,毕竟业务层处理还是挺麻烦的,以前只支持操作的原子性

144. 二叉树的前序遍历

总体思路递归,easy等级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var preorderTraversal = function (root) {
const ans = [];
recursion(root, ans);
return ans
};
function recursion(root, ans) {
if (root === null) return;
ans.push(root.val);
recursion(root.left, ans)
recursion(root.right, ans)
}

Leetcode 671

671. 二叉树中第二小的节点

难度简单198收藏分享切换为英文接收动态反馈

给定一个非空特殊的二叉树,每个节点都是正数,并且每个节点的子节点数量只能为 20。如果一个节点有两个子节点的话,那么该节点的值等于两个子节点中较小的一个。

更正式地说,root.val = min(root.left.val, root.right.val) 总成立。

给出这样的一个二叉树,你需要输出所有节点中的第二小的值。如果第二小的值不存在的话,输出 -1

示例 1:

img

1
2
3
输入:root = [2,2,5,null,null,5,7]
输出:5
解释:最小的值是 2 ,第二小的值是 5 。

示例 2:

img

1
2
3
输入:root = [2,2,2]
输出:-1
解释:最小的值是 2, 但是不存在第二小的值。

提示:

  • 树中节点数目在范围 [1, 25]
  • 1 <= Node.val <= 231 - 1
  • 对于树中每个节点 root.val == min(root.left.val, root.right.val)

Solution

如题意,父节点就是最小值,借鉴了答案,递归条件写错了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var findSecondMinimumValue = function (root) {

let ans = -1;
const parentValue = root.val;//root value

const dfs = (node) => {
if (node === null) {
return;
}
if (ans !== -1 && node.val >= ans) {
return;
}
if (node.val > parentValue) {
ans = node.val;
}
dfs(node.left);
dfs(node.right);
}

dfs(root);
return ans;
};

#Leetcode-1109. 航班预订统计

难度中等157收藏分享切换为英文接收动态反馈

这里有 n 个航班,它们分别从 1n 进行编号。

有一份航班预订表 bookings ,表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firstilasti包含 firstilasti )的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer,其中 answer[i] 是航班 i 上预订的座位总数。

示例 1:

1
2
3
4
5
6
7
8
9
输入:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出:[10,55,45,25,25]
解释:
航班编号 1 2 3 4 5
预订记录 1 : 10 10
预订记录 2 : 20 20
预订记录 3 : 25 25 25 25
总座位数: 10 55 45 25 25
因此,answer = [10,55,45,25,25]

示例 2:

1
2
3
4
5
6
7
8
输入:bookings = [[1,2,10],[2,2,15]], n = 2
输出:[10,25]
解释:
航班编号 1 2
预订记录 1 : 10 10
预订记录 2 : 15
总座位数: 10 25
因此,answer = [10,25]

提示:

  • 1 <= n <= 2 * 104
  • 1 <= bookings.length <= 2 * 104
  • bookings[i].length == 3
  • 1 <= firsti <= lasti <= n
  • 1 <= seatsi <= 104

Solution

题目到是很简单,主要做的就是一维数组做个累加,时间复杂度O(N^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
var corpFlightBookings = function (bookings, n) {
const answer = [];
for (let i = 0; i < n; i++)answer.push(0);
for (let item of bookings) {
const [first, last, seats] = item;
for (let j = first; j <= last; j++) {
answer[j-1] += seats;
}
}
return answer;

};
console.log(corpFlightBookings([[1, 2, 10], [2, 3, 20], [2, 5, 25]], 5))

但是时间只超过了50%,就考虑问题

问题应该在O^2的复杂度上

后来想遍历的时候

  • Array(n).fill(0) 代码更优美
  • 增量加在数组里,最后走for循环跑一次就可以降一层for循环
1
2
3
const [first, last, seats] = item;
answer[first - 1] += seats;
if (last < n) answer[last] -= seats;

LeetCode:剑指 Offer 53

打开网页,突然看到日推是easy难度,本来想就几行代码的事情,弄完了就休息了,提交后–傻了眼–:cry:,居然只打败了6.27%的人,草率了

题目:

剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

限制:

0 <= 数组长度 <= 50000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// first commit
// 执行用时:2 ms, 在所有 Java 提交中击败了6.27%的用户
// 内存消耗:40.8 MB, 在所有 Java 提交中击败了98.84%的用户
class Solution {
public int search(int[] nums, int target) {
if(nums==null||nums.length<0){
return 0;
}
int count = 0;
for (Integer num : nums) {
if(num>target)break;
if (target == num)
count++;
}
return count;
}
}

找到了耗时1ms的答案一看,是foreach替换成了for循环 果然下标访问更快一些

以下贴一个最优解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int search(int[] nums, int target) {
// 就是left right 更快的定位,总体复杂度差不多,不过
int left = getRight(nums,target-1);
int right = getRight(nums,target);
return right-left;

}
public int getRight(int[] nums ,int target){
int left = 0;
int right = nums.length-1;

while(left<=right){
int mid = (left+right)/2;
if(nums[mid]>target){
right = mid-1;
}
else if(nums[mid]<=target){
left = mid + 1;
}
}
return left;
}

}