24春招-2 | 实习刷题

1.CODETOP 100

1.1 后端总体HOT 100

1.1.1 LRU

双向链表

#include <unordered_map>
#include <iostream>
using namespace std;

struct Node {
    Node* prev = nullptr; // 初始化指针为nullptr
    Node* next = nullptr; // 使用next而不是nxt，以增强代码可读性
    int key;
    int val;

    Node(int key, int val) : key(key), val(val) {} // 构造函数初始化键值对
};

class LRUCache {
private:
    int nowCapacity;
    int totCapacity;
    Node* head = nullptr;
    Node* tail = nullptr;
    unordered_map<int, Node*> mp;

    void moveToHead(Node* node) {
        if(node == head) return;

        if(node->prev) node->prev->next = node->next;
        if(node->next) node->next->prev = node->prev;

        if(tail == node) tail = node->prev;

        node->next = head;
        node->prev = nullptr;
        if(head != nullptr) head->prev = node;
        head = node;

        if(tail == nullptr) tail = head; // 当链表只有一个节点时
    }

public:
    LRUCache(int capacity) : nowCapacity(0), totCapacity(capacity) {}

    int get(int key) {
        if(mp.find(key) != mp.end()) {
            moveToHead(mp[key]);
            return mp[key]->val;
        }
        return -1;
    }

    void put(int key, int value) {
        if(mp.find(key) != mp.end()) { // 直接检查键是否存在
            Node* node = mp[key];
            node->val = value;
            moveToHead(node);
        } else {
            Node* node = new Node(key, value);
            if(nowCapacity < totCapacity) {
                nowCapacity++;
            } else {
                // 删除尾节点
                Node* toDelete = tail;
                if(tail->prev) tail->prev->next = nullptr;
                tail = tail->prev;
                mp.erase(toDelete->key);
                delete toDelete;
                if(tail == nullptr) head = nullptr; // 如果链表变空
            }
            if(head != nullptr) head->prev = node;
            node->next = head;
            head = node;
            if(tail == nullptr) tail = head;
            mp[key] = node;
        }
    }
};

1.1.2 反转链表

不断记录下一个，双指针即可，递归浪费栈空间

