leetCode周赛100解题报告 javascript

比赛地址：

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

 

896. 单调数列

896. Monotonic Array

如果数组是单调递增或单调递减的，那么它是单调的。

如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。

当给定的数组 A 是单调数组时返回 true，否则返回 false。

 

示例 1：

输入：[1,2,2,3]
输出：true

示例 2：

输入：[6,5,4,4]
输出：true

示例 3：

输入：[1,3,2]
输出：false

示例 4：

输入：[1,2,4,5]
输出：true

示例 5：

输入：[1,1,1]
输出：true

 

提示：

1. 1 <= A.length <= 50000
2. -100000 <= A[i] <= 100000

题解：循环两次分别判断是否递增或递减。

 

/**
 * @param {number[]} A
 * @return {boolean}
 */
var isMonotonic = function(A) {
    var n = A.length;
    var i;
    for (i = 1; i < n; i++) {
        if (A[i] < A[i - 1]) {
            break;
        }
    }
    if (i == n) {
        return true;
    }
    for (i = 1; i < n; i++) {
        if (A[i] > A[i - 1]) {
            break;
        }
    }
    if (i == n) {
        return true;
    }
    return false;
};

 

 

 

 

 

897. 递增顺序查找树

897. Increasing Order Search Tree

给定一个二叉树，重新排列树，使树中的最小值现在是树的根结点，并且每个结点没有左子结点，只有一个右子结点。

 

示例 ：

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9  

 

提示：

1. 给定树中的结点数介于 1 和 100 之间。
2. 每个结点都有一个从 0 到 1000 范围内的唯一整数值。

题解：中序遍历依次生成新树。

 

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var increasingBST = function(root) {
    var dfs = function(node) {
        if (!node) {
            return;
        }
        dfs(node.left);
        p.right = new TreeNode(node.val);
        p = p.right;
        dfs(node.right);
    }
    var head = new TreeNode(0);
    var p = head;
    dfs(root);
    return head.right;
};

 

 

 

 

 

898. 子数组按位或操作

898. Bitwise ORs of Subarrays

我们有一个非负整数数组 A。

对于每个（连续的）子数组 B = [A[i], A[i+1], ..., A[j]] （ i <= j），我们对 B 中的每个元素进行按位或操作，获得结果 A[i] | A[i+1] | ... | A[j]。

返回可能结果的数量。 （多次出现的结果在最终答案中仅计算一次。）

 

示例 1：

输入：[0]
输出：1
解释：
只有一个可能的结果 0 。

示例 2：

输入：[1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。

示例 3：

输入：[1,2,4]
输出：6
解释：
可能的结果是 1，2，3，4，6，以及 7 。

 

提示：

1. 1 <= A.length <= 50000
2. 0 <= A[i] <= 10^9

题解：遍历A[i]时，用一个集合pre记录前面所有子数组的或操作的结果。

 

/**
 * @param {number[]} A
 * @return {number}
 */
var subarrayBitwiseORs = function(A) {
    var s = new Set();
    var pre = new Set();
    for (var i = 0; i < A.length; i++) {
        s.add(A[i]);
        var newPre = new Set();
        newPre.add(A[i]);
        for (var p of pre) {
            var newNum = (p | A[i])
            newPre.add(newNum);
            s.add(newNum);
        }
        pre = newPre;
    }
    return s.size;
};

 

 

 

 

 

899. 有序队列

899. Orderly Queue

给出了一个由小写字母组成的字符串 S。然后，我们可以进行任意次数的移动。

在每次移动中，我们选择前 K 个字母中的一个（从左侧开始），将其从原位置移除，并放置在字符串的末尾。

返回我们在任意次数的移动之后可以拥有的按字典顺序排列的最小字符串。

 

示例 1：

输入：S = "cba", K = 1
输出："acb"
解释：
在第一步中，我们将第一个字符（“c”）移动到最后，获得字符串 “bac”。
在第二步中，我们将第一个字符（“b”）移动到最后，获得最终结果 “acb”。

示例 2：

输入：S = "baaca", K = 3
输出："aaabc"
解释：
在第一步中，我们将第一个字符（“b”）移动到最后，获得字符串 “aacab”。
在第二步中，我们将第三个字符（“c”）移动到最后，获得最终结果 “aaabc”。

 

提示：

1. 1 <= K <= S.length <= 1000
2. S 只由小写字母组成。

题解：一开始用队列进行广度遍历所有可能的变化字符串，超时了。然后打了个补丁：K>1时直接返回所有字母组合的最小字典序，AC了，感谢上帝。

 

/**
 * @param {string} S
 * @param {number} K
 * @return {string}
 */
var orderlyQueue = function(S, K) {
    if (K > 1) {
        var s = S.split("");
        s.sort();
        return s.join("");
    }
    var sSet = new Set();
    var q = [S];
    while(q.length > 0) {
        var s = q.shift();
        sSet.add(s);
        for (var i = 0; i < K; i++) {
            var sub = s.substring(0, i) + s.substring(i + 1) + s[i];
            if (!sSet.has(sub)) {
                q.push(sub);
            }
        }
    }
    var arr = Array.from(sSet);
    arr.sort();
    return arr[0];
};