leetcode刷题记录——2024年3月-能不能吃完饭再说

LCR 155、将二叉搜索树转为排序的双向链表——树、DFS

用head记录头节点，pre记录当前已建立的排序双向链表的尾节点。中序遍历二叉树，遍历的结果即排序的数字，当pre为空时，说明还没建立任何节点，则让head等于当前节点，然后让pre等于当前节点，否则让pre的后继指针指向当前节点，当前节点的前驱指针指向pre节点即可。

建立完成后，pre即为尾节点，建立尾节点与头节点之间的关系并返回head

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    private Node pre, head;

    public Node treeToDoublyList(Node root) {
        if(root == null){
            return null;
        }
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    private void dfs(Node root){
        if(root == null){
            return;
        }
        dfs(root.left);
        if(pre == null){
            head = root;
        }else{
            pre.right = root;
            root.left = pre;
        }
        pre = root;
        dfs(root.right);
    }
}

LCR 148、验证图书取出顺序——栈

主要思路就是判断takeOut是不是takeIn可能的取出序列。

一个指针记录当前准备放入的书，一个指向准备取出的书，如果当前栈顶的书等于准备取出的书，则一直取出直到栈为空或者栈顶的书不等于准备取出的书，然后移动in指针。

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        int in = 0, out = 0;
        Stack<Integer> s = new Stack<>();
        while(in < putIn.length){
            s.push(putIn[in]);
            while(!s.isEmpty() && s.peek() == takeOut[out]){
                out++;
                s.pop();
            }
            in++;
        }
        return s.isEmpty();
    }
}

平均数为k的最长连续子数组

每次输入时减k，那么问题就变成了和为0的最长子数组。在输入遍历的过程中，记录当前的前缀和，如果之前存在相同的前缀和，则说明这两个前缀和之间的子数组和为0，否则将前缀和和下标存入哈希表。

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

#define ll long long

int main() {
    int res = -1;
    int n, k;
    cin>>n>>k;
    vector<int> nums(n, 0);
    ll prefix = 0;
    unordered_map<ll, int> map;
    map[0] = -1;
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        nums[i] -= k;
        prefix += nums[i];
        if(map.find(prefix) != map.end()){
            res = max(res, i - map[prefix]);
        }else{
            map[prefix] = i;
        }
    }
    cout<<res<<endl;

}
// 64 位输出请用 printf("%lld")

小球投盒——集合

一个集合用来存放操作类型一放入的，一个集合用来存放操作类型二未放入的。

如果集合一大小等于n或者集合二存在x，说明放满了；如果集合二大小大于1或者集合一存在x，也说明放满了。

#include <bitset>
#include <cmath>
#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
    int res = -1;
    int m, n;
    cin >> n >> m;
    int t, x;
    unordered_set<int> put;
    unordered_set<int> unput;
    int cnt = 0;
    while(m--){
        cnt++;
        cin >> t >> x;
        if(x <= n && x >= 1){
            if(t == 1){
                put.insert(x);
                if(put.size() == n || unput.find(x) != unput.end()){
                    cout<<cnt<<endl;
                    return 0;
                }
            }else{
                unput.insert(x);
                if(unput.size() > 1 || put.find(x) != put.end()){
                    cout<<cnt<<endl;
                    return 0;
                }
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

小红结账

略

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> moneys(m, 0);
    int k, c;
    while(n--){
        cin >> k >> c;
        int money = c / k;
        if(c % k != 0){
            money++;
        }
        int p;
        for(int i = 0; i < k - 1; i++){
            cin >> p;
            moneys[p-1] += money;
        }
    }
    for (ll& money: moneys) {
        cout << money << " ";
    }
    cout<<endl;
}
// 64 位输出请用 printf("%lld")

合法IP地址

略

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string ip;
    cin >> ip;
    bool valid = true;
    vector<string> seg;
    string tmp;
    for (auto& ch : ip) {
        if (ch == '.') {
            seg.push_back(tmp);
            if (seg.size() > 3 || tmp.size() == 0 || tmp.size() > 3 ||
                    (tmp.size() > 1 && tmp[0] == '0') || stoi(seg.back()) > 255) {
                valid = false;
                break;
            }
            tmp.clear();
            continue;
        }
        if (ch < '0' || ch > '9') {
            valid = false;
            break;
        }
        tmp += ch;
    }
    if(tmp.length() > 0){
        seg.push_back(tmp);
    }
    if(seg.size() < 4){
        valid = false;
    }
    if (valid) {
        int f = stoi(seg[0]);
        if (f >= 128 && f <= 191) {
            cout << "B_address" << endl;
        } else if (f >= 192 && f <= 223) {
            cout << "C_address" << endl;
        } else if (f >= 1 && f < 126) {
            cout << "A_address" << endl;
        }else if(f == 126 && stoi(seg[1]) == 0 && stoi(seg[2]) == 0 && stoi(seg[3]) == 0){
            cout << "A_address" << endl;
        } 
        else {
            cout << "other" << endl;
        }
    } else {
        cout << "invalid" << endl;
    }
}
// 64 位输出请用 printf("%lld")

小美的游戏——贪心

其实就是取出最大的k个数相乘得到num，然后剩下k-1个数都为1，一个数为num，最后将这些数和优先级队列中的相加

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#define ll long long
using namespace std;
 
int main() {
    int n, k;
    cin >> n >> k;
    priority_queue<ll> queue;
    int tmp;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        queue.push(tmp);
    }
 
    ll ret = k;
    ll num = 1;
    while (k--) {
        num *= queue.top();
        num = num % 1000000007;
        queue.pop();
    }
    num *= queue.top();
    num = num % 1000000007;
    queue.pop();
    ret += num;
    ret = ret % 1000000007;
 
    while (!queue.empty()) {
        ret += queue.top();
        queue.pop();
        ret = ret % 1000000007;
    }
    cout<<ret<<endl;
}
// 64 位输出请用 printf("%lld")

