線上程式設計介紹
阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：
https://developer.aliyun.com/coding本文為大家介紹其中的 第133題：疊疊高 的題目解析，具體如下：
題目描述
等級：容易
知識點：數論
檢視題目：疊疊高A同學買了n張卡片，他想用卡片來疊成一個塔，每層塔由數量不同的房間組成，且高層的房間數量必須少于低層的房間數量，房間可看做兩張傾斜的卡片組成，兩張卡片上面頭部相接觸。特殊的，每層的所有房間必須相鄰，且高層的房間需要建在天花闆上。
當n=13的時候隻有以上兩種方法去疊，但隻能疊高度為2的塔。
相鄰兩個房間之間用一張卡片作為天花闆相連。現在他想知道n張卡片全部使用的情況下他一共可以疊成多少種不同高度的塔。
輸入一個整數n(1 <= n <= 10^9)，表示卡片數量；
輸出一個數字，可以疊成的高度的種類數。
示例1
輸入：
13
輸出：
1
解題思路：數學題
題目中問的是可以組成多少種不同高度的塔。
首先計算每種高度的塔至少需要多少張卡片，然後判斷多出來的卡片數與至少需要的卡片數之間的關系。
觀察下圖三層的塔。從上向下。
第一層一個房間，第二層兩個房間，……，第i層i個房間。
一個房間需要2張卡片，兩個房間需要5張卡牌（每個房間2張+天花闆1張），……，i個房間需要2i+i-1 = 3i-1張。
這樣每一層的卡片數都可以計算出來了，前k層的卡片數求和即可。記前k層最少需要f(k)張卡片
接下來觀察多餘卡片與房間的關系。下圖中圈出來的房間位置從1層放到了2層。是以，對于多出來的卡片，我們可以都放到第一層處理（因為題目隻問有多少種不同高度，而不是多少種不同的搭建方法）。
每多出來一間房，需要3張卡片（包括天花闆）。是以多餘的卡片為3的倍數，則這個高度的塔可以搭建。
計算過程
1、從第一層開始，計算f(i)，直到f(i)大于K。
2、判斷每個f(i)與k的內插補點是否為3的倍數，是，則總數加1。
時間空間複雜度都很小。f(i)不需要一個數組來儲存，隻需要算出目前層的直接判斷是否為3的倍數即可。
看完之後是不是有了想法了呢，快來練練手吧>>