leetCodeウィーク95問題解決報告javascript

もっと読む
競技の住所
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 。

 
ヒント:

2 <= piles.length <= 500

piles.length は偶数です

1 <= piles[i] <= 500

sum(piles) 奇数です

再帰的に模擬して、双方は第一の山と最後の山を取ってみて、自分の石を多くさせます.マンはプレイヤー交代で、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 <= N <= 10^9

2 <= A <= 40000

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);
};