Leetcode-基本数据结构

Leetcode-基本数据结构

数组

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−2<sup>31</sup>,  2<sup>31 </sup>− 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
                return 0;
            }
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }
};

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 <strong>k</strong> 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution {
public:
    void quicksort(vector<int>& nums, int start, int end, int k){
        if(start >= end){
            return;
        }
        int x = nums[start];
        int left = start;
        int right = end;
        while(left < right){
            while(left < right && nums[right] <= x){
                right--;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] > x){
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = x;
        // start    left    end   
        // k
        if(k == left + 1){
            return;
        } else if(k < left+1){
            quicksort(nums, start, left-1,k);
        } else{
            quicksort(nums,left+1,end,k);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        quicksort(nums, 0, nums.size()-1,k);
        return nums[k-1];
    }
};

347. 前K个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

class Solution {
public:
    void quicksort(vector<pair<int,int> >& nums, int start, int end, int k){
        if(start >= end){
            return;
        }
        pair<int,int> x = nums[start];
        int left = start;
        int right = end;
        while(left < right){
            while(left < right && nums[right].second <= x.second){
                right--;
            }
            swap(nums[left],nums[right]);
            while(left < right && nums[left].second > x.second){
                left++;
            }
            swap(nums[left],nums[right]);
        }
        nums[left].first = x.first;
        nums[left].second = x.second;
        // start  left  end;
        if(k == left){
            return;
        } else if(k > left){
            quicksort(nums, left+1, end,k);
        } else{
            quicksort(nums, start, left-1,k);
        }

    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<pair<int, int> > result;
        unordered_map<int, int> mp;
        for(int i=0;i<nums.size();i++){
            mp[nums[i]]++;
        }
        for(auto it=mp.begin();it!= mp.end();it++){
            result.push_back({it->first, it->second});
        }
        quicksort(result, 0, result.size()-1,k);
        vector<int> res;
        for(int i=0;i<k;i++){
            res.push_back(result[i].first);
        }
        return res;
    }
};

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<bool> visit(s.size(),false);
        stack<pair<char,int> > st;
        for(int i=0;i<s.size();i++){
            if(st.empty() || s[i] == '(' || (s[i] == ')' && st.top().first == ')')){
                st.push({s[i],i});
                continue;
            }
            for(int j=st.top().second;j<=i;j++){
                visit[j] = true;
            }
            st.pop();
        }
        int maxlength = 0;
        int index = 0;
        while(index < visit.size()){
            int counttemp = 0;
            while(index < visit.size() && visit[index]){
                counttemp += 1;
                index += 1;
            }
            maxlength = max(maxlength, counttemp);
            while(index < visit.size() && !visit[index]){
                index += 1;
            }
        }
        return maxlength;
    }
};

2570. 合并两个二维数组 - 求和法

给你两个 二维 整数数组 nums1 和 nums2.

  • nums1[i] = [id<sub>i</sub>, val<sub>i</sub>] 表示编号为 id<sub>i</sub> 的数字对应的值等于 val<sub>i</sub> 。
  • nums2[i] = [id<sub>i</sub>, val<sub>i</sub>] 表示编号为 id<sub>i</sub> 的数字对应的值等于 val<sub>i</sub> 。

每个数组都包含 互不相同 的 id ，并按 id 以 递增 顺序排列。

请你将两个数组合并为一个按 id 以递增顺序排列的数组，并符合下述条件：

  • 只有在两个数组中至少出现过一次的 id 才能包含在结果数组内。
  • 每个 id 在结果数组中 只能出现一次 ，并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id ，则认为其对应的值等于 0 。

返回结果数组。返回的数组需要按 id 以递增顺序排列。

class Solution {
public:
    static bool cmp(const vector<int> &a, const vector<int> &b){
        return a[0] < b[0];
    }
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        unordered_map<int, int> mp;
        for(int i=0;i<nums1.size();i++){
            if(mp.find(nums1[i][0]) != mp.end()){
                mp[nums1[i][0]] += nums1[i][1];
            } else{
                mp[nums1[i][0]] = nums1[i][1];
            }
        }
        for(int i=0;i<nums2.size();i++){
            if(mp.find(nums2[i][0]) != mp.end()){
                mp[nums2[i][0]] += nums2[i][1];
            } else{
                mp[nums2[i][0]] = nums2[i][1];
            }
        }
        vector<vector<int> > result;
        for(auto it = mp.begin(); it != mp.end();it++){
            result.push_back(vector<int> {it->first, it->second});
        }
        sort(result.begin(), result.end(), cmp);
        return result;
    }
};

