Cinte's Leetcode Record
0%

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

剑指 Offer 28. 对称的二叉树

递归
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
//**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        return helper(root->left, root->right);
    }
private:
    bool helper(TreeNode* node1, TreeNode* node2)
    {
        if(!node1 && !node2)
            return true;
        if(!node1 || !node2 || node1->val != node2->val)
            return false;
        return helper(node1->left, node2->right) && helper(node1->right, node2->left); 
    }
};
迭代
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        queue<TreeNode*> q;
        q.push(root);
        q.push(root);
        while(!q.empty())
        {
            auto p1 = q.front();
            q.pop();
            auto p2 = q.front();
            q.pop();
            if(!p1 && !p2)
                continue;
            if(!p1 || !p2 || 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: 934 Reading time ≈ 1 mins.

剑指 Offer 27. 二叉树的镜像

递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)
            return nullptr;
        swap(root->left, root->right);
        mirrorTree(root->left);
        mirrorTree(root->right);
        return 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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root)
            return nullptr;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty())
        {
            auto p = s.top();
            s.pop();
            if(p->left)
                s.push(p->left);
            if(p->right)
                s.push(p->right);
            swap(p->right, p->left);
        }        
        return root;
    }
};

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

剑指 Offer 26. 树的子结构

迭代
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!B || !A)
            return false;
        if(A->val == B->val && helper(A->left, B->left) && helper(A->right, B->right))
            return true;
        return isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
private:
    bool helper(TreeNode* A, TreeNode* B)
    {
        if(!B)
            return true;
        if(!A)
            return false;
        if(A->val != B->val)
            return false;
        return helper(A->left, B->left) && helper(A->right, B->right);
        
    }

};

遍历树，碰到A中值和B根相同的点就去递归判断是不是相同子树

情况如下

  1. 当A为空B非空，则false
  2. 当B为空A非空，则便利结束，为true
  3. 当A值!=B值，则false
  4. A值==B值，继续判断

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

剑指 Offer 25. 合并两个排序的链表

递归

参考21. Merge Two Sorted Lists

迭代
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* pesudoHead = new ListNode();
        ListNode* head = pesudoHead;
        while(l1 && l2)
        {
            if(l1->val > l2->val)
            {
                pesudoHead->next = l2;
                l2 = l2->next;
            }else
            {
                pesudoHead->next = l1;
                l1 = l1->next;
            }
            pesudoHead = pesudoHead->next;
        }
        pesudoHead->next = l1 ? l1 : l2;
        return head->next;
    }
};

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

剑指 Offer 14- II. 剪绳子 II

这题由于n的范围加大 1624010226494.png

数学方法 TAIFUZALE

循环求余 这是使得中间值取余不影响结果取余的理论保证 x^a % p = (x^(a-1) % p)(x % p) = ((x^(a-1) % p) x) % p

1
2
3
int ret = 1;
for(int i = 0; i < a; ++i)
    ret = ret * x % p

完整代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3)
            return n - 1;
        int p = 1000000007;
        int a = n / 3;
        int b = n % 3;
        long ret = 1;
        for(int i = 0; i < (b == 1 ? a - 1 : a); ++i)
            ret = ret * 3 % p;
        if(b == 1)
            return ret * 4 % p;
        if(b == 2)
            return ret * 2 % p;
        return ret;

    }
};

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

剑指 Offer 14- I. 剪绳子

dp

参考343. Integer Break

数学方法 TAIFUZALE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3) 
            return n - 1;
        int a = n / 3;
        int b = n % 3;
        int ret = 1;
        if(b == 1)
            return pow(3, a - 1) * 4;
        if(b == 0)
            return pow(3, a);
        return pow(3, a) * 2;
    }
};

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

剑指 Offer 06. 从尾到头打印链表

先反转链表再打印
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 singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ret;
        auto node = reverse(head);
        while(node)
        {
            ret.push_back(node->val);
            node = node->next;
        }
        return ret;
    }
private:
    ListNode* reverse(ListNode* node)
    {
        ListNode* newNext = nullptr;
        while(node)
        {
            auto next = node->next;
            node->next = newNext;
            newNext = node;
            node = next;
        }
        return newNext;
    }
};

T(n) = O(n)

遍历获取大小再倒着来
1
不想写
递归时候返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> ret;
        re(ret, head);
        return ret;
    }
private:
    void re(vector<int>& ret, ListNode* node)
    {
        if(!node)
            return;
        re(ret, node->next);
        ret.push_back(node->val);
    }
};
用堆栈

不想写

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

剑指 Offer 13. 机器人的运动范围

DFS
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:
    int movingCount(int m, int n, int k) {
        int maxStep = 0;
        vector<vector<bool>> memo(m, vector<bool>(n, false));
        backTrack(m, n, k, maxStep, 0, 0, memo);
        return maxStep;
    }
private:
    void backTrack(int m, int n, int k, int& maxStep, int i, int j, vector<vector<bool>>& memo)
    {
        if(i >= m || i < 0 || j >= n || j < 0 || memo[i][j])
            return;
        memo[i][j] = true;
        int sum = 0;
        int it = i, ij = j;
        while(it)
        {
            sum += it % 10;
            it /= 10;
        }
        while(ij)
        {
            sum += ij % 10;
            ij /= 10;
        }
        if(sum > k)
            return;
        else
        {
            ++maxStep;
            backTrack(m, n, k, maxStep, i + 1, j, memo);
            backTrack(m, n, k, maxStep, i - 1, j, memo);
            backTrack(m, n, k, maxStep, i, j + 1, memo);
            backTrack(m, n, k, maxStep, i, j - 1, memo);
        }
    }
};
优化sum的计算方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int movingCount(int m, int n, int k) {
        int maxStep = 0;
        vector<vector<bool>> memo(m, vector<bool>(n, false));
        backTrack(m, n, k, maxStep, 0, 0, memo, 0);
        return maxStep;
    }
private:
    void backTrack(int m, int n, int k, int& maxStep, int i, int j, vector<vector<bool>>& memo,int sum)
    {
        if(i >= m || i < 0 || j >= n || j < 0 || memo[i][j] || sum > k)
            return;
        memo[i][j] = true;
        ++maxStep;
        backTrack(m, n, k, maxStep, i + 1, j, memo, ((i + 1) % 10 != 0 ? 1 : -8) + sum);
        backTrack(m, n, k, maxStep, i, j + 1, memo, ((j + 1) % 10 != 0 ? 1 : -8) + sum);
    }
};
1623937126537.png

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

剑指 Offer 05. 替换空格

遍历替换
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string replaceSpace(string s) {
        string ret = "";
        for(auto& ch : s)
            if(ch == ' ')
                ret += "%20";
            else
                ret += ch;
        return ret;
    }
};
原地替换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string replaceSpace(string s) {
        int len = s.size();
        int spaceCount = 0;
        for(auto& ch : s)
            if(ch == ' ')
                ++spaceCount;
        s.resize(s.size() + 2 * spaceCount);
        for(int i = len - 1,j = s.size() - 1; i >= 0; --i, --j)
        {
            if(s[i] != ' ')
                s[j] = s[i];
            else
            {
                s[j] = '0';
                s[j - 1] = '2';
                s[j - 2] = '%';
                j -= 2;
            }
        }
        return s;
    }
};