关于javascript:LeetCode-算法题系列第一周-25道

【算法进度 213/400 (〃’▽’〃)】，持续加油！

136. 只呈现一次的数字

给定一个非空整数数组，除了某个元素只呈现一次以外，其余每个元素均呈现两次。找出那个只呈现了一次的元素。

阐明：
你的算法应该具备线性工夫复杂度。你能够不应用额定空间来实现吗？

示例 1:

输出: [2,2,1]
输入: 1

示例 2:
输出: [4,1,2,1,2]
输入: 4

哈希表

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {let hash = {}
    for (let i = 0; i < nums.length; i++) {hash[nums[i]] ? hash[nums[i]]++ : hash[nums[i]] = 1
    }
    for (let j in hash) {if (hash[j] === 1) {return j}
    }
};

异或

var singleNumber = function (nums) {let ans = nums[0]
    for (let i = 1; i < nums.length; i++) {ans = ans ^ nums[i]
    }
    return ans
};

278. 第一个谬误的版本

你是产品经理，目前正在率领一个团队开发新的产品。可怜的是，你的产品的最新版本没有通过品质检测。因为每个版本都是基于之前的版本开发的，所以谬误的版本之后的所有版本都是错的。

假如你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个谬误的版本。
你能够通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个谬误的版本。你应该尽量减少对调用 API 的次数。

示例 1：输出：n = 5, bad = 4
输入：4
解释：调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个谬误的版本。示例 2：输出：n = 1, bad = 1
输入：1

二分法

var solution = function (isBadVersion) {return function (n) {
        let left = 1, right = n
        while (left < right) {const mid = Math.floor(left + (right - left) / 2)
            if (isBadVersion(mid)) {right = mid} else {left = mid + 1}
        }
        return left
    };
};

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜寻 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输出: nums = [-1,0,3,5,9,12], target = 9
输入: 4
解释: 9 呈现在 nums 中并且下标为 4

示例 2:

输出: nums = [-1,0,3,5,9,12], target = 2
输入: -1
解释: 2 不存在 nums 中因而返回 -1

提醒：你能够假如 nums 中的所有元素是不反复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。

二分法

var search = function (nums, target) {
    let low = 0, high = nums.length - 1
    while (low <= high) {const mid = Math.floor((high - low) / 2) + low
        const num = nums[mid]
        if (num === target) {return mid} else if (num > target) {high = mid - 1} else if (num < target) {low = mid + 1}
    }
    return -1
};

findIndex

var search = function(nums, target) {return nums.findIndex(v=>v===target)
};

indexOf

var search = function(nums, target) {return nums.indexOf(target)
};

for 循环

var search = function (nums, target) {for (let i = 0; i < nums.length; i++) {if(nums[i] === target) return i
    }
    return -1
};

35. 搜寻插入地位

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按程序插入的地位。

请必须应用工夫复杂度为 O(log n) 的算法。

示例 1:
输出: nums = [1,3,5,6], target = 5
输入: 2

示例 2:
输出: nums = [1,3,5,6], target = 2
输入: 1

示例 3:
输出: nums = [1,3,5,6], target = 7
输入: 4

示例 4:
输出: nums = [1,3,5,6], target = 0
输入: 0

示例 5:
输出: nums = [1], target = 0
输入: 0

提醒:

    1 <= nums.length <= 104
    -104 <= nums[i] <= 104
    nums 为无反复元素的升序排列数组
    -104 <= target <= 104

filter

var searchInsert = function (nums, target) {return nums.filter(v => v < target).length
};

二分法

var searchInsert = function (nums, target) {
    let len = nums.length
    if (len === 0) return 0
    let left = 0, right = len-1
    while (left < right) {// const mid = (left + right) >> 1
        const mid = Math.floor((right - left) / 2 + left)
        if (nums[mid] >= target) {right = mid} else if(nums[mid] < target) {left = mid + 1}
    }
    if (nums[right] < target) {return right + 1}
    return right
};

977. 有序数组的平方

给你一个按 非递加程序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递加程序 排序。

示例 1：输出：nums = [-4,-1,0,3,10]
输入：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：输出：nums = [-7,-3,2,3,11]
输入：[4,9,9,49,121]

提醒：1 <= nums.length <= 104
    -104 <= nums[i] <= 104
    nums 已按 非递加程序 排序
    
进阶：请你设计工夫复杂度为 O(n) 的算法解决本问题

双指针

