朝阳无限好 - Morning Sun Community

 找回密码
 注册
查看: 70|回复: 1

[中等] 93. 复原IP地址

[复制链接]
发表于 2020-4-7 22:05:13 | 显示全部楼层 |阅读模式
给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/restore-ip-addresses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
 楼主| 发表于 2020-4-7 22:06:03 | 显示全部楼层
  1. int getInt(char *s, int pos, int byteCnt)
  2. {
  3.     char tmp[4];
  4.     if (byteCnt > 3) {
  5.         return 0;
  6.     }
  7.     memcpy(tmp, &s[pos], byteCnt);
  8.     tmp[byteCnt] = 0;
  9.     return atoi(tmp);
  10. }

  11. void step(char* s, int index, int pos, int byteCnt, char **result, int *returnSize, int* tmp)
  12. {
  13.     int len = strlen(&s[pos]);
  14.     int size = 17;
  15.     if ((len < byteCnt) || (index > 3) || ((len - byteCnt) > ((4 - index - 1) * 3))) {
  16.         return;
  17.     }
  18.     if ((index == 3) && (len != byteCnt)) {
  19.         return;
  20.     }
  21.     if (byteCnt == 3) {
  22.         if ((s[pos] > '2') || ((s[pos] == '2') && (s[pos + 1] > '5')) || ((s[pos] == '2') && (s[pos + 1] == '5') && (s[pos + 2] > '5'))) {
  23.             return;
  24.         }
  25.     }
  26.     if ((s[pos] == '0') && (byteCnt > 1)) {
  27.         return;
  28.     }
  29.     tmp[index] = getInt(s, pos, byteCnt);
  30.     if (index == 3) {
  31.         result[*returnSize] = (char*)malloc(size);
  32.         snprintf(result[*returnSize], size - 1, "%d.%d.%d.%d", tmp[0], tmp[1], tmp[2], tmp[3]);
  33.         result[*returnSize][size - 1] = 0;
  34.         (*returnSize)++;
  35.     } else {
  36.         step(s, index + 1, pos + byteCnt, 1, result, returnSize, tmp);
  37.         step(s, index + 1, pos + byteCnt, 2, result, returnSize, tmp);
  38.         step(s, index + 1, pos + byteCnt, 3, result, returnSize, tmp);
  39.     }
  40. }

  41. /**
  42. * Note: The returned array must be malloced, assume caller calls free().
  43. */
  44. char ** restoreIpAddresses(char * s, int* returnSize){
  45.     int resultCnt = 0;
  46.     char **result;
  47.     int tmp[4] = {0, 0, 0, 0};

  48.     if (!s || !s[0] || !returnSize) {
  49.         if (returnSize) {
  50.             *returnSize = 0;
  51.         }
  52.         return NULL;
  53.     }
  54.     result = (char**)malloc(81 * sizeof(char*));
  55.     *returnSize = 0;
  56.    
  57.     step(s, 0, 0, 1, result, returnSize, tmp);
  58.     step(s, 0, 0, 2, result, returnSize, tmp);
  59.     step(s, 0, 0, 3, result, returnSize, tmp);
  60.     return result;
  61. }
复制代码
执行结果:通过
显示详情

执行用时 :4 ms, 在所有 C 提交中击败了70.47%的用户
内存消耗 :6 MB, 在所有 C 提交中击败了100.00%的用户
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|小黑屋|手机版|Archiver|朝阳无限好 ( 琼ICP备19005269号-1 )

GMT+8, 2020-7-7 16:30 , Processed in 0.094394 second(s), 24 queries .

快速回复 返回顶部 返回列表