元戎启行春招二面

1、简单问了下实习

2、简单问了下C++

3、给一个string的数字，看能分成多少种点分十进制的IP地址。

vector<string> getIP(string num){

}

如 25525525可以生成以下：

255.255.2.25

2.55.255.255

...

用dfs写的，思路为往string num中放三个小数点,长度为n的num可以放.的位置有n-1个。

需要对每次划分的IP地址判断是否合法。点分十进制的IP地址的每一个十进制数必须在0~255之间。

#include<bits/stdc++.h>
using namespace std;


bool judge(string s){
     int i = 0;
     string now;
     for(;i < s.size(); ++i){
        now.clear();
        while(i < s.size() && s[i] != '.'){
            now += s[i];
            ++i;
        }
        int ans = 0;
        for(int j = 0; j < now.size(); ++j){
            ans = ans*10 + now[j] - '0';
        }
        if(now.size() != 1 && ans == 0) return false;//去掉00,000...
        if(ans < 0 || ans > 255) return false;
        i = i + 1;
     }
     return true;
}

void dfs(int pos, int cnt, int& n, vector<int>& vis,string& nums, vector<string>& ans ){
    if(cnt == 3){
       string temp;
       temp += nums[0];
       for(int i = 0; i < n; ++i){
          if(vis[i] == 1){
            temp += '.';
          }
          temp += nums[i+1];
       }
       if(judge(temp) == true){
        ans.push_back(temp); //判断是合法的IP地址，加入ans
       }
    }
    for(int i = pos; i < n; ++i){
        if(vis[i] != 0) continue;
        vis[i] = 1;
        cnt += 1;
        dfs(i,cnt,n,vis,nums,ans);
        cnt -= 1;
        vis[i] = 0;
    }
}

vector<string> GetIPaddress(string nums){
       int n = nums.size() - 1; //nums中可以放点的位置
       vector<int> vis(n+5,0);
       vector<string> ans;
       dfs(0, 0, n, vis, nums, ans);
       return ans;
}

int main(){

    string s = "25525525";
    auto ans = GetIPaddress(s);
    if(ans.size() == 0) cout << "无效输入！" << endl;
    for(auto v : ans){
        cout << v << endl;
    }
    system("pause");
    return 0;
}