代码随想录Day24_回溯_复原IP.md

复原IP地址

题目理解

1.给出的是字符串，IP地址在【0，255】之间，字符串转数字；
2.0可以单独出现，但是不能跟数字出现；
3.字符串中要插入'.';
4.字符串的大小范围在4~12之间；
5.不能有除数字外的字母；
思路

首先确定答案类型：vector res，一个用来存单个有效IP地址的字符串str；
1.函数返回值：void，函数参数，传进来的string s;
2.确定终止条件：插入4个'.'后；
3.单层回溯：
for循环遍历树的宽度:每次startIndex后移一位；
树的深度：每次.后移一位。后移两位。
问题

1.怎么在字符串中插入.? s.insert(pos,'neirong')

if(start>end){return false;}该条件是在处理空的字符串！很难想到这个边界条件。

1. class Solution {
2. public:
3.     vector<string> res;
4.     void backtrack(string& s, int startIndex, int pointNum) {
5.         if (pointNum == 3) {
6.             if (isValid(s, startIndex, s.size() - 1)) {
7.                 res.push_back(s);
8.             }
9.             return;
10.         }
11.         for (int i = startIndex; i < s.size(); i++) {
12.             if (isValid(s, startIndex, i)) {
13.                 s.insert(s.begin() + i + 1, '.');
14.                 pointNum++;
15.                 backtrack(s, i + 2, pointNum);
16.                 s.erase(s.begin() + i + 1);
17.                 pointNum--;
18.             } else {
19.                 break;
20.             }
21.         }
22.         return;
23.     }
24.     bool isValid(const string& s, int start, int end) {
25.         if (start > end) {
26.             return false;
27.         } // 输入：s=101023     输出：10.102.3.
28.         if (s[start] == '0' && start != end) {
29.             return false;
30.         }
31.         int sum = 0;
32.         for (int i = start; i <= end; i++) {
33.             if (s[i] < '0' || s[i] > '9') {
34.                 return false;
35.             }
36.             // 255逻辑
37.             sum = sum * 10 + (s[i] - '0');
38.             if (sum > 255) {
39.                 return false;
40.             }
41.         }
42.         return true;
43.     }
44.     vector<string> restoreIpAddresses(string s) {
45.         backtrack(s, 0, 0);
46.         return res;
47.     }
48. };

复制代码

求整数数组的所有子集

开始的时候在想每个整数数组都包含一个空的子集如何处理？写出来了但是不知道在哪里处理到了？
[code]class Solution {public:    vectorpath;    vector  res;    void backtrack(vector&nums, int startIndex){        res.push_back(path);        if(startIndex>=nums.size()){            return;        }        for(int i=startIndex;i=nums.size()){            return;        }        for(int i=startIndex;i