leetcode刷题记录——2024年3月

Andromeda

发布于 2024-03-06 08:43:18

1020

发布于 2024-03-06 08:43:18

文章被收录于专栏：Andromeda的专栏

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")

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

集合