未分類

Arranging Coins

BinarySearch, Go, LeetCode, Math

Arranging Coins

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

1
2
3
4
5
6
7
8
n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2.

Example 2:

1
2
3
4
5
6
7
8
9
n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.
提示 解題應用
Math 規律觀查

Default:

1
2
3
func arrangeCoins(n int) int {
}

解答思路:

很單純的題目，只要不斷將n減去一連續數列(1,2,3…)，當n小於0時其減去該數的前一個值就是最大能完成的列數。

程式碼解說:

因為要減去的數列是從1開始，所以先初始化數列起始值為1，接著開始不斷利用迴圈將n與連續數列做相減，而數列的值也依續不斷變大，直到n減去該值時小於0才停止，而因為要找的是有排滿的列數，所以結果就是該數再去-1就是我們要的答案

1
2
3
4
5
6
7
count := 1
for n-count >= 0 {
	n -= count
	count++
}
count--
return count

完整程式碼:

1
2
3
4
5
6
7
8
9
func arrangeCoins(n int) int {
	count := 1
	for n-count >= 0 {
		n -= count
		count++
	}
	count--
	return count
}

總結:

若有一數量的硬幣照每列各有(1,2,3…)的數量排序，找出最大且該列能排滿的位置，只要不斷將n減去一連續數列(1,2,3…)，當n小於0時其減去該數的前一個值就是最大能完成的列數。

分享到