未分類

Plus One

Array, Go, LeetCode, Math

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

提示 解題應用
Array Array/Slice
Math 觀查規律

Default:

1
2
3
func plusOne(digits []int) []int {
}

解答思路:

有點像是在做電子顯示器的邏輯，只是這次不必理會數字怎麼顯示，基本上和預想的差不多，小於9的數字就直接+1做回傳，稍為麻煩的在於進位的處理，如果是一段數字中尾數幾個數字的進位而不影響整體的長度就不需要重新創一個array，直接將進度的位數歸0往前一位+1就好，但如果最後像是99+1的話，就需要擴增array的長度，此時新加長度的開頭一定是1，而在Golang中與其要一個個移動array值，倒不如就直接新增一個slice合併即可。

程式碼解說:

因為+1的值要重最尾巴的數字開始判斷起，所以取得長度後就開始從Array的最後一個值慢慢往前

1
2
3
4
length := len(digits)
for true {
	length--
}

接下來就分成三種情況，如果+1時該位數小於9也就是沒有再進位的狀況就直接把數字+1然後就可以回傳結果了，但如果該值等於9而且長度大於0(表示進位時還在數字長度之中，不需要擴增array)，就先將該位數的值設為0等然後回圈就往下取下一個值做判斷，等同於進位後再往下+1，最後一個else當然就是先前所說的超過數字長度的最大值，也就是進位後開頭為1，這時就是一樣先將該位設為0後，用slice把第一個值賦予1接著就可以與順利的把整個array展開合併回傳結果

1
2
3
4
5
6
7
8
9
10
11
if digits[length-1] < 9 {
	digits[length-1] = digits[length-1] + 1
	break
} else if length-1 > 0 {
	digits[length-1] = 0
} else {
	digits[length-1] = 0
	result := []int{1}
	result = append(result, digits...)
	return result
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func plusOne(digits []int) []int {
	length := len(digits)
	for true {
		if digits[length-1] < 9 {
			digits[length-1] = digits[length-1] + 1
			break
		} else if length-1 > 0 {
			digits[length-1] = 0
		} else {
			digits[length-1] = 0
			result := []int{1}
			result = append(result, digits...)
			return result
		}
		length--
	}
	return digits
}

總結:

將數字每一位數分別儲存至array中時，最需要注意的就是進位後是否超出該數字的長度，共分三種情況:

  • 增加的該位數小於9直接回傳
  • 進位後該位數歸0後繼續做判斷
  • 進位後超出整體數字的出度，新增一個array且第一格放1後與原本的array在後頭做合併
分享到