iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 11
0

今天的挑戰內容是把一個整數本來是十進位表示,變成是二進位表示。例如 5 變成二進位的話是 101,13 變成二進位是 1101。然而我們不只是要以二進位表示,而是找出該整數用二進位表示時,連續最多出現幾個 1。例如 5 的話是 1,13 的話則是 2。那就讓我們開始吧!


Python 3

num = int(input())
max_number = max([len(x) for x in bin(num)[2:].split('0')]) 
print(max_number)
  • 在 Python 有個內置函數 bin 可以很方便地返回某個整數的二進位表示法。而這個返回的值的 Type 是 str。例如 bin(5) 會回傳 '0b101'bin(num)[2:0] 是作 Slicing,也就是取 substring,因為使用 bin 所得到的 str 前兩個字都是 0b ,而我們只要第三個字之後,也就是真正用來表示一個整數的二進位。bin(num)[2:0].split('0') 則是說以 0 作為 separator,得到一個 List,也就是找到所有字串中連續出現 1 的部分。例如 9 的二進位是 1001,那麼就會得到一個 List 是 ['1','','1'] ,中間會有一個空字串是因為 9 的二進位有兩個 0,而 00 之間的部分是 ''
  • 再來我們透過 [len(x) for x in(num)[2:0].split('0')] 得到一個新的 List,每一個元素就是從舊 List 的中的元素,也就是字串,其長度作為新元素,所以例如原來是 ['1','','1'] 就會變成 [1,0,1] ,最後再透過內置函數 max 來得到這個 List 裡面最大的值啦!
  • 這裡充分運用了 Python 提供我們一個很方便簡潔的語法。

Scala

import scala.io.StdIn

object Solution {
    
    def main(args: Array[String]) {
        val n = StdIn.readInt
        println(Integer.toBinaryString(n).split("0").map(_.length).max)
    }
    
}
  • 首先我們先把整數讀進來到 n,接著我們使用 Integer 這個 Class 有個 static method toBinaryString 來把 n 轉成用二進位表示的 String。例如 9 會變成 1001 。然後跟 Python 概念一樣,也是透過 String 的 method split("0") ,把 0 當作 separator 得到一個 Array of string,例如 9 的話就會得到 Array("1", "", "1") 。再來我們 invoke Array 的 method map 。記得 map 叫做映射嗎?所以我們這邊使用 map 就是說我們要把 Array("1", "", "1") 中的每一個元素做轉換變成新的元素。例如 Array(1, 2, 3).map(x => x + 1) 就會變成 Array(2, 3, 4) ,這裡的 x => x + 1 是 anonymous function,也就是用來轉換的函數,每次輪到一個元素,他就會是 x 並且透過 x+1 做轉換。回到我們本來的解法上, map(_.length) 是說,我要取每個元素的長度,也就是 Array 中每個 String 的長度,當然你可以寫成 map(x => x.length) ,但因為我們不 care x 到底是啥,所以就用 _.length 就可以了。經過 map 後得到的是 Array of 每個字串元素的長度,最後再用 max 來得到最大的數字,也就是 max number of consecutive 1 囉!
  • 再舉個實例:25 (輸入)=> Array("11", "", "1") (split 後)=> Array(2, 0, 1) (map 後)=> 2 (結果)

Golang

package main

import (
  "fmt"
  "bufio"
  "os"
  "strconv"
  "strings"
)

func main() {
  scanner := bufio.NewScanner(os.Stdin)
  scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
  binaryString := (strconv.FormatInt(int64(num), 2))
  arrayString := strings.Split(binaryString, "0")
  var max int
  for _, value := range arrayString {
    if l := len(value); l > max {
      max = l
    }
  }
  fmt.Println(max)
}
  • Golang 的部分首先我們先取得要拿來計算的整數放到 num 。接著我們透過 strconv 這個 Package 的 Function FormatInt 來幫我們完成將 num 轉換成用二進位表示的 String(FormatInt 的第二個參數表示幾進位)。再來我們透過 strings這個 Package 的 Function Split ,來達到像其他語言的效果 (一樣也是以 0 作為 Separator)。最後跟其他語言比較不一樣的地方是, Array of String 並沒有內建可以找出元素中的 Max 或 Min,所以我們自己透過 iterate 這個 Array 來去找出元素中最長的 String 是多長,也就是最多連續個數的 1 是連續幾個。這裡比較特別的是 if l := len(value); l > max 是同時賦值並且進行判斷囉!

Rust

use std::io::stdin;
fn main() {
    let n: i32 = {
        let mut s = String::new();
        stdin().read_line(&mut s).unwrap();
        s.trim().parse().unwrap()
    };
    
    let ans = format!("{:b}", n).split('0').map(|s|s.len()).max().unwrap_or(0);
    
    println!("{}", ans);    
}
  • 首先我們看 n (type i32) 是怎麼從 User input 讀到值的。這裡看到 n = {...}n 的值是 Code block 裏頭最後 Return 的值,也就是 s.trim().parse().unwrap() 。記得我們說 Rust 是 Expression-based,所以這裡就是把整個 {...} 當作是一個表達式,而結果,也就是最後 return 的值賦予給 n
  • 再來看我們最後要求的值 ans 。先看到 format!("{:b}", n) 這個 Macro,他就類似其他語言的 Printf,可以格式化字串。而這裡的 ("{:b}", n){} 就是 n 的 placeholder,然而這裡的 :b 表示要把 n 轉成是 binary 的表示方式。可以這麼做的原因是因為在 Rust 的 Integer 有實作 fmt::Binary 這個 Trait 所以才可以轉換。format!("{:b}", n) 得到 n 的二進位表示法的 String。接著 .split('0')0 為 Separator 來得到一個 Iterator (元素是以 0 隔開的 substring)。 map 是 Iterator 的 Function,可以用來轉換成另一個 iterator,而怎麼轉,在這裡就是透過 map 內的 closure (like anonymous function) |s|s.len()s 是每次 Iterator 出來的值,我們取其長度 ( s.len())。接著是 Iterator 的 Function max ,可以找出 Iterator 裡頭最大的數字,也就是最長的長度的值。注意這裡 max() 回傳的是一個 Option (Iterator 內沒東西時回 None)。最後用到我們之前講過的 unwrap_or(0) ,來取出 Some 內的值,或者假使是 None 就是給 default 值0 。上述這一連串的結果最後就是我們要的答案囉!

結語

今天在這四個語言我們盡量利用該語言本身就具備的語法和方法來快速地解決這個問題,當然你也可以用土炮的方法來得到整數的二進位表示法 (概念上是一直取 2 的餘數)。那麼就明天見囉!


上一篇
[Day 9] 自己和自己的對話
下一篇
[Day 11] 我的世界變多維了!
系列文
30 天把自己榨好榨滿的四週四語言大挑戰!30

尚未有邦友留言

立即登入留言