个人网站怎么做推广,做网站的实训报告,做淘宝店铺标志的网站,长沙app网站开发题目描述#xff1a;有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 ‘.’ 分隔。 例如#xff1a;“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址#xff0c;但是 “0.011.25… 题目描述有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 ‘.’ 分隔。 例如“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址但是 “0.011.255.245”、“192.168.1.312” 和 “192.1681.1” 是 无效 IP 地址。 给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。 题目链接LeetCode-93-复原IP地址 解题思路贪心算法 代码实现下面这种效率并不高可以尝试使用 StringBuilder class Solution {ListString res new ArrayList();public ListString restoreIpAddresses(String s) {if (s.length() 12 || s.length() 4){return res;}backTracking(s,0,0);return res;}public void backTracking(String s, int startIndex, int pointSum){if (pointSum 3){// 当字符串中的 . 大于3个时结束递归提前剪枝return;}if (pointSum3){if (isNumber(s, startIndex, s.length()-1)){res.add(new String(s));return;}}for (int i startIndex; i s.length(); i) {if (isNumber(s,startIndex,i)){s s.substring(0,i1) . s.substring(i1);System.out.println(s);backTracking(s, i2, pointSum1);s s.substring(0,i1) s.substring(i2);}else {continue;}}}// 判断s.index[start, end]前闭后闭的区间是否是合法数字public boolean isNumber(String s, int start, int end){if (end start){return false;}int num 0;if (s.charAt(start) 0 end ! start){return false;}for (int i start; i end ; i) {// 第一位也不能是 0如果只有一位可以是0如果后面还有就不能是 0num num *10 s.charAt(i)-0;// 获取[start, end]值}if (num0 || num 255){return false;}else {return true;}}
}
