🌹 喇賽的人 Blog 🌹

🌹 喇低喇賽 🌹

0%

貪心問題

亂寫於 Disqus：
廢話字數： 2.9k 所需傷眼時間 ≈ 3 分鐘

 

LeetCode 122 買賣股票的最佳時機 II

給你一個整數陣列 prices ，其中 prices[i] 表示某檔股票第 i 天的價格。
在每一天，你可以決定是否購買和/或出售股票。你在任何時候 最多 只能持有 一股 股票。你也可以先購買，然後在 同一天 出售。
返回 你能獲得的 最大 利潤 。

prices[j] - prices[i]
prices[j] => 賣出
prices[i] => 買入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// [-6, 4, 5, -7, 3, -2]
maxProfit([7,1,5,10,3,6,4])

var maxProfit = function(prices) {
	//計算每天賣出的價格
	let nums = []
	for(let i = 0, j = 1; i < prices.length - 1;i++,j++)
		nums.push(prices[j] - prices[i])

	console.log(nums)

	//只取正數
	let sum = 0;
	for(let i = 0; i < nums.length; i++)
		if(nums[i] > 0) sum += nums[i]

	return sum;
}

精簡化, 這裡用 Math.max 塞零進去,正數直接往上加, 負數就直接給零

1
2
3
4
5
6
7
8
9
var maxProfit = function(prices) {
	//計算每天賣出的價格
	let nums = []
	let result = 0
	for(let i = 0, j = 1; i < prices.length - 1;i++,j++)
		result += Math.max(prices[j] - prices[i], 0)

	return result;
}

LeetCode 55 CanJump

1
2
3
4
5
6
7
8
9
var canJump = function(nums) {
    if (nums.length == 1) return true;
	let cover = 0;
	for(let i = 0; i <= cover; i++){
		cover = Math.max(i + nums[i],cover);
		if (cover >= nums.length - 1) return true
	}
	return false
};

LeetCode 1005. Maximize Sum Of Array After K Negations

這裡雷點就是 js 的 sort 預設的排序順序是根據字串的 Unicode 編碼位置（code points）而定 會搞得你不要不要的, 所以先執行 nums.sort((a, b) => a - b) 才能正常數字排序
排序完成後對 負數 的取反, 接著找出變化後 array 最小值, 然後用 k % 2 計算餘數 (這樣可以不用 while) 來取反, 最後加總即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var largestSumAfterKNegations = function(nums, k) {
    nums = nums.sort((a, b) => a - b)

	for(let i = 0 ; i < nums.length; i++)
		if(k > 0 && nums[i] <= 0) {
			//取反
			nums[i] = -nums[i];
			k--;
		}

	//取最小值取反
    let minValue = Math.min(...nums);
    let minIndex = nums.indexOf(minValue);	
	if (k % 2 == 1) nums[minIndex] = -nums[minIndex];

	//加總
	let sum = 0;
	for(let i = 0; i < nums.length; i++)
		sum += nums[i];
	
	return sum;
};

LeetCode 134 加油站

這題還滿難想的, 當 sum 小於 0 時, 把 start 位置設定到下個站點, 然後 sum 歸零從新計算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var canCompleteCircuit = function(gas, cost) {
    let total = 0
	for(let i = 0; i < gas.length; i++) total += gas[i] - cost[i]
	
	let sum = 0;
	let start = 0;
	for(let i = 0; i < gas.length; i++) {
		sum += gas[i] - cost[i]
		
		//貪心精華所在
		if(sum < 0) {
			start = i + 1
			sum = 0
		}
	}
	if (total < 0) return -1
	return start
}

LeetCode 860 檸檬水

這題就別想太多, if else 開下去就對了, 唯一要注意就是 20 元找零有兩種情況, 當同時有 5 元及 10 元兩種硬幣時優先把他們找出去, 因為 5 元更加通用, 寫反大概就 gg
另外 20 可以不用紀錄, 因為找零只有 5 or 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var lemonadeChange = function(bills) {
	let five = 0;
	let ten = 0;
	
    for (let i = 0; i < bills.length; i++) {
		if (bills[i] == 5) {
			five++
		}
		if (bills[i] == 10) {
			if (five == 0) return false
			else {
				five--
				ten++
			}
		}
		if (bills[i] == 20) {
			if (ten > 0 && five > 0) {
				five--
				ten--
			} else if (ten == 0 && five >= 3) {
				five -=3
			} else {
				return false
			}

		}
		
		console.log(`${i} five:${five}, ten:${ten}`)
	}
	return true
};
關閉