开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> leetcode 1-10 -> 正文阅读

[数据结构与算法]leetcode 1-10

leetcode 1-10

1. 两数之和

解题思路
从左往右依次遍历一遍,若target-nums[i]能在hash表中找到,就返回下标;若没找到,就将当前下标加入到hash表中

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> umap;
        for(int i = 0; i < nums.size(); ++i){
            int r = target - nums[i];
            if(umap.count(r)) return {umap[r], i};
            umap[nums[i]] = i;
        }
        return {};
    }
};

2. 两数相加

解题思路

从头到尾遍历,while循环的条件l1 || l2,然后将结果放入新节点

注:注意y总这里的间接写法,比如if(l1) t += l1->val, l1 = l1->next;以及cur = cur->next = new ListNode(t % 10);,可以借鉴

代码

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        int t = 0;
        while(l1 || l2){
            if(l1) t += l1->val, l1 = l1->next;
            if(l2) t += l2->val, l2 = l2->next;
            cur = cur->next = new ListNode(t % 10);
            t /= 10;
        }
        if(t) cur->next = new ListNode(t);
        return dummy->next;
    }
};

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

滑动窗口思想

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        memset(hash, 0, sizeof hash); // y总使用的 unordered_map<char, int> 
        int res = 0;
        for(int i = 0, j = 0; i < s.size(); ++i){
            hash[s[i]]++;
            while(j < i && hash[s[i]] > 1){
                --hash[s[j++]]; // 也可以 hash[s[j++]]--;
            }
            res = max(res, i - j + 1);
        }
        return res;
    }
private:
    int hash[255];
};

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

解题思路

find函数作用:在合并后的数组中找到第k大的数

代码

#include<cmath>
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        if(tot % 2 == 0){
            double left = find(nums1, 0, nums2, 0, tot / 2);
            double right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        }

        return find(nums1, 0, nums2, 0, tot / 2 + 1);
    }


    double find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k){
        // 保证nums1剩余的长度一定比nums2短
        if(nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k); 
		// nums1遍历完了,那么第k大的数直接可以求出来为nums2[j + k - 1]
        if(nums1.size() == i) return nums2[j + k - 1]; 
        // nums1没遍历完(那么nums2也一定没有遍历完),求出第一个的最小值
        if(k == 1) return min(nums1[i], nums2[j]);  

        // 记录需要计算的位置
        // sj = j + k - k / 2,因为k可能是奇数,若为奇,那么sj就多一位
        // si = min((int)nums1.size(), i + k / 2),保证si不能超过nums1.size()
        int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
        if(nums1[si - 1] > nums2[sj - 1])
            return find(nums1, i, nums2, sj, k - (sj - j));
        return find(nums1, si, nums2, j,  k - (si - i));
    }
};

5.最长回文子串

解题思路

确定一个中心点i，如果回文串长度是偶数，我们就照ll = i，rr = i + 1来枚举，如果回文串长度为奇数，我们就按照ll = i - 1，rr = i + 1来枚举；

while循环直到s[ll] != s[rr]，判断当前长度(rr - 1) - (ll + 1) + 1 = rr - ll - 1是否为最大长度，若是，更新res

代码

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if(!len) return s;
        string res = s.substr(0, 1);
        for(int i = 0; i < len - 1; ++i){
            int ll = i, rr = i + 1;
            while(ll >= 0 && rr < len && s[ll] == s[rr])--ll, ++rr;
            if(rr - ll - 1 > res.size()) res = s.substr(ll + 1, rr - ll - 1);
            
            ll = i - 1, rr = i + 1;
            while(ll >= 0 && rr < len && s[ll] == s[rr]) --ll, ++rr;
            if(rr - ll - 1 > res.size()) res = s.substr(ll + 1, rr - ll - 1);
        }

        return res;
    }
};

解题思路2

回文串的最大长度另一种解法：字符串+二分

