最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

环球新动态：【算法训练营day28】LeetCode93. 复原IP地址 LeetCode78. 子集 LeetCode90. 子集II

来源：博客园

LeetCode93. 复原IP地址

题目链接：93. 复原IP地址

独上高楼，望尽天涯

想起来简单，写起来还是很难的一道题， 小错误频发。


(资料图片)

慕然回首，灯火阑珊

首先，因为本题要求只能分割成四段，所以不能用start_index来判断是否终止，而是使用point_num是否等于3来判断，point_num等于3即已经分割出三段了，这时候只需要判断剩下的第四段是否合法即可。

其次，和之前的题目不同， 本题不需要单独维护一个path来保存临时结果，只需要在原s上加点即可。

最后，最好使用stol代替stoi防止整型溢出，同时需要提前判断输入的两个参数是否合法，即第一个参数必须小于等于第二个参数。

class Solution {private:    vector result;    bool isIP(const string& s, int start, int end) {        if (start > end) {            return false;        }        else if(end - start > 0 && s[start] == "0") {            return false;        }        else if (stol(s.substr(start, end - start + 1)) > 255) { // stol防止整型溢出            return false;        }        return true;    }    void backtracking(string s, int start_index, int point_num) {        if (point_num == 3) { // 注意使用的是point_num判断终止            if (isIP(s, start_index, s.size() - 1)) {                result.push_back(s);            }            return;        }        for (int i = start_index; i < s.size(); i++) {            if (isIP(s, start_index, i)) {                s.insert(i + 1, "."); // 直接修改s即可                point_num++;                backtracking(s, i + 2, point_num);                s.erase(i + 1, 1);                point_num--;            }            else {                break;            }        }    }public:    vector restoreIpAddresses(string s) {        backtracking(s, 0, 0);        return result;    }};

LeetCode78. 子集

题目链接：78. 子集

独上高楼，望尽天涯

比较简单的一道题，和组合问题很像，区别在于组合问题收集的是叶子节点的结果，本题是收集所有节点的结果。

class Solution {private:    vector> result;    vector path;    void backtracking(vector& nums, int start_index) {        result.push_back(path); // 收集所有节点的结果        for (int i = start_index; i < nums.size(); i++) {            path.push_back(nums[i]);            backtracking(nums, i + 1);            path.pop_back();        }    }public:    vector> subsets(vector& nums) {        backtracking(nums, 0);        return result;    }};

慕然回首，灯火阑珊

想的一样。

LeetCode90. 子集II

题目链接：90. 子集II

独上高楼，望尽天涯

和前面的一道题非常像，这次写在i < start_index上卡壳了，还需要时间消化。

慕然回首，灯火阑珊

理解“树层去重”和“树枝去重”非常重要

class Solution {private:    vector> result;    vector path;    void backtracking(vector& nums, int start_index) {        result.push_back(path);        for (int i = start_index; i < nums.size(); i++) {            if (i > start_index && nums[i] == nums[i-1]){ // 注意这里，i > start_index非常重要                continue;            }            path.push_back(nums[i]);            backtracking(nums, i + 1);            path.pop_back();        }    }public:    vector> subsetsWithDup(vector& nums) {        sort(nums.begin(), nums.end());        backtracking(nums, 0);        return result;    }};

关键词： 灯火阑珊 独上高楼望 独上高楼