把《编程珠玑》读薄

Posted on 2015-02-26 | In 刷题 |

出处：http://hawstein.com/posts/make-thiner-programming-pearls.html

开篇

具体化你的解决的问题。下面是A和B的对话。

A：我该如何对磁盘文件进行排序？
B：需要排序的内容是什么？文件中有多少条记录？每个记录的格式是什么？
A：该文件包含至多10,000,000个记录，每条记录都是一个7位整数。
B：如果文件那么小，为什么要使用磁盘排序呢？为什么不在主存中对它排序？
A：该功能是某大型系统中的一部分，大概只能提供1MB主存给它。
B：你能将记录方面的内容说得更详细一些吗？
A：每个记录是一个7位正整数，没有其它的关联数据，每个整数至多只能出现一次。
... ...

经过一系统的问题，我们可以将一个定义模糊不清的问题变得具体而清晰：

输入：
所输入的是一个文件，至多包含n个正整数，每个正整数都要小于n，这里n=10^7。
如果输入时某一个整数出现了两次，就会产生一个致命的错误。
这些整数与其它任何数据都不关联。
输出：
以增序形式输出经过排序的整数列表。
约束：
大概有1MB的可用主存，但可用磁盘空间充足。运行时间至多允许几分钟，
10秒钟是最适宜的运行时间。

如果主存容量不是严苛地限制在1MB，比如说可以是1MB多，或是1~2MB之间，
那么我们就可以一次性将所有数据都加载到主存中，用Bitmap来做。
10,000,000个数就需要10,000,000位，也就是10,000,000b = 1.25MB。

程序可分为三个部分：第一，初始化所有的位为0；第二，读取文件中每个整数，
如果该整数对应的位已经为1，说明前面已经出现过这个整数，抛出异常，退出程序
(输入要求每个整数都只能出现一次)。否则，将相应的位置1；第三，
检查每个位，如果某个位是1，就写出相应的整数，从而创建已排序的输出文件。

如果主存容量严苛地限制在1MB，而使用Bitmap需要1.25MB，
因此无法一次载入完成排序。那么，我们可以将该文件分割成两个文件，
再分别用Bitmap处理。分割策略可以简单地把前一半的数据放到一个文件，
后一半的数据放到另一个文件，分别排序后再做归并。
也可以把文件中小于某个数(比如5,000,000)的整数放到一个文件，叫less.txt，
把其余的整数放到另一个文件，叫greater.txt。分别排序后，
把greater.txt的排序结果追加到less.txt的排序结果即可。

啊哈！算法

第2章围绕3个问题展开。

给定一个包含32位整数的顺序文件，它至多只能包含40亿个这样的整数，
并且整数的次序是随机的。请查找一个此文件中不存在的32位整数。
在有足够主存的情况下，你会如何解决这个问题？
如果你可以使用若干外部临时文件，但可用主存却只有上百字节，
你会如何解决这个问题？

这是CTCI中的一道题目，详细解答请戳以下链接：

请猛戳我

请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8,i=3，
那么向量abcdefgh旋转之后得到向量defghabc。

这个问题很常见了，做3次翻转即可，无需额外空间：

reverse(0, i-1); // cbadefgh
reverse(i, n-1); // cbahgfed
reverse(0, n-1); // defghabc

给定一本英语单词词典，请找出所有的变位词集。例如，因为“pots”，
“stop”，“tops”相互之间都是由另一个词的各个字母改变序列而构成的，
因此这些词相互之间就是变位词。

这个问题可以分3步来解决。第一步将每个单词按字典序排序，
做为原单词的签名，这样一来，变位词就会具有相同的签名。
第二步对所有的单词按照其签名进行排序，这样一来，变位词就会聚集到一起。
第三步将变位词分组，形成变位词集。示意图如下：

数据决定程序结构

恰当的数据视图实际上决定了程序的结构。
我们常常可以通过重新组织内部数据来使程序变得小而美。

发明家悖论：更一般性的问题也许更容易解决。(有时候吧)

程序员在节省空间方面无计可施时，将自己从代码中解脱出来，
退回起点并集中心力研究数据，常常能有奇效。数据的表示形式是程序设计的根本。

下面是退回起点进行思考时的几条原则：

使用数组重新编写重复代码。冗长的相似代码常常可以使用最简单的数据结构——
数组来更好地表述。

封装复杂结构。当需要非常复杂的数据结构时，使用抽象术语进行定义，
并将操作表示为类。

尽可能使用高级工具。超文本，名字-值对，电子表格，数据库，
编程语言等都是特定问题领域中的强大的工具。

从数据得出程序的结构。在动手编写代码之前，优秀的程序员会彻底理解输入，
输出和中间数据结构，并围绕这些结构创建程序。

提到的书籍：Polya的《How to Solve it》，中文书《怎样解题》；
Kernighan和Plauger的《Elements of Programming Style》；Fred Brooks的《人月神话》
Steve McConnell的《代码大全》；《Rapid Development》；
《Software Project Survival Guide》

编写正确的程序

本章以二分搜索为例子，讲述了如何对程序进行验证及正确性分析。

深入阅读：David Gries的《Science of Programming》
是程序验证领域里极佳的一本入门书籍。

编程中的次要问题

到目前为止，你已经做了一切该做的事：通过深入挖掘定义了正确的问题，
通过仔细选择算法和数据结构平衡了真正的需求，通过程序验证技术写出了优雅的代码，
并且对其正确性相当有把握。万事俱备，只欠编程。

使用断言assert

自动化测试程序

进阶阅读：《Practice of Programming》第5章(调试)，第6章(测试)
《Code Complete》第25章(单元测试)，第26章(调试)

程序性能分析

下图展示了一个程序的性能提升过程，
该程序的作用是对三维空间中n个物体的运动进行仿真。从图中可以看出，
一个程序可以从多方面进行性能提升，而其中算法和数据结构的选择又显得尤为重要。

从设计层面提升程序性能：

问题定义。良好的问题定义可以有效减少程序运行时间和程序长度。

系统结构。将大型系统分解成模块，也许是决定其性能的最重要的单个因素。

算法和数据结构。这个不用说了。

代码调优。针对代码本身的改进。

系统软件。有时候改变系统所基于的软件比改变系统本身更容易。

硬件。更快的硬件可以提高系统的性能。

深入阅读：Butler Lampson的“Hints for Computer System Design”，
该论文特别适合于集成硬件和软件的计算机系统设计。

粗略估算

这一章讲述了估算技术，我认为是相当有用的一章。

文中先抛出一个问题：密西西比河一天流出多少水？如果让你来回答，
你会怎么答，注意不能去Google哦。

作者是这么回答这个问题：假设河的出口大约有1英里宽和20英尺深(1/250英里)，
而河水的流速是每小时5英里，也就是每天120英里。则可以计算出一天的流量：

1英里 * 1/250英里 * 120英里/天  约等于  1/2 英里^3/天

上述算式非常简单，可是在看到这些文字之前，如果有人真的问你，
密西西比河一天流出多少水？你真的能答上来吗？还是愣了一下后，摆摆手，说：
这我哪知道！

对于上面的问题，我们至少可以注意到以下两点：

你需要把问题转换成一个可计算的具体模型。这一点往往不需要太担心，
因为我们做的是估算，所以可以忽视很多无关紧要的因素，可以去简化你的模型，
记住我们要的只是一个粗略计算的结果。比如对于上面的问题，
计算密西西比河一天流出多少水其实就是计算其一天的流量，利用中学所学知识，
流量 = 截面积 x 流速，那我们就只需计算密西西比河的出水口的截面积和流速即可。
我们可以将出水口简化成一个矩形，因此就只需要知道出水口的宽和深即可。

你需要知道常识性的东西。上面我们已经把问题转换成了一个可计算的具体模型：
流量 = 出水口宽 x 出水口深 x 流速。接下来呢？你需要代入具体的数值去求得答案。
而这就需要你具备一些常识性的知识了。比如作者就估计了密西西比河的出口有1英里宽，
20英尺深(如果你估计只有几十米宽，那就相差得太离谱了)。
这些常识性的知识比第1点更值得关注，因为你无法给出一个靠谱的估算值往往是因为这点。

当我们懂得如何把一个问题具体化定义出来并为其选用适当的模型，
并且我们也积累了必要的常识性的知识后，回答那些初看起来无从下手的问题也就不难了。
这就是估算的力量。

以下是估算时的一些有用提示：

两个答案比一个答案好。即鼓励你从多个角度去对一个问题进行估算，
如果从不同角度得到的答案差别都不大，说明这个估算值是比较靠谱的。

快速检验。即量纲检验。即等式两边最终的量纲要一致。
这一点在等式简单的时候相当显而易见。比如位移的单位是米，时间单位是秒，
速度单位是米/秒，那显然我们应该要用位移去除以时间来得到速度，
这样才能保证它们单位的一致。你可能会说，我了个去，这种小学生都懂的事，
你好意思拿出来讲。其实不然，当你面对的是一个具有多个变量的复杂物理公式，
或者你提出某种物理假设，正在考虑将其公式化，该方法可以切切实实地帮你做出检验。

经验法则。“72法则”：1.假设以年利率r%投资一笔钱y年，如果ry = 72，
那么你的投资差不多会翻倍。2.如果一个盘子里的菌群以每小时3%的速率增长，
那么其数量每天(24小时)都会翻倍。在误差不超过千分之五的情况下，
\pi秒就是一个纳世纪。也就是说：

3.14秒 = 10^-9 100年 = 10^-7 年

也就是说，1年大概是3.14x10⁷ 秒。所以如果有人告诉你，一个程序运行10⁷ 秒，
你应该能很快反应出，他说的其实是4个月。

实践。与许多其他活动一样，估算技巧只能通过实践来提高。

