Cinte's Leetcode Record
0%

Posted on Edited on In Disqus:
Symbols count in article: 3.2k Reading time ≈ 3 mins.

101. Symmetric Tree

recursively
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isTwoTreesSymmetric(root->left, root->right);
    }
private:
    bool isTwoTreesSymmetric(TreeNode* lTree, TreeNode* rTree)
    {
        if((!lTree && rTree) || (!rTree && lTree))
            return false;
        if(!lTree && !rTree)
            return true;
        if(lTree->val == rTree->val)
            return isTwoTreesSymmetric(lTree->left, rTree->right) && isTwoTreesSymmetric(lTree->right, rTree->left);
        return false;
    }
};
iteratively queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        q.push(root);
        while(!q.empty())
        {
            auto t1 = q.front();
            q.pop();
            auto t2 = q.front();
            q.pop();
            if(!t1 && !t2) continue;
            if(!t1 || !t2) return false;
            if(t1->val != t2->val) return false;
            q.push(t1->left);
            q.push(t2->right);
            q.push(t1->right);
            q.push(t2->left);
        }
        return true;
    }
};
iteratively stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        s.push(root);
        while(!s.empty())
        {
            auto t1 = s.top();
            s.pop();
            auto t2 = s.top();
            s.pop();
            if(!t1 && !t2) continue;
            if(!t1 || !t2) return false;
            if(t1->val != t2->val) return false;
            s.push(t1->left);
            s.push(t2->right);
            s.push(t1->right);
            s.push(t2->left);
        }
        return true;
    }
};

上述方法从root开始比较了两次，不好，下面改改 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while(!q.empty())
        {
            auto p1 = q.front();
            q.pop();
            auto p2 = q.front();
            q.pop();
            if(!p1 && !p2)
                continue;
            if(!p1 || !p2)
                return false;
            if(p1->val != p2->val)
                return false;
            q.push(p1->left);
            q.push(p2->right);
            q.push(p1->right);
            q.push(p2->left);
        }
        return true;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

75. Sort Colors

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    void sortColors(vector<int>& nums) {
        sort(nums, 0, nums.size() - 1);
    }
private:
    void sort(vector<int>& nums, int lo, int hi)
    {
        if(lo >= hi) return;
        int j = partition(nums, lo, hi);
        sort(nums, lo, j - 1);
        sort(nums, j + 1, hi);
    }
    int partition(vector<int>& nums, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        int v = nums[lo];
        while(true)
        {
            while(i < hi && nums[++i] < v) {}
            while(lo < j && nums[--j] > v) {}
            if(i >=j ) break;
            swap(nums[i], nums[j]);
        }
        swap(nums[lo], nums[j]);
        return j;
    }
};

快速排序算法，每次取一个数为v，将所有大于v的数放在v右边，小于V的数放在v左边，最后将选择的数放到正确位置上，再对剩下的2个进行分而治之

针对具体问题的解决方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int second = nums.size() - 1;
        int zero = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            while(nums[i] == 2 && i < second)
                swap(nums[i], nums[second--]);
            while(nums[i] == 0 && i > zero)
                swap(nums[i], nums[zero++]);
        }
    }
};

总体思路是将0移到最前面，将2移到最后面

这里==2必须放在==0之前，因为2为最大的，将2换到最后去，换回来的只可能比2小，会有可能是0，需要处理。若0在前，则2换完后的0得不到处理。

review 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int z_p = 0, t_p = nums.size() - 1;
        for(int i = 0; i <= t_p; ++i) {
            while(i <= t_p && nums[i] == 2)
                swap(nums[i], nums[t_p--]);
            if(i >= z_p && nums[i] == 0)
                swap(nums[i], nums[z_p++]);
        }
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.3k Reading time ≈ 1 mins.

56. Merge Intervals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
bool mySort(vector<int>& a, vector<int>& b)
{
    return a[0] < b[0];
}
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<int> re;
        sort(intervals.begin(), intervals.end(), mySort);
        re.push_back(intervals[0][0]);
        re.push_back(intervals[0][1]);
        int index = 2;
        for(auto i = intervals.begin() + 1; i != intervals.end(); ++i)
        {
            if((*i)[0] <= re[index - 1])
                re[index - 1] = max(re[index - 1], (*i)[1]);
            else
            {
                re.push_back((*i)[0]);
                re.push_back((*i)[1]);
                index += 2;
            }
        }
        vector<vector<int>> ret;
        for(int i = 0; i < re.size(); i += 2)
        {
            ret.push_back({re[i], re[i + 1]});
        }
        return ret;
    }
};

