发表于

Distinct Subsequences

题目描述

Given a string S and a string T, count the number of distinct subsequences of S which equals T.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

Example 1:

Input: S = “rabbbit”, T = “rabbit”
Output: 3

Example 2:

Input: S = “babgbag”, T = “bag”
Output: 5

解题思路

本题给出了字符串S和字符串T，要求找出S有多少个子字符串与T相同。
使用二维数组count，count[i][j]表示S的前j个字符组成的字符串有多少个子字符串与T的前i个字符组成的字符串相同，假设n为S字符串的长度，m为T字符串的长度，那么count[m][n]即为所求。具体步骤如下：

  • 首先初始化数组的第一行count[0][j]=1，即当T为空串时，S有一个子字符串（空串）与T相同。
  • 除第一行外，初始化数组的第一列count[i][0]=0，即当S为空串时，没有子字符串与T相同。
  • 依次计算数组的每一行，当比较到S[j-1] == T[i-1]时，count[i][j] = count[i][j-1] + count[i-1][j-1]，否则count[i][j] = count[i][j-1]。这是因为当S的当前字符与T的当前字符不相同时，我们并没有得到新的字符因此数量与前面相等；当S的当前字符与T的当前字符相同时，可从下列表格得出规律。

以样例1为例：

Ø r a b b b i t
Ø 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1
a 0 0 1 1 1 1 1
b 0 0 0 1 2 3 3
b 0 0 0 0 1 3 3
i 0 0 0 0 0 3 3
t 0 0 0 0 0 0 3

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int numDistinct(string s, string t) {
        int n = s.length();
        int m = t.length();
        vector<vector<int>> count(m + 1, vector<int>(n + 1, 0));
        for(int i = 0; i < n + 1; i++) {
            count[0][i] = 1;
        }
        for(int i = 1; i < m + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                if(s[j - 1] == t[i - 1]) {
                    count[i][j] = count[i][j-1] + count[i-1][j-1];
                }
                else {
                    count[i][j] = count[i][j-1];
                }
            }
        }
        return count[m][n];
    }
};

发表于 | 更新于

算法分类

常见的排序算法可分为两大类：

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

图1

算法复杂度

排序算法 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度 稳定性
插入排序 \(O(n^2)\) \(O(n^2)\) \(O(n)\) \(O(1)\) 稳定
希尔排序 \(O(n^{1.3})\) \(O(n^2)\) \(O(n)\) \(O(1)\) 不稳定
选择排序 \(O(n^2)\) \(O(n^2)\) \(O(n^2)\) \(O(1)\) 不稳定
堆排序 \(O(nlogn)\) \(O(nlogn)\) \(O(nlogn)\) \(O(1)\) 不稳定
冒泡排序 \(O(n^2)\) \(O(n^2)\) \(O(n)\) \(O(1)\) 稳定
快速排序 \(O(nlogn)\) \(O(n^2)\) \(O(nlogn)\) \(O(nlogn)\) 不稳定
归并排序 \(O(nlogn)\) \(O(nlogn)\) \(O(nlogn)\) \(O(n)\) 稳定
计数排序 \(O(n+k)\) \(O(n+k)\) \(O(n+k)\) \(O(n+k)\) 稳定
桶排序 \(O(n+k)\) \(O(n^2)\) \(O(n)\) \(O(n+k)\) 稳定
基数排序 \(O(nlog(r)m)\) \(O(nlog(r)m)\) \(O(nlog(r)m)\) \(O(n+m)\) 稳定

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

七个常用排序算法

冒泡排序

冒泡排序重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void swap(int &a, int &b) {
	int temp = a;
	a = b;
	b = temp;
}
void bubbleSort(vector<int> &arr) {
	int n = arr.size();
	bool flag = false;
	for (int i = 0; i < n - 1; i++) {
		flag = true;
		for (int j = 0; j < n - 1 - i; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
				flag = false;
			}
		}
		if (flag) break;
	}
}

选择排序

