[LeetCode] IP 주소 복원, 문제 풀이 보고서
오랫동안 ACM 에 관 한 블 로 그 를 쓰 지 않 았 습 니 다. 확실히 최근 에 너무 바 빴 습 니 다. 제 가 예전 에 섭렵 을 너무 적 게 했 기 때 문 입 니 다. 간단 한 app 이 거의 두 달 동안 공 을 들 였 지만 잘 완성 하지 못 했 습 니 다. 부 끄 럽 습 니 다!
청명절 연 휴 3 일 동안 여자친 구 와 함께 밥 을 먹고 탁 구 를 쳤 습 니 다. 하루 에 큰 논문 의 8000 자 를 참 았 습 니 다. 오늘 마지막 날 에 잠 을 보충 하고 ACM 을 썼 습 니 다.
ACM 에 대해 저 는 업무 중 에 사용 할 수 있 는 가능성 이 비교적 적다 고 생각 합 니 다. 그러나 그것 이 쓸모 가 없다 는 것 은 아 닙 니 다. 그리고 저 는 ACM 에 대해 개인 적 인 관심 을 가지 고 있 습 니 다. 그러나 2 개 월 동안 알고리즘 을 만 져 본 적 이 없어 서 쓰기 에 그리 순 조 롭 지 않 습 니 다. 오늘 은 DFS 문 제 를 마음대로 기록 합 니 다.
제목.
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
사고의 방향
우선 IP 주 소 는 4 부분 으로 나 뉘 는데 각 부분의 숫자 합 법 범 위 는 0 - 255 이다.
그 다음 에 주어진 문자열 에 대해 우 리 는 매번 하나, 두 개, 또는 세 개의 문 자 를 취하 여 문자열 을 구성 할 수 있다.경 계 를 넘 지 않 고 문자열 이 0 - 255 의 요 구 를 충족 시 키 지 않 으 면 이 부분 을 보류 하고 나머지 문자열 을 DFS 로 검색 하여 네 부분 을 구성 할 때 까지 합 니 다.선 을 넘 거나 요구 에 맞지 않 으 면 바로 뛰 어 넘 으 면 된다.
AC 코드
public class Solution {
public static ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> res = new ArrayList<String>();
if (s == null || s.length() < 4 || s.length() > 12) {
return res;
}
StringBuilder tmp = new StringBuilder();
depthFS(0, 0, s, tmp, res);
return res;
}
public static void depthFS(int count, int index, String s, StringBuilder tmp,
ArrayList<String> res) {
if (count == 4 && index == s.length()) {
res.add(tmp.toString().substring(0, tmp.length() - 1));
return;
} else {
for (int i = 1; i <= 3 && index + i <= s.length(); i++) {
String tmpStr = s.substring(index, index + i);
if (isValid(tmpStr)) {
int bt = tmp.length();
int ed = tmp.length() + tmpStr.length();
tmp.append(tmpStr).append(".");
depthFS(count + 1, index + i, s, tmp, res);
tmp.delete(bt, ed + 1);
}
}
}
}
public static boolean isValid(String s) {
if (s.charAt(0) == '0') {
return s.equals("0");
}
int num = Integer.parseInt(s);
return num > 0 && num <= 255;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.