T(n) : O(nlogn)
S(n) : O(n)

同样思路的一个Solution

空间和时间占用更少

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        /*
        sort(intervals.begin(), intervals.end(), [](vector<int>& i1, vector<int>& i2)
        {
            return i1[0] < i2[0];
        });
        */
        vector<vector<int>> ret;
        for(auto& interval : intervals)
        {
            if(ret.empty() || interval[0] > ret.back()[1])
                ret.push_back(interval);
            else
                ret.back()[1] = max(interval[1], ret.back()[1]);
        }
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.2k Reading time ≈ 2 mins.

55. Jump Game

这段话很好

跟着答案走

动态规划

首先，确定网格中最后一个元素可以到达他本身，自上而下，进行判断前一个可以到达他的元素是什么
由此，慢慢的，从后面开始，可以到达最后一块的坐标都被用good填充，这样一来，其他的回溯只需要判断能否到达这些good的点即可，而无需全都走到最后一个 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
enum status {
    GOOD,
    BAD,
    UNKNOW
};
class Solution {
public:
    bool canJump(vector<int>& nums) {
        dp = new status[nums.size()];
        fill(dp, dp + nums.size(), UNKNOW);
        dp[nums.size() - 1] = GOOD;
        return backTrack(nums, 0);
    }
private:
    status* dp;
    bool backTrack(vector<int>& nums, int start)
    {
        if(dp[start] != UNKNOW)
            return dp[start] == GOOD;
        
        int maxPos = (start + nums[start] > nums.size() - 1) ? nums.size() - 1 : start + nums[start];
        
        for(int pos = start + 1; pos <= maxPos; ++pos)
        {
            if(backTrack(nums, pos))
            {
                dp[start] = GOOD;
                return true;
            }
        }
        dp[start] = BAD;
        return false;
    }
};
T(n) : O(n^2)
S(n) : O(n)

bottom Up

从最后出发，判断前一步可不可以走到一个good，依次回去。 image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
enum status
{
    UNKNOW,
    GOOD
};
class Solution {
public:
    bool canJump(vector<int>& nums) {
        status* dp = new status[nums.size()];
        fill(dp, dp + nums.size(), UNKNOW);
        dp[nums.size() - 1] = GOOD;
        for(int pos = nums.size() - 2; pos >= 0; --pos)
        {
            int maxPos = pos + nums[pos] > nums.size() - 1 ? nums.size() - 1 : pos + nums[pos];
            for(int cur = maxPos; cur > pos; --cur)
            {
                if(dp[cur] == GOOD)
                {
                    dp[pos] = GOOD;
                    break;
                }
            }
        }
        return dp[0] == GOOD;
    }
};

T(n) : O(n^2)
S(n) : O(n)

greedy

对于一路上的所有good，我能走到右边的就能走到左边的一个good，因此 只需要记录最左边的一个的坐标，空间复杂度降为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int lastPos = nums.size() - 1;
        for(int pos = nums.size() - 2; pos >=0 ; --pos)
        {
            if(pos + nums[pos] >= lastPos)
                lastPos = pos;
        }
        return lastPos == 0;
    }
};

T(n) : O(n)
S(n) : O(1)

更greedy
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        int i = 0;
        for(i; i < nums.size() && maxReach >= i; ++i)
        {
            maxReach = max(i + nums[i], maxReach);
            if(maxReach >= nums.size() - 1) return true;
        }
        return maxReach >= nums.size() - 1;
    }
};

每步都贪，贪不了了就停了

review 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int farest = 0;
        for(int i = 0, sz = nums.size(); i < sz; ++i)
        {
            if(farest < i)
                return false;
            farest = max(farest, i + nums[i]);
        }
        return true;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.1k Reading time ≈ 1 mins.

141. Linked List Cycle

最没技术的做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> set;
        while(head)
        {
            if(set.emplace(head).second)
                head = head->next;
            else
                return true;
        }
        return false;
    }
};

T(n) : O(n)
S(n) : O(n)

two point