它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void swap(int &a, int &b) {
	int temp = a;
	a = b;
	b = temp;
}
void selectionSort(vector<int> &arr) {
	int n = arr.size();
	int minIndex;
	for (int i = 0; i < n - 1; i++) {
		minIndex = i;
		for (int j = i + 1; j < n; j++) {
			if (arr[j] < arr[minIndex]) {
				minIndex = j;
			}
		}
		if (minIndex != i) {
			swap(arr[i], arr[minIndex]);
		}
	}
}

插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。

1
2
3
4
5
6
7
8
9
10
11
12
void insertionSort(vector<int> &arr) {
	int n = arr.size();
	for (int i = 1; i < n; i++) {
		int cur = arr[i];
		int preIndex = i - 1;
		while (preIndex >= 0 && arr[preIndex] > cur) {
			arr[preIndex + 1] = arr[preIndex];
			preIndex--;
		}
		arr[preIndex + 1] = cur;
	}
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

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
26
27
28
29
vector<int> merge(const vector<int> &left, const vector<int> &right) {
	vector<int> res;
	int i = 0, j = 0;
	while (i < left.size() && j < right.size()) {
		if (left[i] < right[j]) {
			res.push_back(left[i++]);
		}
		else {
			res.push_back(right[j++]);
		}
	}
	while (i < left.size()) {
		res.push_back(left[i++]);
	}
	while (j < right.size()) {
		res.push_back(right[j++]);
	}
	return res;
}
void mergeSort(vector<int> &arr) {
	int n = arr.size();
	if (n < 2) return;
	int mid = n / 2;
	vector<int> left(vector<int>(arr.begin(), arr.begin() + mid));
	vector<int> right(vector<int>(arr.begin() + mid, arr.end()));
	mergeSort(left);
	mergeSort(right);
	arr = merge(left, right);
}

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int partition(vector<int> &arr, int left, int right) {
	int pivot = left;
	int index = pivot + 1;
	for (int i = index; i <= right; i++) {
		if (arr[i] < arr[pivot]) {
			swap(arr[i], arr[index]);
			index++;
		}
	}
	swap(arr[pivot], arr[index - 1]);
	return index - 1;
}
void quickSort(vector<int> &arr, int left, int right) {
	int n = arr.size();
	if (left < right) {
		int partitionIndex = partition(arr, left, right);
		quickSort(arr, left, partitionIndex - 1);
		quickSort(arr, partitionIndex + 1, right);
	}
}

堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

在堆排序中，主要有以下几个操作：

  • 创建最大堆：将堆中的所有数据重新排序，使其满足最大堆的性质
  • 堆排序：移除位于第一个根节点的数据，并做最大堆调整的递归运算
  • 最大堆调整：将堆的末端子节点作调整，使得子节点永远小于父节点
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
26
27
28
29
void heapify(vector<int> &arr, int len, int index) {
	int left = index * 2 + 1;
	int right = index * 2 + 2;
	int lagest = index;
	if (left<len&&arr[left]>arr[lagest]) {
		lagest = left;
	}
	if (right<len&&arr[right]>arr[lagest]) {
		lagest = right;
	}
	if (lagest != index) {
		swap(arr[lagest], arr[index]);
		heapify(arr, len, lagest);
	}
}
void buildMaxHeap(vector<int> &arr) {
	int n = arr.size();
	for (int i = n / 2; i >= 0; i--) {
		heapify(arr, n, i);
	}
}
void heapSort(vector<int> &arr) {
	int n = arr.size();
	buildMaxHeap(arr);
	for (int i = n - 1; i > 0; i--) {
		swap(arr[i], arr[0]);
		heapify(arr, i, 0);
	}
}

基数排序

基数排序属于“分配式排序”，又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void radixSort(vector<int> &arr, int maxDigit) {
	int n = arr.size();
	vector<vector<int>> buckets(10, vector<int>());
	for (int i = 0; i <= maxDigit; i++) {
		for (int j = 0; j < n; j++) {
			int index = arr[j] / (i + 1) % 10;
			buckets[index].push_back(arr[j]);
		}
		arr.clear();
		for (int j = 0; j < 10; j++) {
			for (int k = 0; k < buckets[j].size(); k++) {
				arr.push_back(buckets[j][k]);
			}
		}
		buckets = vector<vector<int>>(10, vector<int>());
	}
}

发表于 | 更新于

Capacitated Facility Location Problem

题目描述

Suppose there are n facilities and m customers. We wish to choose:
(1) which of the n facilities to open
(2) the assignment of customers to facilities
The objective is to minimize the sum of the opening cost and the assignment cost.

Note: The total demand assigned to a facility must not exceed its capacity.

input:
图1

解题思路

算法一：贪心算法

该算法主要的贪心策略为：创建一个bool二维数组alloc，alloc[i][j]表示第i个顾客可以分配到第j个设施。在整个assignmentCost表中找到cost最小且可以被分配的assignmentCost[i][j]，该cost对应顾客i和设施j，如果该设施没有足够的容量给该顾客，那么将alloc[i][j]标记为false；如果该设施有足够的容量，就将该顾客分配给该设施，并将alloc[i]标记为false。

主要代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
获取贪心算法执行后的状态
State.cost:该状态的费用
State.occupy:每个设施已分配的空间
State.assign:每个顾客所分配的设施
*/
State Greedy::getBestState() {
	vector<int> assign(customer, -1);
	vector<double> occupy(facility, 0);
	vector<vector<bool>> alloc(customer, vector<bool>(facility, true));
	for (int i = 0; i < customer; i++) {
		int custom, faci;
		while (true) {
			findMin(alloc, custom, faci);
			/*该设施容量足够*/
			if (occupy[faci] + demand[custom] <= capacity[faci]) {
				for (int j = 0; j < alloc[custom].size(); j++) {
					alloc[custom][j] = false;
				}
				occupy[faci] += demand[custom];
				assign[custom] = faci;
				break;
			}
			/*该设施容量不够*/
			else {
				alloc[custom][faci] = false;
			}
		}
	}
	double cost = calculateCost(occupy, assign); //计算cost
	return State(cost, occupy, assign);
}

/*
找到cost最小且可以被分配的顾客和设施
alloc[i][j]:顾客i是否可以分配到设施j
custom:找到的顾客
faci:找到的设施
*/
void Greedy::findMin(const vector<vector<bool>> &alloc, int &custom, int &faci) {
	int m = INT_MAX;
	for (int i = 0; i < assignmentCost.size(); i++) {
		for (int j = 0; j < assignmentCost[i].size(); j++) {
			if (alloc[i][j] && assignmentCost[i][j] < m) {
				m = assignmentCost[i][j];
				custom = i;
				faci = j;
			}
		}
	}
}

/*
计算cost
occupy:每个设施已分配的空间
assign:每个顾客分配的设施
*/
double Greedy::calculateCost(const vector<double> &occupy, const vector<int> &assign) {
	double cost = 0;
	for (int i = 0; i < facility; i++) {
		cost += (occupy[i] > 0) ? openCost[i] : 0; //判断该设施是否已分配，如果是，则加上开启该设施的代价
	}
	for (int i = 0; i < customer; i++) {
		cost += assignmentCost[i][assign[i]];
	}
	return cost;
}

输出

ResultTime(s)
p193070.005
p279930.004
p399930.005
p4119930.004
p592200.005
p679060.004
p799060.005
p8119060.004
p990400.005
p1077260.004
p1197260.006
p12117260.004
p13120320.007
p1491800.007
p15131800.008
p16171800.009
p17120320.009
p1891800.009
p19131800.008
p20171800.009
p21120320.009
p2291800.008
p23131800.008
p24171800.008
p25192480.054
p26161820.054
p27215820.055
p28269820.054
p29192240.054
p30161580.072
p31215580.053
p32269580.056
p33190550.054
p34159890.054
p35213890.055
p36267890.056
p37190550.052
p38159890.053
p39213890.054
p40267890.055
p4171030.009
p4299570.015
p43124480.018
p4472220.009
p4598480.016
p46126390.018
p4764900.009
p4890440.015
p49124200.018
p50100600.011
p51113960.019
p52107640.012
p53128340.022
p54101430.011
p55119380.022
p56238820.087
p57328820.083
p58538820.081
p59391210.084
p60238820.081
p61328820.082
p62538820.082
p63391210.083
p64238820.082
p65328820.082
p66538820.084
p67396710.085
p68238820.082
p69328820.08
p70538820.081
p71391210.082

算法二：模拟退火

模拟退火算法是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法，其物理退火过程由加温过程、等温过程、冷却过程这三部分组成。
模拟退火最重要的部分就是状态产生函数，我在实现中随机采用三种邻域搜索策略的其中一种，一是随机将一位顾客转移到另一个设施，二是随机交换两位顾客，三是随机关闭一个设施。除此之外，模拟退火通常还有一些参数需要手动调整，如初温，末温，降温系数，内循环迭代次数等。

主要代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/*
模拟退火过程
beginTem:初温
endTem:末温
cool:降温系数
iteration:内循环迭代次数
*/
void SA::run(double beginTem, double endTem, double cool, int iteration) {
	/*十次模拟退火过程取其中最好的一次*/
	for (int count = 0; count < 10; count++) {
		genRandomState(); //随机产生一个当前状态
		bestStateForEveryIteration = curState; //记录每次循环的最好状态
		double tem = beginTem;
		/*模拟退火主过程*/
		while (tem >= endTem) {
			for (int i = 0; i < iteration; i++) {
				int ran = rand() % 5; //产生一个随机数，根据随机数选择邻域策略
				/*随机关闭一个设施*/
				if (ran < 1) {
					State nextState = closeRandomFacility();
					if (exp((curState.cost - nextState.cost) / tem) >= rand() % 100 / 100.0) {
						curState = nextState;
					}
				}
				/*随机交换两位顾客*/
				else if (ran < 3) {
					State nextState = exchangeTwoCustomer();
					if (exp((curState.cost - nextState.cost) / tem) >= rand() % 100 / 100.0) {
						curState = nextState;
					}
				}
				/*随机将一位顾客转移到另一个设施*/
				else {
					State nextState = moveCustomerToAnotherFacility();
					if (exp((curState.cost - nextState.cost) / tem) >= rand() % 100 / 100.0) {
						curState = nextState;
					}
				}
				/*更新本次循环的最好状态*/
				if (curState.cost < bestStateForEveryIteration.cost) {
					bestStateForEveryIteration = curState;
				}
			}
			tem *= cool; //降温
		}
		cout << bestStateForEveryIteration.cost << endl;
		/*保存十次循环的最好状态*/
		if (bestStateForEveryIteration.cost < bestState.cost)
			bestState = bestStateForEveryIteration;
	}
}

/*随机产生一个初始状态*/
void SA::genRandomState() {
	while (true) {
		curState.assign = vector<int>(customer);
		curState.occupy = vector<double>(facility, 0);
		for (int i = 0; i < customer; i++) {
			curState.assign[i] = rand() % facility;
			curState.occupy[curState.assign[i]] += demand[i];
		}
		if (isFeasible(curState.occupy)) {
			curState.cost = calculateCost(curState.occupy, curState.assign);
			break;
		}
	}
}

/*随机将一位顾客转移到另一个设施*/
State SA::moveCustomerToAnotherFacility() {
	while (true) {
		int index = rand() % customer; //随机选择一位顾客
		int newFacility = rand() % facility; //随机选择一个设施
		if (curState.occupy[newFacility] + demand[index] <= capacity[newFacility]) {
			State nextState = curState;
			nextState.occupy[nextState.assign[index]] -= demand[index];
			nextState.assign[index] = newFacility;
			nextState.occupy[newFacility] += demand[index];
			nextState.cost = calculateCost(nextState.occupy, nextState.assign);
			return nextState;
		}
	}
}

/*随机交换两位顾客*/
State SA::exchangeTwoCustomer() {
	while (true) {
		int index1 = rand() % customer; //随机选择顾客1
		int index2 = rand() % customer; //随机选择顾客2
		if (curState.occupy[curState.assign[index1]] - demand[index1] + demand[index2] <= capacity[curState.assign[index1]]
			&& curState.occupy[curState.assign[index2]] - demand[index2] + demand[index1] <= capacity[curState.assign[index2]]) {
			State nextState = curState;
			nextState.occupy[nextState.assign[index1]] = nextState.occupy[nextState.assign[index1]] - demand[index1] + demand[index2];
			nextState.occupy[nextState.assign[index2]] = nextState.occupy[nextState.assign[index2]] - demand[index2] + demand[index1];
			int temp = nextState.assign[index1];
			nextState.assign[index1] = nextState.assign[index2];
			nextState.assign[index2] = temp;
			nextState.cost = calculateCost(nextState.occupy, nextState.assign);
			return nextState;
		}
	}
}

/*随机关闭一个设施*/
State SA::closeRandomFacility() {
	int closeFacility = rand() % facility; //随机选择一个要关闭的设施
	State nextState = curState;
	nextState.occupy[closeFacility] = 0;
	for (int j = 0; j < customer; j++) {
		/*找到分配到要关闭设施的顾客*/
		if (nextState.assign[j] == closeFacility) {
			while (true) {
				int newFacility = rand() % facility; //随机为该顾客选择一个新设施
				if (nextState.occupy[newFacility] + demand[j] <= capacity[newFacility]) {
					nextState.assign[j] = newFacility;
					nextState.occupy[newFacility] += demand[j];
					break;
				}
			}
		}
	}
	nextState.cost = calculateCost(nextState.occupy, nextState.assign);
	return nextState;
}

/*
判断当前设施的占用状态是否可行
occupy:设施的占用状态
*/
bool SA::isFeasible(const vector<double> &occupy) {
	for (int i = 0; i < occupy.size(); i++) {
		if (occupy[i] > capacity[i]) return false;
	}
	return true;
}

输出

ResultTime(s)
p189502.581
p280112.588
p395252.592
p4110632.643
p591192.786
p678412.702
p797592.721
p8111892.731
p987112.505
p1077672.503
p1191812.509
p12104532.514
p1394442.53
p1480152.523
p1597442.506
p16116792.518
p1792582.495
p1879002.51
p19100072.521
p20119652.53
p2186862.47
p2279092.497
p2398722.464
p24114442.469
p25152144.129
p26140734.123
p27161394.106
p28181264.1
p29154334.127
p30134854.143
p31163444.133
p32193874.145
p33145114.096
p34126364.099
p35154394.108
p36177484.105
p37137324.094
p38135084.093
p39153104.07
p40170694.077
p4169203.215
p4265702.972
p4362712.836
p4479623.294
p4575682.972
p4671712.861
p4770813.298
p4867622.997
p4966642.883
p5092353.424
p5185743.286
p5297353.542
p53101403.29
p5494753.646
p5588093.282
p56292074.951
p57366794.978
p58481924.994
p59386464.996
p60294404.896
p61335824.887
p62434974.898
p63355684.885
p64292474.888
p65331684.875
p66427064.87
p67346104.928
p68283244.896
p69349924.886
p70437084.934
p71350964.938

算法对比

  • 速度：从时间上可以看出，贪心算法运行速度很快，而模拟退火因为每一轮都跑了十次，所以速度较慢。
  • 结果：贪心算法的结果没有模拟退火好。尤其是贪心策略没有考虑设施开启时的费用，仅考虑分配顾客时的费用，容易陷入局部最优。而模拟退火在整个大的搜索空间求解，并通过几种邻域搜索策略，即使陷入局部最优解，也有几率可以跳出，最终得到的解与全局最优解更加接近。

实验思考

在实现贪心算法时，我后来考虑到了把设施的开启费用加进去，我将整个顾客分配损失表assignmentCost每一列加上了对应设施的开启费用，然后重复之前的贪心策略，选取费用最小的进行分配，如果分配成功且之前该设施未开启，就把assignmentCost的该列减去开启费用，即开启该设施。然而做了这个改进之后并没有之前的效果好，感觉应该是因为这种贪心策略会使得很多顾客挤在某几个设施。
在实现模拟退火时，一开始我实现了两种邻域搜索策略，即随机将一位顾客分配到另一个设施和随机交换两位顾客，在观察结果时我发现，几乎每个设施都打开了，因此我引入了第三种邻域搜索策略，即随机关闭一个设施，并使得这种操作的概率较低，这样做似乎比较容易跳出局部最优，效果挺好。

具体每个测试样例的详细结果和项目源码请参考：github

发表于 | 更新于

Create Maximum Number

题目描述

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Note: You should try to optimize your time and space complexity.

Example 1:

Input:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
Output: [9, 8, 6, 5, 3]

Example 2:

Input:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
Output: [6, 7, 6, 0, 4]

Example 3:

Input:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
Output: [9, 8, 9]

解题思路

本题给定了两个数组和一个整数k，要在两个数组中，一共选出k个数，使得组成的数字最大，且选出的数字相对顺序不能变化。
思路： 对于两个数组我们不是很方便直接计算，而如果在一个数组中选m个数，使得组成的数字最大，那就好做很多，因此我们只需要在一个数组中选m个数，在另一个数组中选k-m个数，最后将两组选出的数合并起来，即可得到我们想要的解。那么接下来的问题就分解为以下几个问题：

  1. 如何从一个数组中选m个数，使得组成的数字最大。对于一个给定长度的数字来说，其高位决定了它的大小，因此我们应该尽可能让这个数的高位更大。假如数组长度为n，给定整数为m，起始位置为k，那么在下标为k到n-m中找一个最大的数作为最高位，并记录该最高位的下标赋值给k，重复以上过程不断找到次高位，即可得到想要的数。
  2. 如何合并两个数组，使得结果最大。与上面的思路类似，同样是尽量使得组成的数字的高位更大，因此我写了一个greater的函数，用来判断两个数组的第一个不一样的数的大小关系。

源代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int> ans(k, 0);
        int n = nums1.size();
        int m = nums2.size();
        for(int i = max(k - m, 0); i <= k && i <= n; i++) {
            vector<int> cur = merge(maxArray(nums1, i), maxArray(nums2, k - i), k);
            if(greater(cur, 0, ans, 0)) {
                ans = cur;
            }
        }
        return ans;
    }
    
    vector<int> maxArray(vector<int> nums, int k) {
        int n = nums.size();
        if(k == n) {
            return nums;
        }
        vector<int> res(k, 0);
        int cur = 0;
        int j = 0;
        int pre = 0;
        while(k > 0) {
            int i = n - k;
            while(i >= pre) {
                if(res[cur] <= nums[i]) {
                    res[cur] = nums[i];
                    j = i + 1;
                }
                i--;
            }
            cur++;
            k--;
            pre = j;
        }
        return res;
    }
    
    vector<int> merge(vector<int> nums1, vector<int> nums2, int k) {
        vector<int> ans(k);
        for (int i = 0, j = 0, r = 0; r < k; ++r)
            ans[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
        return ans;
    }
    
    bool greater(vector<int> nums1, int i, vector<int> nums2, int j) {
        while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
            i++;
            j++;
        }
        return j == nums2.size() || (i < nums1.size() && nums1[i] > nums2[j]);
    }
};