链表

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int cur = 0;
        ListNode* head = new ListNode(-1);
        ListNode* l3 = head;
        while(l1 != NULL || l2 != NULL){
            int target;
            if(l1 == NULL){
                target = l2->val + cur;
                l2 = l2->next;
            } else if(l2 == NULL){
                target = l1->val + cur;
                l1 = l1->next;
            } else{
                target = l1->val + l2->val + cur;
                l1 = l1->next;
                l2 = l2->next;
            }
            if (target >= 10){
                cur = 1;
                target -= 10;
            } else{
                cur = 0;
            }
            l3->next = new ListNode(target);
            l3 = l3->next;
        }
        if(cur == 1){
            l3->next = new ListNode(1);
        }
        return head->next;
    }
};

哈希表

字符串

6. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1){
            return s;
        }
        vector<queue<char> > vt(numRows);
        int nowindex = 0;
        int reverse = false;
        for(int i=0;i<s.size();i++){
            vt[nowindex].push(s[i]);
            if(nowindex == 0 && reverse == true){
                reverse = false;
                nowindex += 1;
            } else if (nowindex == numRows-1 && reverse == false){
                reverse = true;
                nowindex -= 1;
            } else {
                if(reverse == false){
                    nowindex += 1;
                } else{
                    nowindex -= 1;
                }
            }
        }
        string resultstring = "";
        for(int i=0;i<vt.size();i++){
            while(!vt[i].empty()){
                resultstring += vt[i].front();
                vt[i].pop();
            }
        }
        return resultstring;
    }
};

8. 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

  1. 读入字符串并丢弃无用的前导空格
  2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
  3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  4. 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
  5. 如果整数数超过 32 位有符号整数范围 [−2<sup>31</sup>,  2<sup>31 </sup>− 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2<sup>31</sup> 的整数应该被固定为 −2<sup>31</sup> ，大于 2<sup>31 </sup>− 1 的整数应该被固定为 2<sup>31 </sup>− 1 。
  6. 返回整数作为最终结果。

注意：

  • 本题中的空白字符只包括空格字符 ' ' 。
  • 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
class Solution {
public:
    int myAtoi(string s) {
        int res = 0;
        bool havenumsign = false;
        bool negativesign = false;
        bool fakebigsign = false;
        for(int i=0;i<s.size();i++){
            if(s[i] == ' ' && havenumsign == false){
                continue;
            }
            if(s[i] == '-' && havenumsign == false){
                negativesign = true;
                havenumsign = true;
                continue;
            }
            if(s[i] == '+' && havenumsign == false){
                havenumsign = true;
                continue;
            }
            if(s[i] >= '0' && s[i] <= '9'){
                havenumsign = true;
                if(res > (INT_MAX - s[i] + '0') / 10){
                    res = INT_MAX;
                    fakebigsign = true;
                    break;
                }
                res = res * 10 - '0' + s[i];
                continue;
            }
            if(havenumsign == true){
                break;
            }
            break;
        }
        if (negativesign){
            if(res == INT_MAX && fakebigsign){
                return INT_MIN;
            }
            return -res;
        }
        return res;
    }
};

12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

class Solution
{
public:
    string intToRoman(int num)
    {
        pair<int, string> valueSymbols[] = {
            {1000, "M"},
            {900, "CM"},
            {500, "D"},
            {400, "CD"},
            {100, "C"},
            {90, "XC"},
            {50, "L"},
            {40, "XL"},
            {10, "X"},
            {9, "IX"},
            {5, "V"},
            {4, "IV"},
            {1, "I"},
        };
        string roman;
        for (auto &[value, symbol] : valueSymbols)
        {
            while (num >= value)
            {
                num -= value;
                roman += symbol;
            }
            if (num == 0)
            {
                break;
            }
        }
        return roman;
    }
};
Study
#Algorithm #Leetcode #C++
Leetcode-基本数据结构
https://zhangzhao219.github.io/2024/04/02/Leetcode-ds/
作者
Zhang Zhao
发布于
2024年4月2日
许可协议