var sortedSquares = function (nums) {let i = 0, j = nums.length - 1, res = [], k = nums.length - 1
    while (i <= j) {if (nums[i] * nums[i] > nums[j] * nums[j]) {res[k--] = nums[i] * nums[i++]
        } else {res[k--] = nums[j] * nums[j--]
        }
    }
    return res
};

reduce+sort

var sortedSquares = function (nums) {return nums.reduce((acc, prev) => acc.concat(prev * prev), []).sort((a,b)=>a-b)
};

896. 枯燥数列

如果数组是枯燥递增或枯燥递加的，那么它是枯燥的。如果对于所有 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 <= A.length <= 50000
    -100000 <= A[i] <= 100000

var isMonotonic = function (nums) {
    let inc =true,dec = true
    for(let i=0;i<nums.length;i++){if(nums[i+1]-nums[i]>0){dec = false}
        if(nums[i]-nums[i+1]>0){inc = false}
    }
    return dec || inc
};

941. 无效的山脉数组

给定一个整数数组 arr，如果它是无效的山脉数组就返回 true，否则返回 false。

让咱们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：

    arr.length >= 3
    在 0 < i < arr.length - 1 条件下，存在 i 使得：arr[0] < arr[1] < ... arr[i-1] < arr[i]
        arr[i] > arr[i+1] > ... > arr[arr.length - 1]

示例 1：输出：arr = [2,1]
输入：false

示例 2：输出：arr = [3,5,5]
输入：false

示例 3：输出：arr = [0,3,2,1]
输入：true

提醒：1 <= arr.length <= 104
    0 <= arr[i] <= 104

双指针

const validMountainArray = (A) => {
    const n = A.length;
    let i = 0;
    let j = n - 1;

    while (i + 1 < n && A[i] < A[i + 1]) {i++;}
    while (j - 1 >= 0 && A[j - 1] > A[j]) {j--;}
    if (i != 0 && i == j && j != n - 1) {return true;}
    return false;
};

167. 两数之和 II – 输出有序数组

给定一个已依照 非递加顺序排列 的整数数组 numbers，请你从数组中找出两个数满足相加之和等于指标数 target。

函数应该以长度为 2 的整数数组的模式返回这两个数的下标值。numbers 的下标 从 1 开始计数，所以答案数组该当满足 1 <= answer[0] < answer[1] <= numbers.length。

你能够假如每个输出 只对应惟一的答案，而且你 不能够 重复使用雷同的元素。

示例 1：输出：numbers = [2,7,11,15], target = 9
输入：[1,2]
解释：2 与 7 之和等于指标数 9。因而 index1 = 1, index2 = 2。示例 2：输出：numbers = [2,3,4], target = 6
输入：[1,3]

示例 3：输出：numbers = [-1,0], target = -1
输入：[1,2]

提醒：2 <= numbers.length <= 3 * 104
    -1000 <= numbers[i] <= 1000
    numbers 按 非递加程序 排列
    -1000 <= target <= 1000
    仅存在一个无效答案

双指针

var twoSum = function (numbers, target) {
    let i = 0, j = numbers.length-1;
    while (i <= j) {if (numbers[i] + numbers[j] > target) {j--} else if (numbers[i] + numbers[j] === target) {return [++i, ++j]
        } else {i++}
    }
};

1984. 学生分数的最小差值

给你一个 下标从 0 开始 的整数数组 nums，其中 nums[i] 示意第 i 名学生的分数。另给你一个整数 k。

从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化。
返回可能的 最小差值。