发表于 | 更新于

Maximal Square

题目描述

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4

解题思路

本题要在一个01矩阵中找到一个最大方阵的面积，这个方阵包含的都是1.
思路一： 考虑到一个方阵的面积取决于它的右下角能够到达哪里，于是我用一个相同大小的矩阵v，v[i][j]表示以i，j为右下角的方阵的最大边长，于是得到状态方程：当矩阵的第i行第j列元素为1时，v[i][j] = min(v[i-1][j], v[i][j-1], v[i-1][j-1]) + 1；当矩阵的第i行第j列元素为0时，v[i][j] = 0。并在一开始将矩阵v的第一行和第一列初始化，矩阵v的值与01矩阵对应值相等，整个算法的空间复杂度与时间复杂度均为\(O(nm)\)。
思路二： 考虑到实际上每次计算v[i][j]的值时，只需要用到v[i-1][j], v[i][j-1], v[i-1][j-1]，所以实际上可以只用一个大小为n+1的数组存储，将空间复杂度降为\(O(n)\)。

源代码

思路一

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
26
27
28
29
30
31
32
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int max = 0;
        int n = matrix.size();
        if(n == 0) return 0;
        int m = matrix[0].size();
        vector<vector<int>> v(n, vector<int>(m, 0));
        for(int i = 0; i < m; i++) {
            if(matrix[0][i] == '1') {
                v[0][i] = 1;
                max = 1;
            }
        }
        for(int i = 0; i < n; i++) {
            if(matrix[i][0] == '1') {
                v[i][0] = 1;
                max = 1;
            }
        }
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < m; j++) {
                if(matrix[i][j] == '1') {
                    int temp = min(v[i][j-1], v[i-1][j]);
                    v[i][j] = min(temp, v[i-1][j-1]) + 1;
                    if(v[i][j] > max) max = v[i][j];
                }
            }
        }
        return max * max;
    }
};

