LeetCode日志(一)

发表于 | 分类于 | 0
字数统计: 2.8k | 阅读时长 ≈ 13

双指针

回文字符串

680. 验证回文字符串 Ⅱ
由于每次可以删除一个字符，所以从两端开始向中间扫描，如果有不同的字符则判断删除前一个或者后一个看是否构成回文串。

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:
    bool validPalindrome(string s) {
      int len = s.length();
      string t = s;
      reverse(s.begin(), s.end());
      if(t == s)
          return true;
      int l = -1, r = len;
      while(++l < --r){
          if(s[l] != s[r]){
              return isPalidrome(s, l, r - 1) || isPalidrome(s, l + 1, r);
          }
      }
        return true;
    }
    bool isPalidrome(string s, int i, int j){
        while(i < j){
            if(s[i++] != s[j--])
                return false;
        }
        return true;
    }
};

环形链表

141. 环形链表
用两个快慢指针，一个每次前进一格，一个每次前进两个。如果有环则这两个指针一定会相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL)
            return false;
        ListNode *slow = head, *fast = head -> next;
        while(fast != slow){
            if(fast == NULL || fast -> next == NULL)
                return false;
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        return true;
    }
};

链表

相交链表

160.相交链表
用两个指针，一个指向A，一个指向B链表，当有一个到末尾的时候指向另一个链表。如果有相交则最后一定会指向同一个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* l1 = headA, *l2 = headB;
    while (l1 != l2) {
        if(l1 == NULL)
            l1 = headB;
        else 
            l1 = l1 -> next;
        if(l2 == NULL) 
            l2 = headA;
        else 
            l2 = l2 -> next;
    }
    return l1;
    }
};

反转链表

206. 反转链表
递推
用一个指针存储下一个结点和上一个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head -> next == NULL)
            return head;
        ListNode *last = NULL;
        while(head -> next != NULL){
            ListNode *temp = head -> next;
            head -> next = last;
            last = head;
            head = temp;
        }
        head -> next = last;
        return head;
    }
};

递归
递归版本稍微复杂一些，其关键在于反向工作。假设列表的其余部分已经被反转，现在我该如何反转它前面的部分？假设列表为：$n_1 → … → n_{k-1} → n_k → n_{k+1} → … → n_m → Ø$
若从节点$ nk+1 $到 $nm $已经被反转，而我们正处于 $nk$。
$n_1 → … → n_{k-1} → n_k → n_{k+1} ← … ← n_m$
我们希望$ n_{k+1} $的下一个节点指向 $n_k$。
所以，

1
nk.next.next = nk;

要小心的是$ n_1$ 的下一个必须指向 $Ø$ 。如果你忽略了这一点，你的链表中可能会产生循环。如果使用大小为 2 的链表测试代码，则可能会捕获此错误。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head -> next == NULL)
            return head;
        ListNode* res = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return res;
    }
};
删除链表的倒数第N个节点

19. 删除链表的倒数第N个节点

用一个fast指针先向前走n步，然后slow指针和fast指针一起走直到fast走到倒数第二个，然后操作一下删除就可以了。

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 singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast = head;
        while(n--)
            fast = fast -> next;
        if(fast == NULL)
            return head -> next;
        ListNode *slow = head;
        while(fast -> next != NULL){
            fast = fast -> next;
            slow = slow -> next;
        }
        // cout << slow -> val << endl;
        if(slow -> next != NULL)
            slow -> next = slow -> next -> next;
        else
            slow = NULL;
        return head;
    }
};

树

平衡二叉树

110.平衡二叉树
判断一棵树是不是平衡二叉树，判断左右结点的高度差是否相差不到1，若不是则不为平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isbalance = true;
    int dfs(TreeNode* t)
    {
        if(t == NULL)
            return 0;
        int l = dfs(t -> left);
        int r = dfs(t -> right);
        if(abs(l - r) > 1)
            isbalance = false;
        return max(l, r) + 1;
    }
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return isbalance;
    } 
};

合并二叉树