nb! explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head) return false;
        ListNode* fast = head;
        ListNode* slow = head;
        // 当只有一个节点构成个环时，是可以进入循环，如果没环，就无法进入。就可以处理只有一个的情况
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast)
                return true;
        }
        return false;
    }
};

假设slow起始位于N(0),而fast位于N(d - 1)（其中d为一个随机位置）
假设环的长度为M，则t时间后slow位于N(t mod M)，而fast位于N((2t + d) mod M)
\[\left\{ \begin{aligned} t = pM + x \\ 2t + d = qM + x \end{aligned} \right.\] 两式相减
得到t = (q - p)M - d
因此，他们必相遇

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

95. Unique Binary Search Trees II

dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<vector<TreeNode*>> dp(n + 1);
        dp[0] = {nullptr};
        for(size_t i = 1; i <= n; ++i)
        {
            for(size_t j = 1; j <= i; ++j)
            {
                for(auto& nodeLeft : dp[j - 1])
                {
                    for(auto& nodeRight : dp[i - j])
                    {
                        TreeNode* tmp = new TreeNode(j);
                        tmp->left = nodeLeft;
                        tmp->right = clone(nodeRight, j);
                        dp[i].push_back(tmp);
                    }
                }
            }
        }
        return dp.back();
    }
private:
    TreeNode* clone(TreeNode* root, int offset)
    {
        if(!root)
            return nullptr;
        TreeNode* newNode = new TreeNode(root->val + offset);
        newNode->left = clone(root->left, offset);
        newNode->right = clone(root->right, offset);
        return newNode;
    }
};

和Unique Binary Search Trees相似，只不过这个要列举出所有节点

递归分治
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return helper(1, n);
    }
private:
    vector<TreeNode*> helper(int start, int end)
    {
        if(start > end)
            return { nullptr };
        vector<TreeNode*> ret;
        for(int i = start; i <= end; ++i)
        {
            auto left = helper(start, i - 1);
            auto right = helper(i + 1, end);
            for(auto& l : left)
            {
                for(auto& r : right)
                {
                    auto cur = new TreeNode(i);
                    cur->left = l;
                    cur->right = r;
                    ret.push_back(cur);
                }
            }
        }
        return ret;
    }
};

好难想

从下建立起树，然后往上走，连接

Posted on Edited on In Disqus:
Symbols count in article: 2.2k Reading time ≈ 2 mins.

650. 2 Keys Keyboard

dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1);
        dp[1] = 0;
        for(size_t i = 2; i <= n; ++i)
        {
            dp[i] = i;
            for(size_t j = i - 1; j > 1; --j)
            {
                if(!(i % j))
                {
                    dp[i] = dp[j] + i / j;
                    break;
                }
            }
        }
        return dp.back();
    }
};

T(n) : O(n^2) ?
S(n) : O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1);
        dp[1] = 0;
        for(int i = 2; i <= n; ++i)
        {
            dp[i] = i;
            // j 和 i / j必定有一个小于等于根号i
            for(int j = 2; j * j <= i; ++j)
            {
                if(i % j == 0)
                {
                    dp[i] = min(dp[j] + i / j, dp[i]);
                    dp[i] = min(dp[i / j] + j, dp[i]);
                }
            }
        }
        return dp.back();
    }
};

寻找当前的最大除以2...的数，然后将那个数对应的操作翻倍 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Elegant solution.
Allow me to explain what is being done here.
As per the keyboard operations:
to get AA from A we need 2 additional steps (copy-all and then paste)
to get AAA from A we need 3 additional steps (copy-all, then paste, then again paste)

For generating AAAA we need 2 additional steps from AA.
however, to get AAAAAAAA, the most optimal way would be from AAAA, with 2 additional steps (copy-all then paste)
Essentially, we find the next smaller length sequence (than the one under consideration) which can be copied and then pasted over multiple times to generate the desired sequence. The moment we find a length that divides our required sequence length perfectly, then we don't need to check for any smaller length sequences.

