[LeetCode] 248. Strobogrammatic Number III
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
Example:
Input: low = "50", high = "100"Output: 3 Explanation: 69, 88, and 96 are three strobogrammatic numbers.Note:Because the range might be a large number, the low and high numbers are represented as string.
Solution
class Solution {
int count = 0;
public int strobogrammaticInRange(String low, String high) {
Map map = new HashMap<>();
map.put('0', '0');
map.put('1', '1');
map.put('6', '9');
map.put('8', '8');
map.put('9', '6');
List res = new ArrayList<>();
for (int len = low.length(); len <= high.length(); len++) {
dfs(map, low, high, new char[len], 0, len-1, res);
}
System.out.println(res);
return count;
}
private void dfs(Map map, String low, String high, char[] buffer, int left, int right, List res) {
if (left > right) {
String num = new String(buffer);
if ((num.length() == low.length() && num.compareTo(low) < 0) ||
(num.length() == high.length() && num.compareTo(high) > 0)) {
return;
}
count++;
res.add(num);
return;
}
for (char ch: map.keySet()) {
if (buffer.length != 1 && left == 0 && ch == '0') continue;
if (left == right && ch != map.get(ch)) continue;
buffer[left] = ch;
buffer[right] = map.get(ch);
dfs(map, low, high, buffer, left+1, right-1, res);
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
실생활 예 - 재귀 구성 요소플랫 배열을 재귀 객체(트리)로 전환한 재귀 방식으로 주석 표시에 대한 다음은 React의 UI 구현입니다. 달성하고자 하는 최종 결과는 다음과 같습니다. 가장 먼저 볼 수 있는 것은 모든 댓글 본문이 매우 유사하다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
