LeetCode
34 分钟 读完 (大约 5132 个字)

2020-04 LeetCode每日一题做题记录

Apr.30 快乐数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isHappy(self, n: int) -> bool:
        def change(x: int) -> int:
            ret = 0
            while x:
                x, digit = divmod(x, 10)
                ret += digit * digit
            return ret
        
        st = set()
        while n not in st:
            if n == 1:
                return True
            st.add(n)
            n = change(n)
        return False

Apr.29 山脉数组中查找目标值

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
// 4 ms, 7.2 MB
/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
public:
    template<typename Func>
    int binary_search(MountainArray& mountainArr, int target, int l, int r, Func func) {
        target = func(target);
        while (l <= r) {
            int mid = (l + r) / 2;
            int cur = func(mountainArr.get(mid));
            if (cur == target) return mid;
            if (cur < target) l = mid + 1;
            else r = mid - 1;
        }
        return -1;
    }

    int findInMountainArray(int target, MountainArray &mountainArr) {
        int l = 0, r = mountainArr.length() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        int peak = l;
        int index = binary_search(mountainArr, target, 0, peak, [](int x) {
            return x;
        });
        if (index != -1) return index;
        index = binary_search(mountainArr, target, peak + 1, mountainArr.length() - 1, [](int x) {
            return -x;
        });
        return index;
    }
};

Apr.28 数组中数字出现的次数

分组异或。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 40 ms, 16.1 MB
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int xor_all = 0;
        for (int val : nums) xor_all ^= val;
        // xor_all 中 1 的位表示两个只出现过一次的数中这一位不同
        int bit = xor_all & -xor_all; // 以 lowbit(xor_all) 区分两个组别
        int a = 0, b = 0; // 对这两个组别分别做异或
        for (int val : nums) {
            if (val & bit) a ^= val;
            else b ^= val;
        }
        return {a, b};
    }
};

Apr.27 搜索旋转排序数组

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
// 0 ms, 6.4 MB
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) {
            return -1;
        }

        int p = 0, q = 1;
        while (q) {
            if (p + q >= nums.size() || nums[p + q] < nums[p]) {
                q >>= 1;
            } else {
                p += q;
                q <<= 1;
            }
        }

        // nums[p] is the biggest value in nums.
        int l, r;
        if (target >= nums[0]) { // the target's index is in [0, p].
            l = -1;
            r = p + 1;
        } else { // the target's index is in [p+1, nums.size()-1].
            l = p;
            r = nums.size();
        }
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l >= 0 && nums[l] == target ? l : -1;
    }
};

Apr.26 合并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
34
35
36
37
38
39
// 60 ms, 10.4 MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct Cmp {
        bool operator()(const ListNode* a, const ListNode* b) const {
            return a->val > b->val;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
        
        for (ListNode* listHead : lists) {
            if (listHead) heap.push(listHead);
        }
        
        ListNode dummy;
        ListNode* last = &dummy;
        while (!heap.empty()) {
            ListNode* now = heap.top();
            heap.pop();
            
            if (now->next) heap.push(now->next);
            
            last->next = now;
            last = now;
        }
        
        return dummy.next;
    }
};

Apr.25 全排列

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 4 ms, 7.4 MB
class Solution {
public:
    void dfs(vector<vector<int>>& ans, vector<int>& now, const vector<int>& nums, int visit) {
        if (visit == (1 << nums.size()) - 1) {
            ans.emplace_back(now);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (!((visit >> i) & 1)) {
                now.push_back(nums[i]);
                dfs(ans, now, nums, visit ^ (1 << i));
                now.pop_back();
            }
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> tmp;
        dfs(ans, tmp, nums, 0);
        return ans;
    }
};

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 4 ms, 7.2 MB
class Solution {
public:
    void solve(vector<vector<int>>& res, vector<int>& nums, int pos) {
        if (pos == nums.size()) {
            res.emplace_back(nums);
            return;
        }
        for (int i = pos; i < nums.size(); i++) {
            swap(nums[pos], nums[i]);
            solve(res, nums, pos + 1);
            swap(nums[pos], nums[i]);
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        solve(ans, nums, 0);
        return ans;
    }
};
阅读更多

分类

标签云

ACM C++ C++11 Linux MySQL Navicat Python STL VMware Valgrind memcheck 数据结构

最新文章

文章

标签

ACM 2
C++ 1
C++11 3
Linux 2
MySQL 1
Navicat 1
Python 1
STL 7
VMware 1
Valgrind 1
memcheck 1
数据结构 7
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×