Marlin's Blog

「编译当下,重构未来」

二叉树高频题目

题目一:BFS的两种方式 二叉树的层序遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ans;...

归并排序

归并排序 左部分排好序、右部分排好序,利用merge过程让左右整体有序 merge过程:谁小拷贝谁,直到左右两部分所有的数字耗尽 递归实现和非递归实现 时间复杂度O(n * log n) 需要辅助数组,所以额外空间复杂度O(n) 归并排序为什么比O(n^2)的排序快?因为比较行为没有浪费! 利用归并排序的便利性可以解决很多问题 - 归并分治 注意: ...

归并分治

归并分治的原理与补充说明 原理 思考一个大问题的答案是否等于小问题的答案之和: 将一个大问题分解为若干个小问题,分别求解这些小问题的答案。 如果左右两部分的答案是有序的,并且跨越左右产生的答案可以高效计算,那么整个问题可以通过归并的方式解决。 计算“跨越左右产生的答案”: 如果加上左、右各自有序这个设定,会获...

异或运算的骚操作

异或

异或运算的骚操作 问题描述 先来个好玩的问题: 袋子里有 ( a ) 个白球、( b ) 个黑球。每次从袋子里拿出 2 个球,每个球被拿出的概率均等。如果拿出的是 2 个白球或 2 个黑球,那么就往袋子里重新放入 1 个白球;如果拿出的是 1 个白球和 1 个黑球,那么就往袋子里重新放入 1 个黑球。 那么最终袋子里一定会只剩 1 个球,请问最终的球是黑球的概率是多少?用 ( a ) 和 ...

二叉树

二叉树的遍历 前序遍历 访问根节点 前序遍历左子树 前序遍历右子树 (根左右) 1 2 3 4 5 6 7 8 void preorder(TreeNode* root) { if(root == NULL){ return; } cout << root->val << endl; // 根 preorder(roo...

对拍-验证的重要手段

对拍的C++代码实现

前言 在算法竞赛和编程中,对拍(Diff Testing)是一种高效验证代码正确性的方法。它通过对比暴力解法(Brute Force)和优化解法(Optimized Solution)的输出,快速发现逻辑错误。本文将提供完整的C++对拍代码,并逐步讲解其实现原理,帮助你轻松应用到自己的项目中。 对拍的实现 你想要测的方法a 实现复杂度不好但是正确的暴力解法b 实现一个随机样本...

二进制与位运算

位运算

本文只记录了位运算部分。 进制 0x指的是十六进制的前缀 0b指的是二进制的前缀 0指的是八进制的前缀 example: 0x12 == 0b00010010 == 022 == 18 位运算 位运算符: & 按位与运算符,两个位都为1时,结果才为1,否则为0. exp: 0b1010 & 0b1100 == 0b1000 | 按位或运算符,两个位中只要...

入门SQL

SQL-从入门到放弃

什么是数据库(database)? 能存放数据的地方就是数据库. 什么是数据库管理系统(DBMS)? 管理数据库的软件,例如MySQL, SQL Server等. 数据库的分类 关系型数据库(SQL) MySQL Oracle SQL Server PostgreSQL 非关系式数据库(NoSQL) ...

蓝桥杯弱省B组保奖攻略

'菜鸡的自我修养'

本篇攻略面向的对象为 只有语言基础,在竞赛弱省 且 院校普通的同学。 一位菜鸡的蓝桥杯弱省B组保奖攻略 1. 前言 为了不让大家的300块钱打水漂,我写下这一篇保奖攻略。 作者在第十五届蓝桥杯“荣获”陕西省B组省级三等奖,根据自己的经验来看,弱省B组获得省三并不难。 说说我获得省三时具有的知识: c语言基础 数据结构基础 双指针法 大致知道有什么算法 …… 没了? 没了。 ...

四级挂后有感

成绩分析与反思

四级挂了 属实正常。 应该说,没挂才奇怪。 大学以来,基本上没有学过英语,每次说要开始背单词,其实也就坚持个几天后便放弃了。 1月3日后再也没背过单词,日程里面已经欠下了151条背单词代办。 每次考前老师划下重点,随大流跟着同学背一背,就能算得上我为数不多的几次认真学习英语…… 之前虽说略有药丸的感觉,但还心存侥幸。 现实是残酷的,不会给妄想不劳而获的人好结果。 该挂的挂已经挂了,再后悔...