对Leetcode做过的题目做个小小的记录,咱也不知道会不会有更新

1.两数之和


t1.jpg

解题思路

方法一:就按照题意将容器的元素用循环嵌套依次两两相加,判断是否等于目标值
方法二:略优于方法一,求目标值与元素的值的差,判断之后的元素是否存在得出的差
方法三:用unordered_map来存储数据来加快查找速度,但是对内存消耗较大


方法一

方法一代码:

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        int length = nums.size();

        for (int i = 0; i < length; i++)
        {
            for (int j = i + 1; j < length; j++)
            {
                if ((nums[i] + nums[j]) == target)
                {    
                    return nums = { i,j };
                }
            }
        }
        return nums;
    }
};

方法一的效率
t1_1.jpg

方法二

方法二代码:

class Solution_1
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        size_t length = nums.size();

        for (int i = 0; i < length; i++)
        {
            int bad = target - nums[i];
            for (int j = i + 1; j < length; j++)
            {
                if (bad == nums[j])
                {
                    return nums = { i,j };
                }
            }
        }
        return nums;
    }
};

方法二的效率
t1_2.jpg

方法三

方法三代码:

class Solution_1_map
{
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        unordered_map<int, int> mhash;

        int i = 0;
        while(true)
        {
            if (mhash.find(target - nums[i]) == mhash.end())
            {
                mhash[nums[i]] = i;
            }
            else
            {
                return nums = { mhash[target - nums[i]] ,i};
            }
            i++;
        }
        return nums;
    }
};

方法三的效率
t1_3.jpg

2.两数相加


t2.jpg

解题思路

根据题意,依次将两个链表的处在同一位的数字求和,但是要注意处理进位


代码:

struct ListNode 
{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}    
};
class Solution_2
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        ListNode* ret = new ListNode(0);
        ListNode* p = ret;
        bool up = 0;
        int sum = 0;

        while (l1 != nullptr || l2 != nullptr || up != 0)
        {
            sum = l1 ? l1->val + up : up;
            sum += l2 ? l2->val : 0;
            //当同位数之和大于等于10时进位
            if (sum >= 10)
            {
                sum %= 10;
                up = 1;
            }
            else
            {
                up = 0;
            }
            l1 = l1 ? l1->next : l1;
            l2 = l2 ? l2->next : l2;
            p->next = new ListNode(sum);
            p = p->next;
        }
        return ret->next;
    }
};

代码效率
t2_1.jpg

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


t3.jpg

解题思路

利用双指针去遍历整个字符串,从位置0和1开始,如果rp所指向的元素与以滑过的字符串中的元素不相等且未到边界就继续向右滑动rp指针,但遇到元素相同时,与之前子串长度进行对比,如果大于之前子串长度便替换为当前子串长度,随后lp可以直接滑动到下一个元素,rp也滑动到下一个元素的位置,但是注意要处理一些特殊情况,比如:字符串为"",字符串长度小于或等于2


代码

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        if (s == "")
        {
            return 0;
        }

        size_t max = s.length() - 1;
    
        if (max == 0)
        {
            return 1;
        }
        if (max == 1)
        {
            if (s[0] != s[1])
            {
                return 2;
            }
        }
        int ret = 0;

        int lp = 0;
        int rp = 1;

        while (lp <= max)
        {
            for (size_t i = lp; i < rp; i++)
            {
                if (s[i] == s[rp])
                {
                    if (rp - lp > ret)
                    {
                        ret = rp - lp;
                    }
                    lp = i + 1;
                    
                    break;
                }
                
            }
            if (rp == max)
            {
                if (rp - lp >= ret)
                {
                    ret = rp - lp + 1;
                }
                break;
            }
            rp++;
        }

        return ret;
    }
};

代码效率
t3_1.jpg

4.寻找两个有序数组的中位数


t4.jpg

解题思路

方法一:非常简单,但是效率低下,合并数组,冒泡排序,处理特殊情况但如果有一个数组是空的则可以直接判断非空数组长度的奇偶性然后直接返回中位数(因为根据题意数组元素是有序的)
方法二:比较复杂,利用双指针,首先求两个数组的总长度,并判断奇偶性确定中位数所在有序数组的位置,然后分别从两个数组的第一个元素开始,判断两个元素的大小,指向较小的那个元素的指针向后滑动,继续比较,直到到达某一个数组的边界或到中位数位置,到达中位数位置直接返回,到达边界直接滑动非空数组到达中位数位置并返回