思路二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int max = 0;
        int n = matrix.size();
        if(n == 0) return 0;
        int m = matrix[0].size();
        vector<int> v(n + 1, 0);
        int pre = 0;
        for(int j = 0; j < m; j++) {
            for(int i = 1; i < n + 1; i++) {
                int temp = v[i];
                if(matrix[i - 1][j] == '1') {
                    v[i] = min(v[i-1], min(v[i], pre)) + 1;
                    if(v[i] > max) max = v[i];
                } else {
                    v[i] = 0;
                }
                pre = temp;
            }
        }
        return max * max;
    }
};

发表于 | 更新于

Coin Change

题目描述

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

解题思路

本题给出了硬币的面值，要求用最少的硬币组成一个数，组不成就返回-1.
首先声明一个大小为amount+1的数组fewestCoins，fewestCoins[i]表示组成数字i所需的最少硬币数，组不成则为-1，最后fewestCoins[amount]即为所求。将数组的第一个元素初始化为0，因为使用0个硬币就能组成0这个数，其余元素初始化为最大正整数。状态转移为fewestCoins[i] = min(fewestCoins[i], fewestCoins[i - coins[j]] + 1),其中coins[j]为硬币面值，若没有更新fewestCoins[j]，则将其置为-1。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount <= 0) return 0;
        vector<int> fewestCoins(amount + 1, INT_MAX);
        fewestCoins[0] = 0;
        int n = coins.size();
        bool found = false;
        for(int i = 1; i <= amount; i++) {
            found = false;
            for(int j = n - 1; j >= 0; j--) {
                if(coins[j] <= i && fewestCoins[i - coins[j]] != -1) {
                    fewestCoins[i] = min(fewestCoins[i], fewestCoins[i - coins[j]] + 1);
                    found = true;
                }
            }
            if(!found) fewestCoins[i] = -1;
        }
        return fewestCoins[amount];
    }
};

