leetcode Backtracking Recursion Depth-First Search

leetcode 401题

Posted by franki on February 2, 2021

leetcode 401题 二进制手表

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。

每个 LED 代表一个 0 或 1，最低位在右侧。

例如，上面的二进制手表读取 “3:25”。

给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。

示例1:

输入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

思路

递归 + 回溯

代码

function readBinaryWatch(num) {
    if (num === 0) return ["0:00"];
    
    const list = [1, 2, 4, 8, 1, 2, 4, 8, 16, 32];
    let count = 0;
    let res = [];

    dfs(0, 0, 0);
    return res;

    function dfs(start, hour, minute) {
        if (count === num && hour < 12 && minute < 60) {
            res.push(`${hour}:${minute < 10 ? "0"+minute : minute}`);
        }
        if (count >= num || hour > 11 || minute > 59) return;
        for (let i=start; i<list.length; i++) {
            const item = list[i];
            if (i < 4) {
                hour += item;
            } else {
                minute += item;
            }
            count++;
            dfs(i+1, hour, minute);
            count--;
            if (i < 4) {
                hour -= item;
            } else {
                minute -= item;
            }
        }  
    }
}

复杂度分析

  • 时间复杂度: O(n^2)
  • 空间复杂度: O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS