头像

heiyou


访客:812

离线:2小时前


活动打卡代码 LeetCode 74. Search a 2D Matrix

heiyou
2小时前
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;

        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = m * n - 1;

        while(l < r)
        {
            int mid = l + r >> 1;
            if(matrix[mid / m][mid % m] >= target) r = mid;
            else l = mid + 1;
        }

        if(matrix[l / m][l % m] == target) return true;
        else return false;
    }
};



heiyou
2小时前
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return {-1, -1};

        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r + 1>> 1;
            if(nums[mid] <= target) l = mid; 
            else r = mid - 1;
        }

        if(nums[l] != target) return {-1, -1};
        int start = l;
        l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return {l, start};
    }
};



heiyou
2小时前
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        if(nums.empty() || target > nums.back()) return nums.size();

        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};


活动打卡代码 LeetCode 69. Sqrt(x)

heiyou
2小时前
class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while(l < r)
        {
            int mid = l + (long long)r + 1 >> 1;
            if(mid <= x / mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};


活动打卡代码 AcWing 1631. 后序遍历

heiyou
5天前
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 5e4 + 10;

int preorder[N], inorder[N];
int n, index, ans;
unordered_map<int, int> l, r, pos;

int build(int pl, int pr, int il, int ir)
{
    int root = preorder[pl];
    int k = pos[root];
    if(k > il) l[root] = build(pl + 1, pl + k - il, il, k - 1);
    if(k < ir) r[root] = build(pl + k - il + 1, pr, k + 1, ir);
    return root;
}

void dfs(int root)
{
    if(l.count(root)) dfs(l[root]);
    if(r.count(root)) dfs(r[root]);
    if(index == 0)
    {
        index ++;
        ans = root;
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> preorder[i];
    for(int i = 0; i < n; i ++)
    {
        cin >> inorder[i];
        pos[inorder[i]] = i;
    }

    int root = build(0, n - 1, 0, n - 1);
    dfs(root);
    cout << ans << endl;

    return 0;
}




heiyou
5天前
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 40;

unordered_map<int, int> l, r, pos;
int n, inorder[N], postorder[N];
int q[N];

int build(int pl, int pr, int il, int ir)
{
    int root = postorder[pr];
    int k = pos[root];
    if(k > il) l[root] = build(pl, k - 1 - il + pl, il, k - 1);
    if(k < ir) r[root] = build(k + pl - il, pr - 1, k + 1, ir);
    return root;
}

void bfs(int root)
{
    int hh = 0, tt = 0;
    q[0] = root;
    int step = 0;
    while(tt >= hh)
    {
        int head = hh, tail = tt;
        while(hh <= tail)          //遍历这一层
        {
            int t = q[hh ++];
            if(l.count(t)) q[++ tt] = l[t];
            if(r.count(t)) q[++ tt] = r[t];
        }
        if(++ step % 2) reverse(q + head, q + tail + 1);
    }

    cout << q[0];
    for(int i = 1; i < n; i ++) cout << " " << q[i];
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> inorder[i], pos[inorder[i]] = i;
    for(int i = 0; i < n; i ++) cin >> postorder[i];

    int root = build(0, n - 1, 0, n - 1);
    bfs(root);

    return 0;
}



heiyou
5天前
最难的是想出如何在遍历过程中记录中序遍历的顺序
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 40;

int preorder[N], postorder[N];
int n;

int dfs(int l1, int r1, int l2, int r2, string& str)
{
    if(l1 > r1) return 1; //表示发现一组合法方案
    if(preorder[l1] != postorder[r2]) return 0;  //不合法

    int cnt = 0;
    for(int i = l1; i <= r1; i ++)
    {
        string lin, rin;

        int lcnt = dfs(l1 + 1, i, l2, l2 + i - l1 - 1, lin);
        int rcnt = dfs(i + 1, r1, l2 + i - l1, r2 - 1, rin);

        if(lcnt && rcnt)
        {
            cnt += lcnt * rcnt;
            str = lin + to_string(preorder[l1]) + " " + rin;
            if(cnt > 1) break;
        }
    }
    return cnt;
}


int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> preorder[i];
    for(int i = 0; i < n; i ++) cin >> postorder[i];

    string str;
    int cnt = dfs(0, n - 1, 0, n - 1, str);

    if(cnt > 1) puts("No");
    else puts("Yes");

    str.pop_back();
    cout << str << endl;
    return 0;
}



heiyou
6天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

int n, root, max_depth;
int cnt[1010];
int l[N], r[N], pos[N];

void dfs(int father, int u, int depth)
{
    if(pos[u] <= pos[father])
    {
        if(l[father] == 0x3f3f3f3f)  //左孩子为空
        {
            l[father] = u;      //左边节点是u
            cnt[depth + 1] ++;
            max_depth = max(max_depth, depth + 1);
        }
        else dfs(l[father], u, depth + 1);
    }
    else if(pos[u] > pos[father])
    {
        if(r[father] == 0x3f3f3f3f)
        {
            r[father] = u;
            cnt[depth + 1] ++;
            max_depth = max(max_depth, depth + 1);
        }
        else dfs(r[father], u, depth + 1);
    }
}

int main()
{
    memset(l, 0x3f, sizeof l);
    memset(r, 0x3f, sizeof r);
    cin >> n;
    if(n == 1)
    {
        int x;
        cin >> x;
        cout << "1 + 0 = 1" << endl;
        return 0;
    }
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        if(i == 0)
        {
            root = x;
            pos[i] = x;
        }
        else 
        {
            pos[i] = x;
            dfs(0, i, 0); //从第0层开始插入, 根节点编号:0, 需要插入的节点:i
        }
    }

    int a = cnt[max_depth], b = cnt[max_depth - 1];
    cout << a << " + " << b << " = " << a+b << endl;

    return 0;
}



