Skip to content
Ider

沉淀我所学习,累积我所见闻,分享我所体验

Primary Navigation Menu
Menu
  • Home
  • About Ider
    • Who Ider?
    • Why Ider?
    • How Ider?
    • Where Ider?
    • What Ider?

Algorithm Analysis(算法分析)

2015-12-28
28 December
On December 28, 2015
In Algorithm Analysis(算法分析), Knowledge Base(心得笔库), Programming Life(程序人生)

聊聊刷题

在之前的《谈谈面试》中我讲述了我在面试上的经历和看法,而对于软件行业的面试很多都要求被面试者解决一些编程上的问题。这类面试有很多名字:算法题(Algorithm Question)、编程题(Programming Problem)、考代码(Coding Interview)等等,但基本形式都是:给出一道问题的描述和目的,要求写出程序能够接受相应的参数然后完成目标需求最终得到结果。

大部分常见的这类面试问题都被大家总结在了网上,可以直接搜索找到,或者在一些论坛的特定板块(比如未名空间的待字闺中,一亩三分地的面经)里见到讨论,甚至形成了在线测试网站(比如LeetCode、LintCode)直接验证程序的正确性。

由于面试题目的公开性,造就了软件行业特殊的面试准备过程:刷题。很多朋友也会问我:“出去面试还刷题吗?”准确地讲,我刷过算法题目,也经常后悔没有早在还在学校里时就开始刷题,那样就能更早地进入心仪的公司。但现在出去面试前基本都还是忙着正常的工作,不会专门去练习题目。

刷题的目是理解算法和数据结构

好比读书的时候每次老师教授了新的知识后都会布置习题,完成那些作业可能会让我们在考试中碰到原题而拿到高分,但正真的作用是帮助我们理解和消化所学的知识。从简单的理解:“程序=算法+数据结构”,要写好程序就必须去熟悉算法和数据结构,刷题就应该是完成这样的作用。如果题目做不出来,就说明连最基本写程序的能力都没有,自然很难得到公司的青睐。

我常常幻想如果我高考没有失常,能进入更好的学校学习计算机知识,甚至参加ACM小组,得到老师在算法上更好的点拨指导,也因为要参加计算机竞赛,我也会练习更多的题目,现在就不需要刷题了。但现实是在我就读的大学里,算法只是一门选修课,我也没有参加过任何计算机竞赛。但联想高中数学竞赛的培训过程,老师肯定会分类进行知识传授和练习。所以刷题也一样要分类进行强化训练。

LeetCode虽然是最火的题库,但是在我刷题的时候它只是简单的罗列一百多道题目(可参看我的不完全题解列表),所以当时我更倾向去做UVa上的题目。那上边有上千道题目,肯定是不可能做完的,但是有比较好的分类专区,可以专门的加强某一特定算法和数据结构的基础知识。

一开始我连最简单的二分查找(Binary Search)算法都写不好,但是在反复练习之后,我也能总结出二分法的实现,并汇总一些变形题目到博客里。刚毕业那会找工作,好多次面试都挂在了二叉树(Binary Tree)上,后来做遍各类遍历算法,总结了不同的实现方式,就不再担心关于树的操作。动态规划(Dynamic Programming)在我看来是面试时会碰到最难的问题,后来我发现这类问题的关键在于找到类似于数学中的“递归公式”,这样就可以找到递归的实现,之后利用空间来存放中间值来减少时间复杂度。
Read More →

2015-01-30
30 January
On January 30, 2015
In Algorithm Analysis(算法分析), Data Structures(数据结构), Design Patterns(设计模式), Knowledge Base(心得笔库)

树结构遍历的实现汇总

在计算机数据结构中,树(Tree)结构是基础的结构之一,对于其定义、实现以及相关算法在一般的算法与数据结构书中都有详细介绍和分析。不过本文还是想要罗列一下树结构基本的遍历算法,同时简单随机介绍各种遍历算法的使用情境。

本文中将会实现树遍历主要两种方式:深度优先和广度优先。对于深度优先也会包括其三种不同方式:前序遍历、中序遍历、后续遍历。同时对于深度优先的三种方式还会包括最简单直观的递归实现,和相对复杂的迭代实现。

