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;
    }
};

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

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

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n-1;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[0] <= nums[mid]){
                if(nums[0] <= target && target < nums[mid]){
                    right = mid - 1;
                } else{
                    left = mid + 1;
                }
            } else{
                if(nums[mid] < target && target <= nums[n-1]){
                    left = mid + 1;
                } else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

48. 旋转图像

给定一个 *n * × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。**请不要 **使用另一个矩阵来旋转图像。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i=0;i< n / 2;i++){
            for(int j=0;j<(n+1) / 2;j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-j-1][i];
                matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
                matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
                matrix[j][n-i-1] = temp;
            }
        }
    }
};

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i] == 0){
                swap(nums[i], nums[left]);
                left += 1;
            }
        }
        for(int i=left;i<nums.size();i++){
            if(nums[i] == 1){
                swap(nums[i], nums[left]);
                left += 1;
            }
        }
    }
};

73. 矩阵置零

给定一个 <em>m</em> x <em>n</em> 的矩阵，如果一个元素为 0 ** ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。**

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<bool> rowvector(m,false);
        vector<bool> colvector(n,false);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j] == 0){
                    rowvector[i] = true;
                    colvector[j] = true;
                }
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(rowvector[i] == true || colvector[j] == true){
                    matrix[i][j] = 0;
                }
            }
        }
        return;
    }
};

118. 杨辉三角

给定一个非负整数 numRows， 生成「杨辉三角」的前 *numRows *行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int> > result;
        vector<int> temp;
        temp.push_back(1);
        result.push_back(temp);
        if(numRows == 1){
            return result;
        }
        for(int i=2;i<=numRows;i++){
            vector<int> t;
            t.push_back(1);
            for(int j=1;j<i-1;j++){
                t.push_back(result[i-2][j-1] + result[i-2][j]);
            }
            t.push_back(1);
            result.push_back(t);
        }
        return result;
    }
};

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：* 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]

  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

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

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        int right = n-1;
        while(left < right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] < nums[right]){
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
};

链表

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;
    }
};

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(0);
        ListNode* head = dummy;
        while(list1 != NULL && list2 != NULL){
            if(list1->val < list2->val){
                dummy->next = list1;
                dummy = dummy->next;
                list1 = list1->next;
            } else{
                dummy->next = list2;
                dummy = dummy->next;
                list2 = list2->next;
            }
        }
        if(list1 != NULL){
            dummy->next = list1;
        }
        if(list2 != NULL){
            dummy->next = list2;
        }
        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 #C++ #Leetcode
Leetcode-基本数据结构
https://zhangzhao219.github.io/2024/04/02/Leetcode/Leetcode-ds/
作者
Zhang Zhao
发布于
2024年4月2日
许可协议