小美的树上染色——贪心、dfs

要染色的节点最多，那么必然是从叶子节点向上开始染色，这样才能保证染色的节点是最多的。

#include <cmath>
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

void dfs(int n, vector<vector<int>>& g, vector<int>& tree, vector<int>& color, int & res, int exit){
        for(int& num : g[n]){
            // 避免循环遍历
            if(num == exit){
                continue;
            }
            int sq = sqrt(tree[n] * tree[num]);
            dfs(num, g, tree, color, res, n);
            // 从子树开始染色
            if(color[n] == 0 && color[num] == 0 && sq * sq == tree[n] * tree[num]){
                res += 2;
                color[n] = 1;
                color[num] = 1;
            }
        }
}

int main() {
    int n;
    cin >> n;
    vector<int> tree(n);
    vector<int> color(n, 0);
    vector<vector<int>> g(n);
    int cnt = n;
    while (cnt--) {
        cin >> tree[n - 1 - cnt];
    }
    cnt = n - 1;
    int a, b;
    int res = 0;
    while (cnt--) {
        cin >> a >> b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, g, tree, color, res, -1);
    cout << res << endl;
}
// 64 位输出请用 printf("%lld")

977、有序数组的平方——双指针

数组其实是有序的，只不过负数平方之后可能成为最大数了。那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针法了，i指向起始位置，j指向终止位置。定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        vector<int> res(nums.size());
        int ptr = right;
        while(left <= right){
            if(nums[left]*nums[left] > nums[right]*nums[right]){
                res[ptr] = nums[left]*nums[left];
                left++;
            }else{
                res[ptr] = nums[right]*nums[right];  
                right--;           
            }
            ptr--;
        }
        return res;
    }
};

59、螺旋矩阵——模拟

模拟顺时针画矩阵的过程:

填充上行从左到右
填充右列从上到下
填充下行从右到左
填充左列从下到上

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> mt(n, vector<int>(n, 0));
        int l = 0, r = n - 1, t = 0, b = n - 1;
        int num = 1;
        while(num <= n*n){
            for(int i = l; i <= r; i++){
                // cout << "mt[" << t << "][" << i << "] = " << num << endl; 
                mt[t][i] = num++;
            }
            t++;
            for(int i = t; i <= b; i++){
                // cout << "mt[" << i << "][" << r << "] = " << num << endl; 
                mt[i][r] = num++;
            }
            r--;
            if(b >= t){
                for(int i = r; i >= l; i--){
                    // cout << "mt[" << b << "][" << i << "] = " << num << endl; 
                    mt[b][i] = num++;
                }
                b--;
            }
            if(r >= l){
                for(int i = b; i >= t; i--){
                    // cout << "mt[" << i << "][" << l << "] = " << num << endl; 
                    mt[i][l] = num++;
                }
                l++;
            }
        }
        return mt;
    }
};

707、设计链表——链表

略

class Node {
public:
    Node() = default;
    Node(int v){
        val = v;
        pre = nullptr;
        nx = nullptr;
    }
    int val;
    Node* pre;
    Node* nx;
};