为方便起见文中的算法将基于二叉树(Binary Tree)结构,其树节点的结构也简单定义如下:

[codesyntax lang=”cpp” lines=”normal”]

using namespace std;
class Node {
public:
    Node *left;
    Node *right;
    int value;
};

[/codesyntax]

深度优先遍历

深度优先遍历隐藏着回溯法(Backtracking)应用,因此利用递归自动创建堆栈(stack)的性质,就可以非常好的实现这些遍历算法。虽然递归可以通过创建自定义的栈对象来变成迭代,但对于进栈出栈的控制,三种遍历方式有着不同的条件,因而实现反而变得复杂。

递归实现

对于节点的访问操作,定义了如下的方法,其实只是简单的输出节点的值再以空格分隔。对于空节点也将预留输出特别的符号来指示。

[codesyntax lang=”cpp” lines=”normal”]

#define NULL_NODE "#"

void operate(Node *node) {
    if (node == NULL) {
//        cout << (NULL_NODE" ");
    } else {
        cout << node->value << " ";
    }
}

[/codesyntax]

三种深度优先遍历的算法实现如下

[codesyntax lang=”cpp” lines=”normal”]

void preorder(Node *node) {
    if (node == NULL) {
        operate(NULL);
        return;
    }
    
    // operate node before any children
    operate(node);
    preorder(node->left);
    preorder(node->right);
}

void inorder(Node *node) {
    if (node == NULL) {
        operate(NULL);
        return;
    }
    
    inorder(node->left);
    // operate node in the middle of children
    operate(node);
    inorder(node->right);
}

void postorder(Node *node) {
    if (node == NULL) {
        operate(NULL);
        return;
    }
    
    postorder(node->left);
    postorder(node->right);
    // operate node after all child
    operate(node);
}

[/codesyntax]
Read More →

2013-12-26
26 December
On December 26, 2013
In Algorithm Analysis(算法分析), Data Structures(数据结构), Knowledge Base(心得笔库), Language Tips(语言初试), Special Tricks(奇技妙招)

bash中使用printf实现进制转换

最近工作中常涉及到编码转换的问题,比如发送URL的时候需要进行urlencode,上传内容的时候要对MD5进行BASE64的转换。当debug的只能看到8或者16进制的编码而想不到实际的字符是什么,就让人非常烦躁,所以总想有个什么快速的方式能帮助自己进行编码转换 。

最快的方式,应该就像小时候被乘法口诀表一样把他们的对应关系一一记住,但是可能年龄大了记住了东西,外加现在越来越依赖技术带来的便利所以总是不能也不愿意记这些进制关系,一碰到这些问题就Google搜索一下。但这显然这是很 浪费时间的。

如果是用Linux或者Mac系统,用Terminal的话就能带来很多的帮助,比如man ascii就会显出中ASCII在8、10和16进制下所有编码值了。这样子看到一个8或16进制的数,也能很快的找到对应的字符是什么了。不过这还是不过快,毕竟人眼查这样一张有序的表并不会进行二分查找。而且我们希望是能够在O(1)时间复杂度就能得到结果方法。

本文就总结怎么用printf的格式化在Bash环境中实现进制的转换,如果有那个比较好用或常用的,就可以添加到profile中在启动时载入使用。
Read More →

2013-07-18
18 July
On July 18, 2013
In Algorithm Analysis(算法分析), Data Structures(数据结构), Knowledge Base(心得笔库)

从优化到再优化,最长公共子串

最长公共子串(Longest Common Substring)是一个非常经典的面试题目,在实际的程序中也有很高的实用价值,所以把该问题的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已,关键还是享受把学习算法一步步的优化,让时间和空间复杂度一步步的减少的惊喜。

概览

最长公共子串问题的基本表述为:

给定两个字符串,求出它们之间最长的相同子字符串的长度。

最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同,然后取得相同最长的那个。对于一个长度为n的字符串,它有n(n+1)/2 个非空子串。所以假如两个字符串的长度同为n,通过比较各个子串其算法复杂度大致为O(n4)。这还没有考虑字符串比较所需的时间。简单想想其实并不需要取出所有的子串,而只要考虑每个子串的开始位置就可以,这样可以把复杂度减到O(n3)。