heiyou
6天前
我又来了,我真的笨
-1000,1000 直接映射到pos数组就可以了
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

int n, root, max_depth;
int cnt[1010];
int l[N], r[N], pos[N];

void dfs(int father, int u, int depth)
{
    if(pos[u] <= pos[father])
    {
        if(l[father] == 0x3f3f3f3f)  //左孩子为空
        {
            l[father] = u;      //左边节点是u
            cnt[depth + 1] ++;
            max_depth = max(max_depth, depth + 1);
        }
        else dfs(l[father], u, depth + 1);
    }
    else if(pos[u] > pos[father])
    {
        if(r[father] == 0x3f3f3f3f)
        {
            r[father] = u;
            cnt[depth + 1] ++;
            max_depth = max(max_depth, depth + 1);
        }
        else dfs(r[father], u, depth + 1);
    }
}

int main()
{
    memset(l, 0x3f, sizeof l);
    memset(r, 0x3f, sizeof r);
    cin >> n;
    if(n == 1)
    {
        int x;
        cin >> x;
        cout << "1 + 0 = 1" << endl;
        return 0;
    }
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        if(i == 0)
        {
            root = x;
            pos[i] = x;
        }
        else 
        {
            pos[i] = x;
            dfs(0, i, 0); //从第0层开始插入, 根节点编号:0, 需要插入的节点:i
        }
    }

    int a = cnt[max_depth], b = cnt[max_depth - 1];
    cout << a << " + " << b << " = " << a+b << endl;

    return 0;
}



heiyou
6天前
记录一个会超时的做法, acwing只能过一个数据...
pat网站超时一个数据
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int n, root, max_depth;
int cnt[1010];
unordered_map<int, int> l, r;

void dfs(int father, int u, int depth)
{
    if(u <= father)
    {
        if(l.count(father) == 0)  //左孩子为空
        {
            l[father] = u;
            cnt[depth + 1] ++;
            max_depth = max(max_depth, depth + 1);
        }
        else dfs(l[father], u, depth + 1);
    }
    else if(u > father)
    {
        if(r.count(father) == 0)
        {
            r[father] = u;
            cnt[depth + 1] ++;
            max_depth = max(max_depth, depth + 1);
        }
        else dfs(r[father], u, depth + 1);
    }
}

int main()
{
    cin >> n;
    if(n == 1)
    {
        int x;
        cin >> x;
        cout << "1 + 0 = 1" << endl;
        return 0;
    }
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        if(i == 0) root = x;
        else 
        {
            dfs(root, x, 0); //从第0层开始插入
        }
    }

    int a = cnt[max_depth], b = cnt[max_depth - 1];
    cout << a << " + " << b << " = " << a+b << endl;

    return 0;
}