leetCode周赛95解题报告 javascript

白诗秀儿 关注

收藏于 : 2018-07-30 10:36   被转藏 : 1   

比赛地址

https://leetcode-cn.com/contest/weekly-contest-95

 

876. Middle of the Linked List

876. 链表的中间结点

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

 

示例 1:

输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2:

输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。

 

提示:

  • 给定链表的结点数介于 1 和 100 之间。

题解:快慢指针,快指针到尽头,慢指针是中间节点。

 

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    if (!head) {
        return head;
    }
    for (var p1 = head, p2 = head; true; p1 = p1.next, p2 = p2.next.next) {
        if (!p2.next) {
            return p1;
        }
        if (!p2.next.next) {
            return p1.next;
        }
    }
};

 

 

 

 

 

877. Stone Game

877. 石子游戏

亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行,每堆都有正整数颗石子 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的总数是奇数,所以没有平局。

亚历克斯和李轮流进行,亚历克斯先开始。 每回合,玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止,此时手中石子最多的玩家获胜。

假设亚历克斯和李都发挥出最佳水平,当亚历克斯赢得比赛时返回 true ,当李赢得比赛时返回 false 。

 

示例:

输入:[5,3,4,5]
输出:true
解释:
亚历克斯先开始,只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗,这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗,那么剩下的是 [4,5],亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗,那么剩下的是 [3,4],亚历克斯拿走后 4 颗赢得 9 分。
这表明,取前 5 颗石子对亚历克斯来说是一个胜利的举动,所以我们返回 true 。

 

提示:

  1. 2 <= piles.length <= 500
  2. piles.length 是偶数。
  3. 1 <= piles[i] <= 500
  4. sum(piles) 是奇数。

题解:递归模拟,双方都尝试取第一堆和最后一堆,使得自己的石头较多。man为玩家交替,1为先手-1为后手。

 

/**
 * @param {number[]} piles
 * @return {boolean}
 */
var stoneGame = function(piles) {
    var dfs = function(f, r, man) {
        if (f == r) {
            return man * piles[f];
        }
        var nextMan = -1 * man;
        var maxp = Math.max(piles[f] - nextMan * dfs(f + 1, r, nextMan), piles[r] - nextMan * dfs(f, r - 1, nextMan));
        return man * maxp;
    }
    return dfs(0, piles.length - 1, 1) > 0;
};

 以上解法可以计算出正确结果,但是会超时,实际中间结果会重复计算很多次,用cache保存已经计算过的结果,这个是递归优化的常用手段,由于递归本身的开销较大通常会慢些,但相比动态规划思路,自上而下的思考方式较简单易想到,时间复杂度是一样的,代码如下:

 

 

/**
 * @param {number[]} piles
 * @return {boolean}
 */
var stoneGame = function(piles) {
    var dfs = function(f, r, man) {
        if (f == r) {
            return man * piles[f];
        }
        var key = f + "," + r;
        if (!cache[key]) {
            var nextMan = -1 * man;
            var maxp = Math.max(piles[f] - nextMan * dfs(f + 1, r, nextMan), piles[r] - nextMan * dfs(f, r - 1, nextMan));
            cache[key] = man * maxp;
        }
        return cache[key];
    }
    var cache = {};
    return dfs(0, piles.length - 1, 1) > 0;
};

 

 

 

 

 

878. Nth Magical Number

878. 第 N 个神奇数字

如果正整数可以被 A 或 B 整除,那么它是神奇的。

返回第 N 个神奇数字。由于答案可能非常大,返回它模 10^9 + 7 的结果

 

示例 1:

输入:N = 1, A = 2, B = 3
输出:2

示例 2:

输入:N = 4, A = 2, B = 3
输出:6

示例 3:

输入:N = 5, A = 2, B = 4
输出:10

示例 4:

输入:N = 3, A = 6, B = 4
输出:8

 

提示:

  1. 1 <= N <= 10^9
  2. 2 <= A <= 40000
  3. 2 <= B <= 40000

思路:根据题意得出,以A、B的最小公倍数为一个循环,循环内包含所有不大于最小公倍数的所有A和B的倍数,求出循环次数加上最后一次循环的位置即为答案。

 

// 最大公约数
var gcd = function(a, b) {
    if (b) {
        return gcd(b, a % b);
    }
    return a;
}
/**
 * @param {number} N
 * @param {number} A
 * @param {number} B
 * @return {number}
 */
var nthMagicalNumber = function(N, A, B) {
    var cir = A * B / gcd(A, B); // 最小公倍数为一个循环
    var q = [];
    for (var i = A; i < cir; i += A) {
        q.push(i);
    }
    for (var i = B; i < cir; i += B) {
        q.push(i);
    }
    q.push(cir);
    q.sort((a,b)=>a-b);
    var cnt = q.length; // 一个循环的长度
    N--;
    var ans = Math.floor(N / cnt) * cir + q[N % cnt];
    return ans % (1e9 + 7);
};

 

 

 

 

 阅读文章全部内容  
点击查看
文章点评
相关文章
白诗秀儿 关注

文章收藏:1308

TA的最新收藏