头像

acw_zxh

河北经贸大学




离线:9天前


最近来访(10)
用户头像
yxc
用户头像
chasewind32
用户头像
Peter_5
用户头像
Tingting
用户头像
爱吃面条的阿泽
用户头像
xiusike1
用户头像
Chessma
用户头像
zombotany
用户头像
zombotany
用户头像
齐天大仙
用户头像
Lupinus


acw_zxh
11天前

\#include<stdio.h\> \#include<sys/stat.h\> \#include<sys/types.h\> \#include<fcntl.h\> \#include<string.h\> \#include<unistd.h\>

int main(int argc,char* argv[]){ int src_fd,dst_fd; int count; int err; char* buf[100]; src_fd = open(argv[1],RDONLY); if(src_fd == -1){ perror("open_error:src"); return 0; } dst_fd = open(argv[2],WRONLY|O_CREAT,0666); if(dst_fd == -1){ perror("open_error:dst"); return 0; } while(1){ memset(buf,0,sizeof buf); count = read(src_fd,buf,99); if(count <= 0){ perror("read"); return; } count = write(dst_fd,buf,count); if(count <= 0){ perror("write"); return 0; } } err = close(src_fd); if(err != 0){ perror("close_error:src"); return 0; } err = close(dst_fd); if(err != 0){ perror("close_error:dst"); return 0; } return 0; }




acw_zxh
4个月前

题目描述

输入一棵二叉树前序遍历和中序遍历的结果,请重建该二叉树。

注意:

二叉树中每个节点的值都互不相同;
输入的前序遍历和中序遍历一定合法;

样例

给定:
前序遍历是:[3, 9, 20, 15, 7]
中序遍历是:[9, 3, 15, 20, 7]