如果问题的规模太大，我们还可以通过求解它的小规模同质问题来做估算。比如，
我们想测试某个程序运行10亿次需要多长时间，如果你真去跑10亿次，
说不定运行几个小时都没结束，那不是很悲剧？我们可以运行这个程序1万次或是10万次，
得出结果然后倍增它即可。当然，这个结果未必是准确的，
因为你没法保证运行时间是随着运行次数线性增加的。谨慎起见，我们可以运行不同的次数，
来观察它的变化趋势。比如运行10次，100次，1000次，10000次等，
观察它的运行时间是否是线性增加的，或是一条二次曲线。

有时候，我们需要为估算的结果乘上一个安全系数。比如，
我们预估完成某项功能需要时间t，那根据以往经验，也许我们需要为这个值乘上2或4，
这样也许才是一个靠谱的预估值。

Little定律：系统中物体的平均数量等于物体离开系统的平均速率和每个物体在系统中停留
的平均时间的乘积。(如果物体离开和进入系统的总体出入流是平衡的，
那么离开速率也就是进入速率)

举个例子，比如你正在排除等待进入一个火爆的夜总会，
你可以通过估计人们进入的速率来了解自己还要等待多长时间。根据Little定律，
你可以推论：这个地方可以容纳约60人，每个人在里面逗留时间大约是3小时，
因此我们进入夜总会的速率大概是每小时20人。现在队伍中我们前面还有20人，
也就意味着我们还要等待大约一个小时。

深入阅读：Darrell Huff的《How To Lie With Statistics》；关键词：
费米近似(Fermi estimate, Fermi problem)

算法设计技术

这一章就一个小问题研究了4种不同的算法，重点强调这些算法的设计技术。
研究的这个小问题是一个非常常见的面试题：子数组之和的最大值。
如果之前没有听过，建议Google之。

深入阅读：Aho,Hopcroft和Ullman的《Data Structures and Algorithms》
Cormen,Leiserson,Rivest和Stein的《Introduction to Algorithms》

代码调优

前面各章讨论了提高程序效率的高层次方法：问题定义，系统结构，
算法设计及数据结构选择。本章讨论的则是低层次的方法：代码调优。

代码调优的最重要原理就是尽量少用它。不成熟的优化是大量编程灾害的根源。
它会危及程序的正确性，功能性以及可维护性。当效率很重要时，
第一步就是对系统进行性能监视，以确定其运行时间的分布状况。
效率问题可以由多种方法来解决，只有在确信没有更好的解决方案时才考虑进行代码调优。

事实上，如果不是十分十分必要，不要去做代码调优，
因为它会牺牲掉软件的其他许多性质。

so，just skip this chapter。

节省空间

本章讲述了节省空间的一些重要方法。

减少程序所需数据的存储空间，一般有以下方法：

不存储，重新计算。

稀疏数据结构。下面着重讲一下这点。

数据压缩。可以通过压缩的方式对对象进行编码，以减少存储空间。

分配策略。只有在需要的时候才进行分配。

垃圾回收。对废弃的存储空间进行回收再利用。

以下是节省代码空间的几种通用技术：

函数定义。用函数替换代码中的常见模式可以简化程序，同时减少代码的空间需求。

解释程序。用解释程序命令替换长的程序文本。

翻译成机器语言。可以将大型系统中的关键部分用汇编语言进行手工编码。

稀疏数据结构

假设我们有一个200 x 200的矩阵(共40000个元素)，里面只有2000个元素有值，
其它的都为0，示意图如下：

显然这是一个稀疏矩阵，直接用一个200 x 200
的二维数组来存储这些数据会造成大量的空间浪费，共需要200x200x4B=160KB。
所以，我们应该想办法用另一种形式来存储这些数据。

方法一

使用数组表示所有的列，同时使用链表来表示给定列中的活跃元素。
如下图所示：

该结构中，有200个指针(colhead)和2000条记录(每条记录是两个整数和一个指针)，
占用空间是200x4B + 2000x12B = 24800B = 24.8KB，
比直接用二维数组存储(160KB)要小很多。

方法二

我们可以开三个数组来保存这些数，如下图所示：

firstincol是一个长度为201的数组，对于第i列，在数组row中，
下标为firstincol[i]到firstincol[i+1]-1对应的行元素非0，
其值存储在相应的pointnum数组中。

比如对于上图，在第0列中，元素值非0的行有3行，分别是row[0],row[1],row[2],
元素值是pointnum[0],pointnum[1],pointnum[2]；在第1列中，元素值非0的行有2行，
分别是row[3],row[4]，元素值是pointnum[3],pointnum[4]。依次类推。

该结构所需要的存储空间为2x2000x4B + 201x4B = 16804B = 16.8KB。
由于row数组中的元素全部都小于200，所以每个元素可以用一个unsigned char来保存，
firstincol数组中元素最大也就2000，所以可以用一个short(或unsigned short)来保存，
pointnum中的元素是一个4B的int，
最终所需空间变为：2000x4B + 2000x1B + 201x2B = 10402B = 10.4KB。

深入阅读：Fred Brooks的《人月神话》

排序

本章先简单介绍了插入排序，然后着重讲述快速排序。

插入排序

// 版本1
void InsertSort(int a[], int n) {
    for(int i=1; i<n; ++i)
        for(int j=i; j>0 && a[j-1]>a[j]; —j)
            swap(a[j-1], a[j]);
}
// 版本2
void InsertSort1(int a[], int n) {
    for(int i=1; i<n; ++i) {
        int t = a[i];
        int j = i;
        for(; j>0 && a[j-1]>t; —j)
            a[j] = a[j-1];
        a[j] = t;
    }
}

快速排序

我们在这里规定：小于等于pivot的元素移到左边，大于pivot的元素移到右边。

实现1：单向移动版本

这个版本的关键是设置一快一慢两个指针，慢指针左侧都是小于等于pivot(包含慢指针所在位置)，
慢指针到快指针之间的值是大于pivot，快指针右侧的值是还未比较过的。示意图如下：

小于等于pivot    ｜    大于pivot    ｜    ？
             slow                fast

快指针一次一步向前走，遇到大于pivot什么也不做继续向前走。遇到小于等于pivot的元素，
则慢指针slow向前走一步，然后交换快慢指针指向的元素。一次划分结束后，
再递归对左右两侧的元素进行快排。代码如下：

// 数组快排
void QSort(int a[], int head, int end) {
    if(a==NULL || head==end) return;
    int slow = head, fast = head + 1;
    int pivot = a[head];
    while(fast != end) {
        if(a[fast] <= pivot)
            swap(a[++slow], a[fast]);
        ++fast;
    }
    swap(a[head], a[slow]);
    QSort(a, head, slow);
    QSort(a, slow+1, end);
}

排序数组a只需要调用QSort(a, 0, n)即可。该思路同样可以很容易地在链表上实现：

// 单链表快排
void qsort(Node head, Node end){
    if(head==NULL || head==end) return;
    Node slow = head, fast = head->next;
    int pivot = head->data;
    while(fast != end){
        if(fast->data <= pivot){
            slow = slow->next;
            swap(slow->data, fast->data);
        }
        fast = fast->next;
    }
    swap(head->data, slow->data);
    qsort(head, slow);
    qsort(slow->next, end);
}

排序头指针为head的单链表只需调用qsort(head, NULL)即可。

实现2：双向移动版本

版本1能能够快速完成对随机整数数组的排序，但如果数组有序，
或是数组中元素相同，快排的时间复杂度会退化成O(n² )，性能变得非常差。

一种缓解方案是使用双向移动版本的快排，它每次划分也是使用两个指针，
不过一个是从左向右移动，一个是从右向左移动，示意图如下：

小于等于pivot    ｜    ？    ｜    大于pivot
               i            j

指针j不断向左移动，直到遇到小于等于pivot，就交换指针i和j所指元素
(指针i一开始指向pivot)；指针i不断向右移动，直到遇到大于pivot的，
就交换指针i和j所指元素。pivot在这个过程中，不断地换来换去，
最终会停在分界线上，分界线左边都是小于等于它的元素，右边都是大于它的元素。
这样就避免了最后还要交换一次pivot的操作，代码也变得美观许多。

int partition(int a[], int low, int high){
    int pivot = a[low], i=low, j=high;
    while(i < j){
        while(i<j && a[j]>pivot) —j;
        if(i < j) swap(a[i], a[j]);
        while(i<j && a[i]<=pivot) ++i;
        if(i < j) swap(a[i], a[j]);
    }
    return i;
}
void quicksort(int a[], int first, int last){
    if(first<last){
        int k = partition(a, first, last);
        quicksort(a, first, k-1);
        quicksort(a, k+1, last);
    }
}

当然，如果对于partition函数，你如果觉得大循环内的两个swap还是做了些无用功的话，
也可以把pivot的赋值放到最后一步，而不是在这个过程中swap来swap去的。代码如下：

int partition(int a[], int low, int high){
    int pivot = a[low], i=low, j=high;
    while(i<j){
        while(i<j && a[j]>pivot) —j;
        if(i<j) a[i++] = a[j];
        while(i<j && a[i]<=pivot) ++i;
        if(i<j) a[j—] = a[i];
    }
    a[i] = pivot;
    return i;
}

如果数组基本有序，那随机选择pivot(而不像上面那样选择第一个做为pivot)
会得到更好的性能。在partition函数里，我们只需要在数组中随机选一个元素，
然后将它和数组中第一个元素交换，后面的划分代码无需改变，
就可以达到随机选择pivot的效果。

进一步优化

对于小数组，用插入排序之类的简单方法来排序反而会更快，因此在快排中，
当数组长度小于某个值时，我们就什么也不做。对应到代码中，
就是修改quicksort中的if条件：