方法一

方法一代码

class Solution_4_low
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        if (nums1.empty())
        {
            size_t len = nums2.size();
            if (len % 2)
            {
                //元素个数是奇数
                return nums2[(len - 1) / 2];
            }
            else
            {
                //元素个数是偶数
                return ((double)nums2[len / 2 - 1] + nums2[len / 2]) / 2;
            }
        }
        else if (nums2.empty())
        {
            size_t len = nums1.size();
            if (len % 2)
            {
                //元素个数是奇数
                return nums1[(len - 1) / 2];
            }
            else
            {
                //元素个数是偶数
                return ((double)nums1[len / 2 - 1] + nums1[len / 2]) / 2;
            }
        }

        size_t max1 = nums1.size() - 1;

        for (size_t i = 0; i <= max1; i++)
        {
            nums2.push_back(nums1[i]);
        }

        size_t len = nums2.size();
        size_t sum = 0;
        size_t med = len / 2;
        //冒泡排序
        for (size_t i = 0; i < len; i++)
        {
            for (size_t j = i; j < len; j++)
            {
                if (nums2[i] > nums2[j])
                {
                    int swap = nums2[i];
                    nums2[i] = nums2[j];
                    nums2[j] = swap;
                }
            }
            sum++;
            if (sum > med)
            {
                if (len % 2)
                {
                    return nums2[med];
                }
                else
                {
                    return ((double)nums2[med - 1] + nums2[med]) / 2;
                }
            }
        }
        return 0;
    }
};

方法一效率
t4_1.jpg

方法二

方法二代码

class Solution_4
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        if (nums1.empty())
        {
            size_t len = nums2.size();
            if (len % 2)
            {
                //元素个数是奇数
                return nums2[(len - 1) / 2];
            }
            else
            {
                //元素个数是偶数
                return ((double)nums2[len / 2 - 1] + nums2[len / 2]) / 2;
            }
        }
        else if (nums2.empty())
        {
            size_t len = nums1.size();
            if (len % 2)
            {
                //元素个数是奇数
                return nums1[(len - 1) / 2];
            }
            else
            {
                //元素个数是偶数
                return ((double)nums1[len / 2 - 1] + nums1[len / 2]) / 2;
            }
        }
        //两个容器都不为空
        size_t max1 = nums1.size();
        size_t max2 = nums2.size();
        size_t len = max1 + max2;
        max1--;
        max2--;
        if (len % 2)
        {
            //奇数
            size_t obj = len / 2;
            size_t i = 0, j = 0, k = 0;
            while (true)
            {
                if (nums1[i] < nums2[j])
                {
                    k++;
                    if (k == obj)
                    {
                        if (max1 == i)
                        {
                            return nums2[obj - k + j];
                        }
                        if (nums1[i + 1] < nums2[j])
                        {
                            return  nums1[i + 1];
                        }
                        return nums2[j];
                    }
                    if (max1 == i)
                    {
                        return nums2[obj - k + j];
                    }
                    i++;
                }
                else if (nums1[i] == nums2[j])
                {
                    k++;
                    if (k == obj)
                    {
                        return nums2[j];
                    }
                    if (max1 == i)
                    {
                        return nums2[obj - k + j];
                    }
                    else if (max2 == j)
                    {
                        return nums1[obj - k + i];
                    }
                    i++;
                }
                else
                {
                    k++;
                    if (k == obj)
                    {
                        if (max2 == j)
                        {
                            return nums1[obj - k + i];
                        }
                        if (nums1[i] < nums2[j + 1])
                        {
                            return nums1[i];
                        }
                        return nums2[j + 1];

                    }
                    if (max2 == j)
                    {
                        return nums1[obj - k + i];
                    }
                    j++;
                }
            }
        }
        else
        {
            //偶数
            size_t obj = len / 2;
            size_t i = 0, j = 0, k = 0;
            while (true)
            {
                if (nums1[i] < nums2[j])
                {
                    k++;
                    if (k == obj)
                    {
                        if (max1 == i)
                        {
                            return ((double)nums1[i] + nums2[j]) / 2;
                        }
                        if (nums1[i + 1] < nums2[j])
                        {
                            return ((double)nums1[i] + nums1[i + 1]) / 2;
                        }
                        return ((double)nums1[i] + nums2[j]) / 2;
                    }
                    if (max1 == i)
                    {
                        return ((double)nums2[obj - k + j] + nums2[obj - k + j - 1]) / 2;
                    }
                    i++;
                }
                else if (nums1[i] == nums2[j])
                {
                    k++;
                    if (k == obj)
                    {
                        return ((double)nums1[i] + nums2[j]) / 2;
                    }
                    if (max1 == i)
                    {
                        return ((double)nums2[obj - k + j] + nums2[obj - k + j - 1]) / 2;
                    }
                    else if (max2 == j)
                    {
                        return ((double)nums1[obj - k + i] + nums1[obj - k + i - 1]) / 2;
                    }
                    i++;
                }
                else
                {
                    k++;
                    if (k == obj)
                    {
                        if (max2 == j)
                        {
                            return ((double)nums1[i] + nums2[j]) / 2;
                        }
                        if (nums2[j + 1] < nums1[i])
                        {
                            return ((double)nums2[j + 1] + nums2[j]) / 2;
                        }
                        return ((double)nums1[i] + nums2[j]) / 2;
                    }
                    if (max2 == j)
                    {
                        return ((double)nums1[obj - k + i] + nums1[obj - k + i - 1]) / 2;
                    }
                    j++;
                }
            }
        }
    }
};