/**
 * 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* reverseList(ListNode* head) {
        if(!head) return 0;
        ListNode* now = head;
        ListNode* nxt = head->next;
        now->next = 0;
        while(nxt) {
            ListNode* n = nxt->next;
            nxt->next = now;
            now = nxt;
            nxt = n;
        }
        return now;
    }
};

1.1.3. 无重复字符的最长字串

双指针

#include "iostream"
using namespace std;
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int ans = min(n, 1);
        int l = 0, r = 0;
        vector<int> cnt(256,0);
        while(r < n) {
            cnt[s[r]]+=1;
            while(cnt[s[r]] > 1 && l < r) {
                cnt[s[l]] -= 1;
                l++;
            }
            r++;
            ans = max(ans, r-l);
        }
        return ans;
    }
};

1.1.3. K个一组翻转链表

注意链表反转后的逻辑

/**
 * 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:
    void reverseLinkedNode(ListNode* start, ListNode* end) {
        cout << "start" << start->val << "end" << end->val << endl;
        auto now = start;
        auto nxt = start->next;
        while(now) {
            if(now == end) {
                return;
            }
            auto realNext = nxt->next;
            nxt->next = now;
            now = nxt;
            nxt = realNext;
        }
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k==1) return head;
        ListNode* now = head;
        ListNode* st = 0;
        ListNode* ans = 0;
        ListNode* lsted = 0;
        while(now) {
            int n = k-1;
            st = now;
            while(n&&now) {
                now = now->next;  
                n--;
            }
            if(!st) st = head;
            if(!now) return ans;
            //cout << now->val << endl;
            ListNode* nxt = now->next;
            //reverse
            reverseLinkedNode(st, now);
            if(lsted) lsted->next = now;
            lsted = st;
            //cout << " ok" << endl;
            st->next = nxt;
            if(!ans) ans = now;
            now = nxt;
        }
        return ans;
    }
};

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

最小堆，这里有很多解法

#include <queue>
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for(auto x : nums) {
            pq.push(-x);
            if(pq.size() > k) {
                pq.pop();
            }
        }
        return -pq.top();
    }
};

1.1.5. 三数之和

双指针，注意去重方式，需要在i，l，r处全部去重

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        for(int i = 0; i < nums.size();i++) {
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int base = nums[i];
            int l = i+1, r = nums.size() - 1;
            while(l < r) {
                int nowAns = base + nums[l] + nums[r];
                if(nowAns == 0) {
                    // as ans
                    vector<int> v = {base, nums[l], nums[r]};
                    ans.push_back(v);
                    l++;
                    while(l > 0 && l < nums.size() && nums[l] == nums[l-1]) {
                        l++;                    
                    }
                    r--;
                    while(r < nums.size()-1 && r >= 0 && nums[r] == nums[r+1])r--;
                }else if(nowAns > 0) {
                    r--;
                }else {
                    l++;
                }
            }
        }
        return ans;
    }
};

1.1.6. 合并两个有序链表

双指针，注意判空

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(!list1) return list2;
        if(!list2) return list1;
        ListNode* ans = 0;
        ListNode* now = 0;
        while(list1 && list2) {
            if(!ans) {
                if(list1->val < list2->val) ans = list1,now = list1, list1=list1->next;
                else ans = list2, now = list2, list2=list2->next;
            }else{
                if(list1->val < list2->val) now->next = list1, list1 = list1->next;
                else now->next = list2, list2 = list2->next;
                now = now->next;
            }
        }
        while(list2) {
            now->next = list2, list2 = list2->next;
        }
        while(list1) {
            now->next = list1, list1 = list1->next;
        }
        return ans;
    }
};

1.1.7. 快速排序

快排的N种实现方式，双指针法，优化选择。
除此之外，还有堆排，归并需要实现下。

class Solution {
private:
int GetMid(vector<int>& a, int left, int right){
	int mid = (left + right)>>1;   
	if(a[left] < a[mid])
	    if(a[mid] < a[right])
		return mid;                      //mid为中间值
	    else
		if(a[left] < a[right])
		    return right;                //right为中间值
		else
		    return left;                 //left为中间值
	else
	    if(a[mid] > a[right])
		return mid;                      //mid为中间值
	    else
		if(a[left] > a[right])
		    return right;                //right为中间值
		else
		    return left;                 //left为中间值
}
    void sortPartition(vector<int>& nums, int l, int r) {
        if(l>=r) return;
        int i = l;
        int j = r;
        int mid = GetMid(nums, l, r);
        swap(nums[l], nums[mid]);
        int base = nums[l];
        while(i < j) {
            while(i < j && nums[j] >= base)j--;
            while(i < j && nums[i] <= base)i++;
            swap(nums[i], nums[j]);
        } 
        swap(nums[i], nums[l]);
        sortPartition(nums,i+1,r);
        sortPartition(nums,l,i-1);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        sortPartition(nums, 0, nums.size()-1);
        return nums;
    }
};

1.1.8. 搜索旋转数组

注意搜索边界

class Solution {
public:
    int search(vector<int>& arr, int target) {
        int l = 0;
        int r = arr.size()-1;
        while (r > 0 && arr[0] == arr[r]) r--;//去重
        int s = r + 1;//去重后大小
        cout << "size" << s << endl;
        //找二分旋转点
        while(l < r) {
            int mid = (l + r + 1) >> 1;
            if(arr[mid] >= arr[0]) l = mid;
            else r = mid - 1;
        }
        r = l + s;
        l = (l + 1);
        while(l < r) {
            //cout << l << " " << r << endl;
            int mid = (l + r) >> 1;
            if (arr[mid%s] >= target) r = mid;
            else l = mid+1;
        }
        return arr[(l%s)] == target?(l%s):-1;
    }
};

1.1.9. 搜索旋转数组

主要比较痛苦的是排序函数，除此之外没什么

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 最小堆
        auto cmp = [&](const ListNode* lhs, const ListNode* rhs) {
            return lhs->val > rhs->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);

        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        for (auto& node : lists) {
            if (node != nullptr) {
                heap.push(node);
            }
        }

        while (!heap.empty()) {
            ListNode* node = heap.top();
            heap.pop();
            if (node->next != nullptr) {
                heap.push(node->next);
            }
            cur->next = node;
            cur = cur->next;
        }

        ListNode* ret = dummy->next;
        delete dummy;
        dummy = nullptr;

        return ret;
    }
};

1.1.10. 反转链表II

注意边界

/**
 * 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 {
private:
    void reverseNode(ListNode* l, ListNode* r) {
        ListNode* now = l;
        ListNode* nxt = l->next;
        while(nxt) {
            ListNode *n = nxt->next;
            nxt->next = now;
            if(nxt == r) break;
            now = nxt;
            nxt = n;
        }
    }
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left == right) return head;
        left--, right--;
        ListNode *l = head, *llst = 0,  *r = head;
        while(left--) llst = l, l = l->next;
        while(right--) r = r->next;
        ListNode* rnxt = r->next;
        reverseNode(l,r);
        if(llst) llst->next = r;
        else head = r;
        l->next = rnxt;
        return head;
    }
};

1.1.11. 二叉树层序遍历

常规BFS，主要注意容器用法就可以

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root) return ans;
        vector<int> now;
        queue<pair<int,TreeNode*>> q;
        int lst = 1;
        q.push({1, root});
        while(!q.empty()) {
            auto top = q.front();
            q.pop();
            auto frt = top.second;
            int d = top.first;
            if(d > lst) {
                lst = d;
                ans.push_back(now);
                now = {};
            }
            now.push_back(frt->val);
            if(frt->left) q.push({lst+1, frt->left});
            if(frt->right) q.push({lst+1, frt->right});
        }
        if(now.size() > 0) ans.push_back(now);
        return ans;
    }
};

1.1.12 最大回文串

中心扩展法

class Solution {
public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return {left + 1, right - 1};
    }

    string longestPalindrome(string s) {
        int start = 0, end = 0;
        for (int i = 0; i < s.size(); ++i) {
            auto [left1, right1] = expandAroundCenter(s, i, i);
            auto [left2, right2] = expandAroundCenter(s, i, i + 1);
            if (right1 - left1 > end - start) {
                start = left1;
                end = right1;
            }
            if (right2 - left2 > end - start) {
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};

动态规划

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n < 2) {
            return s;
        }

        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        vector<vector<int>> dp(n, vector<int>(n));
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= n; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < n; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= n) {
                    break;
                }

                if (s[i] != s[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin, maxLen);
    }
};

1.1.13 二叉树锯齿形层次遍历

这没啥好做的，层次基础上加个stack就行

1.1.14 二叉树的最近公共祖先

注意判断条件，递归即可

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q){
        bool r1 = false,r2 = false;
        if(root->left) r1 = dfs(root->left, p, q);
        if(root->right) r2 = dfs(root->right, p, q);
        if((r1 && r2) || (
            (r1||r2) && (root==p||root==q)
        )) {
            ans = root;
        }
        return r1||r2||root==p||root==q;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p,q);
        return ans;
    }
};

1.1.15 重排链表

主要注意先找中点，然后反转后半部分，然后合并即可

/**
 * 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:
    void reorderList(ListNode* head) {
        int nodeLen = 0;
        ListNode *now = head;
        while(now) nodeLen++, now = now->next;

        int cnt = 0;
        int targetReverse = nodeLen - nodeLen/2;
        now = head;
        ListNode *nxt = now->next;
        while(nxt) {
            ListNode *n = nxt->next;
            cnt++;
            if(cnt == targetReverse) {
                //cout << cnt << " " << now->val;
                nxt->next = 0;
                now->next = 0;
            }else if(cnt > targetReverse) {
                nxt->next = now;
            }
            now = nxt, nxt = n;
        }

        ListNode *l1 = head;
        ListNode *l2 = now;

        while(l1!=l2 && l1 && l2) {
            ListNode* l1n = l1->next;
            ListNode* l2n = l2->next;
            l1->next = l2;
            l2->next = l1n;
            l1 = l1n, l2=l2n;
        }
    }
};

1.1.16 螺旋矩阵

状态机

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int t = -1,d=matrix.size(),l=-1,r=matrix[0].size();
        vector<int> offset = {1,0};
        vector<int> pos = {0,0};
        int cnt = 0;
        int sq = d * r;
        vector<int> ans(sq);
        while(cnt < sq) {
            //cout << pos[0] << " " << pos[1] << endl;
            ans[cnt++] = matrix[pos[1]][pos[0]];
            if(offset[0]!=0) {
                if(pos[0]+offset[0] >= r) {
                    offset = {0,1};
                    t++;
                }else if(pos[0]+offset[0] <= l){
                    offset = {0,-1};
                    d--;
                }
            }else{
                if(pos[1]+offset[1] >= d) {
                    offset = {-1,0};
                    r--;
                }else if(pos[1]+offset[1] <= t){
                    offset = {1,0};
                    l++;
                }
            }
            pos[0] += offset[0];
            pos[1] += offset[1];
        }
        return ans;
    }
};

1.1.17 相交链表

注意，这里需要注意的问题是判断停止的条件

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *hA, ListNode *hB) {
        if(hA == 0 || hB == 0) return 0;
        ListNode *pA = hA, *pB = hB;
        while (pA != pB) {
            pA = pA == 0 ? hA : pA->next;
            pB = pB == 0 ? hB : pB->next;
        }
        return pA;
    }
};

1.1.18 接雨水

单调栈做法主要要想明白，如果计算新增面积，必须有：左，下，当前构成。以方块的形式消去不同高度

class Solution {
public:
    int trap(vector<int>& h) {
        stack<int> s;
        int ans = 0;
        int n = h.size();
        for(int i = 0; i < n;i++) {
            while(!s.empty() && h[i]>h[s.top()]) {
                int t = s.top();
                s.pop();
                if(s.empty()) break;
                int l = s.top();
                ans += (i - l - 1) * (
                    min(h[l], h[i]) - h[t]
                );
            }
            s.push(i);
        }
        return ans;
    }
};

双指针, 这里主要是找右面最大的 需要在看

class Solution {
public:
    int trap(vector<int>& h) {
        int ans = 0;
        int n = h.size();
        int l = 0, r = n - 1;
        int ml = 0, mr = 0;
        while(l < r) {
            ml = max(ml, h[l]), mr = max(mr, h[r]);
            if(ml < mr) ans+=ml-h[l++];
            else ans+=mr-h[r--];
        }
        return ans;
    }
};

1.1.19 岛屿数量

广搜

class Solution {
public:
    int numIslands(vector<vector<char>>& g) {
        int tx = g[0].size();
        int ty = g.size();
        vector<vector<bool>> vis(ty, vector<bool>(tx,0));

        int d[4][2] = {1,0,0,1,-1,0,0,-1};

        int ans = 0;
        for(int x = 0; x < tx;x++) {
            for(int y = 0; y < ty;y++) {
                if(!vis[y][x] && g[y][x] == '1') {
                    ans++;
                    queue<pair<int,int>> q;
                    q.push({x,y});
                    vis[y][x] = 1;
                    while(!q.empty()) {
                        auto fr = q.front();
                        q.pop();
                        int nx = fr.first;
                        int ny = fr.second;
                        for(int i = 0;i < 4;i++) {
                            int newX = nx + d[i][0];
                            int newY = ny + d[i][1];
                            if(newX >= 0 && newX < tx && newY >= 0 && newY < ty
                            && !vis[newY][newX] && g[newY][newX] == '1') {
                                vis[newY][newX] = 1;
                                q.push({newX,newY});
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
};

1.1.20 买卖股票的最佳时机

没啥说的

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        int mn = 100861111;
        for(auto x:prices) {
            mn = min(mn,x);
            ans = max(ans, x-mn);
        }
        return ans;
    }
};

1.1.21 环形链表

快慢指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *h) {
        ListNode* f = h;
        ListNode* s = h;
        while(f&&s) {
            f = f->next;
            if(f) f = f->next;
            s = s->next;
            if(f&&s&&f == s) return true;
        }
        return false;
    }
};

1.22 两数之和

哈希表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        int idx = 0;
        vector<int> ans;
        for(auto x: nums) {
            if(mp.find(target - x)!=mp.end()) {
                ans = {mp[target-x], idx};
                return ans;
            }
            mp[x] = idx;
            idx++;
        }
        return ans;
    }
};

1.23 全排列

搜索即可

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> vis;
    int size;
    void dfs(int nowPos, vector<int>&nowAns, vector<int>& nums) {
        //for(auto x:nowAns) cout << x << " ";
        //cout << endl;
        if(nowPos == size - 1) {
            vector<int> n;
            for(auto x:nowAns) n.push_back(x);
            ans.push_back(n);
        }else{
            for(int i = 0;i < size;i++) {
                if(!vis[i]) {
                    //cout << i << nums[i] << endl;
                    nowAns[nowPos + 1] = nums[i];
                    vis[i] = 1;
                    dfs(nowPos + 1, nowAns, nums);
                    vis[i] = 0;
                }
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        size = nums.size();
        vis = vector<int>(size+1,0);
        vector <int> temp(size,0);
        dfs(-1, temp, nums);
        return ans;
    }
};

1.23 删除排序链表中的重复元素

/**
 * 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) {
        auto now = head;
        while(now) {
            auto nxt = now->next;
            while(nxt && nxt->val == now->val) {
                now->next = nxt->next;
                nxt = nxt->next;
            }
            now = now->next;
        }
        return head;
    }
};

1.24 最长递增子序列

这题注意一下nlogn解

1. 大保底n^2解

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1,1);
        int ans = 1;
        for(int i = 1;i < n;i++) {
            for(int j = 0;j < i;j++) {
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

1.25 二叉树右视图

没必要做，只要抓准每轮消息队列最后一个