发表于 | 更新于

Perfect Squares

题目描述

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

解题思路

本题要求和为n的平方数的最少个数。
leastNumOfSquare[i]表示和为i的平方数的最少个数，因此leastNumOfSquare[n]即为所求。i可以由某一个数加上一个平方数所得，因此要使leastNumOfSquare[i]最小，就要找到一个平方数，使得leastNumOfSquare[i - 该平方数]最小，所以状态转移方程为leastNumOfSquare[i] = min(leastNumOfSquare[i], leastNumOfSquare[i - j * j] + 1)

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numSquares(int n) {
        vector<int> leastNumOfSquare(n + 1, INT_MAX);
        leastNumOfSquare[0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j*j <= i; j++) {
                leastNumOfSquare[i] = min(leastNumOfSquare[i], leastNumOfSquare[i-j*j] + 1);
            }
        }
        return leastNumOfSquare[n];
    }
};

发表于 | 更新于

Maximum Product Subarray

题目描述

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

解题思路

本题要在一个整数数组中找到一个连续的子数组，使这个子数组的元素的乘积最大。
考虑到这样一个问题，如果这个数组中不包含0，那么以第一个元素为起点的子数组，随着子数组长度的增加，元素乘积的绝对值肯定是非严格递增的，因此我们只需要维护整个过程中的最小值和最大值，因为负的最小值，乘以一个负数，有可能变成一个最大值，最后直接返回最大值即可。
但是如果这个数组中包含0，那么可以把0当做一个分隔符，当遇到0时，我们其实已经求出了0之前的子数组的最大乘积，已经可以把它放在一边，继续计算0之后的子数组的最大乘积，并使用一个变量result记录整个过程中的最大乘积。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxP = nums[0], minP = nums[0], result = nums[0];
        for(int i = 1; i < nums.size(); i++){
            int temp = maxP;
            maxP = max(max(maxP * nums[i], minP * nums[i]), nums[i]);
            minP = min(min(temp * nums[i], minP * nums[i]), nums[i]);
            if(result < maxP) result = maxP;
        }
        return result;
    }
};

