DZ 快樂 LeetCode: 2020

January 2, 2021 21 minute read

Tags: leetcode, 紮馬步

起源是這樣的兒

阿黃姐(小雞老師狀態) 在一陣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
  }

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

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

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

12/23

## 第三題：

難度：MEDIUM 題目：https://leetcode.com/problems/add-two-numbers/

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

kevin

  /**
   * 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

12/24

## 第四題：

難度：EASY 題目：https://leetcode.com/problems/roman-to-integer/

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

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]}`)
  };

美人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
  }

氝🦊Ｘ舞

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 

LeetCode Week2

12/28

## 愛情的第一題：

難度：EASY 題目：167. Two Sum II - Input array is sorted

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]

Chris

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

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

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

12/29

## 愛情的第二題：

難度：Easy 題目：507. Perfect Number

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

Chrissssss

  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
  }

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

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)

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

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

12/30

## 愛情的第三題：

難度：EASY 題目：605. Can Place Flowers

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

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

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

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 
                

Chris

  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
  }

12/31

## 殘酷的第四題（面對它吧，凱開）☹：

難度：EASY 題目：453. Minimum Moves to Equal Array Elements

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)

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
  }

希望可以持續到2021年終! XDD

Twitter Facebook LinkedIn

阿葛廷

DZ 快樂 LeetCode: 2020

2020 的足跡

週二的第二題

LeetCode Week2

You May Also Enjoy

daily Programming: 寶哥出場品質保證又見 GitHub Copilot!

daily Programming: Azure AI Search

當你覺得對方很Ｇ8討厭的時候，放面鏡子照照自己剛剛的行為先吧！

daily Programming: 寶哥出場品質保證 GitHub Copilot

阿葛廷

2020 的足跡

週二的第二題

LeetCode Week2

You May Also Enjoy

daily Programming: 寶哥出場 品質保證 又見 GitHub Copilot!

daily Programming: Azure AI Search

當你覺得對方很Ｇ8討厭的時候，放面鏡子照照自己剛剛的行為先吧！

daily Programming: 寶哥出場 品質保證 GitHub Copilot

daily Programming: 寶哥出場品質保證又見 GitHub Copilot!

daily Programming: 寶哥出場品質保證 GitHub Copilot