MiKin Blog

松岛川树

0%

发表于 分类于 ， ，

322. Coin Change

难度: Medium

刷题内容

原题连接

内容描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例1：

 输入: coins = [1, 2, 5], amount = 11
 输出: 3 
 解释: 11 = 5 + 5 + 1

示例2：

 输入: coins = [2], amount = 3
 输出: -1

说明

你可以认为每种硬币的数量是无限的。

解题方案

**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

动态规划，思路参考：链接

代码：

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
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */

var coinChange = function(coins, amount) {
  // 自底向上的动态规划
  if(coins.length === 0){
    return -1;
  }
  
  // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
  let memo = Array.from({ length: amount+1 });
  memo[0] = 0;
  for(let i = 1; i <= amount; i++){
    let min = Number.MAX_VALUE;
    for(let j = 0; j < coins.length; j++){
      if(i - coins[j] >= 0 && memo[i-coins[j]] < min){
        min = memo[i-coins[j]] + 1;
      }
    }
    // memo[i] = (min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min);
    memo[i] = min;
  }
  
  return memo[amount] === Number.MAX_VALUE ? -1 : memo[amount];
};

发表于 分类于 ， ，

0347. Top K Frequent Elements

难度: Medium

刷题内容

原题连接

内容描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

示例 2:

 输入: nums = [1], k = 1
 输出: [1]

解题方案

思路 1
**- 时间复杂度: O(N*k)**- 空间复杂度: O(N)**

利用原生的sort方法，

  1. 遍历原有数组，推导出每个数字出现的频率。
  2. 根据出现的频率，利用sort进行排序

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
  var list = {}
  if (nums.length === k) {
    return nums
  }
  while (nums.length) {
    var num = nums.pop()
    if (list[num]) {
      list[num]++
    } else {
      list[num] = 1
    }
  }
  
  return Object.keys(list).sort((a, b) => {
    return list[b] - list[a]
  }).slice(0, k).map(n => Number(n))
};

思路 2
**- 时间复杂度: O(N*k)**- 空间复杂度: O(N)**

