DZ 快樂 LeetCode: 2020
起源是這樣的兒
阿黃姐(小雞老師狀態) 在一陣js教學後
大聲地嘶吼: “本公司同仁 資料結構與演算法必須加強!!!!!”
然後 快樂的 DZ 快樂 LeetCode 就誕生了
每天一回 見紅就收
YA!!!!!
2020 的足跡
-
12/21
## 愛情的第一題:
難度:EASY 題目:https://leetcode.com/problems/two-sum/
- Tim
- python
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ for i in range(len(nums)): for j in range(i + 1, len(nums) ): if nums[i] + nums[j] == target: return [i, j]
class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ return [ [i, j] for i in range(len(nums)) for j in range(i+ 1, len(nums)) if nums[i] + nums[j] == target][0]
- javascript
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { for ( let i = 0; i < nums.length; i ++ ) { for ( let j = i + 1; j < nums.length; j ++ ) { if ((nums[i] + nums[j]) === target) return [i , j] } } };
- Chris
- Golang
func twoSum(nums []int, target int) []int { numMap := make(map[int]int) for index, value := range nums { _, ok := numMap[target - value] if ok { return []int{ numMap[target - value], index } } else { numMap[value] = index } } return nil }
- Golang
- Syun
- javascript
var twoSum = function(nums, target) { for( let i = 0 ; i < nums.length; i++ ) { let answer = []; answer.push(i); for( let j = i+1 ; j < nums.length; j++ ) { if (nums[i] + nums[j] === target) { answer.push(j) return answer } } } };
- javascript
- Kevin
- javascript
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { let output = [] for (let i = 0; i < nums.length; i++) { for (let j = i+1; j < nums.length; j ++) { if ((nums[i]+nums[j]) === target) { output = [i,j] break } } if(output.length) { break } } return output };
- Ezra
- javascript
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { for (let i = 0; i < nums.length-1; i++) { for (let j = i+1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j] } } } };
- Tim
-
12/22
週二的第二題
難度:EASY 題目:https://leetcode.com/problems/reverse-integer/
- Kevin
- javascript
/** * @param {number} x * @return {number} */ var reverse = function(x) { let output = '' if (x < 0) { output = '-' x = `${x}`.slice(1) } else { x = x.toString() } stringLength = x.length for (let i = 0; i < stringLength; i++){ output += x[stringLength-i-1] } if (+output > (Math.pow(2,31) -1) || +output < -Math.pow(2,31)) { return 0 } return output };
- Tim
- python
class Solution(object): def reverse(self, x): """ :type x: int :rtype: int """ str_x = str(x) if str_x[0] == '-' : str_x = str_x[1:][::-1] return self.check_range( '-' + str(int(str_x))) return self.check_range(str(int(str_x[::-1]))) def check_range(self, check_value): if int(check_value) > 2147483647 or -2147483648 > int(check_value) : return 0 else: return check_value
- javascript
/** * @param {number} x * @return {number} */ var reverse = function(x) { let strX = JSON.stringify(x) if ( strX.charAt(0) === '-') { strX = strX.substring(1) .split("") .reverse() .join("") return parseInt("-" + checkValue(strX)) } return checkValue(strX.split("").reverse().join("")) }; const checkValue = (value) => { const intX = parseInt(value) if (intX > ( ( 1 << 31) *-1 - 1) || intX < ( 1 << 31 ) ) { return 0; } return JSON.stringify(parseInt(value)) }
- Chris
- golang
func reverse(x int) int { xStr := strconv.Itoa(x) var answer int = 0 for index := len(xStr) - 1; index >= 0; index-- { num, _ := strconv.Atoi(string(xStr[index])) answer += num * int(math.Pow10(index)) } if string(xStr[0]) == "-" { answer = answer / 10 * -1 } if answer > (1 << 31 - 1) || answer < (1 << 31 * -1) { return 0 } return answer }
- Ezra
- javascript
var reverse = function(x) { const input = x.toString() const max = 2147483647 const min = -2147483648 if (x === 0) { return 0 } else { if (x >= 0) { let output = '' for (let i = input.length-1; i >= 0; i--) { output += input[i] } if (output > max) return 0 return output } else { let output = '-' for (let i = input.length-1; i > 0; i--) { output += input[i] } if (output < min) return 0 return output } } };
- Syun
- javascript
var reverse = function(x) { let y = x.toString(); let str = ''; if (y[0] === '-') { str = '-'; } for (let i = y.length-1; i >= 0; i -- ) { if (y[i] !== '-') { str += y[i]; } } if (str < -2147483648 || str > 2147483647) { str = 0; } return str; };
- Kevin
-
12/23
## 第三題:
難度:MEDIUM 題目:https://leetcode.com/problems/add-two-numbers/
- YY
- Python (time & space: $\mathcal{O}(\max{N, M})$)
class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: tail = hat = ListNode() c = 0 n1, n2 = l1, l2 while (n1 is not None) or (n2 is not None) or (c != 0): x = y = 0 if n1 is not None: x, n1 = n1.val, n1.next if n2 is not None: y, n2 = n2.val, n2.next c, z = divmod(x + y + c, 10) tail.next = ListNode(val=z) tail = tail.next return hat.next
- Python (time & space: $\mathcal{O}(\max{N, M})$)
- kevin
- js
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var addTwoNumbers = function(l1, l2) { let result = new ListNode(0, null); const head = result; let modNum = 0; let carry = 0; while (l1 || l2 || carry) { let a = l1 ? l1.val : 0; let b = l2 ? l2.val : 0; let psum = (a + b + carry); carry = Math.floor(psum / 10); modNum = psum % 10; result.val = modNum; l1 = l1 ? l1.next : null; l2 = l2 ? l2.next : null; // 如果有下一個我才需要有next (l1 || l2 || carry) ? result.next = new ListNode(0,null) : null; result = result.next; } return head; };
- Chris
- golang 目前傷眼,有空再改
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { ptr1 := l1 ptr2 := l2 for { ptr1.Val += ptr2.Val if ptr1.Next == nil { ptr1.Next = ptr2.Next break } if ptr2.Next == nil { break } ptr1 = ptr1.Next ptr2 = ptr2.Next } ptr1 = l1 for { if ptr1.Val > 9 { ptr1.Val -= 10 if ptr1.Next == nil { ptr1.Next = &ListNode{ Val: 1, Next: nil } } else { ptr1.Next.Val += 1 } } if ptr1.Next == nil { break } ptr1 = ptr1.Next } return l1; }
- Tim
- python
- yayayayay~~~~
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ l_a = l1 l_b = l2 num_list_a = [] num_list_b = [] while True: num_list_a.append(l_a.val) if l_a.next : l_a = l_a.next else: break while True: num_list_b.append(l_b.val) if l_b.next : l_b = l_b.next else: break num_a_str = '' num_b_str = '' for i in num_list_a[::-1]: num_a_str = num_a_str + str(i) for k in num_list_b[::-1]: num_b_str = num_b_str + str(k) add_num = int(num_a_str) + int(num_b_str) dummy_result = ListNode(0) ans_str = str(add_num)[::-1] pointer = dummy_result for i, r_item in enumerate(ans_str): current = ListNode(val=r_item ) if i == 0: dummy_result.next = current else: pointer.next = current pointer = pointer.next return dummy_result.next
- python
- YY
-
12/24
## 第四題:
難度:EASY 題目:https://leetcode.com/problems/roman-to-integer/
- YY
- Python (time: $\mathcal{O}(N)$, space: $\mathcal{O}(1)$)
R2I = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000, } class Solution: def romanToInt(self, s: str) -> int: out = 0 last_i = 0 for r in s[::-1]: i = R2I[r] if i >= last_i: out += i else: out -= i last_i = i return out
- kevin
- javascript
var romanToInt = function(ss) { const mapObject = { CM: 900, CD: 400, IV: 4, IX: 9, XL: 40, XC: 90, I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000, } let s = ss let result = 0 let valArray = [] valArray = s.match(/CM|CD|IV|IX|XL|XC/gi) || []; s = s.replace(/CM|CD|IV|IX|XL|XC/g, ''); if (s) valArray = [...valArray, ...s.match(/I|V|X|L|C|D|M/gi)]; valArray.forEach(val => { if (val) { result += mapObject[val] } }) return result };
-
Chris 之前寫過了,這次嘗試不同解法!玩玩看用正則表達式來解! 啊當然就又慢又用很多記憶體辣~就豪玩~~~
func romanToInt(s string) int { numAry := []string{ "IV", "IX", "XL", "XC", "CD", "CM", "I", "V", "X", "L", "C", "D", "M" } numMap := map[string]int { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000, "IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900, } answer := 0 for _, value := range numAry { reg := regexp.MustCompile(value) answer += len(reg.FindAllIndex([]byte(s), -1)) * numMap[value] s = reg.ReplaceAllString(s, "") } return answer }
再一個,雖然醜但又快又好!
func romanToInt(s string) int { answer := 0 for index, value := range s { switch string(value) { case "I": answer += 1 case "V": answer += 5 if index - 1 >= 0 && string(s[index-1]) == "I" { answer -= 2 } case "X": answer += 10 if index - 1 >= 0 && string(s[index-1]) == "I" { answer -= 2 } case "L": answer += 50 if index - 1 >= 0 && string(s[index-1]) == "X" { answer -= 20 } case "C": answer += 100 if index - 1 >= 0 && string(s[index-1]) == "X" { answer -= 20 } case "D": answer += 500 if index - 1 >= 0 && string(s[index-1]) == "C" { answer -= 200 } case "M": answer += 1000 if index - 1 >= 0 && string(s[index-1]) == "C" { answer -= 200 } } } return answer }
- Tim
- python
class Solution(object): def romanToInt(self, s): """ :type s: str :rtype: int """ roman_dict = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000 } keep_go = 0 result = 0 for idex, s_str in enumerate(s): if keep_go is not idex: continue keep_go = idex + 1 if s_str == 'I': if s[idex: idex+2] == 'IV': result = result + 4 keep_go = idex + 2 elif s[idex: idex+2] == 'IX': result = result + 9 keep_go = idex + 2 else: result = result + roman_dict[s_str] elif s_str == 'X': if s[idex: idex+2] == 'XL': result = result + 40 keep_go = idex + 2 elif s[idex: idex+2] == 'XC': result = result + 90 keep_go = idex + 2 else: result = result + roman_dict[s_str] elif s_str == 'C': if s[idex: idex+2] == 'CD': result = result + 400 keep_go = idex + 2 elif s[idex: idex+2] == 'CM': result = result + 900 keep_go = idex + 2 else: result = result + roman_dict[s_str] else: result = result + roman_dict[s_str] return result
- javascript
- 土砲姐 就是爽!!!
/** * @param {string} s * @return {number} */ var romanToInt = function(s) { const romanMap = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000 }; const sStr = [...s]; let result = 0; for ( let i = 0; i < sStr.length; i ++ ){ if ( sStr[i] === 'I' ) { if ( sStr.slice(i,i+2).join("") === "IV" ) { result = result + 4 i = i + 1 } else if ( sStr.slice(i,i+2).join("") === "IX" ) { result = result + 9 i = i + 1 } else { result = result + romanMap[sStr[i]] } } else if ( sStr[i] === 'X' ) { if ( sStr.slice(i,i+2).join("") === "XL" ) { result = result + 40 i = i + 1 } else if ( sStr.slice(i,i+2).join("") === "XC" ) { result = result + 90 i = i + 1 } else { result = result + romanMap[sStr[i]] } } else if ( sStr[i] === 'C' ) { if ( sStr.slice(i,i+2).join("") === "CD" ) { result = result + 400 i = i + 1 } else if ( sStr.slice(i,i+2).join("") === "CM" ) { result = result + 900 i = i + 1 } else { result = result + romanMap[sStr[i]] } } else { result = result + romanMap[sStr[i]] } } return result };
- Ezra
- javascript
var romanToInt = function(s) { const roman = { I:1, V:5, X:10, L:50, C:100, D:500, M:1000, } let sum = 0; for(let i = 0 ; i < s.length ; i++){ let n1 = roman[s[i]]; let n2 = roman[s[i+1]]; if(n2 > n1){ sum = sum + n2 - n1; i++ } else { sum = sum + n1; } } return sum; };
- Syun
- Javascript
var romanToInt = function(s) { let result = 0; for( let i = 0; i < s.length; i++) { if (s[i] === 'I') { result += 1; } else if (s[i] === "V") { if (s[i-1] === "I") { result += 3; } else { result += 5; } } else if (s[i] === "X") { if (s[i-1] === "I") { result += 8; } else { result += 10; } } else if (s[i] === "L") { if (s[i-1] === "X") { result += 30; } else { result += 50; } } else if (s[i] === "C") { if (s[i-1] === "X") { result += 80; } else { result += 100; } } else if (s[i] === "D") { if (s[i-1] === "C") { result += 300 } else { result += 500; } } else if (s[i] === "M") { if (s[i-1] === "C") { result += 800; } else { result += 1000; } } } return result; };
- YY
-
12/25
## 愛情的第五題
難度:Easy 題目:https://leetcode.com/problems/subdomain-visit-count/
- kevin
- javascript
var subdomainVisits = function(cpdomains) { let resultObject = {} cpdomains.forEach(cpdomain => { let existDotIndex = 1 const visitCount = cpdomain.split(' ')[0] cpdomain = cpdomain.split(' ')[1] while(existDotIndex !== -1) { if (!resultObject[cpdomain]) { resultObject[cpdomain] = 0 } resultObject[cpdomain] += +visitCount existDotIndex = cpdomain.indexOf('.') cpdomain = cpdomain.substring(existDotIndex+1) } }) return Object.entries(resultObject).map(val => `${val[1]} ${val[0]}`) };
- javascript
- 美人YY
- Python (time & space: $\mathcal{O}(N)$)
from collections import defaultdict class Solution: def subdomainVisits(self, cpdomains: List[str]) -> List[str]: visits = defaultdict(lambda: 0) for cpdomain in cpdomains: count, domain = cpdomain.split() count = int(count) visits[domain] += count for i, c in enumerate(domain): if c == '.': visits[domain[i+1:]] += count return ['{} {}'.format(c, s) for s, c in visits.items()]
- 柯瑞斯
- golang
func subdomainVisits(cpdomains []string) []string { domainCount := map[string]int{} countNdomain := []string{} for _, domain := range cpdomains { countNdomain = strings.Split(domain, " ") count, _ := strconv.Atoi(countNdomain[0]) if _, has := domainCount[countNdomain[1]]; has { domainCount[countNdomain[1]] += count } else { domainCount[countNdomain[1]] = count } for { index := strings.Index(countNdomain[1], ".") if index != -1 { if _, has := domainCount[countNdomain[1][index+1:]]; has { domainCount[countNdomain[1][index+1:]] += count } else { domainCount[countNdomain[1][index+1:]] = count } countNdomain[1] = countNdomain[1][index+1:] } else { break } } } answer := []string{} for k, v := range domainCount { answer = append(answer, strconv.Itoa(v) + " " + k ) } return answer }
- 氝🦊X舞
- python
class Solution(object): def subdomainVisits(self, cpdomains): """ :type cpdomains: List[str] :rtype: List[str] """ subdomain_dict = {} for i in cpdomains: v, d = i.split() v_num = int(v.encode("utf8")) domain_str = d.encode("utf8") while "." in domain_str: if subdomain_dict.get(domain_str, None) == None: subdomain_dict[domain_str] = v_num else: subdomain_dict[domain_str] = subdomain_dict[domain_str] + v_num domain_str = domain_str.split(".", 1)[1] else: # 有機會 dict 沒有 j 個 domain_str, so default num = 0 subdomain_dict[domain_str] = subdomain_dict.get(domain_str, 0) + v_num result = [] for key in subdomain_dict: result.append("{} {}".format(subdomain_dict[key], key)) # 炫砲! # return ["{} {}".format(subdomain_dict[key], key) for key in subdomain_dict] return result
- kevin
LeetCode Week2
-
12/28
## 愛情的第一題:
難度:EASY 題目:167. Two Sum II - Input array is sorted
- HH
- Python (time: $\mathcal{O}(N)$, space: $\mathcal{O}(1)$)
class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: i = 0 j = len(numbers) - 1 while i < j: summ = numbers[i] + numbers[j] if summ < target: i += 1 elif summ > target: j -= 1 else: return [i + 1, j + 1] return [-1, -1]
- Python (time: $\mathcal{O}(N)$, space: $\mathcal{O}(1)$)
- Chris
- Go
func twoSum(numbers []int, target int) []int { head := 0 tail := len(numbers)-1 for { if numbers[head] + numbers[tail] == target { return []int{ head+1, tail+1 } } else if numbers[head] + numbers[tail] > target { tail -= 1 } else { head += 1 } } return []int{} }
- keivn
- Javascript
var twoSum = function (numbers, target) { let point1 = 0; let point2 = numbers.length - 1; while(true) { const ans = numbers[point1]+numbers[point2] if (ans === target) { break } else if (ans > target) { point2-- } else if (ans < target) { point1++ } } return [point1+1,point2+1] };
- Javascript
- Tim
- python
class Solution(object): def twoSum(self, numbers, target): """ :type numbers: List[int] :type target: int :rtype: List[int] """ tmp_dict = {} for i, number in enumerate(numbers): if target-number in tmp_dict: return [ tmp_dict[target-number], i +1 ] else: tmp_dict[number] = i + 1
- typescript
function twoSum(numbers: number[], target: number): number[] { let pEnd: number = numbers.length - 1; let pStart: number = 0; let keepGoing: boolean = true; let result: number[]; while (keepGoing) { console.log(numbers[pEnd]) if (numbers[pEnd] + numbers[pStart] === target ) { result = [ pStart +1, pEnd + 1 ] keepGoing = false; } else if (numbers[pEnd] + numbers[pStart] > target) { pEnd = pEnd -1 } else { pStart = pStart +1 } } return result };
- Ezra
- javascript
var twoSum = function(numbers, target) { let ansAry = [] for (let i = 0; i < numbers.length-1; i++) { for (let j = numbers.length-1; j > i; j--) { if (numbers[i] + numbers[j] === target) { ansAry.push(i+1, j+1) return ansAry } } } };
- javascript
- Syun
- JavaScript
var twoSum = function(numbers, target) { for (let i = 0; i < numbers.length; i ++) { for (let j = i+1; j < numbers.length; j ++) { if (numbers[i] + numbers[j] === target) { return [i+1, j+1] } } } };
- JavaScript
- HH
-
12/29
## 愛情的第二題:
難度:Easy 題目:507. Perfect Number
- YY
- Python (time: $\mathcal{O}\left(\sqrt{N}\right)$, space: $\mathcal{O}(1)$)
class Solution: def checkPerfectNumber(self, num: int) -> bool: if num == 1: return False summ = 1 for i in range(2, int(num**(1/2)) + 1): if num % i == 0: summ += i + (num // i) return summ == num
- Python (time: $\mathcal{O}\left(\sqrt{N}\right)$, space: $\mathcal{O}(1)$)
- Chrissssss
- Go
func checkPerfectNumber(num int) bool { sum := num * -1 last := num - 1 for i := 1; i < last; i++ { if num % i == 0 { sum += num / i sum += i last = num / i } } if sum == num { return true } else { return false } return false }
- Go
- kevin
- javascript
var checkPerfectNumber = function(num) { if (num ===1) { return false } let ans = [] let sqrtNum = Math.floor(Math.sqrt(num)) for (let i = 1; i <= sqrtNum; i++) { if (num%i === 0) { ans.push(i) if (i !== (num/i) && (num/i) !== num) { ans.push(num/i) } } } let sum = 0 ans.forEach(val => sum += val) return sum === num };
- javascript
- Tim 😶
- python
Great Artists Steal
class Solution(object): def checkPerfectNumber(self, num): """ :type num: int :rtype: bool """ if num <= 0 : return False res = 0 high = int(math.sqrt(num)) + 1 for i in range(1, high): if num % i == 0: res += i if i * i != num: res += num/i return num == (res - num)
- python
- Syun
- Javascript
var checkPerfectNumber = function(num) { let count = 0; for( let i = 1; i < num; i++) { if (num % i === 0 ) { count += i } } if (count === num) { return true; } else { return false; } };
- Javascript
- Ezra
- Javascript
var checkPerfectNumber = function(num) { let sum = 0 for (let i = 1; i <= num/2; i++) { if (num % i === 0){ sum = sum + i } } if (sum === num) { return true } else { return false } };
- Javascript
- YY
-
12/30
## 愛情的第三題:
難度:EASY 題目:605. Can Place Flowers
- HY
- Python (time: $\mathcal{O}(N)$, space: $\mathcal{O}(1)$)
class Solution: def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool: if n == 0: return True # 3-state FSM # (0: non-empty, 1: first empty, 2: second empty) state = 1 for x in flowerbed: if x == 0: # empty state += 1 if state == 3: state = 1 n -= 1 if n == 0: return True else: # non-empty state = 0 return n == 1 and state == 2
- Python (time: $\mathcal{O}(N)$, space: $\mathcal{O}(1)$)
- kevin
- javascript
var canPlaceFlowers = function(flowerbed, n) { const flowerbedLength = flowerbed.length for(let i = 0; i<flowerbedLength;i++) { const flower = flowerbed[i] if (flower === 0) { if (i === 0) { if (flowerbedLength === 1) { flowerbed[i] = 1 n = n - 1 } else { if (flowerbed[i+1] === 0) { flowerbed[i] = 1 n = n - 1 } } } else if ( i === flowerbedLength-1) { if (flowerbed[i-1] === 0) { flowerbed[i] = 1 n = n - 1 } } else { if (flowerbed[i-1] === 0 && flowerbed[i+1] === 0) { flowerbed[i] = 1 n = n - 1 } } } if (n <= 0) { break; } if (i === 0) { continue; } } return (n <= 0) };
- javascript
- Syun
- Javascript
var canPlaceFlowers = function(flowerbed, n) { let count = 0; for (let i = 0; i < flowerbed.length; i ++) { if (i === 0) { if (flowerbed.length-1 === i && flowerbed[i] !== 1) { flowerbed[i] = 1; count += 1; }else if (flowerbed[i+1] === 0 && flowerbed[i] !== 1) { flowerbed[i] = 1; count += 1; } } else if (i === flowerbed.length -1) { if (flowerbed[i-1] === 0 && flowerbed[i] !== 1) { flowerbed[i] = 1; count += 1; } } else { if (flowerbed[i-1] === 0 && flowerbed[i+1] === 0 && flowerbed[i] !== 1) { flowerbed[i] = 1; count += 1; } } } if (count >= n) { return true; } else { return false; } };
- Javascript (Chris愛情的調整)
var canPlaceFlowers = function(flowerbed, n) { flowerbed = [0, ...flowerbed, 0]; for (let i = 1; i < flowerbed.length-1; i++ ) { if(flowerbed[i-1] === 0 && flowerbed[i+1] === 0 && flowerbed[i] !== 1) { flowerbed[i] = 1; n -= 1 } } return n <= 0 };
- Javascript
- Tim
- python
人一定要靠自己!
000 (010)101 -> 1 (101) (010)000 -> 3 (101) (101)001 -> 2 (101) (101)010 -> 2 (010) (010)100 -> 1 (101) 101 000 -> 1 (010) 001 -> 0 (001) 010 -> 0 (010) 010 -> 0 (010) 001 000 -> 1 (010) 001 -> 0 (001) 010 -> 0 (010) 010 101 -> 0 (101) 000 -> 2 (101) 001 -> 1 (101) 010 -> 0 (010) 100 -> 1 (101) 100 (100)101 -> 0 (101) (101)000 -> 2 (010) (101)001 -> 1 (001) (101)010 -> 1 (010) (100)100 -> 0 (100) 111 x
class Solution(object): def canPlaceFlowers(self, flowerbed, n): """ :type flowerbed: List[int] :type n: int :rtype: bool """ plots = 0 for idx, i in enumerate(flowerbed): if i is 0 and ( idx == 0 or flowerbed[idx-1] == 0) and ( idx == len(flowerbed)-1 or flowerbed[idx+1] == 0): plots += 1 flowerbed[idx] = 1 return plots >= n
- python
- Chris
- Go
func canPlaceFlowers(flowerbed []int, n int) bool { flowerbed = append([]int{0}, flowerbed...) flowerbed = append(flowerbed, 0) for i := 1; i < len(flowerbed)-1; i++ { if flowerbed[i-1] | flowerbed[i] | flowerbed[i+1] == 0 { flowerbed[i] = 1 n -= 1 } } return n <= 0 }
- Go
- HY
-
12/31
## 殘酷的第四題(面對它吧,凱開)☹:
難度:EASY 題目:453. Minimum Moves to Equal Array Elements
- HY
- Python (time: $\mathcal{O}(N)$, space: $\mathcal{O}(1)$)
class Solution: def minMoves(self, nums: List[int]) -> int: return sum(nums) - min(nums) * len(nums)
- Python (time: $\mathcal{O}(N)$, space: $\mathcal{O}(1)$)
- kevin 有偷偷看討論區的解法了QQ,周末多寫一題回來!!
var minMoves = function(nums) { return nums.reduce((cur, acc) => cur+acc) - Math.min(...nums)*nums.length };
- Tim
- python
- TLE 也很美 :)
class Solution(object): def minMoves(self, nums): """ :type nums: List[int] :rtype: int """ nums.sort() count = 0 keep_going = True while keep_going: # nums.count(nums[0])==len(nums) # len(set(nums)) same = True if nums.count(nums[0])==len(nums) else False if same: return count nums.sort() last_item = nums[-1] nums = [ v + 1 for v in nums[: -1]] nums.append(last_item) count += 1 return count
- Chris
- 原來我還沒寫,趕快補寫
- 說明:
在 nums 裡面,最小的那一個數每一輪一定都會幫他 +1,所以假設我們最後的答案是做了 x 次,我們可以試試看寫出等式。 1. 首先是以最小的那個數字每輪都要幫他 +1 來寫式子,這個最小的數字做完 x 輪,他最後會變成 min + x。 而做到最後,nums 裡面的每個元素都是一樣大,所以總和可以這樣算 (min + x) * length。 2. 為了要求出 x,我們可以試著寫看看另一種算總和的式子,也就是一開始給的 nums 先計算總合,後面用 sum 表示,一開始的總和加上 x 次的對 length - 1 個元素加一,因此可以寫成 sum + (length-1) * x。 3. 把 1 跟 2 的式子寫成方程式: (min + x) * length = sum + (length-1) * x 4. 3 的方程式中,除了 x 以外都是可以求得的已知數,因此我們稍微整理一下式子: a. (min + x) * length = sum + (length-1) * x b. 將乘法展開 => (min * length) + (x * length) = sum + (x * length) - x c. 同時減掉 x * length => (min * length) = sum - x d. 將等式的一邊只留下 x => x = sum - (min * length ) 5. 因此我們就可以知道 x 可以根據 sum 、 min 、 length 求得,因此程式碼只要求出 nums 總和跟 nums 最小的那個元素就可以算出答案。
- Golang
func minMoves(nums []int) int { sum := 0 min := (1<<63) -1 //max int64 for _, value := range nums { sum += value if value < min { min = value } } return sum - len(nums) * min }
- HY
希望 可以持續到2021年終! XDD