C++ 刷题坑: 二分查找也没有那么容易写出来
最近在刷题, 刷了一道比较简单的二分搜索, 但是却让我刷了好几次才过(果真是很久没刷 能力立马下降许多) 题意就是 不允许使用 sqrt 或者 pow 之类的函数来判断一个整数是否是平方数. 比如 4, 16, 64, 25 就是平方数而 3, 7, 11 不是. 很容易想到可以用二分搜索来解决, 算法复杂度是 O(log n), 答案如下: typedef unsigned long long …
Tag: C#
ACM 解题报告 – O(n)找多数算法
给定一些整数, 请找出它们中的的”多数”. 一个数字如果超过了一半, 那么它就是多数. 假定这样的数是存在的. 比如, 给定 , 您的算法将给出 答案 1 因为1出现了4次超过了一半(3.5次) 最直接的算法就是通过 字典(或者HASHMAP)记录每个出现数字的次数, 然后只要判断其中一个出现超过一半了, 就返回它. class Solution { public: /* * @param nums: a list of integers * …
ACM题解系列之 – 最小堆栈 (Min Stack)
没事刷刷题能防止老年痴呆, 而且也能让你随时处于最佳状态, 随时都可以炒老板鱿鱼另谋高就. 题目: 设计一个堆栈(Stack)使 push, pop, 和取最小 min 操作时间复杂度都是 O(1). 这题的难点就是在于怎么样用O(1)常数时间复杂度来取得堆栈里的最小值. class MinStack { public: MinStack() { // write your code here } /* * @param number: An …
代码审核之 重新造轮子
今天在看代码修改记录的时候发现有这么一处改动, 虽然这个改动已经很久了,但是我觉得有必要拿出来大家讨论一下: 2007年 .NET 3.5 之后推出LINQ,其实整个函数只是在做一件事,就是返回类成员 layoutList 中是 LayoutDevice (后面改成LayoutAnt )的列表.但实际上这通过 C#的LINQ只需要用 OfType<LayOutDevice> 或者 OfType<LayOutAnt> 即可(暂且不说改动包括重构类型) 左边的版本实际上是OK的,这就是学校的标教科书版本,无可厚非,但右边的这个版本就大有问题,因为参数含有引用 ref, 也就是说每次都把外面传进的变量给清空了,这种函数拿来单元测试并不友好. 如果一定要重新造轮子,两个版本都有小问题,一个是 private 方法不好单元测试,另一个是都使用了成员变量 layoutList, 最好是改成 public static 公有静态方法,传入 layoutList, 然后像第一种方式返回新的List.这样的话,这个公有静态方法就是不会更改 …
C++ 使用 Parallel For 多线程 计算 圆周率 – Monte Carlo
计算圆周率是个老掉牙的课题. 最为简单的 直接易懂的无非就是通过 Monte Carlo 来随机撒点 然后 计算 在圆内的点和总共的点数的比例再乘于4就能得到一个估计的值. 当然随机数的产生一定要质量好 虽然计算机没有真正的随机算法 但是一些 伪随机 算法 比如 xorshift 就很不错. 单机版本的计算 简单明了. int monte_carlo_count_pi(int n) { int c = 0; for (int …
.NET 程序的保护 – 混淆
几乎所有软件程序都能被破解, 只是时间长短的问题, 国外有一个有名的组织是 ZeroDay 意思就是不用一天就可以破解任何软件. 有两种桌面程序,最常见的就是用 C++/Delphi 编写的 原生 native 代码,这样写出来的软件是不容易看到源代码的,因为编译器做了优化和处理.这样的代码的优点是执行速度快,效率高, 但是关键部分的代码,比如 License 验证,有经验的黑客还是很容易破解的. 俄罗斯有一个很有名的商业软件 VMProtect, 用于保护 native 代码,保护强度非常不错, 加壳,压缩,虚拟指令,防虚拟器,防调试程序等功能,保护出来的文件有时候会被一些杀毒软件认为是恶意的程序.因为用到了一些特殊指令,而杀毒软件无法分析.这种情况下可以通过联系杀毒软件公司将程序加入白名单里. .NET 程序是另一大类别.有点和 Java 类似, .NET 程序编译出来不是 本地代码 (Native),而是中间代码(类似JAVA的 ByteCode). …
.NET 4.0 (4.5) 之后强大的平行 For, ForEach 语句用于多线程执行
.NET 4.0 之后 (e.g. 4.5) 添加了并行 For, ForEach 的支持.如果你的代码里有很多处 SIMD (单指令,多数据 Single Instruction Multiple Data). 就可以通过 Parallel.For 和 Parallel.ForEach 来进行多线程.使用方法非常简单:你不需要再手动创建几个线程,然后同时启动多线程,并等待它们的执行(同步). 首先,你需要引用这两个单元. using System.Threading; using System.Threading.Tasks; 为了演示方便,建立了一个长度为10的数组,元素是 Double 类型. double …