Category: 学习笔记

动态规化 (Dynamic Programming) 是个计算机领域里很重要的算法,我在高中参加过三次信息学奥林匹克竞赛 (ACM),每年必有一题用动归(DP)来解答. 动态规化其实就是 把问题分解成子问题+记忆子问题求解的一个过程. 你如何教你的孩子DP是什么呢? 比如:你给你的孩子5根火柴,你的孩子数了数然后说有5根.然后你再给你的孩子1根火柴然后问一共有多少根,这时候你的孩子会马上说出6根,因为他知道已经有5根了,再加上1根就是6根. 原理就是:把问题分析成更小的问题,并分而求之,子问题的解会被保存下来这样在求解更大的问题的时候就不需要再重新把中间结果再算一遍了. 动态规化的解法经常是较优的一种解法,我们来看这么一道面试题: 给定一个正整数,将它拆分成至少两个正整数,求出这些正整数的最大乘积.比如 整数2,可以拆分成1+1, 乘积是1,当输入是10,需要分解成3+3+4,这样所得的最大乘积是36. 你会怎么解?暴力搜索?这种解法不好写,而且时间复杂度也大.可以用回溯+剪枝,但时间复杂度也相对较大,特别是当N较大的时候也会时间太久Time Exceeded. 动规解答这题就较为简单.这题并没有让你详细写出怎么拆分的方案,只需要解出最大的乘积即可.所以我们有以下的方案: f(n) = max(f(n), max(i – j, f(i – j)) * j)) for …

前不久写的这个 软件工程师面试技巧 的系列, 朋友很喜欢, 所以我打算把我毕生所学(哈哈)整理整理分享于大家,望喜欢.另:我觉得:分享就是一种再学习的过程. 去年 Google 的面试题 – 打印消息 软件工程师面试技巧之 使用哈希表降复杂度 给定一个数独,我们要检查是否有效.一个有效的数独横的竖的都只出现1-9的数字各一次,并且9个小宫格里的数字也只出现1-9各一次. 你能快速的告诉我以下是否是个有效的数独么? 我们只需要检查给定的数独中已经填好的数字.最好的方法就是通过 C++中 STL 的 unordered_set (未排序的集合) 来保存已经出的数字.记得检查下一个9宫格或者行或列的时候清空集合便可. // https://justyy.com/archive/4998 class Solution { public: bool isValidSudoku(vector<vector<char>>& …

去年我参加了 Google 的初面(电话面试), 可惜没有通过. Google 瑞士的一个软件工程师打电话面试, 电话面试就考了一道算法题, 虽然我也准备了近一个月的时间, 但是我回答的并不完美. 虽然和我联系的Google 是在伦敦, 但是面试的时候手机上显示的是 +41 电话 来自 Google 瑞士, 整个面试大约45分钟. 题目是: 给了一些消息 和对应的日期和时间, 如果消息并不在最近10秒钟内打印过 那么就打印. 同时有可能多条消息到达(1秒之内). 就这么一个题目并没有指定接口, 而我们也不需要把所有消息都保存起来, 并且我们知道 这个 打印函数可能一秒内被调用多次: …

最近在刷题, 倒不是为了找工作, 主要是为了练练脑子, 日子过得太舒服, 人脑不动容易变笨. 程序员应该都了解并能熟悉使用 Hash 哈希表, 哈希表的插入和查找时间复杂度是O(1), 空间复杂度是O(N). 我们来看一道简单的面试题: 给定一个数组,找出相差为2的数对,比如: {1, 3, 5, 6, 9} 输出为: (1, 3), (3, 5) 拿到这题的时候 第一感觉是 暴力是否可行? 暴力搜索 复杂度为 O(N2), 大概代码如下: …

Adsense 真是矫情 又给我发警告说哪些文章上不能放广告 因为违反了条例. 目测是机器人抽查, 因为我收到过一次或二次误判, 但是也无法主动联系谷歌 只能登陆Adsense然后选择 解决了问题并给出解决问题的办法: 修改文章, 去掉广告. 这一次的问题只在 这个页面 上, 说是不能在 以下主题相关的帖子上放广告, 因为不是 Family-safe. 以下内容都不被允许放广告, 即使打打擦边球都很有可能被机器人抓到. 一些Adsense广告禁止的博文内容 关于性表现的提示或建议 一些性健康问题的治疗 与怀孕,分娩或计划生育有关的一些性健康建议 关于性传播疾病的讨论 好吧, 我又不想删掉那篇文章, 只能选择不在那篇文章上显示Adsense广告了. 去掉文章前后或者文章中间的广告 …

从PHP5升级到PHP7之后 就在想 为啥没有PHP6? 2004年第一个PHP5.0大版本更新, 然后11年后(2015年12月3日)直接从5跳到了7. 版本6被抛弃了.. 原因有: (1) 性能太差 (2) 项目延时太久 不过一些好的代码还是移回到了 PHP5.3 和 PHP5.4 现在 PHP5.6 和 PHP 7.0 是稳定的版本. 几个性能比较 除了之前的这个帖子大概能看出PHP7是PHP5的好几倍速度, 以下几个是摘抄于这篇帖子. 一些商务网站 能接受的请求数翻了一倍, 速度快 内存用量更少, 可支持的请求数更高了, …

单反照片拍模糊的原因可能包括以下几种：首先是对焦问题，比如对焦点没有对准主体或使用了错误的对焦模式。其次是快门速度太慢，导致拍摄时手抖或被拍摄对象移动，出现运动模糊。此外，镜头或者传感器可能有污渍，影响画质。最后，如果光圈过大（如F1.4、F1.8），景深太浅也可能导致部分画面失焦。解决这些问题，可以检查对焦设置，合理调整快门速度、光圈大小，并保持镜头和相机的清洁。 经常单反照出来的照片是糊的, 还好现在电子技术很强大 可以照很多张 糊的就删掉就可以, 不会增加照片处理的成本 (不用洗出来 再挑). 一般来说 单反照出来糊的有几个原因: 快门速度过慢 slow shutter speed 单反的安全速度是焦距的倒数, 如果使用50mm镜头, 快门速度就不得低于1/50秒, 同样在使用80mm镜头时速度不得低于1/80秒, 否则照片就有可能糊. 光线太暗 光线太暗如果快门太快照片就会糊, 所以在光线暗的情况下可以通过 感光度ISO 或者延长快门时间来补偿光线. 焦点不在拍摄物体或人身上 poor focus 单反得自己对焦, 特别是在大光圈的情况下 …