leetcode-go/medium/179.go

package main

import (
	"sort"
	"strconv"
	"strings"
)

// StringSlice ...
type StringSlice []string

func (strs StringSlice) Len() int {
	return len(strs)
}

func (strs StringSlice) Swap(i, j int) {
	strs[i], strs[j] = strs[j], strs[i]
}

func (strs StringSlice) Less(i, j int) bool { // Less is "More"
	len1, len2 := len(strs[i]), len(strs[j])
	for k := 0; k < len1 && k < len2; k++ {
		if strs[i][k] != strs[j][k] {
			return strs[i][k] > strs[j][k]
		}
	}
	if len1 < len2 {
		for k := len1; k < len2; k++ {
			if strs[i][0] != strs[j][k] {
				return strs[i][0] > strs[j][k]
			}
		}
		return strs[j][1] > strs[j][0] // Important!
	} else if len1 > len2 {
		for k := len2; k < len1; k++ {
			if strs[i][k] != strs[j][0] {
				return strs[i][k] > strs[j][0]
			}
		}
		return strs[i][1] < strs[i][0]
	}
	return false // strs[i] equals strs[j]
}

func largestNumber(nums []int) string {
	strs := make([]string, 0)
	for _, n := range nums {
		strs = append(strs, strconv.Itoa(n))
	}
	sort.Sort(StringSlice(strs))
	var sb strings.Builder
	for _, s := range strs {
		if sb.Len() == 0 && s == "0" {
			continue // No leading zero
		}
		sb.WriteString(s)
	}
	if sb.Len() == 0 {
		return "0"
	}
	return sb.String()
}

// func main() {
// 	println(largestNumber([]int{
// 		12, 121}))
// 	nums := StringSlice([]string{"8308", "830"})
// 	println(nums.Less(0, 1))
// 	println(nums.Less(1, 0))
// 	println(largestNumber([]int{
// 		3, 30, 34, 5, 9}))
// 	println(largestNumber([]int{
// 		824, 938, 1399, 5607, 6973, 5703, 9609, 4398, 8247}))
// 	answer := largestNumber([]int{
// 		9051, 5526, 2264, 5041, 1630, 5906, 6787, 8382, 4662, 4532,
// 		6804, 4710, 4542, 2116, 7219, 8701, 8308, 957, 8775, 4822,
// 		396, 8995, 8597, 2304, 8902, 830, 8591, 5828, 9642, 7100, 3976,
// 		5565, 5490, 1613, 5731, 8052, 8985, 2623, 6325, 3723, 5224,
// 		8274, 4787, 6310, 3393, 78, 3288, 7584, 7440, 5752, 351,
// 		4555, 7265, 9959, 3866, 9854, 2709, 5817, 7272, 43, 1014,
// 		7527, 3946, 4289, 1272, 5213, 710, 1603, 2436, 8823, 5228,
// 		2581, 771, 3700, 2109, 5638, 3402, 3910, 871, 5441, 6861,
// 		9556, 1089, 4088, 2788, 9632, 6822, 6145, 5137, 236, 683,
// 		2869, 9525, 8161, 8374, 2439, 6028, 7813, 6406, 7519})
// 	correct := "995998549642963295795569525905189958985890288238775871870185978591838283748308830827481618052787813771758475277519744072727265721971071006861683682268046787640663256310614560285906582858175752573156385565552654905441522852245213513750414822478747104662455545424532434289408839763963946391038663723370035134023393328828692788270926232581243924362362304226421162109163016131603127210891014"
// 	println(answer == correct)
// }