返回:[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示:
    3
   / \
  9  20
    /  \
   15   7

前序和中序遍历

前序遍历序列:(根节点)[左子树前序遍历序列][右子树子前序遍历序列]
中序遍历序列:[左子树前序遍历序列](根节点)[右子树子前序遍历序列]

算法

1.找到当前子树的根
2.在中序遍历序列中,确定该根节点的左子树和右子树的边界
3.根据子树的节点个数,在前序遍历序列中确定该根节点左子树和右子树边界
4.递归这个过程

时间复杂度

参考文献

C++ 代码

/**
 * 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 {
public:
    vector<int> pre,in;
    TreeNode* dfs(int pl,int pr,int il,int ir){
        TreeNode* root = nullptr;
        if(pl <= pr){
            root = new TreeNode(pre[pl]);
            for(int k = il;k <= ir;k ++){
                if(in[k] == root -> val){
                    root -> left = dfs(pl + 1,pl + k - il,il,k - 1);
                    root -> right = dfs(pl + k - il + 1,pr,k + 1,ir);
                    break;
                }
            }
        }
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        pre = preorder,in = inorder;
        return dfs(0,pre.size() - 1,0,in.size() - 1);
    }
};



活动打卡代码 AcWing 3429. 全排列

acw_zxh
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string s;
bool st[10];

void dfs(string t,int k){
    if(k == 0){
        cout<<t<<endl;
        return;
    }
    for(int i = 0;i < s.size();i ++){
        if(!st[i]){
            st[i] = true;
            dfs(t + s[i],k - 1);
            st[i] = false;
        }
    }
}


int main(){
    cin>>s;
    dfs("",s.size());

    return 0;
}


活动打卡代码 AcWing 3472. 八皇后

acw_zxh
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
/**
 * 设两点分别为(x1,y1)(x2,y2)
 * (1)在同一行:x1 = x2
 * (2)在同一列:y1 = y2
 * (3)在同一斜:y2 - y1 = x2 - x1  || y2 - y1 = -(x2 - x1)
 *          即  abs(y2 - y1) = abs(x2 - x1)
 * */

vector<vector<int>> ans;
vector<int> res;
bool st[N];
int path[N];
void dfs(int k){
    if(k > 8){
        ans.push_back(res);
        return;
    }
    //列
    for(int i = 1;i <= 8;i ++)
    {
        //当前测试点:(k,i)
        if(!st[i]){
           bool flag = true;
           //行
           //前面的点为:(j,res[j-1])
           for(int j = 1;j < k;j ++){
               if(abs(k - j) == abs(i - res[j - 1])){
                   flag = false;
                   break;
               } 
           }
           if(flag){
               st[i] = true;
               res.push_back(i);
               dfs(k + 1);
               res.pop_back();
               st[i] = false;
           }
       }
    }
}

int main(){
    int T,n;
    scanf("%d",&T);
    dfs(1);
    while(T --){
        scanf("%d",&n);

        for(int i = 0;i < 8;i ++){
            printf("%d",ans[n-1][i]);
        }
        puts("");
    }
    return 0;
}


活动打卡代码 AcWing 18. 重建二叉树

acw_zxh
4个月前
/**
 * 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 {
public:
    vector<int> pre,in;
    TreeNode* dfs(int pl,int pr,int il,int ir){
        TreeNode* root = nullptr;
        if(pl <= pr){
            root = new TreeNode(pre[pl]);
            for(int k = il;k <= ir;k ++){
                if(in[k] == root -> val){
                    root -> left = dfs(pl + 1,pl + k - il,il,k - 1);
                    root -> right = dfs(pl + k - il + 1,pr,k + 1,ir);
                    break;
                }
            }
        }
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        pre = preorder,in = inorder;
        return dfs(0,pre.size() - 1,0,in.size() - 1);
    }
};



acw_zxh
4个月前
/**
 * 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 {
public:
    int dfs(TreeNode* p,int deep){
        if(!p -> left && !p->right){
            return deep * p ->val;
        }
        int num = 0;
        if (p -> left)  num  += dfs(p -> left,deep + 1);
        if (p -> right) num  += dfs(p -> right,deep + 1);
        return num;
    }
    int pathSum(TreeNode* root) {
        return dfs(root,0);
    }
};


活动打卡代码 AcWing 3573. 日期累加

acw_zxh
4个月前
#include <iostream>
#include <cstring>
using namespace std;

int days[2][13]= {
    {0,31,28,31,30,31,30,31,31,30,31,30,31},
    {0,31,29,31,30,31,30,31,31,30,31,30,31}
};

bool check(int y){
    return (y % 4 == 0 && y % 100 != 0) || y % 400 == 0;
}

int main(){
    int y,m,d,a;
    int T;
    cin>>T;
    while(T --){
        cin>>y>>m>>d>>a;
        while(a){
            int mon_days = days[check(y)][m] -d + 1;
            if(a >= mon_days){
                d = 1;
                m ++;
                a -= mon_days;
            }else{
                d += a;
                a = 0;
            }
            if(m > 12){
                y ++;
                m %= 12;
            }

        }
        printf("%04d-%02d-%02d\n",y,m,d);
    }
    return 0;
}


活动打卡代码 AcWing 3607. 打印日期

acw_zxh
5个月前
#include <iostream>
#include <algorithm>
using namespace std;
int days[2][13] = {
    {0,31,28,31,30,31,30,31,31,30,31,30,31},
    {0,31,29,31,30,31,30,31,31,30,31,30,31}
};

bool check(int y){
    if (y % 4 ==0 && y % 100 != 0 || y % 400 == 0){
        return true;
    }
    return false;
}


int main(){

    int y,dd;
    while(cin>>y>>dd){
        int d = 0,m = 1;
        while(dd --){
            d ++;
            if (d == days[check(y)][m] + 1){
                d = 1;
                m ++;
            }
        }
        printf("%04d-%02d-%02d\n",y,m,d);
    }


    return 0;
}



acw_zxh
5个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *pa, ListNode *pb) {
        auto p = pa,q = pb;
        while(p != q){
            p = p ? p -> next:pb;
            q = q ? q -> next:pa;
        }
        return p;
    }
};


活动打卡代码 AcWing 3756. 筛选链表

acw_zxh
5个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* filterList(ListNode* head) {
        unordered_set<int> d;
        auto p = head,q= head -> next;
        while(q){
            d.insert(abs(p -> val));
            if (d.find(abs(q -> val)) != d.end()){
                q = q -> next;
                p -> next = q;
            }else{
                p = q;
                q = q -> next;
            }
        }
        return head;
    }
};