if(first < last)  改为  if(last-first > cutoff)

其中cutoff是一个小整数。程序结束时，数组并不是有序的，
而是被组合成一块一块随机排列的值，并且满足这样的条件：
某一块中的元素小于它右边任何块中的元素。我们必须通过另一种排序算法对块内进行排序。
由于数组是几乎有序的，因此插入排序比较适用。

这种方法结合了快排和插入排序，让它们去做各自擅长的事情，往往比单纯用快排要快。

深入阅读：Don Knuth的《The Art of Computer Programming, Volume 3:
Sorting and Searching》；Robert Sedgewick的《Algorithms》；
《Algorithms in C》,《Algorithms in C++》,《Algorithms in Java》。

取样问题

本章讲述了一个小的随机抽样问题，并用不同的方法来解决它。

问题：对于整数m和n，其中m<n，输出0~n-1范围内m个随机整数的有序列表，
不允许重复。

比如m=3, n=5，那么一种可能输出是0，2，3(要求有序)。实现1来自Knuth的TAOCP，
时间复杂度O(n)：

void GenKnuth(int m, int n) {
    for(int i=0; i<n; ++i) {
        if((bigrand()%(n-i)) < m) {
            cout<<i<<endl;
            —m;
        }
    }
}

其中，bigrand()的作用是返回一个很大的随机整数。

实现2：在一个初始为空的集合里面插入随机整数，直到个数足够。代码如下：

void GenSets(int m, int n) {
    set<int> s;
    while(s.size() < m)
        s.insert(bigrand() % n);
    set<int>::iterator i;
    for(i=s.begin(); i!=s.end(); ++i)
        cout<<*i<<endl;
}

实现3：把包含整数0～n-1的数组顺序打乱，然后把前m个元素排序输出。
该方法的性能通常不如Knuth的算法。代码如下：

void GenShuf(int m, int n) {
    int x[n];
    for(int i=0; i<n; ++i)
        x[i] = i;
    for(int i=0; i<m; ++i) {
        int j = randint(i, n-1);
        swap(x[i], x[j]);
    }
    sort(x, x+m);
    for(int i=0; i<m; ++i)
        cout<<x[i]<<endl;
}

深入阅读：Don Knuth的《The Art of Computer Programming,
Volume 2: Seminumerical Algorithms》

搜索

本章详细研究这样一个搜索问题：在没有其他相关数据的情况下，如何存储一组整数？
为些介绍了5种数据结构：有序数组，有序链表，二叉搜索树，箱，位向量。

其中，二叉搜索树应该熟练掌握，以下是一种实现：

struct Node {
    int data;
    Node lchild, rchild, parent;
    Node(): lchild(NULL), rchild(NULL), parent(NULL) { }
};
class BST {
private:
    static const int kMax = 1000;
    Node root, *parent, nodes[kMax];
    int size;
private:
    Node minimum(Node node);
    Node maximum(Node node);
    Node successor(Node node);
    Node predecessor(Node node);
    void Insert(Node &node, int x);
    void InorderTraver(Node node);
    Node Find(Node node, int x);
public:
    BST(): root(NULL), parent(NULL), size(0) {
        memset(nodes, '\0', sizeof(nodes));
    }
    void Insert(int x);
    void InorderTraver();
    Node Find(int x);
    void Remove(Node z);
};
Node BST::minimum(Node node) {
    if(node == NULL) return NULL;
    while(node->lchild)
        node = node->lchild;
    return node;
}
Node BST::maximum(Node node) {
    if(node == NULL) return NULL;
    while(node->rchild)
        node = node->rchild;
    return node;
}
Node BST::successor(Node node) {
    if(node->rchild)
        return minimum(node->rchild);
    Node y = node->parent;
    while(y && node==y->rchild) {
        node = y;
        y = node->parent;
    }
    return y;
}
Node BST::predecessor(Node node) {
    if(node->lchild)
        return maximum(node->lchild);
    Node y = node->parent;
    while(y && node==y->lchild) {
        node = y;
        y = node->parent;
    }
    return y;
}
void BST::Insert(Node* &node, int x) {
    if(node == NULL) {
        nodes[size].data = x;
        nodes[size].parent = parent;
        node = &nodes[size];
        ++size;
        return;
    }
    parent = node;
    if(x < node->data)
        Insert(node->lchild, x);
    else
        Insert(node->rchild, x);
}
void BST::Insert(int x) {
    Insert(root, x);
}
void BST::InorderTraver(Node* node) {
    if(node == NULL) return;
    InorderTraver(node->lchild);
    cout<<node->data<<" ";
    InorderTraver(node->rchild);
}
void BST::InorderTraver() {
    InorderTraver(root);
}
Node BST::Find(Node node, int x) {
    if(node == NULL) return NULL;
    if(x < node->data) return Find(node->lchild, x);
    else if(x > node->data) return Find(node->rchild, x);
    else return node;
}
Node BST::Find(int x) {
    return Find(root_, x);
}
void BST::Remove(Node z) {
    if(!z->lchild && !z->rchild) {
        if(z == root) root = NULL;
        else if(z == z->parent->lchild)
            z->parent->lchild = NULL;
        else
            z->parent->rchild = NULL;
    }
    else if(z->lchild==NULL || z->rchild==NULL) {
        if(z == root) {
            if(z->lchild) root = z->lchild;
            else root = z->rchild;
            root->parent = NULL;
        }
        else {
            if(z==z->parent->lchild && z->lchild) {
                z->parent->lchild = z->lchild;
                z->lchild->parent = z->parent;
            }
            else if(z==z->parent->lchild && z->rchild) {
                z->parent->lchild = z->rchild;
                z->rchild->parent = z->parent;
            }
            else if(z==z->parent->rchild && z->lchild) {
                z->parent->rchild = z->lchild;
                z->lchild->parent = z->parent;
            }
            else {
                z->parent->rchild = z->rchild;
                z->rchild->parent = z->parent;
            }
        }
    }
    else {
        Node *s = predecessor(z);
        z->data = s->data;
        if(z == s->parent)
            s->parent->lchild = s->lchild;
        else
            s->parent->rchild = s->lchild;
        if(s->lchild)
            s->lchild->parent = s->parent;
    }
}

堆

本章主要介绍堆，下面是关于堆的一些主要操作：

// 最大堆实现, 数组下标从1开始，a[0]不使用。
// 交换两数
void swap(int &a, int &b) {
    int t = a;
    a = b;
    b = t;
}
// 把第i个元素向上移动
void ShiftUp(int a[], int i) {
    while(i>1 && a[i]>a[i/2]) {
        swap(a[i], a[i/2]);
        i >>= 1;
    }
}
// 把第i个元素向下移动
void ShiftDown(int a[], int n, int i) {
    while((i=2*i) <= n) {
        if(i+1<=n && a[i+1]>a[i]) ++i;
        if(a[i] > a[i/2]) swap(a[i], a[i/2]);
        else break;
    }
}
// 把数组a变成具备最大堆性质的数组
void MakeHeap(int a[], int n) {
    for(int i=n/2; i>0; —i)
        ShiftDown(a, n, i);
}
// 向堆中插入元素x
void Insert(int a[], int &n, int x) {
    a[++n] = x;
    ShiftUp(a, n);
}
// 删除堆中第i个元素
void Del(int a[], int &n, int i) {
    a[i] = a[n—];
    if(i>1 && a[i]>a[i/2]) ShiftUp(a, i);
    else ShiftDown(a, n, i);
}
// 堆排序，时间复杂度O(nlogn)
void HeapSort(int a[], int n) {
    MakeHeap(a, n);
    for(int i=n; i>1; —i) {
        swap(a[i], a[1]);
        ShiftDown(a, i-1, 1);
    }
}

字符串

程序1：循环输入并将每个单词插入集合S(忽略重复单词)，然后排序输出。

int main(void) {
    set<string> s;
    set<string>::iterator j;
    string t;
    while(cin >> t)
        s.insert(t);
    for(j=s.begin(); j!=s.end(); ++j)
        cout<<*j<<endl;
    return 0;
}

程序2：单词计数

int main(void) {
    map<string, int> m;
    map<string, int>::iterator j;
    string t;
    while(cin >> t)
        m[t]++;
    for(j=m.begin(); j!=m.end(); ++j)
        cout<<j->first<<" "<<j->second<<endl;
    return 0;
}

程序3：建立自己的哈希表(散列表)，以下是一种实现：

class Hash {
public:
    Hash(): seed(131), size(0) {
        memset(head, 0, sizeof(head));
    }
    void Insert(const char str) {
        unsigned int id = hash(str);
        char dst = (char)node[size].word;
        while(dst++ = str++);
        node[size].next = head[id];
        head[id] = &node[size];
        ++size_;
    }
    bool Find(const char str) {
        unsigned int id = hash(str);
        for(Node p=head_[id]; p; p=p->next) {
            char dst = (char)p->word;
            int i = 0;
            for(; (str+i) && (str+i)==(dst+i); ++i);
            if(!(str+i) && !(dst+i)) return true;
        }
        return false;
    }
private:
    unsigned int hash(const char str) {// BKDR Hash Function
        unsigned int hash = 0;
        while(str) {
            hash = hash  seed_ + (str++);
        }
        return (hash & 0x7FFFFFFF) % kHashSize;
    }
private:
    unsigned int seed;
    unsigned int size;
    static const int kWordSize = 26 + 1;
    static const int kNodeSize = 20000;
    static const int kHashSize = 10001;
    struct Node {
        char word[kWordSize];
        Node next;
    };
    Node node_[kNodeSize];
    Node head_[kHashSize];
};

后缀数组

假设我们有以下字符串及一个char*数组：

 char c[20] = "hawstein";
 char* pc[20];

我们让指针pc[i]指向字符串的第i个字符，即：