方法二效率
t4_2.jpg

5.最长回文子串


t5.jpg

解题思路

中心扩张,即使用双指针从中心位置开始依次向两边滑动,直到碰到边界或字符不相等,然后保存当前滑动过的子字符串,中心位置向右滑动一个单位,但是无法判断回文串的奇偶性,因此需要使用中心单字符扩张也需要使用中心双字符扩张


代码

class Solution_5_v2
{
public:
    string longestPalindrome(string s)
    {
        int length = s.length();

        if (length <= 1)
        {
            return s;
        }

        constexpr auto left_max = 0;;
        int right_max = length - 1;

        //--------单字符扩张
        int med = 0;
        int leftp = med;
        int rightp = med;

        string ret;

        while (med <= right_max)
        {
            if (leftp == left_max || rightp == right_max)    //扩张到达左边界或右边界
            {
                if (s[leftp] != s[rightp])        //两端不等->有效回文串两端内缩1个长度
                {
                    if (ret.length() < rightp - leftp - 1)
                    {
                        ret.clear();
                        ret = s.substr(leftp + 1, rightp - leftp - 1);
                    }
                    med++;
                    leftp = med;
                    rightp = med;
                    continue;
                }
                else
                {
                    if (ret.length() < rightp - leftp + 1)
                    {
                        ret.clear();
                        ret = s.substr(leftp, rightp - leftp + 1);
                    }
                    med++;
                    leftp = med;
                    rightp = med;
                    continue;
                }
            }
            else         //扩张未遇到边界
            {
                if (s[leftp] != s[rightp])        //两端不等->有效回文串两端内缩1个长度
                {
                    if (ret.length() < rightp - leftp - 1)
                    {
                        ret.clear();
                        ret = s.substr(leftp + 1, rightp - leftp - 1);
                    }
                    med++;
                    leftp = med;
                    rightp = med;
                    continue;
                }

                leftp--;
                rightp++;
            }
        }

        //---------双字符扩张
        int mleft = 0, mright = 1;
        leftp = mleft;
        rightp = mright;

        while (mright <= right_max)
        {
            if (leftp == left_max || rightp == right_max)
            {
                if (s[leftp] != s[rightp])
                {
                    if (ret.length() < rightp - leftp - 1)
                    {
                        ret.clear();
                        ret = s.substr(leftp + 1, rightp - leftp - 1);
                    }
                    mleft++;
                    mright++;
                    leftp = mleft;
                    rightp = mright;
                    continue;
                }
                else
                {
                    if (ret.length() < rightp - leftp + 1)
                    {
                        ret.clear();
                        ret = s.substr(leftp, rightp - leftp + 1);
                    }
                    mleft++;
                    mright++;
                    leftp = mleft;
                    rightp = mright;
                    continue;
                }
            }
            else
            {
                if (s[leftp] != s[rightp])
                {
                    if (ret.length() < rightp - leftp - 1)
                    {
                        ret.clear();
                        ret = s.substr(leftp + 1, rightp - leftp - 1);
                    }
                    mleft++;
                    mright++;
                    leftp = mleft;
                    rightp = mright;
                    continue;
                }
                leftp--;
                rightp++;
            }
        }

        return ret;

    }
};

代码效率
t5_1.jpg

Last modification:April 15th, 2020 at 09:13 am