并查集概述

并查集（Union-Find）是一种用于处理集合关系的算法，在连通图的相关问题中非常实用。基本的操作包括集合的并（Union）和查找元素所属集合（Find）。

算法思路如下：每一个集合，都有一个代表元。在同一个集合中的所有元素，它们的代表元必然相同。要区分一个元素属于哪一个集合，找到它的代表元即可。

其存储结构通常为一个一维数组（N代表元素总数）：

1

int father[N + 1] = { 0 };

初始化如下：

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

for (int i = 1; i <= N; i++) {
    father[i] = i;
}
``` 
那么根据定义，用于查找某个元素所在集合的代表元的函数可以这样实现：
```c++
int getFather(int x) {
    if (father[x] == x) {
        return x;
    } else {
        return getFather(father[x]);
    }
}

但是，当元素数量很大，多次的递归显然效率较低。那么，可以引入“压缩路径”的方法：

1
2
3
4
5
6
7
8
9
10

int getFather(int x) {
    if (father[x] == x) {
        return x;
    }
    else {
        int xFather = getFather(father[x]);
        father[x] = xFather;
        return xFather;
    }
}

这样，在每一次递归之后，都会更新father[x]的值，实现了压缩路径的目的，避免了多次重复的递归。这种方式实现的并查集，时间复杂度为O(n)。

题目描述

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:
Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note:

1. The length of the given array will not exceed 15.
2. The range of integer in the given array is [-100,100].
3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

题目大意是：从给定的一组数中，找到所有递增的子序列。但其实这里的递增（increasing）包含了所有非递减的子序列，从样例中可知。还有一点需要注意的是，题目给定的一组数（vector<int> nums）其实是有序的，即不能通过改变nums中的数的顺序来获取递增的子序列。虽然这一点在题目中没有明确说明，但是评测中会有这么一个样例：

Input: [4,3,2,1]
Output: []

因此，在实现时还要注意保持nums中数列的顺序。

Selection问题

题目描述

有一道经典的算法题”Selection”

SELECTION
Input: A list of numbers S; an integer k
Output: The kth smallest element of S
For instance, if k = 1, the minimum of S is sought, whereas if k = |S|/2, it is the median.

算法分析

这道题有很多解法，最简单的就是先对所有数排序。但是显然当数据较大时，这种方法效率不高。使用分治算法就可以在此基础上提高效率，因为只需对一部分而不是全部数据进行排序。
大致思路如下：每一次，先从数组中选出任意一个参考数pivot。选取的方法几乎不会影响效率，一般来说随机选取即可。选取好pivot后，对数组进行遍历，将所有数据分为三组，即小于，等于，大于pivot的三组。例如：

若选取5作为参考数，则分成的三组为：

分组后，根据各组中数的数量，即可进行下一层递归，因此算法如下：

O(nlogn)实现

题目描述

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

算法分析

题目要求为在一个二维矩阵中查找一个数，找到则返回true，否则返回false。
遇到查找的问题，我首先想到的是使用二分法。但是由于题目中的矩阵，虽然每一行每一列都是有序的，但是无法确定matrix[i+1][j]和matrix[i][j+1]的大小关系，因此，考虑对这个二维矩阵拆分为两层一维，并分别使用二分法。首先，用一次二分法确定行的范围：

题目描述

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:
Given [3, 1, 5, 8]
Return 167
nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []
coins = 315 + 358 + 138 + 181 = 167

算法分析

对于这个问题，难以直接找到一个公式化的方法。但是，注意到，每一个大区间所能获得的最大金币数（指的是当这一区间内所有的气球都已经被引爆后，获得的金币数），是取决于它之中的小区间的最大金币数的。且分出的子问题规模较小，易于解决。于是，我们可以才有自顶向下的分治算法来解决。

题目描述

在众多的数据结构中，二叉树是一种特殊而重要的结构，有着广泛的应用。二叉树或者是一个结点，或者有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。

遍历一棵二叉树就是按某条搜索路径巡访其中每个结点，使得每个结点均被访问一次，而且仅被访问一次。最常使用的有三种遍历的方式：

１．前序遍历：若二叉树为空，则空操作；否则先访问根结点，接着前序遍历左子树，最后再前序遍历右子树。