自行实现的排序方式

  1. 遍历原有数组，推导出每个数字出现的频率。
  2. 利用快排实现排序
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
let partion = function(arr, left, right){
    let i = left;
    let j = right;
    let base = arr[left];
    while(i<j){
        while(arr[j].freq<=base.freq && i<j){
            j--;
        }
        while(arr[i].freq>=base.freq && i<j){
            i++;
        }
        let tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    arr[left] = arr[i];
    arr[i] = base;
    return i;
}

let quickSort = function(arr, left, right, k){
    if(left < right){
        let m = partion(arr, left, right);
        if(m<k-1){
            quickSort(arr, m+1, right, k);
        }else if(m>k-1){
            quickSort(arr, left, m-1, k);
        }
    }
}

let Node = function(val, freq){
    this.val = val;
    this.freq = freq;
}
var topKFrequent = function(nums, k) {
    let map = {};
    nums.forEach(e=>{
        if(map[e]){
            map[e].freq += 1;
        }else{
            map[e] = new Node(e, 1);
        }
    });
    let arr = [];
    for(let i in map){
        arr.push(map[i]);
    }
    quickSort(arr, 0, arr.length-1, k);
    let res = [];
    for(let i=0; i<k; i++){
        res.push(arr[i].val);
    }
    return res;
};

发表于 分类于 ， ，

402. Remove K Digits

难度: Medium

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.
Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

  • 使用栈的思路
  • 如果n是num的长度，我们要去除k个，那么需要剩下n-k个数，定义一个result数组用于保存剩下的字符，与result中最后一个字符相比，比它小，
  • 栈中最后一个字符出栈，该字符进栈，否则该字符直接进栈。值得注意的是在删除k个数之后，若剩下的数前面有0，应该去掉。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function(num, k) {
    let stack = [], numDigits = num.length;
    for (let i = 0; i < numDigits; i++) {
        while(k > 0 && stack.length && stack[stack.length - 1] > num[i]) {
            stack.pop();
            k--;
        }
        stack.push(num[i]);
    }
    stack = k > 0 ? stack.slice(0, -k) : stack;
    return stack.join('').replace(/^0+/, '') || '0';
};

发表于 分类于 ， ，

406. Queue Reconstruction By Height

难度: medium

刷题内容

原题连接

内容描述

假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。

注意：
总人数少于1100人。

示例 1:

1
2
3
4
5
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

解题方案

思路 1
**- 时间复杂度: O(N²)**- 空间复杂度: O(N)**

贪心算法
思路
个子矮的人的位置不会影响到其他人，他的位置不会影响到其他人。

操作步骤

  1. 对人群排序，由高到低，身高相同再由低到高
  2. 建立一个空队列
  3. 对排序后的人群进行遍历，将当前遍历的人 按照他的索引（n）插入到队列第n的位置

代码：

1
2
3
4
5
6
7
8
var reconstructQueue = function(people) {
  people.sort((a, b) => ((b[0] - a[0]) || (a[1] - b[1])));
  let queue = [];
  people.forEach(person => {
    queue.splice([person[1]], 0, person);
  })
  return queue
};

发表于 分类于 ， ，

485. Max Consecutive Ones

难度: Easy

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
10
11
12
Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.
Note:

The input array will only contain 0 and 1.
The length of input array is a positive integer and will not exceed 10,000

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

  • 使用temp保存每个0之间的差值
  • 找出最大的差值即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function(nums) {
    var max = 0,temp = 0;
    for(var i =0;i<nums.length;i++){
        nums[i]===0?temp=0:temp++;
        max = Math.max(temp,max);
    }
    return max;
};

发表于 分类于 ， ，

539. Minimum Time Difference

难度: Medium

刷题内容

原题连接

内容描述

1
2
3
4
5
6
7
8
9
Given a list of 24-hour clock time points in "Hour:Minutes" format, find the minimum minutes difference between any two time points in the list.

Example 1:
Input: ["23:59","00:00"]
Output: 1

Note:
The number of time points in the given list is at least 2 and won't exceed 20000.
The input time is legal and ranges from 00:00 to 23:59.

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

  • 将所有时间转换成分钟数，然后进行sort排序
  • 计算两个数之间的差值，找出最小差值即可
  • 不要忘记第一个时间与最后一个时间相比较

代码：

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
/**
 * @param {string[]} timePoints
 * @return {number}
 */
var findMinDifference = function(timePoints) {
    var dayTime = 24*60;
    var minTime = 24*60;
    var temp = timePoints.map(function (value) {
        var t = value.split(':');
        return parseInt(t[0])*60+parseInt(t[1]);
    });
    temp.sort(function (a,b) {
        return a-b;
    });
    for(var i =0;i<temp.length;i++){
        var diff;
        var f=i-1,b=i;
        if(i==0)
            f=temp.length-1;
        if((temp[f]-temp[b])>(dayTime/2)){
            diff = Math.abs(temp[f]-(temp[b]+dayTime));
            minTime = diff<minTime?diff:minTime;
        }else {
            diff = Math.abs(temp[f]-temp[b]);
            minTime = diff<minTime?diff:minTime;
        }
    }
    return minTime===1440?0:minTime;
};

发表于 分类于 ， ，

581. 最短无序连续子数组

难度: Easy

刷题内容

原题连接

内容描述

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

你找到的子数组应是最短的，请输出它的长度。

示例1:

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

说明 :

  1. 输入的数组长度范围在 [1, 10,000]。
  2. 输入的数组可能包含重复元素 ，所以升序的意思是<=。

解题方案

思路 1
**- 时间复杂度: O(1)**- 空间复杂度: O(N)**

省空间的算法，但是耗时间

每次循环，如果当前数组的第一位是最小值，则将其“弹出”；如果最后一位是最大值，则也将其“弹出”；如果以上两种情况都没有，则说明剩下的数组是最短无序连续子数组

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
  while (nums.length) {
    if (nums[0] === Math.min(...nums)) {
      nums.shift()
    } else if (nums[nums.length - 1] === Math.max(...nums)) {
      nums.pop()
    } else {
      return nums.length
    }
  }
  return nums.length
};

思路 2
**- 时间复杂度: O(1)**- 空间复杂度: O(2N)**

省时间的算法，但是耗空间

与上面方法比较，不用每次都计算最大值和最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var findUnsortedSubarray = function(nums) {
  const newNums = [...nums]
  nums.sort((a, b) => (a - b))
  let startIndex = 0
  let endIndex = 0
//   正向查找
  for (let i = 0; i < newNums.length; i++) {
    if (nums[0] === newNums[i]) {
      nums.shift()
    } else {
      break
    }
  }
//  逆向查找
  for (let j = newNums.length - 1; j > 0; j--) {
    if (nums[nums.length - 1] === newNums[j]) {
      nums.pop();
    } else {
      break
    }
  }
  return nums.length;
};

