Leetcode | DIONYSEN BLOG

一些力扣题的答案

哈希

两数之和

题目：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

答案：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> t;
        for(int i = 0; i< nums.size(); i++){
            auto it = t.find(target - nums[i]);
            if(it != t.end()){
                return {it->second, i};
            }
            else{
                t[nums[i]] = i;
            }
        }
        return {};
    }
};

数组

最大子数组和

题目：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

答案：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = nums[0];
        int sum = 0;
        for(int num : nums){
            sum += num;
            maxSum = std::max(sum, maxSum);
            if(sum < 0){
                sum = 0;
            }
        }
        return maxSum;
    }
};

此中sum为现在的子数组和，sum小于零，再加一个新的数还不如直接把这个新的数当作新的子数组，因此sum小于零就舍弃当前子数组。而过程中这些子数组都会对比一次被maxSum记录下，最终的maxSum就是最大的子数组和。

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

题目：

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

答案：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() == 0){
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for(int i = 0; i < intervals.size(); i ++){
            if( !merged.size() ||  intervals[i][0] > merged.back()[1]){
                merged.push_back({intervals[i][0], intervals[i][1]});
            }else{
                merged.back()[1] = max(merged.back()[1], intervals[i][1]);
            }
        }
        return merged;
    }
};

翻转数组

题目：

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

答案：

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

未整理

公共前缀

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        if (!strs.size()) {
            return "";
        }
        string prefix = strs[0];
        int count = strs.size();
        for (int i = 1; i < count; ++i) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (!prefix.size()) {
                break;
            }
        }
        return prefix;
    }
    string longestCommonPrefix(const string& str1, const string& str2)
    {
        int length = min(str1.size(), str2.size());
        int index = 0;
        while (index < length && str1[index] == str2[index]) {
            ++index;
        }
        return str1.substr(0, index);
    }
};

合并两个正序数组

class Solution {
public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
        int i = nums1.size() - 1;
        m--;
        n--;
        while (n >= 0) {
            while (m >= 0 && nums1[m] > nums2[n]) {
                swap(nums1[i--], nums1[m--]);
            }
            swap(nums1[i--], nums2[n--]);
        }
    }
};

回文数

#include <cmath>
#include <iostream>
using namespace std;
class Solution {
public:
    int index = 0;
    int first = 0, last = 0;
    int t = 0;
    bool isPalindrome(int x)
    {
        if (x < 0) {
            return false;
        }

        t = x;
        while (x != 0) {
            x = x / 10;
            index++;
        }

        for (int i = 1; i < index / 2 + 1; i++) {
            first = getNumOfPosition(t, i, index);
            last = getNumOfPosition(t, index + 1 - i, index);
            if (first != last) {
                return false;
            }
        }
        return true;
    }
    int getNumOfPosition(int x, int pos, int index)
    {
        x = x / pow(10, pos - 1);
        x = x % 10;
        return x;
    }
};

括号匹配

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
    bool isValid(string s)
    {
        if (s.size() % 2 == 1) {
            return false;
        }
        unordered_map<char, char> pairs = {
            { ')', '(' },
            { ']', '[' },
            { '}', '{' },
        };
        stack<char> stk;
        for (char ch : s) {
            if (pairs.count(ch)) { //判断遍历时所取的字符ch是否是pairs中的key,如果是则进入if，不是就把ch放入栈中
                if (stk.empty() || stk.top() != pairs[ch]) { //当ch为pairs中的key时（也即右括号），判断栈顶元素是否与此时ch（key）对应的value相等，如果不等就说明括号不匹配，返回false,另一种不匹配的情况是ch为右括号，但空栈，也返回false
                    return false;
                } else
                    stk.pop(); // 如果匹配，栈顶元素出栈
            } else
                stk.push(ch);
        }
        return stk.empty(); //遍历完成后，栈应为空，若不为空，说明括号不匹配
    }
};
int main()
{
    string s = "[(){}]()()()()";
    Solution solution;
    cout << solution.isValid(s)
         << endl;
    return 0;
}

罗马数字转整型

#include <cmath>
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
    int s_Num = 0;
    int pos = -1;
    int add = 0;
    int romanToInt(string s)
    {
        for (int i = 0; i < s.length(); ++i) {
            switch (s[i]) {
            case 'M':
                s_Num += 1000;
                break;
            case 'D':
                s_Num += 500;
                break;
            case 'C':
                s_Num += 100;
                break;
            case 'L':
                s_Num += 50;
                break;
            case 'X':
                s_Num += 10;
                break;
            case 'V':
                s_Num += 5;
                break;
            case 'I':
                s_Num += 1;
                break;
            default:
                break;
            }
        }
        findS(s, "CM", 200);
        findS(s, "CD", 200);
        findS(s, "XC", 20);
        findS(s, "XL", 20);
        findS(s, "IX", 2);
        findS(s, "IV", 2);
        return s_Num + add;
    }
    void findS(const string s, const string str, int div)
    {
        for (size_t i = 0; (i = s.find(str, i)) != std::string::npos; i++) {
            this->add -= div;
        }
    }
};
int main()
{
    string s = "MCMXCI";
    Solution solution;
    cout << solution.romanToInt(s) << endl;
    return 0;
}

爬楼梯

class Solution {
public:
    int climbStairs(int x) {
        int a = 1, b = 2, s = 0;
        if (x <= 2) {
            return x;
        } else {
            for (int ret = 3; ret <= x; ret++) {
                s = a + b;
                a = b;
                b = s;
            }
        }
        return s;
    }
};

删除链表中重复元素

/**
 * Definition for singly-linked list.
 * 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) {
        if(head==nullptr) return head;
        ListNode *p;
        ListNode *q;
        for (p = head, q = p->next; p->next != nullptr, q != nullptr; ) {
            if (p->val == q->val) {
                if(q->next != nullptr){
                    q = q->next;
                    p->next = q;
                }else {
                    p->next = nullptr;
                    break;
                }
            }else {
                p = p->next;
                q=q->next;
            }
        }
        return head;
    }
};

移除数组中相同的元素

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        int i = nums.front();
        for (auto it = nums.begin() + 1; it != nums.end();) {
            if (i == *it) {
                nums.erase(it);
            } else {
                i = *it;
                it++;
            }
        }
        for (auto it = nums.begin(); it != nums.end(); it++) {
            cout << *it << "  ";
        }
        cout << endl;
        return nums.size();
    }
};
int main()
{
    Solution s;
    vector<int> nums = { 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 };
    cout << s.removeDuplicates(nums) << endl;
    return 0;
}

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

class Solution {
    public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};