２．中序遍历：若二叉树为空，则空操作；否则先中序遍历左子树，接着访问根结点，最后再前中遍历右子树。

３．后序遍历：若二叉树为空，则空操作；否则先后序遍历左子树，接着后序遍历右子树，最后再访问根结点。

对一棵二叉树，如果给出前序遍历和中许遍历的结点访问顺序，那么后序遍历的顺序是唯一确定的，也很方便地求出来。但如果现在只知道前序遍历和后序遍历的顺序，中序遍历的顺序是不确定的，例如：前序遍历的顺序是ABCD，而后序遍历的顺序是CBDA，那么就有两课二叉树满足这样的顺序（见图(1)和图(2)）。

现在的问题是给定前序遍历和后序遍历的顺序，要求出总共有多少棵不同形态的二叉树满足这样的遍历顺序。

Input

整个输入有两行，第一行给出前序遍历的访问顺序，第二行给出后序遍历的访问顺序。

二叉树的结点用一个大写字母表示，不会有两个结点标上相同字母。输入数据不包含空格，且保证至少有一棵二叉树符合要求。

Output

输出一个整数，为符合要求的不同形态二叉树的数目。

Sample Input

ABCD
CBDA

Sample Output

2

算法分析

首先思考：什么样的两棵不同二叉树，会有相同的先序遍历和后序遍历呢？

根据中序遍历和先序遍历，或者根据中序遍历和后序遍历，都能够确定唯一的一棵二叉树，但是只根据先序遍历和后序遍历，是无法达到这个目的的。

原因如下：
先序遍历和后序遍历有一个共同的缺点，即无法确定一个子结点，是它的父结点的左儿子还是右儿子。

例如：

A 　　　　A
/　　　　　\
B　　　　　B
\　　　　　／
C　　　　 C

以上两棵二叉树，结构明显不同，但是先序遍历都是ABC，后序遍历都是CBA。而只有通过中序遍历，才能找到两者的区别：前者是BCA，后者是ACB。而在先序和后序遍历结果相同的情况下，导致结构差异产生的，便是子树所在的左/右方向不同。

那么，原问题就可以转化为：根据先序和后序遍历，求这样的二叉树中只有一个子树的结点的个数n，那么，2的n次方即是不同形态的二叉树的数量。

接下来，要用简单的方法解出这道题，首先要弄清楚先序遍历和后序遍历的规律。

以题目中的先序ABCD，后序CBDA为例，先序遍历的第一个结点A，以及后序遍历的最后一个结点A，必定是整棵二叉树的根结点。先序遍历中，根结点的后一位B，一定是A的子结点，但暂时无法确定是左子树还是右子树，只能根据先序遍历的顺序暂时默认为左子树。后序遍历中，根结点的前一位D，也一定是A的子结点，那么默认为A的右子树。显然，B、D分别是A的左、右子结点，A并不是我们想找的只有一个子树的父结点。只有当先序中A的后一位，与后序中A的前一位相同时，可以确定，A只有一个子树。

代码实现

根据这种规律，可以写出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main() {
    string pre;
    string post;
    cin >> pre >> post;
    int counter = 0;
    // 遍历先序中的每一个结点
    for (int i = 0; i < pre.length(); i++)
        for (int j = post.length() - 1; j >= 0; j--)
        // 对于先序中的每一个结点，在后序中找到
            if (pre[i] == post[j]) {
                if (i != pre.length() - 1 && j != 0 && pre[i + 1] == post[j - 1])
            // 先序中该结点的后一位，与后序中该结点的前一位相同时，计数器++
                    counter++;
                break;
            }
    int answer = pow(2, counter);
    cout << answer << endl;
    return 0;
}

本文为博主原创文章，转载请注明出处。

题目描述

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.

Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484.

Given any positive integer N, you are supposed to find its paired palindromic number and the number of steps taken to find it.

Input Specification:

Each input file contains one test case. Each case consists of two positive numbers N and K, where N (<= 1010) is the initial numer and K (<= 100) is the maximum number of steps. The numbers are separated by a space.

题目描述

题目如下：
Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:
•The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
•Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
•Customer[i] will take T[i] minutes to have his/her transaction processed.
•The first N customers are assumed to be served at 8:00am.

Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.