0%

打算分为以下几个方面记录一些校园资料。虽然大部分都被我存到笔记软件中,以后就放这里吧。笔记软件里面的东西越来越多,尽管已经为每篇笔记设置了标签和分类,但依然有点冗肿了,并且搜索有点慢。

阅读全文 »

随着认识的积累,对编程语言的看法也在改变。

以下内容,纯吐槽。

C,C++,Java

本科的时候只接触了C,C++,Java,那就先吐槽一下他们吧。

期初很狭隘的认为学习一两个编程语言就足够了,这样就可以做许多东西了,学那么多编程语言有必要吗?

阅读全文 »

列出的解答仅为自己的思路,仅供参考,欢迎指出错误。

题目Wiki及参考答案

http://www.algorithm.cs.sunysb.edu/algowiki/index.php/Weighted-graphs-TADM2E

该页面答案,也是由用户编辑的,不确定是完全的正确。

MST

6-2 最短路径与MST

题目

Is the path between two vertices in a minimum spanning tree necessarily a shortest path between the two vertices in the full graph? Give a proof or a counterexample.

阅读全文 »

列出的解答仅为自己的思路,仅供参考,欢迎指出错误。

题目Wiki及参考答案

http://www.algorithm.cs.sunysb.edu/algowiki/index.php/Search-TADM2E

该页面答案,也是由用户编辑的,不确定是完全的正确。

Backtracking

7-1 permutations

题目

A derangement is a permutation p of {1,…,n} such that no item is in its proper position, i.e. pi≠i for all 1≤i≤n. derangement Write an efficient backtracking program with pruning that constructs all the derangements of n items.

阅读全文 »

列出的解答仅为自己的思路,仅供参考,欢迎指出错误。

题目Wiki及参考答案

http://www.algorithm.cs.sunysb.edu/algowiki/index.php/Graphs-TADM2E

我的解答

遍历

5-6

题目

In breadth-first and depth-first search, an undiscovered node is marked discovered when it is first encountered, and marked processed when it has been completely searched. At any given moment, several nodes might be simultaneously in the discovered state.
(a) Describe a graph on n vertices and a particular starting vertex v such that Θ(n) nodes are simultaneously in the discovered state during a breadth-first search starting from v.
(b) Describe a graph on n vertices and a particular starting vertex v such that Θ(n) nodes are simultaneously in the discovered state during a depth-first search starting from v.
(c) Describe a graph on n vertices and a particular starting vertex v such that at some point Θ(n) nodes remain undiscovered, while Θ(n) nodes have been processed during a depth-first search starting from v. (Note, there may also be discovered nodes.)

解答

(a) Wrost case: 所有的节点都与根节点v直接相连。
(b) Wrost case: 所有的节点的出度都小于等于2,即所有的点都在一条线上。
(c) 非连通图。

阅读全文 »

列出的解答仅为自己的思路,仅供参考,欢迎指出错误。

题目Wiki及参考答案

http://www.algorithm.cs.sunysb.edu/algowiki/index.php/Sorting-searching-TADM2E

我的解答

面试问题

4-45

题目

Given a search string of three words, find the smallest snippet of the document that contains all three of the search words—i.e., the snippet with smallest number of words in it. You are given the index positions where these words occur in the document, such as word1: (1, 4, 5), word2: (3, 9, 10), and word3: (2, 6, 15). Each of the lists are in sorted order, as above.

解答

每个单词出现的位置列表都是有序的,将它们看做是队列。设定min_len保存当前最短的片段的长度,初始化为-1.算法步骤如下:

  1. 若各队列不空,将各队列最小元素出队,组成三元组
  2. 得三元组(a1, a2, a3)
  3. 求三元组中的最大值max,与最小值min,则当前片段长度len = max-min+1
  4. 如果min_len为-1或min_len大于lenmin_len = len,保存三元组.
  5. 删除三元组中最小者min,若min对应队列不空,取新元素加入到三元组,执行2,若空,退出循环。
变形及分析

变形

假设输入数据不是3个单词的出现位置,而直接是一个字符串数组,那么如何找到满足要求的最小片段?

分析

cur为访问数组的当前位置,3个变量l1, l2, l3,代表cur前面离cur最近的3个单词(w1, w2, w3)的位置。若cur上的单词为3个单词之一,不妨设为w3,则计算w3与w1,w2的距离即cur-l1+1cur-l2+1,取小者为min,另minmin_len比较,若min更小,保存min,及当前3个单词的位置。当遍历数组结束时,最后的min_len与保存的3元素的位置即满足要求的最小片段。

阅读全文 »