// if sequence of length 'j' can be pasted multiple times to get length 'i' sequence
if (i % j == 0) {
    // we just need to paste sequence j (i/j - 1) times, hence additional (i/j) times since we need to copy it first as well.
    // we don't need checking any smaller length sequences 
    dp[i] = dp[j] + (i/j);
    break;
}
1
2
3
如果找到了一个更短的序列也能被整除，假设第一次找到的为j，第二次找到的为k，则j / k = m，设i / j = n，则i / k = m * n。则dp[j] = dp[k] + m，而dp[i] = dp[j] + n = dp[k] + m * n
则dp[i] = dp[j] + n = dp[k] + m * n = dp[k] + m + n，因为当m > 1 && n > 1时，m+n<mn(mn - (m + n) = (m - 1)(n - 1))，所以第一次遇到的就是最小的结果。
当然，如果不放心的话，也可以用min来遍历
##### solution数学方法

Prime Factorization 整数分解

看题解吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minSteps(int n) {
        int ret = 0;
        int d = 2;
        while(n > 1)
        {
            while(!(n % d))
            {
                ret += d;
                n /= d;
            }
            ++d;
        }
        return ret;
    }
};

T(n) : O(n) worst
S(n) : O(1)

Posted on Edited on In Disqus:
Symbols count in article: 575 Reading time ≈ 1 mins.

139. Word Break

##### dp

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict;
        for(auto& word : wordDict)
        {
            dict.insert(word);
        }
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for(size_t i = 1; i <= s.size(); ++i)
        {
            for(size_t j = 0; j < i; ++j)
            {
                if(dp[j] && (dict.find(s.substr(j, i - j)) != dict.end())) // 对于后面的i来说，要用到前面的结果，如果某一块前面部分是true的且剩下的也是可分的，那么这一块也是true，就不用重复判断前面部分了
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp.back();
    }
};
};

T(n) : O(n^2) ?
S(n) : O(n)

动态规划 ： 用数组存储子问题的值，用子问题的值直接得到现在问题的值

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

279. Perfect Squares

backTrack 超时了，虽然可以运行但是太慢了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int numSquares(int n) {
        int count = INT_MAX;
        int temp = 0;
        backTrack(n, count, temp);
        return count;
        
    }
private:
    void backTrack(int n, int& count, int& temp)
    {
        if(n == 0)
            count = min(count, temp);
        
        for(size_t i = sqrt(n); i > 0; --i)
        {
            ++temp;
            backTrack(n - i * i, count, temp);
            --temp;
        }
    }
};
dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numSquares(int n) {
        vector<int> cnt(n + 1, INT_MAX - 1);
        cnt[0] = 0;
        for(size_t i = 1; i <= n; ++i)
        {
            for(size_t j = 1; j * j <= i; ++j)
            {
                cnt[i] = min(cnt[i - j * j] + 1, cnt[i]);
            }
        }
        return cnt[n];
    }
};

T(n) : O(nlogn)
S(n) : O(n)

动态规划 ： 用数组存储子问题的值，用子问题的值直接得到现在问题的值

BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int numSquares(int n) {
        // 整体转化为对一个图的BFS
        // 当且仅当节点I和节点J相差一个perfect square number的时候，两点连线
        int depth = 1;
        vector<bool> visited(n, false); // 访问过的点 
        vector<int> prefectNumber; 
        // 先计算低于n的所有完全平方数
        for(int i = 1; i * i <= n; ++i)
        {
            prefectNumber.push_back(i * i);
            visited[i * i - 1] = true;
        }
        // 如果n本身就是完全平方数，那就直接返回
        if(prefectNumber.back() == n)
            return 1;
        queue<int> q;
        // 这是第一圈，先把所有完全平方数push进去
        for(auto& num : prefectNumber)
            q.push(num);
        // 开始往外扩圈
        while(!q.empty())
        {
            ++depth;
            for(int i = 0, j = q.size(); i < j; ++i)
            {
                auto p = q.front();
                q.pop();
                for(auto& num : prefectNumber)
                {
                    // 首次碰到等于n的那一圈就是所要求的最小值
                    if(num + p == n)
                        return depth;
                    // 访问过的点不需要再去访问，反之去访问并把这个点加入到下一圈要访问的候选
                    else if(num + p < n && !visited[num + p - 1])
                    {
                        visited[num + p - 1] = true;
                        q.push(num + p);
                    // 大于n的节点无需访问，由于存着的完全平方数是递增的，所以可以直接跳出循环。
                    }else if(num + p > n)
                        break;
                }
            }
        }
        return 0;
    }
};

