Link: https://leetcode.com/problems/total-waviness-of-numbers-in-range-i/description/

Đề bài#

You are given two integers num1 and num2 representing an inclusive range [num1, num2].

The waviness of a number is defined as the total count of its peaks and valleys:

• A digit is a peak if it is strictly greater than both of its immediate neighbors.
• A digit is a valley if it is strictly less than both of its immediate neighbors.
• The first and last digits of a number cannot be peaks or valleys.
• Any number with fewer than 3 digits has a waviness of 0.

Return the total sum of waviness for all numbers in the range [num1, num2].

Example 1:

Input: num1 = 120, num2 = 130
Output: 3
Explanation:

In the range [120, 130]:

• 120: middle digit 2 is a peak, waviness = 1.
• 121: middle digit 2 is a peak, waviness = 1.
• 130: middle digit 3 is a peak, waviness = 1.
• All other numbers in the range have a waviness of 0.

Thus, total waviness is 1 + 1 + 1 = 3.

Example 2:

Input: num1 = 198, num2 = 202
Output: 3
Explanation:

In the range [198, 202]:

• 198: middle digit 2 is a peak, waviness = 1.
• 201: middle digit 2 is a peak, waviness = 1.
• 202: middle digit 3 is a peak, waviness = 1.
• All other numbers in the range have a waviness of 0.

Thus, total waviness is 1 + 1 + 1 = 3.

Example 3:

Input: num1 = 4848, num2 = 4848
Output: 2
Explanation:
Number 4848: the second digit 8 is a peak, and the third digit 4 is a valley, giving a waviness of 2.

Constraints:

• 1 <= num1 <= num2 <= $10^5$

Phân tích bài toán#

Bài toán khiến người giải mất 1 khoảng thời gian để hiểu và làm thử. Cách basic nhất là viết 1 hàm check, dếm số con sóng trong từ số, trả về kết quả và duyệt qua. Cách này pass luôn nên mình không cần overthinking tối ưu. Một số lợi thế như sau:

• Convert số sang chuỗi, duyệt từng phần tử, khi so sánh ký tự ‘0’, ‘1’, ‘2’ … ‘9’, do mã ASCII nên nó vẫn so sánh đúng.
• Tối đa constraints là 10^5, tức là thường số lớn nhất để đếm thành công mất O(3) - Do bỏ qua ký tự đầu cuối, và lặp từ num1 => num2 max cũng chỉ 10000 số => Khoảng 30K phép tính => time-complexity rất ok để brute force - O(n).
• Con số này nhỏ như thế nào?
  Một máy tính hiện đại chạy JavaScript (V8 Engine) có thể xử lý khoảng $10^8$ (100 triệu) phép tính đơn giản mỗi giây. Vì thế, việc xử lý dưới $500,000$ phép tính chỉ tiêu tốn chưa đến 2ms đến 5ms trên máy chủ LeetCode.

Final solution#

/**
 * @param {number} num1
 * @param {number} num2
 * @return {number}
 */

function countWaves(num) {
    if (num < 100) {
        return 0;
    }
    let waves = 0;
    const numString = String(num);
    for (let i = 1; i < numString.length - 1; i++) {
        if (numString[i] < numString[i-1] && numString[i] < numString[i+1]) {
            waves++;
        }
        if (numString[i] > numString[i-1] && numString[i] > numString[i+1]) {
            waves++;
        }
    }
    return waves
}
var totalWaviness = function(num1, num2) {
    let total = 0;
    for (let i = num1; i <= num2; i++) {
        total += countWaves(i)
    }
    return total
};