摘要：
t＝&；左边目标）；数据颜色）；正确的右=新根；右=新_根->；=NULL）new_ root->；父项=根；left=根；parent=新根；左边父项=根->；父母亲
大三寒假之前
第一次投递 CVTE，稀烂。
智能指针，父子析构函数，volatile，继承与虚函数
希尔排序，选择排序，插入排序，冒泡排序，用数组和链表的效率比较
2022/3/2 宝融科技
总的来说比上次好，背的C++八股文有点用，Linux也有点用，线程进程编程重点
已知：int m=10;下列表示引用的方法中，哪个是在正确的
A:int &x=m;
B:int &y=10;
C:int &z;
D:int &t=&m;
extern "C"：实现C++和C的混合编程
substr strstr sprint memcpy哪个不可以啥字符串赋值
三个线程 ，id分别是ABC，各自打印十次，要求顺序输出ABCABCABC。。。。。。。
2022/3/3 同讯科技
交了一份C语言实现红黑树小任务
花了两三天时间研究了下，发现是比以前做的平衡二叉树难多了，主要是插入和删除情况，红黑树它不一样。
不能是那种，先插入或者删除，然后调用一个平衡函数维护红黑树。
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 typedef struct RBTreeNode { 5 int data; //数据域 6 int color; //0黑色 1红色 7 struct RBTreeNode *parent;//父亲结点 8 struct RBTreeNode *left; //左子结点 9 struct RBTreeNode *right; //右子结点 10 } RBTreeNode; 11 RBTreeNode *RBTreeEndNode; 12 void search(RBTreeNode *root,int target){ 13 if (root == NULL) 14 return ; 15 if(target == root->data){ 16 printf("找到%d了，color:%d\n",root->data,root->color); 17 return; 18 } 19 if(target < root->data) 20 search(root->left,target); 21 if(target > root->data) 22 search(root->right,target); 23 return ; 24 } 25 void preOrderTraverse(RBTreeNode *root){ 26 if (root == NULL) 27 return ; 28 if (root->parent != NULL) 29 printf("%d color: %d parent:%d\n", root->data, root->color, root->parent->data); 30 else 31 printf("%d color: %d\n", root->data, root->color); 32 preOrderTraverse(root->left); 33 preOrderTraverse(root->right); 34 } 35 RBTreeNode *left_rotation(RBTreeNode *root){ 36 //处理新根节点 37 RBTreeNode *new_root = root->right; 38 //处理新根父母 39 new_root->parent = root->parent; 40 if (root->parent != NULL){ 41 //判断父亲左右 42 if (new_root->parent->left == root) 43 new_root->parent->left = new_root; 44 else 45 new_root->parent->right = new_root; 46 } 47 //移走新根左节点 48 root->right = new_root->left; 49 if (new_root->left != NULL)new_root->left->parent = root; 50 //新加新根左节点 51 new_root->left = root; 52 root->parent = new_root; 53 54 return new_root; 55 } 56 RBTreeNode *right_rotation(RBTreeNode *root){ 57 //处理新根节点 58 RBTreeNode *new_root = root->left; 59 //处理新根父母 60 new_root->parent = root->parent; 61 if (root->parent != NULL){ 62 //判断父亲左右 63 if (new_root->parent->left == root) 64 { 65 new_root->parent->left = new_root; 66 }else{ 67 new_root->parent->right = new_root; 68 } 69 } 70 //移走新根右节点 71 root->left = new_root->right; 72 if (new_root->right != NULL)new_root->right->parent = root; 73 //新加新根右节点 74 new_root->right = root; 75 root->parent = new_root; 76 return new_root; 77 } 78 RBTreeNode *insert(RBTreeNode *root, int data, RBTreeNode *parent){ 79 if (NULL == root){ 80 RBTreeNode *node = (RBTreeNode *)malloc(sizeof(RBTreeNode)); 81 if (node == NULL){ 82 printf("malloc error \n"); 83 return NULL; 84 } 85 node->data = data; 86 node->parent= parent; 87 node->color = 1; 88 node->right = NULL; 89 node->left = NULL; 90 RBTreeEndNode = node; 91 return node; 92 } 93 if (data > root->data) 94 root->right = insert(root->right, data, root); 95 else 96 root->left = insert(root->left, data, root); 97 return root; 98 } 99 RBTreeNode *rebalance3(RBTreeNode *root, RBTreeNode *rootNode){//要放在insertRB之前 100 //1 新节点在根节点 101 if (root->parent == NULL){ 102 root->color = 0; 103 return root; 104 } 105 //2 有父节点 106 //2.1 父节点是黑色，啥也不用干 107 if (root->parent->color != 0){ 108 //2.2 父节点是红色,祖父一定是黑色啦，看叔叔是啥颜色 109 RBTreeNode *parent, *gparent, *uncle; 110 parent = root->parent; 111 gparent = root->parent->parent; 112 //先判断父节点是祖父节点的左节点还是右节点，即叔叔节点是啥 113 //2.2.1 父节点是祖父节点的左节点 114 if (parent == gparent->left){ 115 uncle = gparent->right; 116 //2.2.1.1如果叔叔也是红色 117 if (uncle != NULL && uncle->color == 1){ 118 parent->color = 0; 119 uncle->color = 0; 120 gparent->color = 1; 121 122 return rebalance3(gparent, rootNode); 123 }else{ 124 //2.2.1.2如果叔叔黑色 或不存在 125 //2.2.1.2.1 root是左节点 126 if (root == parent->left){ 127 parent->color = 0; 128 gparent->color = 1; 129 gparent = right_rotation(gparent); 130 }else{ 131 //2.2.1.2.2 root是右节点 132 //1.root与父节点交换 并把父节点设为新root的左节点,即转化为2.2.1.2.1 133 gparent->left = root; 134 root->parent = gparent; 135 root->left = parent; 136 parent->parent = root; 137 parent->right = NULL; 138 return rebalance3(parent, rootNode); 139 } 140 } 141 }else{ 142 //2.2.2 父节点是祖父节点的右节点 143 uncle = gparent->left; 144 //2.2.2.1如果叔叔也是红色 145 if (uncle != NULL && uncle->color == 1){ 146 parent->color = 0; 147 uncle->color = 0; 148 gparent->color = 1; 149 return rebalance3(gparent, rootNode); 150 }else{ 151 //2.2.2.2如果叔叔黑色 或不存在 152 //2.2.2.2.1 root是左节点 153 if (root == parent->left){ 154 //1.root与父节点交换 并把父节点设为新root的左节点,即转化为2.2.2.2.2 155 gparent->right = root; 156 root->parent = gparent; 157 root->right = parent; 158 parent->parent = root; 159 parent->left = NULL; 160 return rebalance3(parent, rootNode); 161 }else{ 162 //2.2.2.2.2 root是右节点 163 parent->color = 0; 164 gparent->color = 1; 165 gparent = left_rotation(gparent); 166 } 167 } 168 } 169 } 170 return rootNode; 171 } 172 RBTreeNode *inserRB(RBTreeNode *root, int data, RBTreeNode *parent){ 173 root = insert(root,data,parent); 174 return rebalance3(RBTreeEndNode,root); 175 } 176 RBTreeNode *FindMin(RBTreeNode *root) 177 { 178 if (root == NULL||root->left ==NULL) 179 return root; 180 return FindMin(root->left); 181 } 182 RBTreeNode *Delete(RBTreeNode *root, int target, RBTreeNode *rootNode) 183 { 184 if (root == NULL) 185 return NULL; 186 if (target > root->data) 187 rootNode = Delete(root->right, target, rootNode); 188 else if(target < root->data) 189 rootNode = Delete(root->left, target, rootNode); 190 else if(target == root->data){ 191 printf("%d删除成功！",target); 192 //删除根节点 193 if (root->parent == NULL){ 194 free(root); 195 root = NULL; 196 return root; 197 } 198 RBTreeNode *parent, *brother; 199 parent = root->parent; 200 //1.没有左右节点 201 if (root->left == NULL && root->right == NULL){ 202 //1.1被删除节点是红色，直接删除即可 203 if (root->color == 1){ 204 if (root == parent->left){ 205 parent->left = NULL; 206 }else{ 207 parent->right = NULL; 208 } 209 free(root); 210 root = NULL;//删除自身 211 }else{ 212 //1.2被删除节点是黑色，一定有兄弟节点 破坏了平衡性 需要重新平衡 213 //1.2.1被删除节点在父节点的左数上 214 if (root == parent->left){ 215 free(root); 216 root = NULL; 217 parent->left = NULL;//删除自身 218 brother = parent->right; 219 //1.2.1.1兄弟节点是黑色 220 if (brother->color == 0){ 221 //1.2.1.1.1 兄弟节点是黑色,且有一个右节点，右节点必然是红色 222 if (brother->right != NULL && brother->left == NULL){ 223 brother->right->color = parent->color; 224 parent = left_rotation(parent); 225 }else if (brother->right == NULL && brother->left != NULL){ 226 //1.2.1.1.2 兄弟节点是黑色,且有一个左节点，左节点必然是红色 227 brother->color = parent->color; 228 parent->right = brother->left; 229 230 brother->parent = brother->left; 231 232 brother->left->parent = parent; 233 brother->left->right = brother; 234 brother->left = NULL; 235 236 parent = left_rotation(parent); 237 }else if (brother->right != NULL && brother->left != NULL){ 238 //1.2.1.1.3 兄弟节点是黑色,且有俩节点，必然都是红色 239 brother->color = parent->color; 240 brother->right->color = 0; 241 parent->color = 0; 242 243 parent = left_rotation(parent); 244 }else{ 245 //1.2.1.1.4 兄弟节点是黑色,且没有节点 黑色路径必然要-1了 递归 246 parent->right->color = 1; 247 return rebalance3(parent->right,rootNode); 248 } 249 }else{ 250 //1.2.1.2兄弟节点是红色，父节点一定是黑色，它一定有俩黑色子节点 251 //兄弟节点置黑,兄弟左节点置红 252 brother->color = 0; 253 brother->left->color = 1; 254 parent = left_rotation(parent); 255 } 256 }else{ 257 //1.2.2被删除节点在父节点的右数上 258 free(root); 259 root = NULL; 260 parent->right = NULL;//删除自身 261 brother = parent->left; 262 //1.2.2.1 兄弟节点是黑色 263 if (brother->color == 0){ 264 //1.2.2.1.1 兄弟节点是黑色,且有一个左节点，左节点必然是红色 跟1.2.1.1.1是镜像关系 265 if (brother->right == NULL && brother->left != NULL){ 266 //把父亲颜色赋值给兄弟节点的左节点 267 brother->left->color = parent->color; 268 parent = right_rotation(parent); 269 270 }else if(brother->right != NULL && brother->left == NULL){ 271 //1.2.2.1.2 兄弟节点是黑色,且有一个右节点，右节点必然是红色 跟1.2.1.1.2是镜像关系 272 parent->left = brother->right; 273 brother->color = parent->color; 274 brother->parent = brother->right; 275 276 brother->right->parent = parent; 277 brother->right->left = brother; 278 brother->right = NULL; 279 parent = right_rotation(parent); 280 }else if(brother->right != NULL && brother->left != NULL){ 281 //1.2.2.1.3 兄弟节点是黑色,且有俩节点，必然都是红色 跟1.2.1.1.3是镜像关系 282 brother->left->color = 0; 283 brother->color = parent->color; 284 parent = right_rotation(parent); 285 }else{ 286 //1.2.2.1.4 兄弟节点是黑色,且没有节点 黑色路径必然要-1了 递归 287 parent->left->color = 1; 288 return rebalance3(parent->left,rootNode); 289 } 290 }else{ 291 //1.2.2.2兄弟节点是红色，父节点一定是黑色，它一定有俩黑色子节点 292 //兄弟节点置黑,兄弟右节点置红 293 brother->color = 0; 294 brother->right->color = 1; 295 parent = right_rotation(parent); 296 } 297 } 298 } 299 }else if (root->left != NULL && root->right == NULL){ 300 //2.只有左节点 该左节点必然是红色，那root一定是黑色,root值替换为左节点的值，删除左节点 301 root->data = root->left->data; 302 free(root->left); 303 root->left = NULL; 304 }else if (root->right != NULL && root->left == NULL){ 305 //3.只有右节点 该右节点必然是红色，那root一定是黑色,root值替换为右节点的值，删除右节点 306 root->data = root->right->data; 307 free(root->right); 308 root->right = NULL; 309 }else{ 310 //4.左右都有的情况，选取后继节点 311 RBTreeNode *min = FindMin(root->right); 312 root->data = min->data; 313 rootNode = Delete(min, min->data, rootNode); 314 } 315 } 316 317 return rootNode; 318 } 319 320 int main(){ 321 struct RBTreeNode *node = NULL; 322 node = inserRB(node, 8, NULL); 323 node = inserRB(node, 4, NULL); 324 node = inserRB(node, 12, NULL); 325 node = inserRB(node, 2, NULL); 326 node = inserRB(node, 1, NULL); 327 node = inserRB(node, 1, NULL); 328 while(1){ 329 char operation[10000]; 330 int data; 331 scanf("%s",operation); 332 if(strcmp(operation, "quit") == 0) 333 return 0; 334 else if(strcmp(operation, "foreach") == 0) 335 preOrderTraverse(node); 336 else if(strcmp(operation, "search") == 0){ 337 scanf("%d",&data); 338 search(node,data); 339 } 340 else if(strcmp(operation, "add") == 0){ 341 scanf("%d",&data); 342 node = inserRB(node, data, NULL); 343 } 344 else if(strcmp(operation, "del") == 0){ 345 scanf("%d",&data); 346 node = Delete(node, data, node); 347 }else{ 348 printf("你输入的格式有误，请重新输入。参考如下：\nadd 1\ndel 1\n foreach\nsearch 1\n quit\n"); 349 } 350 } 351 352 preOrderTraverse(node); 353 }
2022/3/4 美团 练习题
保留两位小数
1 #include<iostream> 2 #include<iomanip> 3 using namespace std; 4 int main() 5 { 6 double a=3.14159265358; 7 8 //加入setprecision(n) 设置浮点数有效数字 9 cout<<setprecision(3)<<a<<endl; //将精度改为3（即有效数字三位） 输出3.14 10 11 //加入setiosflags(ios::fixed) 设置浮点数以固定的小数位数显示 12 cout<<setiosflags(ios::fixed)<<setprecision(2)<<a<<endl; 13 //控制精度为小数位 setprecision(3)即保留小数点2位 输出3.14 14 cout<<a<<endl; //fixed和setprecision的作用还在，依然显示3.14 15 16 return 0; 17 }
2022/3/5 美团笔试
第一道很简单，sort排序完一个for就解决了
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int main(){ 5 int n; 6 cin>>n; 7 int a[n]; 8 int dp[n][2]={0}; 9 for(int i=0;i<n;i++){ 10 cin>>a[i]; 11 dp[i][1] = 1; 12 } 13 sort(a,a+n);//可打乱顺序的自己排序 14 dp[0][0] = a[0]; 15 for(int i=1;i<n;i++){ 16 if(a[i]-dp[i-1][0]>1){ 17 dp[i][0] = a[i]; 18 dp[i][1] = dp[i-1][1]+1; 19 }else{ 20 dp[i][0] = dp[i-1][0]; 21 dp[i][1] = dp[i-1][1]; 22 } 23 24 } 25 cout<<dp[n-1][1]<<endl; 26 return 0; 27 }
第二道最大子段和，可翻转部分子数组，负数情况没处理好，91%。
1 #include<iostream>//i之前顺序，i之后逆序可翻。取和 2 #include<algorithm> 3 #include<math.h> 4 using namespace std;//9 -2 1 -3 4 -1 2 1 -5 4 5 int main(){// 6 -1 3 -5 2 -1 3 6 int n; 7 cin>>n; 8 int a[n]; 9 for(int i=0;i<n;i++){ 10 cin>>a[i]; 11 } 12 int dp[n]={0}; 13 int sum = 0; 14 for(int i=0;i<n;i++){ 15 sum+=a[i]; 16 dp[i] = sum; 17 sum = max(sum,0); 18 } 19 for(int i=0;i<n;i++) 20 cout<<dp[i]<<" ";cout<<endl; 21 int rdp[n] = {0}; 22 int rsum = 0; 23 for(int i=n-1;i>=0;i--){ 24 rsum+=a[i]; 25 rdp[i] = rsum; 26 rsum = max(rsum,0); 27 } 28 for(int i=0;i<n;i++) 29 cout<<rdp[i]<<" ";cout<<endl; 30 for(int i=n-1;i>=0;i--){//右边翻转数组的数如果小于0就不要了 31 rdp[i] = max(rdp[i],0); 32 } 33 for(int i=n-2;i>=0;i--){ 34 rdp[i] = max(rdp[i],rdp[i+1]); 35 } 36 for(int i=0;i<n;i++) 37 cout<<rdp[i]<<" ";cout<<endl; 38 int result = a[0]; 39 for(int i=0;i<n-1;i++){ 40 result = max(result,dp[i]+rdp[i]); 41 } 42 cout<<result<<endl; 43 return 0; 44 }
第三道空间几何切豆腐
第四道区间操作题，原数组和任意排序，多次查询和增加区间内的值，查询到的结果求和，要求和最大
2022/3/7 同讯科技
说我红黑树写的还行，然后笔试
一、单选 1、以下不属于socket的类型的是（ D ） A 流式套接字 B 数据报套接字 C 网络套接字 D 原始套接字 2、如果进程A调用fork函数，创建进程B，然后进程B在调用fork函数，创建进程C，进程C调用exec执行新的程序，那么各个进程以什么顺序来执行：（ D ）。 A 以A、B、C的顺序执行 B 以C、B、A的顺序执行 C 以B、C、A的顺序执行 D 无固定执行顺序 3、内核的编译主要步骤不包括下面哪项( D ) A 内核配置 B 加载内核 C 建立内核 D 建立依存关系 4、以太头部大小 为（ ）byte，其实中目的MAC 的长度为（ ） byte.（ A ） A 14 6 B 16 6 C 24 6 D 14 8 5、数据库操作中，以下哪种操作能够实现实体完整性（D ） A 设置唯一键 B 设置外键 C 减少数据冗余 D 设置主键 6、下面的程序，在Ubuntu PC的terminal运行，打印几个hello_( A ) main(){ fork(); printf("hello\n"); fork(); printf("hello\n"); while(1); } A 6 B 4 C 2 D 8 7、下面这个程序，三次打印的data分别是（ C ）。 int data = 10; int child_process() { printf("Child process %d, data%d\n",getpid(),data); data = 30; printf("Child process %d, data%d\n",getpid(),data); _exit(0); } int main(int argc,char* argv[]){ if(vfork()==0) { child_process(); } else{ sleep(1); printf("Parent process %d,data %d\n",getpid(), data); } } A 10, 10,10 B 10, 30,30 C 10, 30,10 D 10, 10,30 8、MAC地址为01:80:C2:00:00:01, 该MAC地址类型为（ C ） A. 单播 B.组播 C.广播 D.任播 二、判断 1、可以使用signal()来给同一进程组中的所有进程发送信号。（对 ） 2、从一个空FIFO中读取数据时会发生阻塞，但从一个空PIPE中读取数据时不会发生阻塞。（ 错） 3、路由器负责转发分组，但不知道转发的是UDP报文还是TCP报文。( 错 ) 4、同一台机器上分别使用UDP和TCP通信的两个进程不能分配数值相同的端口号。（对 ） 5、在流式套接字编程中，客户端建立连接用的套接字不必调用bind()函数绑定本地IP地址和端口号，系统会自动为其分配。（ 错 ） 6、用于接收广播数据时，数据报套接字可不必绑定本地地址。（ 错 ） 三、填空题 1、标准以太网MTU 大小为（ 1500 ）。 2、你家的路由器如果是PPPoe拨号接入运营商，路由器上的MTU应该设置为（ 1500 ）。 3、最大VLAN ID 是（ 255.255.255.255 ）。 4、交换机端口 （port link-type） 常用的两种类型是（ trunk ） 和 （ access ）。 四、简答 1、某人想要访问淘宝,他在其浏览器中输入http://www.taobao.com并按回车，直到进入淘宝首页，问：在此过程中，按照TCP/IP参考模型，从应用层到网络层都用到了哪些协议？这些协议在这里的任务是什么？ DNS协议，解析url地址得到IP地址， TCP/IP协议，三次握手建立连接， Http协议，发送超文本格式数据 五、编程设计（头文件可忽略） 1、编写一个TCP并发服务器端程序，可以把客户端发来的消息回射给客户端。 Socket sk = new Socket(); sk.bind(IPAddress,port); Listen(sk); While(1){ accept(sk); Recv(sk）； Send(sk,”hello”); Close(sk); }
计网考的多，稀里糊涂的哈哈。应该是红黑树看代码能力，然后接下来笔试看计算机基础。