但这个问题最好的解决办法是动态规划法,在后边会更加详细介绍这个问题使用动态规划法的契机:有重叠的子问题。进而可以通过空间换时间,让复杂度优化到O(n2),代价是空间复杂度从O(1)一下子提到了O(n2)。

从时间复杂度的角度讲,对于最长公共子串问题,O(n2)已经是目前我所知最优的了,也是面试时所期望达到的。但是对于空间复杂度O(n2)并不算什么,毕竟算法上时间比空间更重要,但是如果可以省下一些空间那这个算法就会变得更加美好。所以进一步的可以把空间复杂度减少到O(n),这是相当美好了。但有一天无意间让我发现了一个算法可以让该问题的空间复杂度减少回原来的O(1),而时间上如果幸运还可以等于O(n)。
Read More →

2013-05-21
21 May
On May 21, 2013
In Algorithm Analysis(算法分析), Front Interface(界面构想), Knowledge Base(心得笔库), Mathematical Theory(数学理论)

连续平滑的贝塞尔曲线

在我研究生的时候,我上了一门OpenGL的课程。我非常喜欢OpenGL,因为它让我写的程序从此不再只局限于黑白的终端界面,而变得艳丽多彩。从那么课上,我也第一次认识了“贝塞尔曲线Bézier Curve”,它是那么的神奇,仅仅用几个点通过一个公式就能表现出一条优美的曲线。

这让一直热爱数学的我无法自拔,仿佛又回到了高中,坐在课堂里听着彪哥(我的高中数学老师)给我们讲述着各种曲线方程:抛物线、椭圆、双曲线……可惜怎么就从来没有提到过贝塞尔曲线呢。好吧,不在高考考纲之中。

贝塞尔方程的优点在于可以利用较少的存储几个点就能描绘出光滑的曲线或者曲面。而方程的计算也不会消耗太多的时间,真可谓是图形学中的一把利器。虽然后来并没有继续学习和使用OpenGL,但是也在其它很多方面又再次接触到了贝塞尔曲线,比如CSS中的一些渐变方法(Timing Function),iOS动画的时间方程。
Read More →

2013-04-23
23 April
On April 23, 2013
In Algorithm Analysis(算法分析), Data Structures(数据结构), Mathematical Theory(数学理论), Special Tricks(奇技妙招)

寻找比特位

人类有十个手指,所以我们的算数都是10 进制的,而计算机的世界里,所有事物都只由0和1呈现出来,所以数字也只能用2进制表示。因为2进制的表示方式,在计算机里对于数字的运算,除了现实中常用的“加减乘除”,更多了“与非或”这些位运算。

在进行数学运算的过程中,我们经常会总结出一些技巧方法,而这些方法其实跟进制有很大的关系。比如小学老师就告诉我们:检查一个整数能否被3整除,只要派定各个数位上的数字加起来是否能被3;判定一个整数是否能被5整除,只要看最后一位是不是0或5。而这些规律却不能适用到2进制表示的数字上。

不过利用2进制的特殊性,我们也能从位运算上找到很多的技巧。比如一个常见的面试问题:

有一组数包含了1到100的整数,且每个整数只出现一次且随机出现于数组中,现在有一个数被从中删除,请找出被删除的数。

Read More →

2012-09-08
08 September
On September 8, 2012
In Algorithm Analysis(算法分析), Knowledge Base(心得笔库)

二分查找法的实现和应用(进阶篇)

在《二分查找法的实现和应用汇总》中,我介绍了二分查找法的基本应用,不过在面试的准备过程中,我还碰到了更多对于二分查找法的更进一步的使用。其实在《二分查找法的实现和应用汇总》的最后,我已经介绍了一个非常规的使用,也就是基于“轮转后的有序数组(Rotated Sorted Array)”检查某一个数是否存在。

在此篇文章中,我将进一步介绍更多我碰到的一些二分查找法的应用。
Read More →

2012-05-03
03 May
On May 3, 2012
In Algorithm Analysis(算法分析), Data Structures(数据结构), Knowledge Base(心得笔库), Language Tips(语言初试)

