461b2aa2700847499fc881829a8ef9f7.jpg

【算法進(jìn)度 213/400 (〃'▽'〃)】，繼續(xù)加油芋浮！

136. 只出現(xiàn)一次的數(shù)字

給定一個(gè)非空整數(shù)數(shù)組威沫，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次伤哺。找出那個(gè)只出現(xiàn)了一次的元素燕侠。

說明：
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度者祖。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

示例 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. 第一個(gè)錯(cuò)誤的版本

你是產(chǎn)品經(jīng)理绢彤，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開發(fā)新的產(chǎn)品七问。不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測(cè)茫舶。由于每個(gè)版本都是基于之前的版本開發(fā)的械巡，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的。

假設(shè)你有 n 個(gè)版本 [1, 2, ..., n]饶氏，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本讥耗。
你可以通過調(diào)用 bool isBadVersion(version) 接口來判斷版本號(hào) version 是否在單元測(cè)試中出錯(cuò)。實(shí)現(xiàn)一個(gè)函數(shù)來查找第一個(gè)錯(cuò)誤的版本疹启。你應(yīng)該盡量減少對(duì)調(diào)用 API 的次數(shù)古程。

示例 1：
輸入：n = 5, bad = 4
輸出：4
解釋：
調(diào)用 isBadVersion(3) -> false 
調(diào)用 isBadVersion(5) -> true 
調(diào)用 isBadVersion(4) -> true
所以，4 是第一個(gè)錯(cuò)誤的版本喊崖。

示例 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. 二分查找

給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target 挣磨，寫一個(gè)函數(shù)搜索 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)荤懂，否則返回 -1趋急。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4

示例 2:

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

提示：

    你可以假設(shè) nums 中的所有元素是不重復(fù)的。
    n 將在 [1, 10000]之間势誊。
    nums 的每個(gè)元素都將在 [-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循環(huán)

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

35. 搜索插入位置

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值粟耻，并返回其索引查近。如果目標(biāo)值不存在于數(shù)組中，返回它將會(huì)被按順序插入的位置挤忙。

請(qǐng)必須使用時(shí)間復(fù)雜度為 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 為無重復(fù)元素的升序排列數(shù)組
    -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. 有序數(shù)組的平方

給你一個(gè)按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個(gè)數(shù)字的平方 組成的新數(shù)組册烈，要求也按 非遞減順序 排序戈泼。

示例 1：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后，數(shù)組變?yōu)?[16,1,0,9,100]
排序后赏僧，數(shù)組變?yōu)?[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 已按 非遞減順序 排序
    
進(jìn)階：

    請(qǐng)你設(shè)計(jì)時(shí)間復(fù)雜度為 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. 單調(diào)數(shù)列

如果數(shù)組是單調(diào)遞增或單調(diào)遞減的大猛，那么它是單調(diào)的。如果對(duì)于所有 i <= j淀零，A[i] <= A[j]挽绩，那么數(shù)組 A 是單調(diào)遞增的。 如果對(duì)于所有 i <= j驾中，A[i]> = A[j]唉堪，那么數(shù)組 A 是單調(diào)遞減的模聋。當(dāng)給定的數(shù)組 A 是單調(diào)數(shù)組時(shí)返回 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. 有效的山脈數(shù)組

給定一個(gè)整數(shù)數(shù)組 arr链方，如果它是有效的山脈數(shù)組就返回 true，否則返回 false灶搜。

讓我們回顧一下侄柔，如果 A 滿足下述條件，那么它是一個(gè)山脈數(shù)組：

    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. 兩數(shù)之和 II - 輸入有序數(shù)組

給定一個(gè)已按照 非遞減順序排列 的整數(shù)數(shù)組 numbers 暂题，請(qǐng)你從數(shù)組中找出兩個(gè)數(shù)滿足相加之和等于目標(biāo)數(shù) target 。

函數(shù)應(yīng)該以長(zhǎng)度為 2 的整數(shù)數(shù)組的形式返回這兩個(gè)數(shù)的下標(biāo)值究珊。numbers 的下標(biāo) 從 1 開始計(jì)數(shù) 薪者，所以答案數(shù)組應(yīng)當(dāng)滿足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假設(shè)每個(gè)輸入 只對(duì)應(yīng)唯一的答案 剿涮，而且你 不可以 重復(fù)使用相同的元素言津。

示例 1：
輸入：numbers = [2,7,11,15], target = 9
輸出：[1,2]
解釋：2 與 7 之和等于目標(biāo)數(shù) 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
    僅存在一個(gè)有效答案

雙指針

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. 學(xué)生分?jǐn)?shù)的最小差值

給你一個(gè) 下標(biāo)從 0 開始 的整數(shù)數(shù)組 nums 悬槽，其中 nums[i] 表示第 i 名學(xué)生的分?jǐn)?shù)。另給你一個(gè)整數(shù) k 瞬浓。

從數(shù)組中選出任意 k 名學(xué)生的分?jǐn)?shù)初婆，使這 k 個(gè)分?jǐn)?shù)間 最高分 和 最低分 的 差值 達(dá)到 最小化 。
返回可能的 最小差值 猿棉。

示例 1：

輸入：nums = [90], k = 1
輸出：0
解釋：選出 1 名學(xué)生的分?jǐn)?shù)磅叛，僅有 1 種方法：
- [90] 最高分和最低分之間的差值是 90 - 90 = 0
可能的最小差值是 0