617. 合并二叉树
将两棵树合并成一棵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode* merge(TreeNode* t1, TreeNode* t2)
    {
        if(t1 == NULL && t2 == NULL)
            return NULL;
        if(t1 == NULL)
            return t2;
        if(t2 == NULL)
            return t1;
        t1 -> left = merge(t1 -> left, t2 -> left);
        t1 -> right = merge(t1 -> right, t2 -> right);
        t1 -> val += t2 -> val;
        return t1; 
    }
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        return merge(t1, t2);
    }
};

路径总和 III

437. 路径总和 III
最初想的一个暴力的方法，把每个结点可以形成的数都存到vector中遍历相加，很慢。

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
class Solution {
public:
    // map<TreeNode*, map<int, int> > mp;
    int cnt;
    vector<int> dfs(TreeNode* t, int sum){
        vector<int> res;
        if(t == NULL)
            return res;
        if(t -> left == NULL && t -> right == NULL)
        {
            if(t -> val == sum)
                cnt++;
            res.push_back(t -> val);
            return res;
        }
        vector<int> l = dfs(t -> left, sum);
        vector<int> r = dfs(t -> right, sum);
        for(auto idx: l)
        {
            res.push_back(idx + t -> val);
            if(idx + t -> val == sum)
                cnt++;
        }
        for(auto idx: r)
        {
            res.push_back(idx + t -> val);
            if(idx + t -> val == sum)
                cnt++;
        }
        res.push_back(t -> val);
        if(t -> val == sum)
            cnt++;
        return res;
        
    }
    int pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return cnt;
    }
};

正解应该是两个递归，答案应该是当前结点和为sum的个数加上左结点和为sum的个数加上右结点和为sum的个数。
计算和为sum可以dfs直到叶子结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(root == NULL)
            return 0;
        int res = 0;
        res = pathSum(root -> left, sum) + pathSum(root -> right, sum) + dfs(root, sum);
        return res;
    }
    int dfs(TreeNode* t, int sum)
    {
        if(t == NULL)
            return 0;
        int res = (sum == t -> val);
        res += dfs(t -> left, sum - t -> val) + dfs(t -> right, sum - t -> val);
        return res;
        
    }
};

对称二叉树

101. 对称二叉树
判断一棵二叉树是不是对称，想了半天没想出来。
后来把根结点的其中一棵子树反转判断是否和另一棵相等即可。
好像不是正解。先放个代码

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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* rv(TreeNode* root)
    {
        if(root == NULL)
            return NULL;
        TreeNode* l = rv(root -> left);
        TreeNode* r = rv(root -> right);
        root -> left = r;
        root -> right = l;
        return root;
    }
    bool isSame(TreeNode* a, TreeNode* b)
    {
        if(a == NULL && b == NULL)
            return true;
        if(a == NULL || b == NULL)
            return false;
        if(a -> val != b -> val)
            return false;
        return isSame(a -> left, b -> left) && isSame(a -> right, b -> right);
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;
        TreeNode* t1 = root -> left;
        TreeNode* t2 = rv(root -> right);
        return isSame(t1, t2);
    }
};

正解可以用一个递归处理。注意判断是不同子树上的两棵子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isOkay(TreeNode* l, TreeNode* r)
    {
        if(l == NULL && r == NULL)
            return true;
        if(l == NULL || r == NULL)
            return false;
        if(l -> val != r -> val)
            return false;
        return isOkay(l -> left, r -> right) && isOkay(l -> right, r -> left);//判断是对应对称的两棵子树
    }
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;
        return isOkay(root -> left, root -> right);
    }
};

打家劫舍

337. 打家劫舍 III
当前结点取或者不取，简单的树形dp一下，每次记录取或者不取的最大值。一遍dfs

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:
    pair<int, int> dfs(TreeNode* root)
    {
        pair<int, int> res;
        if(root == NULL)
            return make_pair(0, 0);
        if(root -> left == NULL && root -> right == NULL)
            return make_pair(root -> val, 0);
        pair<int, int> l = dfs(root -> left);
        pair<int, int> r = dfs(root -> right);
        res.first = l.second + r.second + root -> val;
        res.second = max(l.first, l.second) + max(r.first, r.second);
        return res;
    }
    int rob(TreeNode* root) {
        if(root == NULL)
            return 0;
        pair<int, int> ret = dfs(root);
        cout << ret.first << ' ' << ret.second << endl;
        return max(ret.first, ret.second);
    }
};