发表于 分类于 ， ，

881. Boats to Save People

难度: Medium

刷题内容

原题连接

内容描述

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
The i-th person has weight people[i], and each boat can carry a maximum weight of limit.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.  (It is guaranteed each person can be carried by a boat.)

 

Example 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
Example 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
Example 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
Note:

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000

解题方案

思路 1
**- 时间复杂度: O(N logN)**- 空间复杂度: O(N)**

  • 使用贪心算法，将数组进行排序之后进行处理

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function(people, limit) {
    people.sort(function (a,b) { return a-b });
    var num=0;
    for(var left = 0,right = people.length-1;right-left>=0;right--){
        if(people[left]+people[right]<=limit)
            left++;
        num++;
    }
    return num;
};

发表于 分类于 ， ，

997. Find The Town Judge

难度: Easy

刷题内容

原题连接

内容描述

在一个小镇里，按从 1 到 N 标记了 N 个人。传言称，这些人中有一个是小镇上的秘密法官。

如果小镇的法官真的存在，那么：

  1. 小镇的法官不相信任何人。
  2. 每个人（除了小镇法官外）都信任小镇的法官。
  3. 只有一个人同时满足属性 1 和属性 2 。

给定数组 trust，该数组由信任对 trust[i] = [a, b] 组成，表示标记为 a 的人信任标记为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份，请返回该法官的标记。否则，返回 -1。

示例 1：

1
2
输入：N = 2, trust = [[1,2]]
输出：2

示例 2：

1
2
输入：N = 3, trust = [[1,3],[2,3]]
输出：3

示例 3：

1
2
输入：N = 3, trust = [[1,3],[2,3],[3,1]]
输出：-1

示例 4：

1
2
输入：N = 3, trust = [[1,2],[2,3]]
输出：-1

示例 5：

1
2
输入：N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
输出：3

提示：

  1. 1 <= N <= 1000
  2. trust.length <= 10000
  3. trust[i] 是完全不同的
  4. trust[i][0] != trust[i][1]
  5. 1 <= trust[i][0], trust[i][1] <= N

解题方案

思路
- 时间复杂度: O(N)

- 空间复杂度: O(N)

利用trustedMap来存储“被信任者”的列表，数组下标代表村民的“标记”，数组元素的值代表“被多少人信任”。

利用trustOtherMap来存储“村民信任列表”，数组下标代表村民的“标记”，数组元素的值代表该村民“信任几个人”。

根据题目，每个人（除了小镇法官外）都信任小镇的法官。所以trustedMap中值为N-1的那个元素下标即是法官；但是小镇的法官不相信任何人。所以上一步得到的标记所在trustOtherMap的值一定是空。

执行用时 :136 ms, 在所有 JavaScript 提交中击败了**95.77%**的用户

内存消耗 :43.4 MB, 在所有 JavaScript 提交中击败了**68.00%**的用户

代码：

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
/**
 * @param {number} N
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function(N, trust) {
  let trustedMap = []
  let trustOtherMap = []
  if (N === 1 && trust.length === 0) {
    return 1
  }
  trust.forEach(([person, trustedPerson]) => {
    if (trustedMap[trustedPerson]) {
      trustedMap[trustedPerson]++
    } else {
      trustedMap[trustedPerson] = 1
    }
    if (trustOtherMap[person]) {
      trustOtherMap[person]++
    } else {
      trustOtherMap[person] = 1
    }
  })
  const trustedPerson = trustedMap.findIndex(i => i === (N - 1))
  if (trustedPerson !== -1 && !trustOtherMap[trustedPerson]) {
    return trustedPerson
  } else {
    return -1
  }
};

发表于 分类于 ， ，

1025. Divisor Game

难度: Esay

刷题内容

原题连接

https://leetcode-cn.com/problems/divisor-game/

内容描述

爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字N。
如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。

示例1:

 输入：2
 输出：true
 解释：爱丽丝选择 1，鲍勃无法进行操作。

示例2:

 输入：3
 输出：false
 解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。

解题方案

思路
**- 时间复杂度: O(1)**- 空间复杂度: O(1)**

1
2
3
4
5
6
7
/**
 * @param {number} N
 * @return {boolean}
 */
var divisorGame = function(N) {
    return N % 2 === 0; 
};