优化：将长度为偶数的回文串转换为奇数的回文串：在串中每一个字符间加入一个未出现的字符，比如#（本题解未实现）

通过字符串hash记录前缀hash和后缀hash
然后遍历每一个中点,
(1)对于长度为奇数的回文串,我们的长度范围为0~min(i - 1, n - i)
(2)对于长度为偶数的回文串,则当前点i为右半部分的起点,那么我们的长度范围为0~min(i - 1, n - i + 1)

代码

typedef unsigned long long ULL;
const int N = 1010, mod = 131;
class Solution {
public:
    ULL p[N], pre[N], post[N];
	
	// 获取字符串hash值
    int get(ULL h[], int ll, int rr){
        return h[rr] - h[ll - 1] * p[rr - ll + 1];
    }

    string longestPalindrome(string s) {
        if(s.empty()) return s;
        s = " " + s;
        int n = s.size();

        p[0] = 1;
        for(int i = 1, j = n; i <= n; ++i, --j){
            pre[i] = pre[i - 1] * mod + s[i] - 'a' + 1;
            post[i] = post[i - 1] * mod + s[j] - 'a' + 1;
            p[i] = p[i - 1] * mod;
        }

        int ans = 0, st = 0;//最长的长度 该长度的起点下标
        for(int i = 1; i <= n; ++i){//枚举回文中点 若为偶数回文 则为右半段的起点
            // 奇数长度的回文串
            int ll = 0, rr = min(i - 1, n - i);
            while(ll < rr){
                int mid = ll + rr + 1 >> 1;
                // 所以两边是: i-mid, i-1和i+1, i + mid
                if(get(pre, i - mid, i - 1) == get(post, n - (i + mid) + 1, n - (i + 1) + 1)) ll = mid;
                else rr = mid - 1;
            }
            if(ans < ll * 2 + 1){
                ans = ll * 2 + 1;
                st = i - ll;
            }

            // 长度为偶数的回文串
            // 1~i-1 和 i~n之间对比,所以最大长度取min(i - 1, n - i + 1)
            ll = 0, rr = min(i - 1, n - i + 1);
            while(ll < rr){
                int mid = ll + rr + 1 >> 1;
                // 所以两边是: i-mid, i-1和i, i+mid-1
                if(get(pre, i - mid, i - 1) == get(post, n - (i + mid - 1) + 1, n - (i) + 1)) ll = mid;
                else rr = mid - 1;
            }
            if(ans < ll * 2){
                ans = ll * 2;
                st = i - ll;
            }
        }
        return s.substr(st, ans);
    }
};

6.Z字形变换

解题思路

声明numRows个string，然后模拟

代码

class Solution {
public:
    string convert(string s, int numRows) {
        if(!s.size() || numRows == 1) return s;
        string nums[numRows];

        nums[0] += s[0];
        int cur_row = 1;
        bool f = true; // 定义方向
        for(int i = 1; i < s.size(); ++i){
            nums[cur_row] += s[i];
            if(f){
                if((cur_row + 1) % numRows == 0){
                    cur_row --;
                    f = false;
                }else{
                    cur_row ++;
                }
            }else{
                if(cur_row == 0){
                    cur_row ++;
                    f = true;
                }else cur_row--;
            }
        }
        
        string ans = "";
        for(int i = 0; i < numRows; ++i){
            ans += nums[i];
        }
        return ans;
    }
};

解题思路2

(找规律) O(n)

这种按某种形状打印字符的题目，一般通过手画小图找规律来做。
我们先画行数是4的情况：

0     6       12
1   5 7    11 ..
2 4   8 10
3     9

从中我们发现，对于行数是 n 的情况：

对于第一行和最后一行，是公差为 2(n?1) 的等差数列，首项是 0 和 n?1；
对于第 i 行(0<i<n?1)，是两个公差为 2(n?1) 的等差数列交替排列，首项分别是 i 和 2n?i?2；

所以我们可以从上到下，依次打印每行的字符。

