LeetCode || 大杂烩w

454. 4Sum II

题意：给四个数组，每个数组内取一个数使得四个数和为0，问有多少种取法

思路：枚举为On4，考虑两个数组，On2枚举所有可能的和，将和的出现次数存入map中，On2枚举另两个数组，看是否加和为0

class Solution {

public:

    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {

        int na = A.size(), nb = B.size(), nc = C.size(), nd = D.size();

        int cnt = ;

        map<int, int> mp;

        for (int i = ; i < na; i++) {

            for (int j = ; j < nb; j++) {

                int sum = A[i] + B[j];

                if (mp[-sum]) mp[-sum]++;

                else mp[-sum] = ;

            }

        }

        for (int i = ; i < nc; i++) {

            for (int j = ; j < nd; j++) {

                int sum = C[i] + D[j];

                if (mp[sum]) cnt += mp[sum];

            }

        }

        return cnt;

    }

};

24. Swap Nodes in Pairs

题意：交换一个链表中每相邻两个元素

想看到就是多加个头的空指针操作（

ListNode *emptyhead = new ListNode(-);

emptyhead -> next = head;

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* swapPairs(ListNode* head) {

        ListNode *emptyhead = new ListNode(-);

        emptyhead -> next = head;

        ListNode *p = head, *q, *lst = emptyhead;

        while (lst -> next && lst -> next -> next) {

            p = lst -> next;

            q = p -> next;

            p -> next = q -> next;

            q -> next = p;

            lst -> next = q;

            lst = p;

        }

        return emptyhead -> next;

    }

};

25. Reverse Nodes in k-Group

题意：将每k个元素倒序

Given this linked list: ->->->->

For k = , you should return: ->->->->

For k = , you should return: ->->->->

思路：用两个指针来取倒序的一段

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

class Solution {

public:

    ListNode* reverseKGroup(ListNode* head, int k) {

        ListNode *emptyhead = new ListNode(-);

        emptyhead -> next = head;

        ListNode *pre = emptyhead, *cur = emptyhead;

        int i = ;

        while (cur -> next) {

            i++;

            cur = cur -> next;

            if (i % k == ) {

                pre = reverse(pre, cur -> next);

                cur = pre;

            }

        }

        return emptyhead -> next;

    }

    ListNode* reverse(ListNode* pre, ListNode* nxt) {

        ListNode *lst, *cur;

        lst = pre -> next;

        cur = lst -> next;

        while (cur != nxt) {

            lst -> next = cur -> next;

            cur -> next = pre -> next;

            pre -> next = cur;

            cur = lst -> next;

        }

        return lst;

    }

};

29. Divide Two Integers

题意：不用乘除模运算，完成整数乘法，若溢出则输出INT_MAX，向0取整

思路：思路是往下减，一个一个减布星，来移位

class Solution {

public:

    int divide(int dividend, int divisor) {

        long long res = ;

        int flag = ;

        if ((dividend <  && divisor > ) || (dividend >  && divisor < )) {

            flag = -;

        }

        long long m = abs((long long)dividend);

        long long n = abs((long long)divisor);

        long long base, t;

        while (m >= n) {

            base = n;

            t = ;

            while (m >= (base << )) {

                base <<= ;

                t <<= ;

            }

            m -= base;

            res += t;

        }

        if (flag == -) return int(-res);

        if (res > ) return ;

        return res;

    }

};

31. Next Permutation

题意：给一个序列，输出字典序下一个的序列

思路：对于已经是字典序的序列特判，输出倒序；其他情况下，

从后往前找到第一个开始减小的元素

1 5 4 3 1

然后从后往前找到第一个比2大的元素，交换它们

1 5 4 1

然后把3之后的序列倒置

1 3 1 2 4 5

嘛拿纸笔画一画就好惹（

class Solution {

public:

    void nextPermutation(vector<int>& nums) {

        int n = nums.size();

        int flag = ;

        int last, idx;

        for (int i = n - ; i >= ; i--) {

            if (nums[i] < nums[i + ]) {

                last = nums[i];

                idx = i;

                flag = ;

                break;

            }

        }

        if (flag == ) {

            reverse(nums.begin(), nums.end());

        } else {

            for (int i = n - ; i >= idx + ; i--) {

                if (nums[i] > last) {

                    nums[idx] = nums[i];

                    nums[i] = last;

                    break;

                }

            }

            reverse(nums.begin() + idx + , nums.end());

        }

        return;

    }

};

// 1 2 4 5 6 -> 1 2 4 6 5

// 1 2 4 6 5 -> 1 2 5 4 6

// 1 3 4 2 -> 1 4 2 3

// 3 4 2 1 -> 4 1 2 3

46. Permutations

题意：输出全排列

next_permutation 输出从当前排列之后的所有全排列（所以要 sort 和 do while）

class Solution {

public:

    vector<vector<int>> permute(vector<int>& nums) {

        vector<vector<int>> res;

        sort(nums.begin(), nums.end());

        do {

            res.push_back(nums);

        } while (next_permutation(nums.begin(), nums.end()));

        return res;

    }

};

56. Merge Intervals

结构体vector的排序姿势……？

为啥cmp不行啊qwq（

struct Interval {

     int start;

     int end;

     Interval() : start(), end() {}

     Interval(int s, int e) : start(s), end(e) {}

 };

vector<Interval>& intervals;

sort(intervals.begin(), intervals.end(), [](Interval &a, Interval &b) {return a.start < b.start;});

巴特西

LeetCode || 大杂烩w

最新文章

热门文章