示例 2：
輸入：nums = [9,4,1,7], k = 2
輸出：2
解釋：選出 2 名學(xué)生的分?jǐn)?shù)，有 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. 旅行終點(diǎn)站

給你一份旅游線路圖萨赁，該線路圖中的旅行線路用數(shù)組 paths 表示弊琴，其中 paths[i] = [cityAi, cityBi] 表示該線路將會(huì)從 cityAi 直接前往 cityBi 。請(qǐng)你找出這次旅行的終點(diǎn)站杖爽，即沒有任何可以通往其他城市的線路的城市敲董。

題目數(shù)據(jù)保證線路圖會(huì)形成一條不存在循環(huán)的線路，因此恰有一個(gè)旅行終點(diǎn)站慰安。

示例 1：
輸入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
輸出："Sao Paulo" 
解釋：從 "London" 出發(fā)腋寨，最后抵達(dá)終點(diǎn)站 "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". 
顯然精置，旅行終點(diǎn)站是 "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. 鏈表的中間結(jié)點(diǎn)

給定一個(gè)頭結(jié)點(diǎn)為 head 的非空單鏈表脂倦，返回鏈表的中間結(jié)點(diǎn)。

如果有兩個(gè)中間結(jié)點(diǎn)元莫，則返回第二個(gè)中間結(jié)點(diǎn)赖阻。

示例 1：
輸入：[1,2,3,4,5]
輸出：此列表中的結(jié)點(diǎn) 3 (序列化形式：[3,4,5])
返回的結(jié)點(diǎn)值為 3 。 (測(cè)評(píng)系統(tǒng)對(duì)該結(jié)點(diǎn)序列化表述是 [3,4,5])踱蠢。
注意火欧，我們返回了一個(gè) ListNode 類型的對(duì)象 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]
輸出：此列表中的結(jié)點(diǎn) 4 (序列化形式：[4,5,6])
由于該列表有兩個(gè)中間結(jié)點(diǎn)茎截，值分別為 3 和 4苇侵，我們返回第二個(gè)結(jié)點(diǎn)。

提示：
    給定鏈表的結(jié)點(diǎn)數(shù)介于 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. 猜數(shù)字大小

374. 猜數(shù)字大小

猜數(shù)字游戲的規(guī)則如下：
每輪游戲榆浓，我都會(huì)從 1 到 n 隨機(jī)選擇一個(gè)數(shù)字。 請(qǐng)你猜選出的是哪個(gè)數(shù)字撕攒。
如果你猜錯(cuò)了陡鹃，我會(huì)告訴你，你猜測(cè)的數(shù)字比我選出的數(shù)字是大了還是小了抖坪。

你可以通過調(diào)用一個(gè)預(yù)先定義好的接口 int guess(int num) 來獲取猜測(cè)結(jié)果萍鲸，返回值一共有 3 種可能的情況（-1，1 或 0）：
-1：我選出的數(shù)字比你猜的數(shù)字小 pick < num
1：我選出的數(shù)字比你猜的數(shù)字大 pick > num
0：我選出的數(shù)字和你猜的數(shù)字一樣擦俐。恭喜脊阴！你猜對(duì)了！pick == num

返回我選出的數(shù)字蚯瞧。

示例 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. 數(shù)字轉(zhuǎn)換為十六進(jìn)制數(shù)

405. 數(shù)字轉(zhuǎn)換為十六進(jìn)制數(shù)

給定一個(gè)整數(shù)蹬叭，編寫一個(gè)算法將這個(gè)數(shù)轉(zhuǎn)換為十六進(jìn)制數(shù)。對(duì)于負(fù)整數(shù)状知，我們通常使用 補(bǔ)碼運(yùn)算 方法秽五。

注意:

十六進(jìn)制中所有字母(a-f)都必須是小寫。
十六進(jìn)制字符串中不能包含多余的前導(dǎo)零饥悴。如果要轉(zhuǎn)化的數(shù)為0坦喘，那么以單個(gè)字符'0'來表示；對(duì)于其他情況西设，十六進(jìn)制字符串中的第一個(gè)字符將不會(huì)是0字符瓣铣。 
給定的數(shù)確保在32位有符號(hào)整數(shù)范圍內(nèi)。
不能使用任何由庫(kù)提供的將數(shù)字直接轉(zhuǎn)換或格式化為十六進(jìn)制的方法贷揽。

示例 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. 子數(shù)組最大平均數(shù) I

給你一個(gè)由 n 個(gè)元素組成的整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 棠笑。請(qǐng)你找出平均數(shù)最大且 長(zhǎng)度為 k 的連續(xù)子數(shù)組，并輸出該最大平均數(shù)禽绪。

任何誤差小于 10-5 的答案都將被視為正確答案蓖救。

示例 1：
輸入：nums = [1,12,-5,-6,50,3], k = 4
輸出：12.75
解釋：最大平均數(shù) (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. 移動(dòng)零

給定一個(gè)數(shù)組 nums洪规，編寫一個(gè)函數(shù)將所有 0 移動(dòng)到數(shù)組的末尾，同時(shí)保持非零元素的相對(duì)順序循捺。

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

說明:
    必須在原數(shù)組上操作斩例，不能拷貝額外的數(shù)組。
    盡量減少操作次數(shù)从橘。

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