进一步改进动态规化的空间复杂度
昨天发了这个帖子讲到动态规化的2种改进, 一种是记忆, 另一种是把递归改成迭代. 今天稍微想了一下, 还可以从空间复杂度里入手. 我们先看一下之前的’最优’方案: function f($x, $y) { $ans = array(); for ($i = 0; $i <= $x; ++ $i) $ans = 1; for ($i = 0; …
从A到B再到C有多少种方法?
有这么一题, 一个人从A到C, 一定要经过B, 并且每次走一步向东或者向北, 不能回头, 问一共有多少不同的方法. 暴力搜索(穷举) 理论上说, 你可以用暴力列举所有从A到C的走法 然后再一一比较是否经过B, 不过这种方法很低效因为需要列举出所有走法. 如果水平有X步垂直有Y步那么一共的方案有: or 可以这么理解, 一共有 x+y 步 选其中 x 或者 y 步来往东或者往北走. 纯数学方法: 排列组合 细想一下, 我们只要分两个阶段即可: 第一个阶段计算由A到B的方法数, 第二个阶段计算由B到C的方法数, 然后这么一乘就是最后的方案数了. …
软件工程师面试技巧之: 动态规划/整数拆分
动态规化 (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>>& …
小白教程: 怎么领取 BCC (Bitcoin Cash) ?
这个月初比特币(8月1日)的硬分叉 (Hard Fork) 是互联网加密货币的一大新闻, 像我这等小白, 只关心钱包里的钱是否增值. 计算机中的 fork 意思就是进程自我复制一份 除了进程 pid 不一样, 执行的代码都一样, 这次比特币 (代码BTC) 进行了 fork 操作, 分出一孩子 也就是 BCC (Bitcoin Cash). 那么我用以下在LINUX下的C程序来演示一下这过程. #include <stdio.h> #include <unistd.h> #include …
去年 Google 的面试题: 打印消息
去年我参加了 Google 的初面(电话面试), 可惜没有通过. Google 瑞士的一个软件工程师打电话面试, 电话面试就考了一道算法题, 虽然我也准备了近一个月的时间, 但是我回答的并不完美. 虽然和我联系的Google 是在伦敦, 但是面试的时候手机上显示的是 +41 电话 来自 Google 瑞士, 整个面试大约45分钟. 题目是: 给了一些消息 和对应的日期和时间, 如果消息并不在最近10秒钟内打印过 那么就打印. 同时有可能多条消息到达(1秒之内). 就这么一个题目并没有指定接口, 而我们也不需要把所有消息都保存起来, 并且我们知道 这个 打印函数可能一秒内被调用多次: …