for(int i=0; i<8; ++i)
    pc[i] = &c[i];

这时候我们输出pc[i]，会得到字符串”hawstein”的所有后缀：

hawstein
awstein
wstein
stein
tein
ein
in
n

然后，我们对数组pc进行排序，将所有后缀按字典序排序：

sort(pc, pc+8, cmp);

其中，比较函数cmp如下：

1
2
3

inline bool cmp(char p, charq) {
    return strcmp(p, q) < 0;
}

这时，我们再输出pc[i]，会得到排序后的结果：

awstein
ein
hawstein
in
n
stein
tein
wstein

我们把数组pc称为“后缀数组”。这里需要注意，数组pc
中存储的是指向每个后缀首字符的地址。我们也可以存储每个后缀首字符在原数组中的下标，
效果是一样的。

本章中用后缀数组解决了一个小问题：可重叠最长重复子串。比如对于字符串”banana”，
其后缀数组为：

a
ana
anana
banana
na
nana

扫描一次数组，比较相邻子串，找到相邻子串的最长公共前缀即可。本例为”ana”，
其中一个a是重叠的。

后缀数组是处理字符串的有力工具，常见的两种实现方法是：倍增算法和DC3算法。
推荐阅读以下材料来学习后缀数组：

许智磊，《后缀数组》

罗穗骞，《后缀数组——处理字符串的有力工具》

Black Mirror Christmas Special

Posted on 2015-02-26 | In 追剧 |

Roman to Integer, Integer to Roman, ZigZag Conversion

Posted on 2015-02-26 | In 刷题 |

Roman to Integer

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

Solution

How roman numbers work:

M | D | C | L | X | V | I |

1000 | 500 | 100 | 50 | 10 | 5 | 1 |

If the current character is larger than previous one, then we substract previous form current, otherwise add up all digits.

public int romanToInt(String s) {
        if(s==null) return 0;
        int n=s.length(),res=0;
        for(int i=0 ; i< n;i++){
    
            switch(s.charAt(i)){
            
                case 'I': 
                    if(i<n-1 && s.charAt(i+1)!='I'){res-=1;break;}
                    else{res+=1; break;}
                
                case 'V': 
                    if(i<n-1 && s.charAt(i+1)!='I'){res-=5;break;}
                    else {res+=5; break;}
                case 'X': 
                    if(i<n-1 && (s.charAt(i+1)=='L'||s.charAt(i+1)=='C'||s.charAt(i+1)=='D'||s.charAt(i+1)=='M')){res-=10;break;}
                    else {res+=10; break;}
                case 'L': 
                    if(i<n-1 && (s.charAt(i+1)=='C'||s.charAt(i+1)=='D'||s.charAt(i+1)=='M')){res-=50;break;}
                    else {res+=50; break;}
                case 'C': 
                    if(i<n-1 && (s.charAt(i+1)=='D'||s.charAt(i+1)=='M')){res-=100; break;}
                    else {res+=100;break;}
                case 'D': 
                    if(i<n-1 && s.charAt(i+1)=='M') {res-=500; break;}
                    else {res+=500; break;}
                case 'M': res+=1000; break;
            }
        }
        return res;
    }

Integer to Roman

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

Solution