时间复杂度分析：每个字符遍历一遍，所以时间复杂度是O(n)

class Solution {
public:
    string convert(string s, int n) {
        string res;
        if(n == 1) return s;
        for(int i = 0; i < n; ++i){
            if(i == 0 || i == n - 1){
                for(int j = i; j < s.size(); j += 2 * n - 2) res += s[j];
            }else{
                for(int j = i, k = 2 * n - i - 2;
                    j < s.size() || k < s.size();
                    j += 2 * n - 2, k += 2 * n - 2)
                {
                    if(j < s.size()) res += s[j];
                    if(k < s.size()) res += s[k];
                }
            }
        }
        return res;
    }
};

7.整数反转

解题思路

while循环依次得到res（合法），判断res在本次正数或负数翻转时是否合法，合法则得到新的res

c++中的%运算：

1234 % 10 = 4

-1234 % 10 = -4

代码

不管题目要求解法

class Solution {
public:
    int reverse(int x) {
        long long res = 0; // 直接用一个long long来存
        while(x){
            res = res * 10 + x % 10;
            x /= 10;
        }
        if(res > INT_MAX || res < INT_MIN) return 0;
        return res;
    }
};

按照题目要求解

class Solution {
public:
    int reverse(int x) {
        int r = 0;
        while(x){
            if(r > 0 && r > (INT_MAX - x % 10) / 10) return 0;
            if(r < 0 && r < (INT_MIN - x % 10) / 10) return 0;
            r = r * 10 + x % 10;
            x /= 10;
        }
        return r;
    }
};

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

class Solution {
public:
    int myAtoi(string s) {
        int k = 0;
        while(k < s.size() && s[k] == ' ') ++k;

        int minus = 1;
        if(s[k] == '-') minus = -1, ++k;
        else if(s[k] == '+') ++k;

        long long res = 0;
        for(int i = k; i < s.size() && isdigit(s[i]); ++i){
            res = res * 10 + s[i] - '0';
            if(res > INT_MAX) break;
        }

        res *= minus;
        if(minus == 1 && res > INT_MAX) return INT_MAX;
        else if(minus == -1 && res < INT_MIN) return INT_MIN;

        return res;
    }
};

解题思路

模拟

代码

class Solution {
public:
    int myAtoi(string s) {
        int k = 0;
        while(k < s.size() && s[k] == ' ') ++k;
        if(k == s.size()) return 0;

        int minus = 1;
        if(s[k] == '-') minus = -1, ++k;
        else if(s[k] == '+') ++k;

        if(!isdigit(s[k])) return 0;
        int res = minus * (s[k++] - '0'); // 将符号存在首位
        for(int i = k; i < s.size() && isdigit(s[i]); ++i){
            int x = s[i] - '0';
            if(res > 0 && res > (INT_MAX - x) / 10) return INT_MAX;
            else if(res < 0 && res < (INT_MIN + x) / 10) return INT_MIN;
            if(minus > 0) res = res * 10 + x;
            else if(minus < 0) res = res * 10 - x;
        }

        return res;
    }
};

9.回文数

解题思路

转换成字符串，判断翻转后的是否一样

代码

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        
        string s = to_string(x);
        return s == string(s.rbegin(), s.rend());
    }
};

解题思路

参考力扣第七题：整数翻转

优化：可以只翻转后 len/2 个，本代码未实现

代码

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        
        long long rx = 0;
        int t = x;
        while(t){
            rx = rx * 10 + t % 10;
            t /= 10;
        }
        return rx == x;
    }
};

10.正则表达式匹配

解题思路

模板

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = " " + s;
        p = " " + p;
        f[0][0] = true;
        for(int i = 0; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                if(j + 1 <= m && p[j + 1] == '*') continue;

                if(i && p[j] != '*') f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                else if(p[j] == '*') f[i][j] = f[i][j - 2] 
                                    || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
            }
        }
        return f[n][m];
    }
private:
    bool f[25][35];
};