Restore IP Addresses -- LeetCode
이 문제 의 해법 은 NP 문제 에 매우 가깝다.
재 귀적 해법 도 채택 했다.기본 적 인 사 고 는 합 법 적 인 숫자 를 꺼 내 IP 주소 의 하나 로 한 다음 에 나머지 항목 을 재 귀적 으로 처리 하 는 것 이다.하나의 나 무 를 상상 할 수 있 습 니 다.각 결점 에는 세 개의 가능 한 가지 가 있 습 니 다.(범 위 는 0-255 이기 때문에 한 사람 두 사람 또는 세 사람 으로 구성 할 수 있 습 니 다)그리고 여기 나무의 층 수 는 4 층 을 초과 하지 않 습 니 다.IP 주 소 는 4 단 으로 구성 되 기 때문에 도착 한 후에 우 리 는 다시 돌아 갈 필요 가 없습니다.끝 낼 수 있 습 니 다.여기 서 상술 한 종료 조건 을 제외 하고 다른 하 나 는 문자열 을 다 읽 은 것 이다.이 나무의 규 모 는 고정 되 어 있 음 을 알 수 있 으 며,일반적인 NP 문제 처럼 되 지 는 않 을 것 이다.
그러면 시간 복잡 도 는 입력 의 규모 에 달 려 있 고 지수 급 이기 때문에 이 문 제 는 NP 문제 가 아니다.
그의 가 지 는 4 단 이기 때문에 제한 이 있다.코드 는 다음 과 같 습 니 다:
public ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> res = new ArrayList<String>();
if(s==null || s.length()==0)
return res;
helper(s,0,1,"",res);
return res;
}
private void helper(String s, int index, int segment, String item, ArrayList<String> res)
{
if(index>=s.length())
return;
if(segment == 4)
{
String str = s.substring(index);
if(isValid(str))
{
res.add(item+"."+str);
}
return;
}
for(int i=1;i<4&&(i+index<=s.length());i++)
{
String str = s.substring(index, index+i);
if(isValid(str))
{
if(segment==1)
helper(s,index+i,segment+1,str,res);
else
helper(s,index+i,segment+1,item+"."+str,res);
}
}
}
private boolean isValid(String str)
{
if(str==null || str.length()>3)
return false;
int num = Integer.parseInt(str);
if(str.charAt(0)=='0' && str.length()>1)
return false;
if(num>=0 && num<=255)
return true;
return false;
}실현 에 있어 서 숫자 가 합 법 적 인 ip 주소 인지 아 닌 지 를 판단 하 는 함수 가 필요 합 니 다.먼저 0-255 사이 이 고 그 다음 에 앞 문 자 는 0 이 될 수 없습니다.나머지 는 NP 문제 입 니 다.
for 순환
하.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