发表于 | 更新于

Triangle

题目描述

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

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

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

解题思路

本题要在一个三角形中从上到下找到最短路径和。
要找到这样一条路径，使用贪心算法是不行的，必须遍历三角形的每个位置。我们可以发现，到达第i行第j列的元素的最短路径是到达第i-1行的第j-1列和j列的较小值再加上第i行第j列的值。因此可以利用动态规划，自顶向下推导，先求出上面的最短路径和，逐步求到最后一行。另外，我们可以发现，我们每次推导某一行的最短路径和的时候，只需要上一层的最短路径和，再往上就不需要了，因此我们为了节省空间，可以只申请一个长度为n的数组，n为三角形的行数，并从行末往前遍历，这样的算法空间复杂度为\(O(n)\)，时间复杂度为\(O(n^2)\)。

源代码

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
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        if(n == 0) return 0;
        vector<int> dist(n, 0);
        dist[0] = triangle[0][0];
        for(int i = 1; i < n; i++) {
            dist[i] = triangle[i][i] + dist[i-1];
            for(int j = i - 1; j > 0; j--) {
                if(dist[j-1] < dist[j])
                    dist[j] = dist[j-1] + triangle[i][j];
                else 
                    dist[j] = dist[j] + triangle[i][j];
            }
            dist[0] = triangle[i][0] + dist[0];
        }
        int min = dist[0];
        for(int i = 1; i < n; i++) {
            if(dist[i] < min)
                min = dist[i];
        }
        return min;
    }
};