二叉树中第二小的节点

671. 二叉树中第二小的节点
给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。
给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。
如果有节点的值不大于它的子节点的值，所以我们只要判断一下当前结点和左右两个结点的是否相等，如果相等就继续往下处理。
否则就是一组备选答案。
然后dfs回来的时候，看两个结点的值，如果两个值不为-1，则返回两者中较小的。
如果有一个不为-1，则返回这个值。
或者返回-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
25
26
class Solution {
public:
    int dfs(TreeNode* root){
        if(root == NULL)
            return -1;
        if(root -> left == NULL && root -> right == NULL)
            return -1;
        int lv = root -> left -> val;
        int rv = root -> right -> val;
        if(lv == root -> val)
            lv = dfs(root -> left);
        if(rv == root -> val)
            rv = dfs(root -> right);
        if(lv != -1 && rv != -1)
            return min(lv, rv);
        if(lv == -1)
            return rv;
        return lv;
    }
    int findSecondMinimumValue(TreeNode* root) {
        if(root == NULL)
            return -1;
        int ret = dfs(root);
        return ret;
    }
};

二叉树的前序遍历

144. 二叉树的前序遍历
二叉树的前序遍历非递归写法。
用一个栈，先存放右结点，再存放左结点，进行遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL)
            return res;
        vector<TreeNode*> st;
        st.push_back(root);
        while(st.size()){
            TreeNode* now = st.back();
            res.push_back(now -> val);
            st.pop_back();
            if(now -> right)
                st.push_back(now -> right);
            if(now -> left)
                st.push_back(now -> left);
        }
        return res;
    }
};

二叉树的后序遍历

145. 二叉树的后序遍历
由于前序是root -> left -> right
而后序是left -> right -> root
所以我们只需要把前序入栈的顺序反一下，再取个反就可以了。

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<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL)
            return res;
        vector<TreeNode*> st;
        st.push_back(root);
        while(st.size()){
            TreeNode* now = st.back();
            res.push_back(now -> val);
            st.pop_back();
            if(now -> left)
                st.push_back(now -> left);
            if(now -> right)
                st.push_back(now -> right);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

二叉树的中序遍历

94. 二叉树的中序遍历
中序遍历的非递归写法，用一个额外结点now。
每次遍历左子树直到叶子结点，将一路上所有的左结点都加入栈。
然后将当前的右结点设为now

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<int> res;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == NULL)
            return res;
        stack<TreeNode*> st;
        TreeNode* now = root;
        while(st.size() || now != NULL){ 
            while(now != NULL){
                st.push(now);
                now = now -> left;
            }
            TreeNode* t = st.top();
            st.pop();
            res.push_back(t -> val);
            now = t -> right;
        }
        return res;
    }
};

分治

数组中的第K个最大元素

215. 数组中的第K个最大元素
arrangeK表示将前k大的k个元素置于数组右侧

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:
    void arrangeK(vector<int>& nums, int k, int l, int r)
    {
        if(l > r)
            return;
        int key = nums[l];
        int a = l, b = r;
        while(a != b)
        {
            while(nums[b] >= key && a < b)
                b--;
            while(nums[a] <= key && a < b)
                a++;
            swap(nums[a], nums[b]);
        }
        swap(nums[l], nums[a]);
        if(r - a + 1 == k)
            return;
        else if(r - a + 1 > k)
            arrangeK(nums, k, a + 1, r);
        else
            arrangeK(nums, k - (r - a + 1), l, a - 1);
    }
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        arrangeK(nums, k, 0, len - 1);
        int res = INT_MAX;
        for(int i = len - 1; i >= len - k; i--)
            res = min(res, nums[i]);
        return res;
    }
};

来发评论吧~
Powered By Valine
v1.5.2