示例 1：输出：nums = [90], k = 1
输入：0
解释：选出 1 名学生的分数，仅有 1 种办法：- [90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2：输出：nums = [9,4,1,7], k = 2
输入：2
解释：选出 2 名学生的分数，有 6 种办法：- [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
- [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
- [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
- [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
可能的最小差值是 2

提醒：1 <= k <= nums.length <= 1000
    0 <= nums[i] <= 1

var minimumDifference = function (nums, k) {nums = nums.sort((a, b) => a - b)
    let ret = Infinity
    for (let i = 0; i + k - 1 < nums.length; i++) {if (nums[i + k - 1] - nums[i] < ret) {ret = nums[i + k - 1] - nums[i];
        }
    }
    return ret
};

1436. 旅行终点站

给你一份游览线路图，该线路图中的旅行线路用数组 paths 示意，其中 paths[i] = [cityAi, cityBi] 示意该线路将会从 cityAi 间接返回 cityBi。请你找出这次旅行的终点站，即没有任何能够通往其余城市的线路的城市。

题目数据保障线路图会造成一条不存在循环的线路，因而恰有一个旅行终点站。

示例 1：输出：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输入："Sao Paulo" 
解释：从 "London" 登程，最初到达终点站 "Sao Paulo"。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo"。示例 2：输出：paths = [["B","C"],["D","B"],["C","A"]]
输入："A"
解释：所有可能的线路是："D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
显然，旅行终点站是 "A"。示例 3：输出：paths = [["A","Z"]]
输入："Z"

提醒：1 <= paths.length <= 100
    paths[i].length == 2
    1 <= cityAi.length, cityBi.length <= 10
    cityAi != cityBi
    所有字符串均由大小写英文字母和空格字符组成。

Set

var destCity = function(paths) {let ans = new Set()
    for(let i of paths){ans.add(i[0])
    }
    for(let j  of paths){if(!ans.has(j[1])){return j[1]
        }
    }
    return ''
};

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 之间。

var middleNode = function(head) {
    let slow = head,fast = head;
    while(fast!==null && fast.next!==null){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow
};

374. 猜数字大小

374. 猜数字大小

猜数字游戏的规定如下：

每轮游戏，我都会从 1 到 n 随机抉择一个数字。请你猜选出的是哪个数字。如果你猜错了，我会通知你，你猜想的数字比我选出的数字是大了还是小了。

你能够通过调用一个事后定义好的接口 int guess(int num) 来获取猜想后果，返回值一共有 3 种可能的状况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。祝贺！你猜对了！pick == num

返回我选出的数字。

示例 1：输出：n = 10, pick = 6
输入：6

示例 2：输出：n = 1, pick = 1
输入：1

示例 3：输出：n = 2, pick = 1
输入：1

示例 4：输出：n = 2, pick = 2
输入：2

提醒：1 <= n <= 231 - 1
    1 <= pick <= n

二分法

var guessNumber = function (n) {
    let left = 1, right = n
    while (left < right) {const mid = Math.floor((right - left) / 2 + left)
        if (guess(mid) <= 0) {right = mid} else {left = mid + 1}
    }
    return left
};

405. 数字转换为十六进制数

405. 数字转换为十六进制数

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，咱们通常应用 补码运算 办法。

留神:

十六进制中所有字母 (a-f) 都必须是小写。十六进制字符串中不能蕴含多余的前导零。如果要转化的数为 0，那么以单个字符 '0' 来示意；对于其余状况，十六进制字符串中的第一个字符将不会是 0 字符。给定的数确保在 32 位有符号整数范畴内。不能应用任何由库提供的将数字间接转换或格式化为十六进制的办法。

示例 1：输出:
26

输入:
"1a"

示例 2：输出:
-1

输入:
"ffffffff"

var toHex = function (num) {const hex = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f']
    if (num === 0) {return '0'}
    let ans = "";
    if (num < 0) {num = Math.pow(2, 32) - Math.abs(num);
    }
    while (num) {ans += hex[num % 16];
        num = Math.floor(num / 16);
    }
    return ans.split("").reverse().join("");
};

643. 子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k。请你找出平均数最大且 长度为 k 的间断子数组，并输入该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：输出：nums = [1,12,-5,-6,50,3], k = 4
输入：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：输出：nums = [5], k = 1
输入：5.00000

提醒：n == nums.length
    1 <= k <= n <= 105
    -104 <= nums[i] <= 104

var findMaxAverage = function (nums, k) {let max = ans = [...nums].slice(0, k).reduce((acc, prev) => acc += prev);
    for (let i = 1; i <= nums.length - k; i++) {ans = ans - nums[i - 1] + nums[i + k - 1]
        max = Math.max(ans, max)
    }
    return max / k
};

283. 挪动零

给定一个数组 nums，编写一个函数将所有 0 挪动到数组的开端，同时放弃非零元素的绝对程序。

示例:
输出: [0,1,0,3,12]
输入: [1,3,12,0,0]

阐明:
    必须在原数组上操作，不能拷贝额定的数组。尽量减少操作次数。

var moveZeroes = function (nums) {
    let i = 0, j = 0;
    while (i < nums.length) {if (nums[i] != 0) {nums[j++] = nums[i]
        }
        i++
    }
    for (let a = j; a < nums.length; a++) {nums[a] = 0
    }
    return nums
};