先減到<1000;
對(duì)于 >100, >10, >1 分為三檔，每檔里有4個(gè)“分界點(diǎn)”花嘶，針對(duì)每個(gè)分界點(diǎn)，循環(huán)減散罕。
三層for循環(huán)挑随∽茨看著時(shí)間復(fù)雜度挺大，但其實(shí)最外層兩個(gè)循環(huán)次數(shù)都是常數(shù)兜挨；里面的是
O(n)膏孟。所以整體時(shí)間復(fù)雜度是O(n)。
一個(gè)通用的寫法：
package main
import "fmt"
func l_m12(num int) string? {
? ? var res string
? ? mp := map[int]string{
? ? ? ? 1:"I",
? ? ? ? 5:"V",
? ? ? ? 10:"X",
? ? ? ? 50:"L",
? ? ? ? 100:"C",
? ? ? ? 500:"D",
? ? ? ? 1000:"M",
? ? ? ? 4:"IV",
? ? ? ? 9:"IX",
? ? ? ? 40:"XL",
? ? ? ? 90:"XC",
? ? ? ? 400:"CD",
? ? ? ? 900:"CM",
? ? }
? ? jins :=[][]int{}
? ? jins = append(jins,[]int{1,4,5,9})
? ? jins = append(jins,[]int{10,40,50,90})
? ? jins = append(jins,[]int{100,400,500,900})
? ? for ;;{
? ? ? ? if num<1000{
? ? ? ? ? ? break
? ? ? ? }
? ? ? ? res +="M"
? ? ? ? num-=1000
? ? }
? ? for j:=2;j>=0;j--{
? ? ? ? line:=jins[j]
? ? ? ? for i :=3; i>=0;i--{
? ? ? ? ? ? for ;num>=line[i];{
? ? ? ? ? ? ? ? res += mp[line[i]]
? ? ? ? ? ? ? ? num -= line[i]
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return res
}
// I? ? ? ? ? ? 1
// V? ? ? ? ? ? 5
// X? ? ? ? ? ? 10
// L? ? ? ? ? ? 50
// C? ? ? ? ? ? 100
// D? ? ? ? ? ? 500
// M? ? ? ? ? ? 1000
func main(){
? ? fmt.Println(l_m12(1994))
}
