本篇文章主要介绍了"[LeetCode 93] Restore IP Addresses"，主要涉及到方面的内容，对于Javajrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下：
题目链接：restore-ip-addressesimport java.util.ArrayList;
import java.util.List;/*** ...
题目链接：restore-ip-addresses
import java.util.ArrayList;
import java.util.List;
/**
*
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)
*
*/
public class RestoreIPAddresses {
// 147 / 147 test cases passed.
// Status: Accepted
// Runtime: 236 ms
// Submitted: 0 minutes ago
//回溯法
//时间复杂度O(n ^ 4) 空间复杂度O(n)
public List ips = new ArrayList();
public List restoreIpAddresses(String s) {
restoreIpAddresses(s, 0, "", 0);
return ips;
}
/**
*
* @param s 原始ip字符串
* @param cur 原始ip字符串的游标，表示当前从哪开始取数
* @param ip 已经生成的ip的中间值
* @param count 纪录已经生成的点位个数
*/
public void restoreIpAddresses(String s, int cur, String ip, int count) {
if(s.length() > 16) {
return;
}
if(count == 4 && cur < s.length())
return;
if(cur == s.length()) {
if (count == 4) {
ips.add(ip.substring(0, ip.length() - 1));
}
return;
}
//点分组为一位数时
int num1 = stringToInteger(s.substring(cur, cur + 1));
if (num1 >= 0 && num1 < 10) {
restoreIpAddresses(s, cur + 1, ip + num1 + ".", count + 1);
}
//点分组为两位数时
if (cur + 1 < s.length()) {
int num2 = stringToInteger(s.substring(cur, cur + 2));
if (num2 > 9 && num2 < 100) {
restoreIpAddresses(s, cur + 2, ip + num2 + ".", count + 1);
}
}
//点分组为三位数时
if (cur + 2 < s.length()) {
int num3 = stringToInteger(s.substring(cur, cur + 3));
if (num3 > 99 && num3 < 256) {
restoreIpAddresses(s, cur + 3, ip + num3 + ".", count + 1);
}
}
}
//字符转换为数值
public int stringToInteger(String s) {
int n = 0;
for (Character digit : s.toCharArray()) {
n = n * 10 + digit - '0';
}
return n;
}
public static void main(String[] args) {
System.out.println(new RestoreIPAddresses().restoreIpAddresses("25525511135"));
System.out.println(new RestoreIPAddresses().restoreIpAddresses("1111"));
}
}
以上就介绍了[LeetCode 93] Restore IP Addresses，包括了方面的内容，希望对Javajrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播有兴趣的朋友有所帮助。
本文网址链接：http://www.codes51.com/article/detail_124348.html