发表于 | 更新于

Candy

题目描述

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively. The third child gets 1 candy because it satisfies the above two conditions.

解题思路

本题要为小朋友分糖果，每个小朋友有自己的等级，要求每个小朋友都有糖果，且等级较高的小朋友要比旁边的小朋友拿的糖果多，求分出去的糖果最少数量。
从头到尾遍历ratings数组，一共可以分为三种情况：

  1. 后一个小朋友的等级比前一个高，那么分给后一个小朋友的糖果数量是前一个的加一。
  2. 后一个小朋友的等级与前一个相等，那么分给后一个小朋友一个糖果即可。
  3. 后一个小朋友的等级比前一个低，那么分给后一个小朋友一个糖果，且前面的部分小朋友的糖果数量需要加一，这部分小朋友的等级应该是从前往后递减的。但是没有必要每次遇到一个等级较低的小朋友就更新前面的小朋友的糖果数，可以记录下来，直到遇到一个小朋友的等级大于或等于前一个，或者遍历完成，此时再做累加。

整个算法的时间复杂度为\(O(n)\)。

源代码

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
26
27
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int sum = 1;
        int prev = 1;
        int countDown = 0;
        for(int i = 1; i < n; i++) {
            if(ratings[i] >= ratings[i-1]) {
                if(countDown > 0) {
                    sum += countDown*(countDown + 1) / 2;
                    if(countDown >= prev) sum += countDown - prev + 1;
                    prev = 1;
                    countDown = 0;
                }
                prev = ratings[i] == ratings[i-1] ? 1 : (prev + 1);
                sum += prev;    
            }
            else countDown++;
        }
        if(countDown > 0) {
            sum += countDown*(countDown + 1) / 2;
            if(countDown >= prev) sum += countDown - prev + 1;
        }
        return sum;
    }
};
0%