LeetCode 刷题集锦

题目链接

题目描述

解题思路

运行结果

题目链接

题目描述

解题思路

运行结果

题目链接

888. 公平的糖果交换

题目描述

解题思路

vis[B] 数组标记 B中出现的数，然后根据遍历数组A中的数，B中存在合适的交换的数，则交换。

时间复杂度：O(n)。

运行结果

参考代码

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        vector<int> result;

        int MAX_N = 100010;
        bool visB[MAX_N];
        // 初始化
        for(int i=0; i<MAX_N; i++) {
            visB[i] = false;
        }
        
        // MaxTotal 10000*100000
        int totalA = 0, totalB = 0;
        int lengthA = A.size();
        int lengthB = B.size();
        for(int i=0; i<lengthA; i++) {
            totalA += A[i];
        }
        
        for(int i=0; i<lengthB; i++) {
            totalB += B[i];
            visB[B[i]] = true;
        }
        
        int distace = (totalB-totalA)/2;
        for(int i=0; i<lengthA; i++) {
            int temp = A[i]+distace;
            if(temp > 0 && temp < MAX_N) {
                if(visB[temp] == true) {
                    result.push_back(A[i]);
                    result.push_back(temp);
                    break;
                }
            }
        }
        
        return result;
    }
};

题目链接

445. 两数相加 II

题目描述

解题思路

把链表存到动态数组vector里面，然后使用两个vector模拟加法。

时间复杂度:O(n)。

运行结果

参考代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* result = NULL;
        vector<int> v1, v2;
        v1.clear();
        v2.clear();
        v1.push_back(0);
        v2.push_back(0);
        while(l1 != NULL) {
            v1.push_back(l1->val);
            l1 = l1->next;
        }
        while(l2 != NULL) {
            v2.push_back(l2->val);
            l2 = l2->next;
        }
        
        int len1 = v1.size(), len2 = v2.size();
        int length = min(len1-1, len2-1);
        
        if(len1 >= len2) {
            for(int i=1; i<=length; i++) {
                v1[len1-i] = v1[len1-i]+v2[len2-i];  
                if(v1[len1-i] >= 10) {
                    v1[len1-i] -= 10;
                    v1[len1-i-1] ++;
                }
            }
            for(int i=len1-length-1; i>=1; i--) {
                if(v1[i] >= 10) {
                    v1[i] -= 10;
                    v1[i-1] ++;
                }
            }
            ListNode* temp;
            if(v1[0] != 0) {
                temp = new ListNode(v1[0]);
                result = temp;
            }
            for(int i=1; i<len1; i++) {
                if(NULL == result) {
                    temp = new ListNode(v1[i]);
                    result = temp; 
                } else {
                    temp->next = new ListNode(v1[i]);
                    temp = temp->next;
                }
            }
        } else{
            for(int i=1; i<=length; i++) {
                v2[len2-i] = v1[len1-i]+v2[len2-i];
                if(v2[len2-i] >= 10) {
                    v2[len2-i] -= 10;
                    v2[len2-i-1] ++;
                }
            }
            for(int i=len2-length-1; i>=1; i--) {
                if(v2[i] >= 10) {
                    v2[i] -= 10;
                    v2[i-1] ++;
                }
            }
            ListNode* temp;
            if(v2[0] != 0) {
                temp = new ListNode(v2[0]);
                result = temp;
            }
            for(int i=1; i<len2; i++) {
                if(NULL == result) {
                    temp = new ListNode(v2[i]);
                    result = temp; 
                } else {
                    temp->next = new ListNode(v2[i]);
                    temp = temp->next;
                }
            }
        }
        return result;
    }
};