class MyLinkedList {
private:
    Node* head;
    Node* tail;
    int size;
public:
    MyLinkedList() {
        head = new Node();
        tail = head;
        size = 0;
    }
    
    int get(int index) {
        if(index < size && index >= 0){
            Node* cur = head->nx;
            while(index--){
                cur = cur->nx;
            }
            return cur->val;
        }
        return -1;
    }
    
    void addAtHead(int val) {
        if(size == 0){
            addAtTail(val);
            return;
        }
        Node* tmp = new Node(val);
        tmp->nx = head->nx;
        tmp->pre = head;
        head->nx->pre = tmp;
        head->nx = tmp;
        size++;
    }
    
    void addAtTail(int val) {
        Node* tmp = new Node(val);
        tail->nx = tmp;
        tmp->pre = tail;
        tail = tmp;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index > size){
            return;
        }
        if(index == 0){
            addAtHead(val);
        }else if(index == size){
            addAtTail(val);
        }else{
            Node* tmp = new Node(val);
            Node* cur = head;
            while(index--){
                cur = cur->nx;
            }
            tmp->nx = cur->nx;
            tmp->pre = cur;
            cur->nx->pre = tmp;
            cur->nx = tmp;
            size++; 
        }
    }
    
    void deleteAtIndex(int index) {
        if(index >= size || index < 0){
            return;
        }
        Node* cur = head;
        if(index == size - 1){
            tail = tail->pre;
        }
        while(index--){
            cur = cur->nx;
        }
        Node* del = cur->nx;
        cur->nx = cur->nx->nx;
        if(del->nx != nullptr){
            del->nx->pre = cur;
        }
        delete del;
        del = nullptr;
        size--; 
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

15、三数之和——双指针

首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。接下来如何移动left 和right呢，如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        int index = 0, left = 1, right = nums.size() - 1;
        for(; index < nums.size() - 2; index++){
            if(nums[index] > 0){
                return res;
            }
            if (index > 0 && nums[index] == nums[index - 1]) {
                continue;
            }
            left = index + 1;
            right = nums.size() - 1;
            while(left < right){
                if(nums[index] + nums[left] + nums[right] == 0){
                    res.push_back({nums[index], nums[left], nums[right]});
                    int l = nums[left];
                    int r = nums[right];
                    int i = nums[index];
                    while(left < right && nums[++left] == l){}
                    while(left < right && nums[--right] == r){}
                }else if(nums[index] + nums[left] + nums[right] > 0){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return res;
    }
};

18、四数之和——双指针

跟三数之和思路一样

#define ll long long
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        if(nums.size() < 4){
            return res;
        }
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > target && nums[i] >= 0){
                break;
            }
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            for(int j = i + 1; j < nums.size(); j++){
                int left = j + 1, right = nums.size() - 1;
                ll ij = nums[i] + nums[j];
                if(ij > target && ij >= 0){
                    break;
                }
                if(j > i + 1 && nums[j] == nums[j-1]){
                    continue;
                }
                while(left < right){
                    int l = nums[left];
                    int r = nums[right];
                    ll lr = l + r;
                    if(ij + lr == target){
                        res.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while(left < right && nums[++left] == l){}
                        while(left < right && nums[--right] == r){}
                    }else if(ij + lr > target){
                        right--;
                    }else{
                        left++;
                    }
                }
            }
        }
        return res;
    }
};

1262、可被三整除的最大和——动态规划

使用一个动态规划数组 dp 来跟踪每个余数（被 3 除）的最大和。数组 dp 的大小为 3，对应三种可能的余数（0、1 和 2）。

在循环中，对于每个数字 nums[i]，计算 a、b 和 c，这些是当前数字 nums[i] 与 dp 中当前值的和。

求余找出 a、b 和 c 被 3 除的余数。这告诉我们要更新 dp 的哪个元素，用它当前值和新计算出的和之间的最大值来更新 dp 的每个元素。

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> dp(3, 0);
        for(int i = 0; i < nums.size(); i++){
            int a, b, c;
            a = dp[0] + nums[i];
            b = dp[1] + nums[i];
            c = dp[2] + nums[i];
            dp[a%3] = max(dp[a%3], a);
            dp[b%3] = max(dp[b%3], b);
            dp[c%3] = max(dp[c%3], c);
        }
        return dp[0];
    }
};

------本页内容已结束，喜欢请分享------

文章作者

能不能吃完饭再说

隐私政策

PrivacyPolicy

用户协议

UseGenerator

许可协议

NC-SA 4.0

文章版权归作者所有，未经允许请勿转载。

THE END