LeetCode：3、4、83、88

3、无重复字符的最长子串

#include <string>
using namespace std;
class Solution {
  public:
    int lengthOfLongestSubstring(string s) {
        int len = 0;
        while (!s.empty()) {
            bool flag = 0;
            for (int i = 0; i < s.length(); i++) {
                if (flag)
                    break;
                for (int j = 0; j < i; j++) {
                    if (s[i] == s[j]) {
                        len = i > len ? i : len;
                        s = s.substr(j + 1);
                        flag = 1;
                        break;
                    }
                }
            }
            if (!flag) {
                len = s.length() > len ? s.length() : len;
                break;
            }
        }
        return len;
    }
};

4、寻找两个正序数组的中位数

#include <vector>
using namespace std;
class Solution {
  public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        /*vector<int> nums3;
         int i = 0, j = 0;
         bool choose;
         while (i <= nums1.size() && j <= nums2.size())
             if (i == nums1.size() || j == nums2.size())
                 break;
             else if (nums1[i] <= nums2[j])
                 nums3.push_back(nums1[i++]);
             else
                 nums3.push_back(nums2[j++]);
         while (i < nums1.size())
             nums3.push_back(nums1[i++]);
         while (j < nums2.size())
             nums3.push_back(nums2[j++]);
         return nums3.size() % 2 ? (double)nums3[(nums3.size() - 1) / 2]
                                 : (double)(nums3[(nums3.size() - 1) / 2] + nums3[(nums3.size() + 1) / 2]) / 2;*/
        // 2094/2094 cases passed (32 ms)
        // Your runtime beats 47.42 % of cpp submissions
        // Your memory usage beats 11.78 % of cpp submissions (87.7 MB)
        //!不符合时间复杂度要求( O(log (m+n)) )，不知道为什么过
        /*int m = nums1.size();
        int n = nums2.size();
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;*/
    }
    /*int findKth(vector<int> &nums1, int i, vector<int> &nums2, int j, int k) {
        if (i >= nums1.size())
            return nums2[j + k - 1]; // nums1为空数组
        if (j >= nums2.size())
            return nums1[i + k - 1]; // nums2为空数组
        if (k == 1) {
            return min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.size()) ? nums1[i + k / 2 - 1] : INT_MAX;
        int midVal2 = (j + k / 2 - 1 < nums2.size()) ? nums2[j + k / 2 - 1] : INT_MAX;
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }*/
    // 2094/2094 cases passed (32 ms)
    // Your runtime beats 47.42 % of cpp submissions
    // Your memory usage beats 57.87 % of cpp submissions (86.9 MB)
    //!有空得再做一次==，做完这题彻底奠定了要由难到易刷题的决心，不要一口气吃成个胖子
};

83、删除排序链表中的重复元素

/*struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};*/
class Solution {
  public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *pos = head;
        while (pos) {
            if (pos->next && pos->next->val == pos->val) {
                ListNode *del = pos->next;
                pos->next = pos->next->next;
                delete del;
            } else
                pos = pos->next;
        }
        return head;
        // 166/166 cases passed (12 ms)
        // Your runtime beats 44.55 % of cpp submissions
        // Your memory usage beats 10.5 % of cpp submissions (11.4 MB)
        //!没有加del的结果
        // 166/166 cases passed (8 ms)
        // Your runtime beats 84.64 % of cpp submissions
        // Your memory usage beats 43.11 % of cpp submissions (11.3 MB)
        //!回收了垃圾的结果
    }
};

88、合并两个有序数组

#include <vector>
using namespace std;
class Solution {
  public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
        /*int i = 0, j = 0;
        while (i < m && j < n) {
            if (nums1[i] >= nums2[j]) {
                nums1.pop_back();
                nums1.insert(nums1.begin() + i, nums2[j++]);
                m++;
            }
            i++;
        }
        while (n - j) {
            nums1.insert(nums1.begin() + i, nums2[j++]);
            nums1.pop_back();
            i++;
        }*/
        // 59/59 cases passed (4 ms)
        // Your runtime beats 52.77 % of cpp submissions
        // Your memory usage beats 92.62 % of cpp submissions (8.7 MB)
        for (int i = 0, j = 0; i < m + n && j < n; i++) {
            if (nums1[i] >= nums2[j] || i >= m) {
                nums1.insert(nums1.begin() + i, nums2[j++]);
                nums1.pop_back();
                m++;
            }
        }
        // 59/59 cases passed (4 ms)
        // Your runtime beats 52.77 % of cpp submissions
        // Your memory usage beats 92.62 % of cpp submissions (8.7 MB)
        //*两个都是自己写的，一开始是第二版但没注意到m++，换成第一版测试了好久才发现这个问题，再利用原版提升效率，一个小错误竟然浪费了我半个下午，干
    }
};