public String intToRoman(int num) {
     int[] numbers={1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
     String[] tokens={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
     StringBuilder sb=new StringBuilder();
     int i=0;
     while(num>0){
         int tmp=num/numbers[i];
         num=num-tmp*numbers[i];
         for(int k=tmp;k>=1;k--){
             sb.append(tokens[i]);
         }
         i++;
     }
     return sb.toString();
 }

ZigZag Conversion

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

1
2
3

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

Solution

Each group of words are 2*nRows-2, we add the String row by row. Be careful about first and last row:

public String convert(String s, int nRows) {
        int nCol=0,size=2*nRows-2;
        if(s==null || nRows==1) return s; 
        StringBuilder res=new StringBuilder();
        //add char to stringbuilder row by row
        for(int i=0;i<nRows;i++){
            for(int j=i;j<s.length();j+=size){
                res.append(s.charAt(j));
                if(i!=0 && i!=nRows-1 && j+size-2*i<s.length())
                res.append(s.charAt(j+size-2*i));
            }    
        }
         return res.toString();
    }

Majority Element, Gray Code

Posted on 2015-02-26 | In 刷题 |

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

Two pass solution

public int majorityElement(int[] num) {
    int n=num.length;
    HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
    for(int i=0;i<n;i++){
        if(!map.containsKey(num[i])) map.put(num[i], 1);
        else map.put(num[i], map.get(num[i])+1);
        if(map.get(num[i])>=(n/2)+1) return num[i];
    }
    return 0;
}

Moore voting algorithm

Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. This takes O(n) time.

  
  public int majorityElement(int[] num) {
    int n=num.length, count=1;
    int tmp=num[0];
    for(int i=1;i<n;i++){
        if(count==0) {tmp=num[i];count++;}
        else if(num[i]==tmp) count++;
        else count--;
    }
    return tmp;     
}

Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

Recursive solution

For 3 bit case: [0,1,3,2,6,7,5,4], we found that the first four numbers in case n=3 are the same as the the numbers in case n=2. Besides, [6,7,5,4] = [2+4,3+4,1+4,0+4].

public List<Integer> grayCode(int n) {
    List<Integer> ret = new ArrayList<Integer>();
    if (n == 0) {
        ret.add(0);
        return ret;
    }
    
    ret = grayCode(n - 1);
    
    for (int i = ret.size() - 1; i >= 0; i--) {
        int num = ret.get(i);
        num += 1 << (n - 1);
        ret.add(num);
    }
    
    return ret;
}

Iterative Solution

Use the above mentioned mirror image property:

public ArrayList<Integer> grayCode(int n) {
  ArrayList<Integer> result = new ArrayList<Integer>();
  if (n == 0) {
    result.add(0);
    return result;
  }
  ;
  result.add(0);
  result.add(1);
  for (int i = 1; i < n; i++) {
    ArrayList<Integer> tmp = new ArrayList<Integer>(result);
    Integer a = 1 << i;
    for (int k = result.size() - 1; k >= 0; k--) {
      tmp.add(result.get(k) + a);
    }
    result = tmp;
  }
  return result;
}

Reverse Integer, Reverse Linked List I, Reverse Linked List II, Reverse Nodes in k-Group, Rotate List

Posted on 2015-02-26 | In 刷题 |

Reverse Integer

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
Update (2014-11-10):
Test cases had been added to test the overflow behavior.

First Solution:

First I thought of converting int to string then use two pointer to reverse the number, but we need to pay attention to the two sepcial cases mentioned above. I will update that solution after I solved ‘reverse string’ problem.
The following solution uses only one parameter x, we get each digit by computing x%10 and add it to result, then we multiply result with 10 each round. This method deal with first special case of last digit 0 itself, but didn’t pass OJ because of overflows.

public int reverse(int x) {
        int res=0;
        while(x!=0){
            res=x%10+res*10;
            x=x/10;
        }
        return res;
    }

Correct Solution:

After running a few tests, I figured the overflow probelm occurs when we try to add to Integer.MAX_VALUE(2^32-1), or subtract from Integer.MIN_VALUE(-2^32), this would cause number jump from minus to positive and therefore wrong output.
So first we record the sign of the number, and use ABS(x) to compute the ABS of reversed int, during which we check if the new res>Integer.MAX_VALUE,moving res to one side is a really clever trick. At last, output the right sign of result.

public int reverse(int x) {
       int res=0,num=Math.abs(x);
       boolean sign=x>0? true:false;
       while(num!=0){
       //check if res>Integer.MAX_VALUE
        if(res>(Integer.MAX_VALUE-num%10)/10) return 0;
           res=num%10+res*10;
           num=num/10;
       } 
       return sign? res:-res;
   }

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Reverse a Singly LinkedList

First I thought of solving this problem: reverse 1->2->3 to 3->2->1.

Naive solution is to use a stack and reconstruct the list:

public static ListNode reverse(ListNode head) {
  Stack<ListNode> stack = new Stack<ListNode>();
  while (head != null) {
    stack.add(head);
    head = head.next;
  }
  ListNode current = stack.pop();
  head = current;
  while (!stack.empty()) {
    ListNode next = stack.pop();
    current.next=next;
    current = next;
  }
  return head;  
}

Better solution:

We need to update each node.next

Before that, we need to record the original node.next to continue

Use two pointers, pre to the previous element, and post to the next element

public ListNode reverse(ListNode head){
  ListNode pre=null,post=null,cur=head;
  while(cur!=null){
    post=cur.next;
    cur.next=pre;
    pre=cur;
    cur=post;
  }
  return pre;
}

Iterative Method are even more efficent, but harder to understand…

public ListNode reverse(ListNode head){
  ListNode cur=head;
  if(cur==null||cur.next==null)
    return cur;
  ListNode post=cur.next;
  cur.next=null;
  //rest is the last element, the new head
  ListNode rest=reverse(post);
  //update node.next
  post.next=cur;
  return rest;
}

Correct Solution:

Different from reverse a Singly LinkedList, we now only need to reverse a part of it (m to n). We use the following pointers:

preM: the last node before m

pre: the last node among the part already reversed. Dont’t need to be udpated, as it always points to the same node

cur: the node we want to add after PreM, in other words, the first node among the part already reversed. Need to be set to pre.next


  public ListNode reverseBetween(ListNode head, int m, int n){
  ListNode pre=null,post=null;
  ListNode dummy=new ListNode(0);
  dummy.next=head;
  ListNode preM=dummy,cur=null;
  for (int i =1;i<=n;i++){
    if(i<m)
      preM=preM.next;
    else if(i==m){
      pre=preM.next;
      cur=pre.next;
    }
    else{
      pre.next=cur.next;
      //made a mistake here by cur.next=pre; 
      cur.next=preM.next;
      preM.next=cur;
      cur=pre.next;
    }
  }
  return dummy.next;
}

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

Iterative Solution:

We use the sub-process of reverse(ListNode start,ListNode end), while we scan through the list, keep three pointers:

pref: breakpoint for different groups.

start: first node of current group. Initialized as node 1

end: last node of current group

Each round we:

move pref to position, set start and end pointer

reverse current group, link last node to the rest

link pref to the returned head, and repeat

This is One Pass O(n) solution.

  
  public ListNode reverseKGroup(ListNode head, int k) {
  ListNode dummy=new ListNode(0);
  dummy.next=head;
  ListNode pref=dummy, start, end;
  while(pref!=null){
    start=pref.next;
    end=pref;
    //move end pointer K times, pointing to kth node
    for (int i=0;i<k;i++){
      end=end.next;
      //last nodes not enough for a group
      if(end==null) return dummy.next;
    }
    //link pref with head of reversed group
    pref.next=reverse(start,end);
    //move pref pointer K times, pointing to the node before next group
    for(int j=0;j<k;j++){pref=pref.next;}
  } return dummy.next;
}
public ListNode reverse(ListNode start,ListNode end){
  ListNode post=end.next,tmp;
  ListNode pre=start,cur=start.next;
  //inside this group
  while(cur!=post){
     tmp=cur.next;
     cur.next=pre;
     pre=cur;
     cur=tmp;
  }
  //don't forget to link end of reversed group with the rest nodes
  start.next=post;
  return pre;
}

Two Pass Solution:

I first thought of this solution, but wasn’t careful enough with the details…

First scan through the list and get the number of groups

For each group i smaller than num, use an inner loop to do the following:

reverse each group, keep curhead and curtail as inner group pointers, move cur to first node outside of group

if is the first group, we update head and let tail=curtail, in other rounds we just attach curhead to tail.

At last, don’t forget to attach the leftover nodes curtail.next=cur

  
  public ListNode reverseKGroup(ListNode head,int k){
  if(k==0||k==1) return head;
  ListNode count=head;
  int n=0;
  while(count!=null){count=count.next;n++;}
  int num=n/k;
  if(num==0) return head;
  ListNode curtail=null, curhead=null, tail=null, pre=null, cur,tmp=null;
  cur=head;
  for(int i=0;i<num;i++){
    pre=null;
    for(int j=0;j<k;j++){
      if(cur!=null){
        tmp=cur.next;
        cur.next=pre;
        pre=cur;
      }
      if(j==0) curtail=cur;
      if(j==(k-1)) curhead=cur;
      cur=tmp;
    }
    if(tail==null) head=curhead;
    else tail.next=curhead;
    tail=curtail;
  }
  curtail.next=cur;
  return head;
}

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

Naive Solution

First count the length of list, link the last node with head to form a loop. Now cur is pointing to the last node, we use a for loop to move it to (n-k)th node, and break the loop there. At last, return (n-k).next as new head.


public ListNode rotateRight(ListNode head, int n) {
     int k=1;
     ListNode cur=head;
     if(cur==null||cur.next==null||n==0) return head;
     while(cur.next!=null){cur=cur.next;k++;}
     cur.next=head;
     //set n to the position of new head in the original list
     n=n%k;
     for(int i=0;i<k-n;i++){
         cur=cur.next;
     }
     head=cur.next;
     cur.next=null;
     return head;
 }

Substring with Concatenation of All Words, Longest Substring Without Repeating Characters, Minimum Window Substring, Longest Palindromic Substring

Posted on 2015-02-26 | In 刷题 |

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: “barfoothefoobarman”
L: [“foo”, “bar”]
You should return the indices: [0,9].
(order does not matter).

Brute Force Solution

Two Hashmaps

rest: store all words in L, including times of appreance

found: renew at each round, store matched words, including times of appreance

Two pointers

i: starting index of current substring

j: numebers of words matched to current substring

public ArrayList<Integer> findSubstring(String S, String[] L) {
     ArrayList<Integer> res=new ArrayList<Integer>();
     HashMap<String, Integer> rest=new  HashMap<String, Integer>();
     HashMap<String, Integer> found=new  HashMap<String, Integer>();
     if(S==null||L.length==0) return res;
     int wordlen=L[0].length(), Llen=L.length, Slen=S.length();
     for(int i = 0; i<L.length;i++){
         int num=1;
         if(rest.get(L[i])!=null) 
             num+=rest.get(L[i]);
         rest.put(L[i], num);
     }
    
     for(int i=0; i<Slen-Llen*wordlen+1;i++){
         int j=0;
         found.clear();
         for(;j<Llen;j++){
             int start=i+j*wordlen;
             int end=start+wordlen;
             int num=1;
             String tmp=S.substring(start, end);
             if(!rest.containsKey(tmp)) break;
             if(found.get(tmp)!=null) num+=found.get(tmp);
             if(num>rest.get(tmp)) break;
             found.put(tmp, num);
         }
         if(j==Llen) res.add(i);
     }
     return res;   
 }

Minimun Window Solution

outer loop: i increment wordlen times, each time scan through S

inner loop: j increment wordlen per time, until first letter of last word

each outerloop: reset count=0, reset index=i

each innerloop: curdict to store current window

If tmp str not found in dict, increment index, reset count and curdict
If found, add to curdict, count++
before count++: compare num, if exceeded, increment index ,then decrement count and curdict
If count equals listlen add index into result, increment index, update curdict

public static ArrayList<Integer> findSubstring(String S, String[] L) { 
  ArrayList<Integer> res = new ArrayList<Integer>();
  if(S==null||L==null||S.length()==0||L.length==0)
     return res;
  int wordLen = L[0].length();//same length for each word in dictionary
  
  //put given dictionary into hashmap with each word's count
  HashMap<String, Integer> dict = new HashMap<String, Integer>();
  for(String word: L){
      if(!dict.containsKey(word))
         dict.put(word, 1);
      else
         dict.put(word, dict.get(word) + 1);
  }
  
  for(int i = 0; i < wordLen; i++){
      int count = 0;
      int index = i;//index of each startpoint
      HashMap<String, Integer> curdict = new HashMap<String, Integer>();
      //till the first letter of last word 
      for(int j = i; j <= S.length() - wordLen; j += wordLen){
          String curWord = S.substring(j, j + wordLen);
          //check each word to tell if it existes in give dictionary
          if(!dict.containsKey(curWord)){
              curdict.clear();
              count = 0;
              index = j + wordLen;
          }else{
              //form current dictionary
              if(!curdict.containsKey(curWord))
                 curdict.put(curWord, 1);
              else
                 curdict.put(curWord, curdict.get(curWord) + 1);
              
              //count for current found word and check if it exceed given word count
              if(curdict.get(curWord) <= dict.get(curWord)){
                  count++;
              }else{
                while(curdict.get(curWord) > dict.get(curWord)){
                     String temp = S.substring(index, index + wordLen);
                     curdict.put(temp, curdict.get(temp)-1);
                     index = index + wordLen;//make index move next
                     if(curdict.get(temp)<dict.get(temp))
                     count--;
                 }
              }
              
              //put into res and move index point to nextword 
              //and update current dictionary as well as count num
              if(count == L.length){
                  res.add(index);
                  String temp = S.substring(index, index + wordLen);
                  curdict.put(temp, curdict.get(temp)-1);
                  index = index + wordLen;
                  count--;
              }
          }
      }//end for j
  }//end for i
   return res;
 }

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Brute force method

Find all substrings and check if each of it contains only unique characters. As for the maxlength, we use Greedy Algorithm to only keep the longest substring seen so far. There are one inner loop and each check takes linear time, O(N^2) time won’t pass the OJ.

public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0) return 0;
int maxlen=1;
Hashtable <Character, Boolean> map=new Hashtable<Character, Boolean>();
for(int i=0;i< s.length();i++){
    for(int j=i;j<s.length();j++){
        if(map.containsKey(s.charAt(j))){map.clear(); break;}
        else{map.put(s.charAt(j), false);}
        int len=map.size();
        if(len>maxlen){maxlen=len;}
    }
}
    return maxlen;
}

Better Solution
Use a Hashmap/Hashset recording current substring and two pointers to record current positions.


public int lengthOfLongestSubstring(String s) {
    if(s==null||s.length()==0) return 0;
        int maxlen=1,l=0,r=0;
        Hashtable <Character, Boolean> map=new Hashtable<Character, Boolean>();
        while(r<s.length()){
            char tmp=s.charAt(r);
            if(!map.containsKey(tmp)||map.get(tmp)==false){
                map.put(tmp, true);
                maxlen=Math.max((r-l+1), maxlen);
            }
            else{
                while(s.charAt(l)!=s.charAt(r)){map.put(s.charAt(l), false);l++;}
                l++;
            }
            r++;
        }
        
        return maxlen;
}

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Min Sliding Window Solution

Use a Hashmap to record each character, numbers in T

Two pointers:

left: increment when current substring contains all chars in T, pass unrelevant chars and exceeded chars
right: increment each loop, if found a match in T decrement its Hashmap value

Minlen: when we found a new substring update minlength

