LC: 247. Strobogrammatic Number II
https://leetcode.com/problems/strobogrammatic-number-ii/
247. Strobogrammatic Number II
Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Example 1:
Input: n = 2
Output: ["11","69","88","96"]Example 2:
Input: n = 1
Output: ["0","1","8"]Constraints:
1 <= n <= 14
The Essence:
Man kann bemerken, dass die strobogrammatischen Zahlen palindromisch sind. Man soll also aus bestimmten Ziffern eine palindromische Zeichenfolge bilden. Man beachtet dabei die Symmetrie der Zeichenfolge. Wenn man z. B. das Zeichen ‘6’ stellt, soll man für den entgegengesetzten Index das Zeichen ‘9’ stellen.
Bei diesem Problem ist es wichtig zu erkennen, dass diese "strobogrammatische" Zahl, die mit mathematischen Begriffen beschrieben wird, nur eine weitere Erscheinung von etwas ist, das im ersten Blick nichts mit Zeichen zu tun hat. Es ist wichtig zu beachten, dass einige Tatsachen im Wesentlichen eigentlich sehr ähnlich sein können.
Details:
Wir sollen beachten, dass wir keine '0' am Anfang sollen, das wäre keine gültige Zahl.
Wir können auch die “symmetrische” Zahlenpaare wie ‘6’-’9’, ‘0’-’0’, ‘8’-’8’ usw. in eine Tabelle einfügen und alle Möglichkeiten durchsuchen.
Der hier beschriebene Algorithmus ist unter Verwendung eines Backtracking-Algorithmus zu implementieren. Für den Problemlöser ist es wichtig, sich mit solchen algorithmischen Techniken vertraut zu machen.
Solutions:
Default Code:
Last updated