题目描述

英文题目

• Implement int sqrt(int x).

  Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

  Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

  Example 1:

  1 2	Input: 4 Output: 2

  Example 2:

  1 2 3 4

  Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

中文题目

• 实现 int sqrt(int x) 函数。

  计算并返回 x 的平方根，其中 x 是非负整数。

  由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

  示例 1:

  1 2	输入: 4 输出: 2

  示例 2:

  1 2 3 4

  输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

介绍

分析

基本思想:

通过一遍排序将需要排序的数据分成两部分，使其中一部分数据比另一部数据小，然后再分别对这两部分继续进行这种排序，按此规则继续，直到每个部分为空或者只含一个数时，整个排序结束。

算法描述:

1. 从数列中挑出一个元素，称该元素为“基准”
2. 扫描一遍数列，将所有比“基准”小的元素排在基准前面，所有比“基准“大的元素排在基准后面
3. 通过递归，将各子序列划分为更小的序列，直到把小于基准值元素的子数列和大于基准值元素的子数列排序

介绍

将两个有序数列合并成一个有序数列

根据实现方式分为“从上往下”和“从下往上”两种方式

分析图使用的graphviz

介绍

分析

基本思想:

1

将需要排序的序列划分为若干个较小的序列，对这些序列进行直接插入排序，通过这样的操作可使需要排序的数列基本有序，最后再使用一次直接插入排序对整个数列进行排序

算法描述:

1. 首先使用元素数量的一半作为增量，划分为n/2个子序列，分别对这些子序列分别进行插入排序
2. 再原有增量基础上，缩小一般，划分为n/4个子序列，分别对这些子序列分别进行插入排序
3. 重复上述步骤，知道n/4>=1，对整个序列进行插入排序

介绍

分析

基本思想:

1

对n个记录进行扫描，选择最小的记录，将其输出，接着在剩下的n-1个记录中扫描，选择最小的记录将其输出，不断重复这个过程，直到只剩下一个记录为止，即可完成数据从小到大的排序过程

算法描述:

1. 从数据中选择最小（或最大）的一个数据，然后将该数与第一个数交换
2. 从剩下数据中选择最小（或最大）的一个数，然后将和第二个数进行交换
3. 重复下去，直到只剩下一个数据为止

介绍

分析

基本思想:

1

通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到对应位置并插入该数据，使数据形成有序排列

算法描述:

1. 第1个元素，作为有序序列
2. 从数组中获取下一个元素，在已排序的元素序列中从后向前扫描，并判断给元素与已排序元素的大小
3. 若排序序列的元素大于新元素，则将排序序列该元素移到下一位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置
6. 重复步骤2-5，直到处理完成

介绍

分析

基本思想:

1

对排序记录关键字从后往前（逆序）进行多遍扫描，当发现两个关键字的次序与排序要求的规则不符时，就将这两个记录进行交换

算法描述:

1. 将A[n]与A[n-1]进行比较，若A[n] < A[n-1],则交换两元素的位置
2. 修改数组下标，是需要比较的两个元素为A[n-1]和A[n-2]，重复步骤1，直到A[2]和A[1]比较完成为止，即完成第一遍扫描
3. 经过第一遍扫描，最小的或最大的已经排到最上面A[1]，进行第二遍扫描，只扫描到A[3]与A[2]进行比较为止
4. 经过n-1遍扫描，前n-1个数都已经排序完成，最后一个A[n]肯定最大或最小

递归需要满足的三个条件

1. 一个问题的解可以分解为几个子问题的解
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
3. 存在递归终止条件

如何编写递归代码？

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归弊端

堆栈溢出（限制递归调用的最大深度)

重复计算（通过一个数据结构（比如散列表）来保存已经求解过的 f(k)，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算）

函数调用耗时多

空间复杂度高

我们平时调试代码喜欢使用 IDE 的单步跟踪功能，像规模比较大、递归层次很深的递归代码，几乎无法使用这种调试方式。对于递归代码，你有什么好的调试方法呢？

调试递归:
1.打印日志发现，递归值。
2.结合条件断点进行调试。

分治公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

divide_conquer(problem, param1, param2, ...)

# recursion terminator
if problem结束
	print_result
	return
	
#prepare data
data = prepare_data(problem)
subproblems = split_proble(problem, data)

# conquer subproblems
subresult1 = self.divide_conquer(subproblesm[0], p1,...)
subresult2 = self.divide_conquer(subproblesm[1], p1,...)
...

# process and generate the final result
result = process_result(subresult1, subresult2, subresult3, ...)

递归公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

recursion(level, param1, param2, ...)

# recursion terminator
if level > MAX_LEVEL
	print_result
	return
	
#prepare logic in current level
process_data(level, data, ...)

# drill down
self.recursion(level + 1, p1, ...)

# reverse the current level status if needed
reverse_state(level)

题目描述

英文题目

• Implement the following operations of a queue using stacks.

  • push(x) – Push element x to the back of queue.
  • pop() – Removes the element from in front of queue.
  • peek() – Get the front element.
  • empty() – Return whether the queue is empty.

  Example:

  1 2 3 4 5 6 7

  MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false

  Notes:

  • You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

中文题目

• 使用栈实现队列的下列操作：

  • push(x) – 将一个元素放入队列的尾部。
  • pop() – 从队列首部移除元素。
  • peek() – 返回队列首部的元素。
  • empty() – 返回队列是否为空。

  示例:

  1 2 3 4 5 6 7

  MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false

  说明:

  • 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

###

题目描述

英文题目

Implement the following operations of a stack using queues.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• empty() – Return whether the stack is empty.

Example:

1
2
3
4
5
6
7

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

• You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

中文题目

使用队列实现栈的下列操作：

• push(x) – 元素 x 入栈
• pop() – 移除栈顶元素
• top() – 获取栈顶元素
• empty() – 返回栈是否为空

注意:

• 你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。