public String minWindow(String S, String T) {
    HashMap<Character,Integer> dict=new HashMap<Character,Integer>();
    int tlen=T.length(), slen=S.length(),minlen=slen+1;
    for (int i=0;i<tlen;i++){
        int num=1;
        if(dict.containsKey(T.charAt(i))) num+=dict.get(T.charAt(i));
        dict.put(T.charAt(i),num);
    }
    int count=0,left=0,start=0;
    for(int i=0;i<slen;i++){
        if(dict.containsKey(S.charAt(i))){
            dict.put(S.charAt(i),dict.get(S.charAt(i))-1);
            if(dict.get(S.charAt(i))>=0) count++;
            if(count==tlen){
                while(count==tlen){
                    if(i-left+1<minlen){minlen=i-left+1; start=left; }
                    if(dict.containsKey(S.charAt(left))) {
                         dict.put(S.charAt(left),dict.get(S.charAt(left))+1);
                         if(dict.get(S.charAt(left))>0) count--;
                    }
                    left++;
                }
            }
        }
    }
    
     return minlen>slen? "":S.substring(start,start+minlen);
    
}

Another version using two hashmaps:

public String minWindow(String S, String T) {
    HashMap<Character, Integer> dict = new HashMap<>();
    for (int i = 0; i < T.length(); i++) {
        char c = T.charAt(i);
        if (!dict.containsKey(c))
            dict.put(c, 1);
        else
            dict.put(c, dict.get(c) + 1);
    }
    HashMap<Character, Integer> found = new HashMap<>();
    int foundCounter = 0;
    int start = 0;
    int end = 0;
    int min = Integer.MAX_VALUE;
    String minWindow = "";
    while (end < S.length()) {
        char c = S.charAt(end);
        if (dict.containsKey(c)) {
            if (found.containsKey(c)) {
                if (found.get(c) < dict.get(c))
                    foundCounter++;
                found.put(c, found.get(c) + 1);
            } else {
                found.put(c, 1);
                foundCounter++;
            }
        }
        if (foundCounter == T.length()) {
            //When foundCounter equals to T.length(), in other words, found all characters.
            char sc = S.charAt(start);
            while (!found.containsKey(sc) || found.get(sc) > dict.get(sc)) {
                if (found.containsKey(sc) && found.get(sc) > dict.get(sc))
                    found.put(sc, found.get(sc) - 1);
                start++;
                sc = S.charAt(start);
            }
            if (end - start + 1 < min) {
                minWindow = S.substring(start, end + 1);
                min = end - start + 1;
            }
        }
        end++;
    }
    return minWindow;
}

Array Solution

To count occurrence of characters, instead of using a hash map, can use an int array of 256
Two pointer method with one point to end and one point to start.
Pointer advance condition: move end forward till finds one window, then move start forward till the window no longer valid

  
  public String minWindow(String S, String T) {
        int[] map=new int[256],found=new int[256];
        int start=0, count=0,end=0,minlen=S.length()+1,tlen=T.length(),slen=S.length();
        String min="";
        for(int i = 0; i < tlen; i++){
            map[T.charAt(i)]++;
        }
        for(;end<slen;end++){
            if(map[S.charAt(end)]>found[S.charAt(end)]) {count++;}
            found[S.charAt(end)]++;
            if(count==T.length()){
                while(found[S.charAt(start)]>map[S.charAt(start)])
                {   found[S.charAt(start)]--;
                    start++;
                }
                if(end-start+1<minlen) {minlen=end-start+1; min = S.substring(start, end+1);
}
                found[S.charAt(start)]--;
                start++;
                count--;
            }
        }
        return min;
    }

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Brute Force Solution

Find all possible substrings and check if each is palindrome. O(N^3) too LTE…

public String longestPalindrome(String s) {
       int maxlen=0; 
       String maxstr=null;
       for(int i=0;i<s.length();i++){
           for(int j=i+1;j<s.length();j++){
               String tmp=s.substring(i,j+1);
               if(IsPalindrome(tmp)&&tmp.length()>maxlen)
                   {
                   maxlen=tmp.length();
                   maxstr=tmp;}
           }
       }return maxstr;
   }
 
 public Boolean IsPalindrome(String s) {
       for(int i=0;i<s.length();i++){
       if(s.charAt(i)!=s.charAt(s.length()-1-i)) return false;
       } return true;
   }

DP Solution

Time O(n^2) Space O(n^2) but didn’t pass OJ. Why?
Three rounds of loops:

set diagonal to 1: t[i][i]=0

set top-right second diagonal: t[i][i+1]=1 if two consecutive character

set whole table [diagonaly]

a. start from substring length 3 to full length

b. inner loop: from 0 to length-len, check substring(i, i+len), set t[i][i+len-1] according to changing rule:

c. If s.charAt(i) == s.charAt(j) then t[i][j] = t[i + 1][j - 1]

public String longestPalindrome2(String s) {
          int maxlen=0; 
          String maxstr=null;
          int[][] t=new int[s.length()][s.length()];
          for(int i=0;i<s.length();i++){t[i][i]=1;}
          for(int i=0;i<s.length()-1;i++){
              if(s.charAt(i)==s.charAt(i+1))
                  {t[i][i+1]=1;
                  maxlen=2;maxstr=s.substring(i,i+2);}
              else t[i][i+1]=0;
              }
          
          printTable(t);
          
          for (int len = 3; len <= s.length(); len++) {
              for (int i = 0; i <= s.length()-len; i++) {
                  int j = i + len - 1;
                  if (s.charAt(i) == s.charAt(j)) {
                      t[i][j] = t[i + 1][j - 1];
                      if (t[i][j] == 1 && len > maxlen)
                          maxstr = s.substring(i, j + 1);
                  } 
                  else {t[i][j]=0;}
                  printTable(t);
              }
          }
          
          return maxstr;
          
    }
      
    public static void printTable(int[][] x){
          for(int [] y : x){
              for(int z: y){
                  System.out.print(z + " ");
              }
              System.out.println();
          }
          System.out.println("------");
      }

Another Algorithm

i from 0 to length-1, get palindrom substring with center of i or i, i+1, keep updating the longest substring: Time O(n^2), space O(1)

public String longestPalindrome(String s) {       
          String maxstr = "";
          for (int i = 0; i < s.length(); i++) {
              // get longest palindrome with center of i eg: BAB
              String tmp = helper(s, i, i);
              if (tmp.length() > maxstr.length()) {
                  maxstr = tmp;
              }
       
              // get longest palindrome with center of i, i+1 eg: ABBA
              tmp = helper(s, i, i + 1);
              if (tmp.length() > maxstr.length()) {
                  maxstr = tmp;
              }
          }
       
          return maxstr;
      }
    
    public static String helper(String s, int begin, int end) {
          while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
              begin--;
              end++;
          }
          return s.substring(begin + 1, end);
          }

Manacher’s algorithm
Computes the longest palindromic substring in linear time.

Remove Duplicates from Sorted List I & II, Remove Duplicates from Sorted Array I & II

Posted on 2015-02-26 | In 刷题 |

Remove Duplicates from Sorted List I

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution

Two loops One pointer solution, only move cursor to next when we confirmed cur.next.val!==cur.val.

public ListNode deleteDuplicates(ListNode head) {
    ListNode h = head;
    if(head==null||head.next==null) return head;
    ListNode cur= head;
    while(cur!=null){
        while(cur.next!=null&&cur.next.val==cur.val)
        cur.next=cur.next.next;
        cur=cur.next;
    }
    return h;
}

Or we can use only one loop:

public ListNode deleteDuplicates(ListNode head) {
      ListNode h = head;
      if(head==null||head.next==null) return head;
      ListNode cur= head;
      while(cur!=null){
          ListNode tmp=cur.next;
          if(tmp!=null&&tmp.val==cur.val){
              cur.next=tmp.next;}
          else cur=cur.next;
      }
      return h;
  }

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution

Similar to how we deleted duplicates in I, now we add a pre pointer to record the last non-duplicate element, and a dummy head to deal with cases where head needs to be removed. Note: we can only move pre to next when we confirmed now cur is pointing to a unique element.

public ListNode deleteDuplicates(ListNode head) {
       ListNode dummy=new ListNode(0);
       dummy.next=head;
       ListNode cur=head, pre=dummy;
       while(cur!=null&& cur.next!=null){
           //if dup found, keep cur at last dup element
           if(cur.val==cur.next.val){
           while(cur.next!=null&&cur.val==cur.next.val){cur=cur.next;}
           //remove the dups, remember to move the cur for detecting more dups
           pre.next=cur.next;
           cur=cur.next;}
           //move the two pointers next when no dup found
           else {pre=pre.next; cur=cur.next;}     
       }       
       return dummy.next;
   }

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

Solution

Just replace current element with the first non-duplicate, in other words, non-equal-to-current element.

public int removeDuplicates(int[] A) {
          int n=A.length;
          int count=0;
          if(A.length==0) return 0;
          for(int i=0;i<n;i++){
              //count points to the last element of our new array, i pointer finds the next non-dup element
              if(A[i]!=A[count]){A[++count]=A[i];}
          }return count+1;
      }

Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].

Solution

The solution is a bit tricky. We use two pointers, pre to keep the second duplicate element, and cur to keep the first element different from current duplicate element. Then we replcace the next element of pre, to whatever next element cur is pointing at.

public int removeDuplicates(int[] A) {
       int n = A.length;
       int pre=1,cur=2;
       if(n==0||n==1||n==2) return n;
       while(cur<n){
           //confirm no three dups in new array  
           if(A[cur]==A[pre-1]){
               //cur points to the first element different from current dups
               cur++;
           }
           else {
               //move pre to the third dup element
               pre++;
               //replace the third dup with the next element 
               A[pre]=A[cur];
               cur++;
           }
       }
       return pre+1;
       
   }

Regular Expression Matching, Edit Distance, Rotate Image, Spiral Matrix

Posted on 2015-02-26 | In 刷题 |

Regular Expression Matching

Implement regular expression matching with support for ‘.’ and ‘‘.
‘.’ Matches any single character.
‘‘ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char s, const char p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “a“) → true
isMatch(“aa”, “.“) → true
isMatch(“ab”, “.“) → true
isMatch(“aab”, “ca*b”) → true

Recursive solution

