LeetCode

本文主要记载自己的刷LeetCode经历。

1. Two Sum

题目

Approach #1

使用两个for循环，时间复杂度为$O(n^2)$，空间复杂度为:$O(n1)$。

//Runtime:560 ms
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int len = nums.size();
        vector<int> result;
        for(int i=0; i<len; i++) {
            for(int j=i+1; j<len;j++) {
                if(nums[i] + nums[j] == target) {
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
        }
    }
};

Approach #2

使用哈希函数组织的map，时间复杂度为$O(n)$，空间复杂度为:$O(n)$。

//Runtime: 16 ms
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int len = nums.size();
        vector<int> result;
        unordered_map<int, int> myMap;
        for(int i=0; i<len; i++) {
            myMap[nums[i]] = i;
        }
        for(int i=0; i<len; i++) {
            int complement = target - nums[i];
            if(myMap.find(complement) != myMap.end() && myMap[complement] != i) {
                    result.push_back(i);
                    result.push_back(myMap[complement]);
                    return result;
            }
        }
    }
};

2. Add Two Numbers

题目

Approach

使用单向连边，注意点运算符“.”和箭头运算符“->”都可以用于访问成员，其中点运算获取类对象的一个成员，箭头运算获取指针指向对象的成员。时间复杂度为$O(max(m,n))$，空间复杂度为:$O(max(m,n))$。

//Runtime: 36 ms
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* result = &dummy;
        int cnt = 0, sum = 0, val = 0;
        
        while (l1 || l2) {
            sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + cnt;
            cnt = sum / 10;
            val = sum % 10;
            result->next = new ListNode(val);
            result = result->next;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
        } 
        if(cnt > 0) {
            result->next = new ListNode(cnt);
        }
        return dummy.next;
    }
};

3. Longest Substring Without Repeating Characters

题目

Approach

使用哈希函数组织的map，关键字为字符，对应的值为字符在字符串中的位置。
l = max(l, myMap[s[r]]+1)用于返回有重复字符时候的左边界位置。

• tmmzuxt s[l]是第二个m，s[r]是最后一个t，此时不需要更新l。

• mmzuxtabt s[l]是第二个m，s[r]是最后一个t，此时需要将l移动至a。

    //Runtime: 56 ms
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int len = s.size();
            int l = 0, r = 0, res = 0;
            unordered_map<char, int> myMap;
            while(r < len) {
                if(myMap.find(s[r]) != myMap.end()) {
                    l = max(l, myMap[s[r]]+1);	//返回有重复字符时候的左边界位置
                }
                myMap[s[r]] = r;
                res = max(res, r-l+1);
                r++;
            }
            return res;
        }
    };
  

6. ZigZag Conversion

题目

Approach

basic_string<>有双重身份，一是代替传统的字符串，所以应该有strlen函数，给出相应的字符串长度；另一个身份是可以用作STL容器，所以要按照STL容器的惯例给出size()。
本题的重点是要求出周期$2 * numRows - 2$,然后首行末行的循环周期都是此周期，中间行还需要进行单独计算。

//Runtime: 16 ms
class Solution {
public:
    string convert(string s, int numRows) {
        int len = s.size();
        if(numRows < 2){
            return s;
        }
        string tmp = "";
        int cnt = 2 * numRows - 2;
        for(int i=0; i<numRows; i++) {
     	    for(int j=i; j<len; j+=cnt) {
                tmp += s[j]; 
                if(i>0 && i<numRows-1){		//计算中间行的循环，以cnt为一个循环周期
                	int num = cnt + j - 2 * i;  
                	if(num < len) {
                    	tmp += s[num];    
                  	}
                 }
        	}
        }
        return tmp;
    }
};
    

237. Delete Node in a Linked List

题目

Approach

时间复杂度和空间复杂度都为$O(1)$。

//Runtime: 16 ms
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};  

328. Odd Even Linked List

题目

Approach

若链表非空，至少有一个元素，此时就可看出，while循环的终止条件使用even和even->next较合适。时间复杂度为$O(n)$，我们需要遍历n个节点；空间复杂度为:$O(1)$，我们所需要的只是4个指针。

//Runtime: 20 ms 
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL) return NULL;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;;
        while(even && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};