上海网站设计成功柚v米科技,seo全国最好的公司,php网站开发建设,西宁网站建设西宁有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 . 分隔。
例如#xff1a;0.1.2.201 和 192.168.1.1 是 有效 IP 地址#xff0c;但是 0.011.255.2…有效 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 中的任何数字。你可以按 任何 顺序返回答案。
思路一递归
int segments[4];
char** ans;
int ans_len;void dfs(char* s, int segId, int segStart) {int len_s strlen(s);if (segId 4) {if (segStart len_s) {char* ipAddr (char*)malloc(sizeof(char) * (len_s 4));int add 0;for (int i 0; i 4; i) {int number segments[i];if (number 100) {ipAddr[add] number / 100 0;}if (number 10) {ipAddr[add] number % 100 / 10 0;}ipAddr[add] number % 10 0;if (i ! 4 - 1) {ipAddr[add] .;}}ipAddr[add] 0;ans realloc(ans, sizeof(char*) * (ans_len 1));ans[ans_len] ipAddr;}return;}if (segStart len_s) {return;}if (s[segStart] 0) {segments[segId] 0;dfs(s, segId 1, segStart 1);}int addr 0;for (int segEnd segStart; segEnd len_s; segEnd) {addr addr * 10 (s[segEnd] - 0);if (addr 0 addr 0xFF) {segments[segId] addr;dfs(s, segId 1, segEnd 1);} else {break;}}
}char** restoreIpAddresses(char* s, int* returnSize) {ans (char**)malloc(0);ans_len 0;dfs(s, 0, 0);(*returnSize) ans_len;return ans;
}
分析
本题返回所有可能组成ip地址的情况可使用递归的方法判断各个数字组成ip地址的情况同时注意前数为零时零只能单独作为ip地址再将每个找到的数转换为字符最后返回
总结
本题考察递归的应用将每个数可能组成地址的情况列举出来即可得到答案