一圈一圈地往外找

math，借助Legendre's three-square theorem

摸了

Posted on Edited on In Disqus:
Symbols count in article: 3.4k Reading time ≈ 3 mins.

131. Palindrome Partitioning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    vector<vector<string>> partition(string s) {
        int size = s.size();
        vector<vector<string>> ret;
        vector<string> temp;
        backTrack(ret, temp, s, 0);
        return ret;
    }
private:
    void backTrack(vector<vector<string>>& ret, vector<string>& temp, string& s, size_t start)
    {
        if(start > s.size() - 1)
            ret.push_back(temp);
        
        for(size_t i = start; i < s.size(); ++i)
        {
            if(isPalindrome(s.substr(start, i - start + 1)))
            {
                temp.push_back(s.substr(start, i - start + 1));
                backTrack(ret, temp, s, i + 1);
                temp.pop_back();
            }
        }
    }
    bool isPalindrome(string s) {
        auto lo = s.begin();
        auto hi = s.end() - 1;
        while(lo < hi)
        {
            if(!isAlphabet(*lo))
                ++lo;
            else if(!isAlphabet(*hi))
                --hi;
            else
            {
                if(*lo != *hi)
                    return false;
                ++lo;
                --hi;
            }
            
        }
        return true;
    }
    bool isAlphabet(char& ch)
    {
        if(ch >= 'a' && ch < 'z')
            return true;
        else
            return false;
    }
};
review
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<string> tmp;
        backTrack(s, s.size(), 0, tmp);
        return ret;
    }
private:
    vector<vector<string>> ret;
    void backTrack(string& s, int length, int index, vector<string>& tmp)
    {
        if(index == length)
        {
            ret.emplace_back(tmp);
            return;
        }
        for(int i = index; i < length; ++i)
        {
            if(isPalindorm(s, index, i))
            {
                tmp.push_back(s.substr(index, i - index + 1));
                backTrack(s, length, i + 1, tmp);
                tmp.pop_back();
            }
        }
    }
    inline bool isPalindorm(string& s, int i, int j)
    {
        while(i < j) {
            if(s[i++] != s[j--])
                return false;
        }
        return true;
    }
};

但是可以发现，回溯过程中会出现许多的重复的判断回文子串，所以有2种优化策略，一是预先判断回文子串，而是在回溯过程中进行记忆。

预先判断回文子串 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<string> tmp;
        memo.assign(s.size(), vector<int>(s.size(), 1));
        int n = s.size();
        for(int i = n - 1; i >= 0; --i)
            for(int j = i + 1; j < n; ++j)
                memo[i][j] = s[i] == s[j] && memo[i + 1][j - 1];
        backTrack(s, s.size(), 0, tmp);
        return ret;
    }
private:
    vector<vector<string>> ret;
    vector<vector<int>> memo;
    void backTrack(string& s, int length, int index, vector<string>& tmp)
    {
        if(index == length)
        {
            ret.emplace_back(tmp);
            return;
        }
        for(int i = index; i < length; ++i)
        {
            if(memo[index][i])
            {
                tmp.push_back(s.substr(index, i - index + 1));
                backTrack(s, length, i + 1, tmp);
                tmp.pop_back();
            }
        }
    }
};
在回溯过程中记忆 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<string> tmp;
        memo.assign(s.size(), vector<int>(s.size()));
        backTrack(s, s.size(), 0, tmp);
        return ret;
    }
private:
    vector<vector<string>> ret;
    vector<vector<int>> memo;
    void backTrack(string& s, int length, int index, vector<string>& tmp)
    {
        if(index == length)
        {
            ret.emplace_back(tmp);
            return;
        }
        for(int i = index; i < length; ++i)
        {
            if(isPalindorm(s, index, i) == 1)
            {
                tmp.push_back(s.substr(index, i - index + 1));
                backTrack(s, length, i + 1, tmp);
                tmp.pop_back();
            }
        }
    }
    // memo[i][j] == 0为未搜索，1为是回文子串，-1为不是
    inline int isPalindorm(string& s, int i, int j)
    {
        if(memo[i][j])
            return memo[i][j];
        if(i >= j)
            return memo[i][j] = 1;
        return s[i] == s[j] ? isPalindorm(s, i + 1, j - 1) : -1;
    }
};