[筆記] LeetCode 刷題記錄 (53,78,169,268)

章節連結

題目

53. Maximum Subarray
78. Subsets
169. Majority Element
268. Missing Number

歷次 LeetCode 刷題記錄

LeetCode 在需要接觸演算碼的工程師中，為相當知名的練習場所。當你有需要挑戰自己的腦筋、面試前的準備……等，都滿適合來這邊看一下你的演算法和資料結構的熟悉程度。這回要筆記的有：Maximum Subarray、Subsets、Majority Element 和 Missing Number。

題目

53. Maximum Subarray

[連結]：https://leetcode.com/problems/maximum-subarray/

/* 
*  1. 運用 Two Pointer 的概念：每次左右兩個相加若比新的 pointer 小，那 sum 就改以新 pointer 的值為新開始
*  2. 承上，由於 sum 的值會一直變動，故要新增一個 result 值來儲存每次 sum 的結果。當然的，在儲存到 result 前要再比一次大小
*/
var maxSubArray = function(nums) {
    let sum = nums[0]
    let result = nums[0]
    
    for(let i=1; i<nums.length; i++){
        let pointer = nums[i]
        sum = Math.max(sum+pointer,pointer)
        result = Math.max(result,sum)
    }
    
    return result
};

* 1. 運用 Two Pointer 的概念：每次左右兩個相加若比新的 pointer 小，那 sum 就改以新 pointer 的值為新開始

* 2. 承上，由於 sum 的值會一直變動，故要新增一個 result 值來儲存每次 sum 的結果。當然的，在儲存到 result 前要再比一次大小

var maxSubArray = function(nums) {

let sum = nums[0]

let result = nums[0]

for(let i=1; i<nums.length; i++){

let pointer = nums[i]

sum = Math.max(sum+pointer,pointer)

result = Math.max(result,sum)

}

return result

};

78. Subsets

[連結]：https://leetcode.com/problems/subsets/

/* 跑雙層 forEach，並推送其值到結果的 array 中 */
var subsets = function(nums) {
    let result = [[]]
    
    nums.forEach(num=>{
        /*相當於取出單一數字元素如 2*/
        result.forEach(d=>{
            /*相當於取出 [] 後，再解構造出新 array*/
            /*若取出[1]，則 [...d, num] 就如同 [1, 2], [1,3]*/
            result.push([...d, num])
        })
    })
    
    return result
};

/* 跑雙層 forEach，並推送其值到結果的 array 中 */

var subsets = function(nums) {

let result = [[]]

nums.forEach(num=>{

/*相當於取出單一數字元素如 2*/

result.forEach(d=>{

/*相當於取出 [] 後，再解構造出新 array*/

/*若取出[1]，則 [...d, num] 就如同 [1, 2], [1,3]*/

result.push([...d, num])

})

return result

};

169. Majority Element

[連結]：https://leetcode.com/problems/majority-element/

/* 
 *  1. 建立一個 hash map，來記錄出現次數
 *  2. 如果 result 的 value 計數 < counter 物件內單一組 key-value 對的 value 計數，那就將 result 的結果換成這一組 
 *  3. 回傳 result.key 就是答案
*/

var majorityElement = function(nums) {
    let counter = {}
    let result = {key:0, value:0}
    for(let i=0; i<nums.length;i++){
       if(!counter[nums[i]]){
           counter[nums[i]] = 1
       }else{
           counter[nums[i]] ++
       }
    }

    for(let [key, value] of Object.entries(counter)){
        if(value > result.value){
            result.key = key
            result.value = value
        }
    }
    
    return result.key;
};

* 1. 建立一個 hash map，來記錄出現次數

* 2. 如果 result 的 value 計數 < counter 物件內單一組 key-value 對的 value 計數，那就將 result 的結果換成這一組

* 3. 回傳 result.key 就是答案

var majorityElement = function(nums) {

let counter = {}

let result = {key:0, value:0}

for(let i=0; i<nums.length;i++){

if(!counter[nums[i]]){

counter[nums[i]] = 1

}else{

counter[nums[i]] ++

}

for(let [key, value] of Object.entries(counter)){

if(value > result.value){

result.key = key

result.value = value

}

return result.key;

};

268. Missing Number

[連結]：https://leetcode.com/problems/missing-number/

/* 
 *  1. 先將陣列排序
 *  2. 排除特殊狀況：長度為 1 的時候，輸出的值為 0 or 1、如果第一個不是 0 ，那輸出一定是 0
 *  3. 跑迴圈，如果 nums[i] !== i ，那就是輸出 index
 *  4. 如果完整跑完迴圈，則輸出 nums.length 
*/

var missingNumber = function(nums) {
    let result = undefined
    nums = nums.sort((a,b)=>a-b>0?1:-1);
    
    if(nums.length === 1){
        return nums[0] === 0 ? 1 : 0
    }

    if(nums[0] !== 0) return 0;
    
    for(let i=0; i<nums.length;i++){
        if(nums[i] !==i){
            return i
        }
    }
    
    if(!result){
        return nums.length;
    }
};