So hard to think of all the cases….

Base case: p was cut to zero
Special Case: p=1, when to return false? (now p!=’‘, this case will be process next
Case 1: p.charAt(1) is not ‘‘,
Case 2: p.charAt(1) is ‘*’,


  public boolean isMatch(String s, String p){
  //base case
  if(p.length()==0) return s.length()==0;
  //p=1 special case
  if(p.length()==1 || p.charAt(1)!='*'){
    //false case: s len=0; 
        /*if the first char of s and the first char of p is not the same, 
        and the char of p is not '.', return false; 
    if(s.length()<1 || p.charAt(0)!=s.charAt(0) && p.charAt(0)!='.')
      return false;
    //otherwise, compare the rest of the string of s and p.
    else return isMatch(s.substring(1),p.substring(1));
  }
  //p!=1 and  when the second char of p is '*'
  else{
    int i=-1;
    while(i<s.length() && (i< 0 || p.charAt(0)=='.' || p.charAt(0)==s.charAt(i))){
      //start from isMatch(s itself, p.substring(2)) stands for 0 preceding element
      //when the '*' stands for 1 or more preceding element,try every possible number
      if(isMatch(s.substring(i+1), p.substring(2)))
        return true;
      i++;}
  }
  return false;
}

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

Recursive Solution

public int minDistance(String word1, String word2) {
        if(word1.equals(word2)) return 0;
        if(word1==null || word1.length()<=0) return word2.length();
        if(word2==null || word2.length()<=0) return word1.length();
         
        int delete_dis=minDistance(word1.substring(1),word2)+1;  
        int add_dis=minDistance(word1,word2.substring(1))+1;
        int change_dis=minDistance(word1.substring(1),word2.substring(1)) + word1.charAt(0)==word2.charAt(0) ?  0 : 1;
        
        return Math.min(Math.min(delete_dis, add_dis), change_dis);
    
    }

DP Solution


  public int minDistance(String word1, String word2) {
    if(word2.length()==0) return word1.length();
    if(word1.length()==0) return word2.length();
    int m=word1.length()+1, n=word2.length()+1;
    int[][] Dis=new int[m][n];
    //initiate null cases
    for(int i=0;i<m;i++){Dis[i][0]=i;}
    for(int j=0;j<n;j++){Dis[0][j]=j;}
    //fill up whole table
    for(int i=1; i<m;i++){
        for(int j=1;j<n;j++){
            int del_dis=Dis[i-1][j]+1;
            int add_dis=Dis[i][j-1]+1;
            int change_dis=Dis[i-1][j-1]+ (word1.charAt(i-1)==word2.charAt(j-1)? 0 :1);
            Dis[i][j]=Math.min(Math.min(del_dis,add_dis),change_dis);
        }
    }
    return Dis[m-1][n-1];
    
}

Rotate Image

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?

Solution

swap four directions layer by layer:

public void rotate(int[][] matrix) {
  
    int len = matrix[0].length;
    for (int layer = 0; layer < len / 2; layer++) {
      for (int i = layer; i < len - 1 - layer; i++) {
        // save upper
        int temp = matrix[layer][i];
     
        // upper = left
        matrix[layer][i] = matrix[len - 1 - i][layer];
        // left = bottom
   
        matrix[len - 1 - i][layer] = matrix[len - 1 - layer][len - 1 - i];
      
        // bottom = right
        matrix[len - 1 - layer][len - 1 - i] = matrix[i][len - 1 - layer];
        // right = up
        matrix[i][len - 1 - layer] = temp;
        
      }
    }
  }

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Solution

public ArrayList<Integer> spiralOrder(int[][] matrix) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    if(matrix == null || matrix.length == 0) return result;
    int m = matrix.length;
    int n = matrix[0].length;
    int x=0; 
    int y=0;
    while(m>0 && n>0){
        //if one row/column left, no circle can be formed
        if(m==1){
            for(int i=0; i<n; i++){
                result.add(matrix[x][y++]);
            }
            break;
        }else if(n==1){
            for(int i=0; i<m; i++){
                result.add(matrix[x++][y]);
            }
            break;
        }
        //below, process a circle
        //top - move right
        for(int i=0;i<n-1;i++){
            result.add(matrix[x][y++]);
        }
        //right - move down
        for(int i=0;i<m-1;i++){
            result.add(matrix[x++][y]);
        }
        //bottom - move left
        for(int i=0;i<n-1;i++){
            result.add(matrix[x][y--]);
        }
        //left - move up
        for(int i=0;i<m-1;i++){
            result.add(matrix[x--][y]);
        }
        x++;
        y++;
        m=m-2;
        n=n-2;
    }
    return result;
}

Same Tree, Symmetric Tree, Balanced Binary Tree, Binary Tree Level Order Traversal, Binary Tree Level Order Traversal II, Maximum Depth of Binary Tree, Minimum Depth of Binary Tree

Posted on 2015-02-26 | In 刷题 |

Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Recursive Solution

public boolean isSameTree(TreeNode p, TreeNode q) {
      if(p==null && q==null) return true;
      if(p!=null && q!=null && p.val==q.val){
          return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
      }
      return false;
  }

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:

But the following is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

Recursive Solution

Just traverse both on left and right branches of the root symmetricaly and check if the values are equal.

public boolean isSymmetric(TreeNode root) {
     if(root==null) return true;
     return rec(root.left ,root.right);
 }
 
 private boolean rec(TreeNode l, TreeNode r){
     if(l==null && r==null) return true;
     else if(l!=null && r!=null && l.val==r.val) 
     return rec(l.left,r.right) && rec(l.right, r.left);
     else return false;
 }

Iterative Solution

Two Stacks to store the two partitions of nodes that are supposed to be equal.

public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        Stack<TreeNode> l=new Stack<TreeNode>();
        Stack<TreeNode> r=new Stack<TreeNode>();
        l.push(root.left);
        r.push(root.right);
        while(!l.isEmpty() && ! r.isEmpty()){
            TreeNode left=l.pop();
            TreeNode right=r.pop();
            if(left==null && right==null) continue;
            else if(left!=null && right!=null && right.val==left.val){
                l.push(left.left); l.push(left.right);
                r.push(right.right); r.push(right.left); 
            } 
            else return false;
        }
        return true;
    }

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Recursive Solution

Two Nested Recursive:

getheight returns the highest depths of current node

break and return false if two children’s height differ by more than 1

else continue checking for both children, until reached null node.

public boolean isBalanced(TreeNode root) {
      if(root==null) return true;
      if(Math.abs(getheight(root.left) - getheight(root.right)) > 1) return false;
      return isBalanced(root.left) && isBalanced(root.right);
  }
  
  private int getheight(TreeNode cur){
      if(cur==null) return 1;
      return 1+Math.max(getheight(cur.left), getheight(cur.right));
  }

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

BFS Solution

use two queues to store all nodes on the current level and their children level, when current level queue is empty, go to the next level

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> curlevel=new LinkedList<TreeNode>();
        Queue<TreeNode> nextlevel=new LinkedList<TreeNode>();
        if(root==null) return res;
        curlevel.add(root);
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        while(!curlevel.isEmpty())
        {
            TreeNode cur=curlevel.poll();
            tmp.add(cur.val);
            if(cur.left!=null)
            nextlevel.add(cur.left);
            if(cur.right!=null)
            nextlevel.add(cur.right);
            
            if(curlevel.isEmpty()){
              curlevel=nextlevel;
              nextlevel=new LinkedList<TreeNode>();
              res.add(new ArrayList<Integer>(tmp));
              tmp.clear();
            }
        }
        return res;
    }

DFS Solution

recursively add new levels to the list, keep a variable height to track when to create new list:

int height=0;
   public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
    ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
    dfs(res, root,0);
    return res;
 }
 private void dfs( ArrayList<ArrayList<Integer>> res, TreeNode root, int height){
    if(root==null) return;
    if(height>=res.size()){
      res.add(new ArrayList<Integer>());
    }
    res.get(height).add(root.val);
    dfs(res, root.left, height+1);
    dfs(res, root.right, height+1);
 }

Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

BFS Solution

Just reverse the result list at the end…

public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> curlevel=new LinkedList<TreeNode>();
        Queue<TreeNode> nextlevel=new LinkedList<TreeNode>();
        if(root==null) return res;
        curlevel.add(root);
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        while(!curlevel.isEmpty())
        {
            TreeNode cur=curlevel.poll();
            tmp.add(cur.val);
            if(cur.left!=null)
            nextlevel.add(cur.left);
            if(cur.right!=null)
            nextlevel.add(cur.right);
            
            if(curlevel.isEmpty()){
              curlevel=nextlevel;
              nextlevel=new LinkedList<TreeNode>();
              res.add(new ArrayList<Integer>(tmp));
              tmp.clear();
            }
        }
        ArrayList<ArrayList<Integer>> resnew=new ArrayList<ArrayList<Integer>>();
        for(int i=res.size()-1;i>=0;i--){
            resnew.add(res.get(i));
        }
        return resnew;
    }

Or More concise


public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
      ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
      Queue<TreeNode> curlevel=new LinkedList<TreeNode>();
      if(root==null) return res;
      curlevel.add(root);
      while(!curlevel.isEmpty())
      {
         int levelnum=curlevel.size();
         ArrayList<Integer> tmp = new ArrayList<Integer>();
         for(int i=0;i<levelnum;i++){
             if(curlevel.peek().left!=null) curlevel.offer(curlevel.peek().left);
             if(curlevel.peek().right!=null) curlevel.offer(curlevel.peek().right);
             tmp.add(curlevel.poll().val);
         }
         res.add(0,tmp);
      }
      
      return res;
  }

DFS Solution

int height=0;
   public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root){
    ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
    dfs(res, root,0);
    return res;
 }
 private void dfs( ArrayList<ArrayList<Integer>> res, TreeNode root, int height){
    if(root==null) return;
    if(height>=res.size()){
      res.add(0,new ArrayList<Integer>());
    }
    res.get(res.size()-height-1).add(root.val);
    dfs(res, root.left, height+1);
    dfs(res, root.right, height+1);
 }

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

DFS Solution

public int maxDepth(TreeNode root) {
    if(root==null) return 0;
    return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}

Iterative Solution

Use a List to store BFS nodes, and an extra node to keep track of the last node on current level:

public int maxDepth(TreeNode root) {
      int depth=0;
      if(root==null) return depth;
      LinkedList<TreeNode> q=new LinkedList<TreeNode>();
      q.offer(root);
      TreeNode levelend=root, tmp;
      while(!q.isEmpty()){
          tmp=q.poll();
          if(tmp.left!=null) q.offer(tmp.left);
          if(tmp.right!=null) q.offer(tmp.right);
          if(tmp==levelend){
              depth++;
              levelend=q.peekLast();
          }
      } return depth;
  }

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

DFS Solution

A little different from max path: when one child is null, return the other half, when both is null return 1

public int minDepth(TreeNode root) {
    if(root==null) return 0;
    if(root.left==null && root.right==null) return 1;
    if(root.left==null) return minDepth(root.right)+1;
    else if(root.right==null) return minDepth(root.left)+1;
    else return Math.min(minDepth(root.left), minDepth(root.right))+1;
}

BFS Solution

One List to store BFS nodes, one list to store depth, min path found when reached any leaf:

public int minDepth(TreeNode root) {
    if(root == null) return 0;
    int res=0;
    LinkedList<TreeNode> l=new LinkedList<TreeNode>();
    LinkedList<Integer> count=new LinkedList<Integer>();
    l.offer(root); count.offer(1);
    while(!l.isEmpty()){
        TreeNode tmp=l.poll();
        res=count.poll();
        if(tmp.left!=null){
            l.offer(tmp.left);
            count.offer(res+1);
        }
        if(tmp.right!=null){
            l.offer(tmp.right);
            count.offer(res+1);
            }
        if(tmp.left==null && tmp.right==null) return res;    
    } return 0;
}

Construct Binary Tree from Preorder and Inorder Traversal, Construct Binary Tree from Inorder and Postorder Traversal, Binary Tree Inorder Traversal, Convert Sorted Array to Binary Search Tree, Convert Sorted List to Binary Search Tree, Flatten Binary Tree to Linked List

Posted on 2015-02-26 | In 刷题 |

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

Solution

int pre=0;
public TreeNode buildTree(int[] preorder, int[] inorder) {
    //if(preorder.length==0||inorder.length==0){return null;}
    int l=0;
    int r=preorder.length-1;
    return build(preorder,inorder,l, r);
}
public TreeNode build(int[] preorder, int[] inorder,int l, int r){
    if(l>r){return null;}
    int cur=preorder[pre];
    TreeNode node=new TreeNode(cur);
    pre++;
    int i=0;
    for (i=l; i<=r; i++){
        if(inorder[i]==cur)
        {break;}
    }
     
    node.left=build(preorder,inorder,l, i-1);
    node.right=build(preorder,inorder,i+1, r);
    
   return node;
}

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

Almost the same with previous one, only this time we scan postorder from backwards and recursively add to the right subtree first.

int pos=0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        pos=inorder.length-1;
       return helper(inorder, postorder, 0, inorder.length-1);
    }
    
    private TreeNode helper(int[] inorder, int[] postorder, int l, int r){
            if(l>r) return null;
            int cur=postorder[pos];
            TreeNode tmp=new TreeNode(cur);
            pos--;
            int i=l;
            for(;i<=r;i++){
                if(inorder[i]==cur) break;
            }
            
            tmp.right=helper(inorder,postorder, i+1, r);
            tmp.left=helper(inorder, postorder, l, i-1);
            return tmp;
    }

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},

return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

Recursive Method(Trivial)

public ArrayList<Integer> inorderTraversal(TreeNode root) {
    ArrayList<Integer> res= new ArrayList<Integer>();
      //第一次没过..少了这句
      if(root==null) return res;
    return helper(root,res);
}
private  ArrayList<Integer> helper(TreeNode cur,ArrayList<Integer> res){
    if(cur==null) return null;
    helper(cur.left, res);
    res.add(cur.val);
    helper(cur.right, res);
    return res;
}

Iterative Method

Inorder: left child -> parent -> right child

Use a stack to track nodes

Exit while loop when stack is empty and current node is null

push nodes in the stack when current node is not null, then move to left subtree
pop node when current node is null, move to right subtree

public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res= new ArrayList<Integer>();
        Stack<TreeNode> nodestack=new Stack<TreeNode>();
        if(root==null) return res;
        while(!nodestack.isEmpty() || root!=null){
            if(root!=null){
                nodestack.push(root);
                root=root.left;
            }
            else{
                TreeNode tmp=nodestack.pop();
                res.add(tmp.val);
                root=tmp.right;
            }
        }
        return res;
}

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Solution

Use recursion, find median element each time, move to left/right subtree.

public TreeNode sortedArrayToBST(int[] num) {
       return helper(num, 0, num.length-1);
   }
   
   private TreeNode helper(int[] num,int l, int r){
       if(l>r) return null;
       int mid=(l+r)/2;
       TreeNode newnode=new TreeNode(num[mid]);
       newnode.left=helper(num, l, mid-1);
       newnode.right=helper(num, mid+1, r);
       return newnode;
   }

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Naive Solution

Just convert LinkedList to Array first…

public TreeNode sortedListToBST(ListNode head) {
       ListNode cur = head;
       List<Integer> res = new ArrayList<Integer>();
       while (cur != null) {
           res.add(cur.val);
           cur = cur.next;
       }
       return helper(res, 0, res.size() - 1);
   }
    private TreeNode helper(List<Integer> res,int l, int r){
       if(l>r) return null;
       int mid=(l+r)/2;
       TreeNode newnode=new TreeNode(res.get(mid));
       newnode.left=helper(res, l, mid-1);
       newnode.right=helper(res, mid+1, r);
       return newnode;
   }

Recursive Solution

The trick here is to use two pointers, one slow and one twice the speed, to find the median element.

public static TreeNode sortedListToBST(ListNode head) {  
        return rec(head, null);  
    }  
      
    // 在区间[start, end)里递归，后面的end是包括在内的，这样可以避免要多用一个指针来记录mid前的节点  
    public static TreeNode rec(ListNode start, ListNode end){  
        if(start == end){  
            return null;  
        }  
          
        // 一次遍历找到中点的方法：快慢指针  
        ListNode mid = start;           // 该指针最终会指向中点  
        ListNode probe = start;         // 探针最终会到达end  
        while(probe!=end && probe.next!=end){       // 探针完成搜索，注意停止条件是和end比较而不是和null比！  
            mid = mid.next;  
            probe = probe.next.next;  
        }  
          
        TreeNode root = new TreeNode(mid.val);  
        root.left = rec(start, mid);  
        root.right = rec(mid.next, end);  
        return root;  
    }

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.
For example,
Given

The flattened tree should look like:

Iterative Solution

Using a stack to solve this problem is easy: start from root, push right, left into stack. If stack is not empty, set cur.right to stack.peek(). Continue to process the next node from top of stack.
But to do it inplace requires to keep track of the origin right node. Overall process is to squeeze the left node into between its parents and right child.

public void flatten(TreeNode root) {
        TreeNode head=new TreeNode(0);
        head.right=root;
        TreeNode cur=head;
        
        while(cur.right!=null){
            cur=cur.right;
            if(cur.left!=null){
                TreeNode end=cur.left;
                while(end.right!=null)
                end=end.right;
                TreeNode tmp=tmp=cur.right;
                cur.right=cur.left;
                end.right=tmp;
                cur.left=null;
            }
        } head.right=null;
        
    }

«1…456 »

目录

Roman to Integer

Solution

Integer to Roman

Solution

ZigZag Conversion

Solution

Majority Element

Two pass solution

Moore voting algorithm

Gray Code

Recursive solution

Iterative Solution

Reverse Integer

First Solution:

Correct Solution:

Reverse Linked List II

Reverse a Singly LinkedList

Better solution:

Correct Solution:

Reverse Nodes in k-Group

Iterative Solution:

Two Pass Solution:

Rotate List

Naive Solution

Substring with Concatenation of All Words

Brute Force Solution

Longest Substring Without Repeating Characters

Brute force method

Minimum Window Substring

Array Solution

Longest Palindromic Substring

Brute Force Solution

DP Solution

Remove Duplicates from Sorted List I

Solution

Remove Duplicates from Sorted List II

Solution

Remove Duplicates from Sorted Array

Solution

Remove Duplicates from Sorted Array II

Solution

Regular Expression Matching

Recursive solution

Edit Distance

Recursive Solution

DP Solution

Rotate Image

Solution

Spiral Matrix

Solution

Same Tree

Recursive Solution

Symmetric Tree

Recursive Solution

Iterative Solution

Balanced Binary Tree

Recursive Solution

Binary Tree Level Order Traversal

BFS Solution

DFS Solution

Binary Tree Level Order Traversal II

BFS Solution

DFS Solution

Maximum Depth of Binary Tree

DFS Solution

Iterative Solution

Minimum Depth of Binary Tree

DFS Solution

BFS Solution

Construct Binary Tree from Preorder and Inorder Traversal

Solution

Construct Binary Tree from Inorder and Postorder Traversal

Binary Tree Inorder Traversal

Recursive Method(Trivial)

Iterative Method

Convert Sorted Array to Binary Search Tree

Solution

Convert Sorted List to Binary Search Tree

Naive Solution