我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 93. 復原IP地址
題目
給定一個只包含數字的字串，復原它并回傳所有可能的 IP 地址格式，
有效的 IP 地址正好由四個整數（每個整數位于 0 到 255 之間組成），整數之間用 '.' 分隔，
示例:
輸入: "25525511135"
輸出: ["255.255.11.135", "255.255.111.35"]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/restore-ip-addresses
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
思路1-單個段分析遞回（或者3for暴力解決）
因為ipv4段只有4段，所以可以直接3for解決，寫成遞回也行，一樣的邏輯；
具體看代碼吧，還是比較簡單的，思路清晰；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(3^{4}*|s|\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $ 如果不算存結果的空間
演算法原始碼示例
package leetcode;
import java.util.ArrayList;
import java.util.List;
/**
* @author ZhouJie
* @date 2020-8-10 15:09:24
* @Description: 93. 復原IP地址
*
*/
public class LeetCode_0093 {
}
class Solution_0093 {
/**
* @author: ZhouJie
* @date: 2020-8-10 17:01:33
* @param: @param s
* @param: @return
* @return: List<String>
* @Description: 1-ipv4只有4段，直接三段for回圈即可解決，且每段的判斷邏輯相同；
*
*/
public List<String> restoreIpAddresses(String s) {
List<String> list = new ArrayList<String>();
int len;
if (s == null || (len = s.length()) < 4 || len > 12) {
return list;
}
int n;
// 每段都有四個判斷：
// 1-剩余長度大于剩余段*3，則在當前回圈內continue；
// 2-剩余長度小于剩余段，直接break；
// 3-當前段非單個0且有前導0的，break；
// 4-轉int后大于255的，break；
for (int i = 0; i < 3; i++) {
n = len - i - 1;
if (n > 9) {
continue;
}
if (n < 3 || myCheck(s, 0, i + 1)) {
break;
}
for (int j = i + 1; j < 3 + i + 1; j++) {
n = len - j - 1;
if (n > 6) {
continue;
}
if (n < 2 || myCheck(s, i + 1, j + 1)) {
break;
}
for (int k = j + 1; k < 3 + j + 1; k++) {
n = len - k - 1;
if (n > 3) {
continue;
}
if (n < 1 || myCheck(s, j + 1, k + 1)) {
break;
}
// 最后一個段校驗
if (myCheck(s, k + 1, len)) {
continue;
}
list.add(new StringBuffer(s).insert(i + 1, ".").insert(j + 2, ".").insert(k + 3, ".").toString());
}
}
}
return list;
}
private boolean myCheck(String s, int i, int j) {
s = s.substring(i, j);
return s.startsWith("0") && j - i > 1 || Integer.parseInt(s) > 255;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/86680.html
標籤：Java