画虎画皮难画骨,编程编码难编译

古语“画虎画皮难画骨”,是说画老虎时要画它的外表很容易,可要将老虎的气势画出来却很难。

对于现在的程序员来说,似乎也是这样子,可以写出整洁的代码,设计出优异的程序,但却不一定需要知道代码在编译之后的是如何运行的。

但是有时候,能了解表面背后的故事,知道一些程序编译过程,其实对写出一个正确的正确的程序会有很大的帮助,这起源自一段很简单的问题实现:两整数交换。
Read More →

2012-04-13
13 April
On April 13, 2012
In Algorithm Analysis(算法分析), English Posts(英文写作), Knowledge Base(心得笔库), Mathematical Theory(数学理论)

String Redution问题的分析

这是一道关于字符串的操作的问题,一开始思考的时候,感觉需要取出各种不同的子序列,如果是这样时间复杂度就会变成指数级别。不过在朋友的指示下,发现其实它是有规律可寻的,最后的算法时间负责度只要O(n),而且代码极其简单。

虽然朋友是直接告诉了我其中的规律,但是我还是花了点时间思考和证明了一下,才放心的写下了代码。现在把它总结在这里。

整个问题的证明基本是使用数学归纳法,以及奇数和偶数的一些性质。感叹数学的世界真奇妙。也庆幸自己一直以来我十分喜欢数学。其实计算机的世界本来就是建立在各种数学理论之上,比如离散数学,模糊数学,逻辑数学。但是计算机又让数学的应该变得更加的广阔。

(你可以在看完题之后直接跳到红色的部分看这个问题的结论。)
Read More →

2012-04-01
01 April
On April 1, 2012
In Algorithm Analysis(算法分析), Knowledge Base(心得笔库)

二分查找法的实现和应用汇总

在学习算法的过程中,我们除了要了解某个算法的基本原理、实现方式,更重要的一个环节是利用big-O理论来分析算法的复杂度。在时间复杂度和空间复杂度之间,我们又会更注重时间复杂度。

时间复杂度按优劣排差不多集中在:

O(1), O(log n), O(n), O(n log n), O(n2), O(nk), O(2n)

到目前位置,似乎我学到的算法中,时间复杂度是O(log n),好像就数二分查找法,其他的诸如排序算法都是 O(n log n)或者O(n2)。但是也正是因为有二分的 O(log n), 才让很多 O(n2)缩减到只要O(n log n)。
Read More →

Posts pagination

1 2 Next
Facebook
Twitter
LinkedIn
RSS
ZhiHu

Recent Posts

  • 三年居家工作感受
  • Pixel Watch智能手表和Pixel 5, 6 Pro 及 7 Pro手机
  • 我拥有过的无线耳机
  • 毕业工作一个月,我差点被开除
  • 我拥有过的移动硬盘
  • ProtoBuf 2.0 method count optimization for android development
  • 面过100场行为面试后

Categories

  • Algorithm Analysis(算法分析)
  • Article Collection(聚宝收藏)
  • Data Structures(数据结构)
  • Design Patterns(设计模式)
  • English Posts(英文写作)
  • Front Interface(界面构想)
  • IT Products(数码产品)
  • Knowledge Base(心得笔库)
  • Language Tips(语言初试)
  • Mathematical Theory(数学理论)
  • Mobile Development(移动开发)
  • Programming Life(程序人生)
  • Reading Notes(阅而后知)
  • Software Engineering(软件工程)
  • Special Tricks(奇技妙招)
  • Tangential Speech(漫话杂谈)

Tags

Aero Android API Bash Binary Search Bitwise Operation Book C/C++ Career Chrome Conference CSS Debug Device DOM Extension Framework Game Gradle Hearthstone HTML Initialization Intellij Interview iOS Java JavaScript jQuery Keyword Language Issues Mac Microsoft Mobile Modifier Objective-C PHP Principle Reference Regular Expression Static String Tools Tutorial UI XML

Blogroll

  • Ahmed's Blog
  • Gert Lombard's Blog
  • Gordon Luk
  • Jack & Allison
  • 开发部落

Archives

Designed using Chromatic. Powered by WordPress.