筆試算法模拟題精解之“壞掉的時鐘”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“98.壞掉的時鐘”的解法探究。先來看一下題目内容：

題目描述

等級：容易

知識點：模拟

檢視題目：壞掉的時鐘

B同學有一個時鐘，能夠顯示1-d，初始值為1。這個時鐘每天顯示的數字加一，特殊的，當某天顯示的值為d時，第二天就會顯示1。

但是每個月的時間并不總是d天，是以B同學就要通過手動調整使得顯示的時間正确，每次手調都可以使顯示數字加一。

現在給你n個月每月的天數，請你計算一下若是讓時鐘每天顯示的數字都是正确的，他這n個月一共需要調多少次時鐘。

輸入月份數n（1 <= n <= 10^5）、時鐘的最大顯示時間d（1 <= d <= 10^4）和一個包含n個數的數組，第i個數表示第i個月有ai天（1 <= ai <= d）

輸出使時鐘正常顯示一共要調整的次數。

示例1

輸入：

3

5

[3, 4, 3]

輸出：

解題方法：模拟

本題關鍵在于了解題意：

題幹的含義是，在除去最後一個月後，其餘每個月的最後一天的24點時，時鐘上的邏輯時間會超過那個月的最大天數，同時實際時間變為下一個月的第1天。此時邏輯時間和實際時間有差别，需要調整時鐘，讓邏輯時間重新回到1，使其符合實際時間。

如題中例子所指：

3
5
[3, 4, 3]           

• 第1個月第1天，時鐘實際值1，符合；
• 第1個月第2天，時鐘實際值2，符合；
• 第1個月第3天，時鐘實際值3，符合；
• 第2個月第1天，時鐘實際值4，不符合，對時鐘進行2次加1操作，時鐘實際值變為1，符合；
• ......
• 第3個月第1天，時鐘實際值5，不符合，對時鐘進行1次加1操作，時鐘實際值變為1，符合；
• 第3個月第3天，時鐘實際值3，符合；
• 結束，共需要調整3次。

時間複雜度：O(n)

空間複雜度：O(1)

趁熱打鐵，快來練練手吧：

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，社群定制衛衣、雙肩背包等你來拿~每天都有好禮相送~點選了解周賽詳情：

線上程式設計内測中，搶先周賽赢好禮！面試考試前，快來刷刷題！

上一篇： 筆試算法模拟題精解之”斐波那契字元數” 下一篇： 筆試算法模拟題精解之“完美排列”