hihoCoder 1552-缺失的拼图

hihoCoder 1552-缺失的拼图

#1552 : 缺失的拼图

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi在玩一个拼图游戏。如下图所示,整个拼图是由N块小矩形组成的大矩形。现在小Hi发现其中一块小矩形不见了。给定大矩形以及N-1个小矩形的顶点坐标,你能找出缺失的那块小矩形的顶点坐标吗?

输入

第一行包含一个整数,N。
第二行包含四个整数,(X0, Y0), (X'0, Y'0),代表大矩形左下角和右上角的坐标。
以下N-1行每行包含四个整数,(Xi, Yi), (X'i, Y'i),代表其中一个小矩形的左下角和右上角坐标。
对于30%的数据, 1 <= N <= 1000
对于100%的数据,1 <= N <= 100000 所有的坐标(X, Y)满足 0 <= X, Y <= 100000000

输出

输出四个整数(X, Y), (X', Y')代表缺失的那块小矩形的左下角和右上角的坐标。

样例输入
5
0 0 4 5
0 0 3 1
0 1 2 5
3 0 4 5
2 2 3 5
样例输出
2 1 3 2

一个矩形由N个小矩形拼接而成,现在丢了一个小矩形,怎样才能找到这个小矩形呢。所有矩形都用左下角坐标和右上角坐标表示。
这一题也很有意思,丢掉的那个小矩形的坐标肯定是其他N-1个矩形的坐标中的某4个。我们可以统计每个坐标点出现的次数,如果出现偶数次,则这个点所在的矩形是出现过的,否则这个点就是缺失矩形的某个顶点。最后,从缺失的4个顶点中找出左下角坐标和右上角坐标。
完整代码如下:

#include<algorithm>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> Point;
int main() {
	//freopen("input.txt", "r", stdin);
	int n;
	scanf("%d", &n);
	map<Point, int> hash;
	int a, b, c, d;
	while (n--) {
		Point left_bottom, right_top;
		scanf("%d %d %d %d", &left_bottom.first, &left_bottom.second, &right_top.first, &right_top.second);
		Point left_top = Point(left_bottom.first, right_top.second), right_bottom = Point(right_top.first, left_bottom.second);
		++hash[left_bottom];
		++hash[right_top];
		++hash[left_top];
		++hash[right_bottom];
	}
	set<Point> ans;
	for (auto p : hash) {
		if (p.second % 2 == 1) {
			ans.insert(p.first);
		}
	}
	a = c = ans.begin()->first;
	b = d = ans.begin()->second;
	for (auto p : ans) {
		a = min(a, p.first);
		b = min(b, p.second);
		c = max(c, p.first);
		d = max(d, p.second);
	}
	printf("%d %d %d %d\n", a, b, c, d);
	return 0;
}

本代码提交AC,用时432MS。

hihoCoder 1551-合并子目录

hihoCoder 1551-合并子目录

#1551 : 合并子目录

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi的电脑的文件系统中一共有N个文件,例如:
/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall
小Hi想统计其中一共有多少个不同的子目录。上例中一共有8个不同的子目录:
/hihocoder
/hihocoder/offer22
/hihocoder/offer22/solutions
/hihocoder/challenge30
/hihocoder/challenge30/p1
/game
/game/moba
/game/moba/dota2/

输入

第一行包含一个整数N (1 ≤ N ≤ 10000)
以下N行每行包含一个字符串,代表一个文件的绝对路径。保证路径从根目录"/"开始,并且文件名和目录名只包含小写字母和数字。
对于80%的数据,N个文件的绝对路径长度之和不超过10000
对于100%的数据,N个文件的绝对路径长度之和不超过500000

输出

一个整数代表不同子目录的数目。

样例输入
3
/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall
样例输出
8

给定很多个文件的绝对路径,问从这些文件的绝对路径中,我们可以知道其一共有多少个不同文件夹出现过。
常规思路很简单,直接解析每个文件所在的每一级文件夹路径,存到一个set里面,最后返回unordered_set的大小。但是这种方法TLE,看了一下,内存基本也用完了。因为对于100%的数据,路径长度太长了,hash的时间和空间都随之增长。
后来马上想到,路径问题是一层一层的,有可能很多文件的路径前缀都是相同的,那么我们可以构建一个Trie树,每个节点仅是当前文件夹的名称。最后我们统计一下构建好的Trie树的节点个数,就是文件夹的个数。
完整代码如下:

#include<algorithm>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
struct Node {
	string key_;
	map<string, Node*> children_;
	Node(string key) :key_(key) {};
};
int main() {
	//freopen("input.txt", "r", stdin);
	int n;
	scanf("%d\n", &n);
	string line;
	Node* root = new Node("");
	while (n--) {
		getline(cin, line);
		int pre = 0;
		int pos = line.find('//');
		Node* cur = root;
		while (pos != string::npos) {
			if (pos != 0) {
				string tmp = line.substr(pre + 1, pos - pre - 1);
				if (cur->children_[tmp] == NULL) {
					cur->children_[tmp] = new Node(tmp);
				}
				cur = cur->children_[tmp];
			}
			pre = pos;
			pos = line.find('//', pos + 1);
		}
	}
	ll ans = 0;
	queue<Node*> q;
	q.push(root);
	while (!q.empty()) {
		Node* cur = q.front();
		q.pop();
		++ans;
		for (auto it : cur->children_) {
			q.push(it.second);
		}
	}
	printf("%lld\n", ans - 1);
	return 0;
}

本代码提交AC,用时126MS。

hihoCoder 1550-顺序三元组

hihoCoder 1550-顺序三元组

题目1 : 顺序三元组

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个长度为N的数组A=[A1, A2, ... AN],已知其中每个元素Ai的值都只可能是1, 2或者3。
请求出有多少下标三元组(i, j, k)满足1 ≤ i < j < k ≤ N且Ai < Aj < Ak

输入

第一行包含一个整数N
第二行包含N个整数A1, A2, ... AN。(1 ≤ Ai ≤ 3)
对于30%的数据,1 ≤ N ≤ 100
对于80%的数据,1 ≤ N ≤ 1000
对于100%的数据,1 ≤ N ≤ 100000

输出

一个整数表示答案

样例输入
6
1 3 2 1 2 3
样例输出
3

给定一个数组,只包含1,2,3这三个数,问数组中有多少个三元组下标(i,j,k),满足a[i]<a[j]<a[k]。
我一开始的想法是,找出所有1,2,3出现的下标,对于每一个1的下标i,去2的下标数组中找一个lowerbound j,然后用j在3的下标数组中找一个lowerbound k,则3的下标数组中k往后的下标都是符合条件的。这需要两层循环,过了90%的数据,然后TLE了。
后来经过大神点拨,要想得到符合条件的三元组,则2一定要在中间,所以我们可以遍历原数组,对于每一个出现的2,用其左边的1的频数乘以其右边3的频数,就是这个2可以构成的合法三元组的个数。
为了不重复计算,我们可以提前算好每个位置左边和右边1和3的频数,到时候直接用left[1]*right[3]就好了。完整代码如下:

#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
int main() {
	//freopen("input.txt", "r", stdin);
	int n = 0;
	scanf("%d", &n);
	vector<int> nums(n, 0);
	map<int, int> left, right;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &nums[i]);
		++right[nums[i]];
	}
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		--right[nums[i]];
		if (nums[i] == 2) {
			ans += left[1] * right[3];
		}
		++left[nums[i]];
	}
	printf("%lld\n", ans);
	return 0;
}

本代码提交AC,用时18MS。

LeetCode Find K Closest Elements

LeetCode Find K Closest Elements
Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

  1. The value k is positive and will always be smaller than the length of the sorted array.
  2. Length of the given array is positive and will not exceed 104
  3. Absolute value of elements in the array and x will not exceed 104

给定一个有序数组,要从中找出k个和x最接近的元素,按升序排列输出。
首先在有序数组中用二分查找找到x的lowerbound,如果lowerbound指向begin(),则取开头k个元素即可;如果lowerbound指向end(),则取末尾k个元素;否则,令left指向lowerbound-1,right指向lowerbound,每次取left、right中和x差值最小的那个数,直到取够k个为止。最后对结果数组排序。
完整代码如下:

class Solution {
public:
	vector<int> findClosestElements(vector<int>& arr, int k, int x) {
		vector<int> ans;
		int n = arr.size();
		auto it = lower_bound(arr.begin(), arr.end(), x);
		if (it == arr.begin()) {
			while (ans.size() < k) {
				ans.push_back(*it++);
			}
			return ans;
		}
		else if (it == arr.end()) {
			while (ans.size() < k) {
				ans.push_back(*--it);
			}
			return ans;
		}
		else {
			int right = it - arr.begin();
			int left = right - 1;
			int left_diff = INT_MAX, right_diff = INT_MAX;
			while (ans.size() < k) {
				if (left >= 0)left_diff = abs(arr[left] - x);
				else left_diff = INT_MAX;
				if (right < n)right_diff = abs(arr[right] - x);
				else right_diff = INT_MAX;
				if (left_diff <= right_diff) {
					ans.push_back(arr[left]);
					--left;
				}
				else {
					ans.push_back(arr[right]);
					++right;
				}
			}
		}
		sort(ans.begin(), ans.end());
		return ans;
	}
};

本代码提交AC,用时143MS。

LeetCode Judge Route Circle

LeetCode Judge Route Circle
Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.
The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.
Example 1:

Input: "UD"
Output: true

Example 2:

Input: "LL"
Output: false

一个机器人,初始站在原点(0,0),UDLR分别表示上下左右,给定一个机器人行走的轨迹字符串,问最终机器人能回到原点吗。
简单题,直接判断走过的水平和垂直方向的差值是否为0,代码如下:

class Solution {
public:
	bool judgeCircle(string moves) {
		int horizon = 0, vertical = 0;
		for (auto c : moves) {
			if (c == 'U')++vertical;
			else if (c == 'D')--vertical;
			else if (c == 'L')--horizon;
			else if (c == 'R')++horizon;
		}
		return horizon == 0 && vertical == 0;
	}
};

本代码提交AC,用时29MS。

hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

#1543 : SCI表示法

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

每一个正整数 N 都能表示成若干个连续正整数的和,例如10可以表示成1+2+3+4,15可以表示成4+5+6,8可以表示成8本身。我们称这种表示方法为SCI(Sum of Consecutive Integers)表示法。
小Hi发现一个整数可能有很多种SCI表示,例如15可以表示成1+2+3+4+5,4+5+6,7+8以及15本身。小Hi想知道N的所有SCI表示中,最多能包含多少个连续正整数。例如1+2+3+4+5是15包含正整数最多的表示。

输入

第一行一个整数 T,代表测试数据的组数。
以下 T 行每行一个正整数N。
对于30%的数据,1 ≤ N ≤ 1000
对于80%的数据,1 ≤ N ≤ 100000
对于100%的数据,1 ≤ T ≤ 10,1 ≤ N ≤ 1000000000

输出

对于每组数据输出N的SCI表示最多能包含多少个整数。

样例输入
2
15
8
样例输出
5
1

每一个正整数都可以表示成一串连续正整数的和,比如15=1+2+3+4+5,8=8(8也是一串连续正整数的和,只不过该串长度为1罢了:))。给定一个正整数N,问N最长能由多少个连续的正整数的和表示。
要使连续串的长度越长,则这些数越小越好。我们可以用滑动窗口的方法,设[i,j]的累加和为sum,则当sum>n时,++i;当sum<n时,++j;当sum==n时,len=j-i+1,更新最大长度。当j>n时循环终止。
完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld", &n);
		if (n == 1 || n == 2) {
			printf("1\n");
		} else {
			ll i = 1, j = 2;
			ll sum = i + j, ans = 0;
			while (true) {
				while (j <= n && sum < n) {
					++j;
					sum += j;
				}
				if (j > n)break;
				while (i < j && sum > n) {
					sum -= i;
					++i;
				}
				if (sum == n) {
					//printf("%d\n", j - i + 1);
					ans = max(ans, j - i + 1);
					break;
				}
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

无奈,提交后TLE,只过了80%的数据。
实在想不出哪里还可以优化了,网上搜库,发现是记录A109814,但是没有递推公式,OEIS上给出的MAPLE程序也需要现算,试了一下,还是TLE。
后来请教某大神,发现一个巧妙的优化方法。如果从1加到i的累加和是sum,如果sum<n,令left=n-sum,如果left是i的正数倍,则从1~i这i个数,每个数都加上left/i,得到的新序列也是连续的,且和正好是sum+(left/i)*i=n,所以我们得到一个长度为i的连续和是n。
举个例子,当n=14时,遍历i,当i=4时,sum=1+2+3+4=10,剩余差值为left=n-sum=4,4%i=0,此时,给每个数加上left/i=1,就变成了2+3+4+5=14=n。
所以,我们只是从1开始遍历,知道累加和大于n,并没有从2开始重新遍历,这种方法需要的遍历数其实是很少的。
完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
	freopen("input.txt", "r", stdin);
	scanf("%lld", &t);
	while (t--) {
		scanf("%lld", &n);
		if (n == 1 || n == 2) {
			printf("1\n");
		}
		else {
			ll ans = 1;
			for (ll i = 1; i < n; ++i) {
				ll sum = (1 + i)*i / 2;
				if (sum > n)break;
				ll left = sum - n;
				if (left%i == 0) {
					ans = max(ans, i);
				}
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

本代码提交AC,用时10MS。

hihoCoder 1542-无根数变有根树

hihoCoder 1542-无根数变有根树

#1542 : 无根数变有根树

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定一棵包含 N 个节点的无根树,小Hi想知道如果指定其中某个节点 K 为根,那么每个节点的父节点是谁?

输入

第一行包含一个整数 N 和 K。1 ≤ N ≤ 1000, 1 ≤ K ≤ N
以下N-1行每行包含两个整数 a 和 b,代表ab之间存在一条边。 1 ≤ ab ≤ N
输入保证是一棵树。

输出

输出一行包含 N 个整数,分别代表1~N的父节点的编号。对于 K 的父节点输出0。

样例输入
5 4
1 2
3 1
4 3
5 1
样例输出
3 1 4 0 1

给定一个无根树(其实就是DAG),如果以该树的某个顶点K为根,要求输出每个节点的父节点。
简单题,以K为根,进行DFS,遍历过程中记录每个节点的父节点就好了。完整代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
const int kMaxN = 1005;
int n, k;
vector<int> parent(kMaxN, 0);
vector<vector<int>> graph(kMaxN, vector<int>(kMaxN, 0));
void DFS(int node, int pre) {
	parent[node] = pre;
	graph[node][pre] = 0;
	graph[pre][node] = 0;
	for (int i = 1; i <= n; ++i) {
		if (graph[node][i] == 1) {
			DFS(i, node);
		}
	}
	graph[node][pre] = 1;
	graph[pre][node] = 1;
}
int main() {
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &k);
	int a, b;
	for (int i = 0; i < n - 1; ++i) {
		scanf("%d %d", &a, &b);
		graph[a][b] = 1;
		graph[b][a] = 1;
	}
	DFS(k, 0);
	for (int i = 1; i <= n; ++i)
		printf("%d ", parent[i]);
	return 0;
}

本代码提交AC,用时42MS。

LeetCode Dota2 Senate

LeetCode Dota2 Senate
In the world of Dota2, there are two parties: the Radiant and the Dire.
The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

  1. Ban one senator's right:
    A senator can make another senator lose all his rights in this and all the following rounds.
  2. Announce the victory:
    If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.

Given a string representing each senator's party belonging. The character 'R' and 'D' represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n.
The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.
Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire.
Example 1:

Input: "RD"
Output: "Radiant"
Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights any more since his right has been banned.
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

Input: "RDD"
Output: "Dire"
Explanation:
The first senator comes from Radiant and he can just ban the next senator's right in the round 1.
And the second senator can't exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator's right in the round 1.
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

Note:

  1. The length of the given string will in the range [1, 10,000].

Dota2中有两个党派,分别是Radiant和Dire,分别用R和D表示。给定一个长度为n的字符串s,表示n个人,如果s[i]='R',表示第i个人是Radiant党的人;如果s[i]='D',表示第i个人是Dire党的人。
投票过程是从1~n不断重复的,每个人可以禁止任何一个其他人投票。如果某个人投票之后,剩下的人都是同一个党派的,则该党派胜利。问最终是哪个党派的人胜利。
使用贪心的原则,因为是round-based的投票方式,为了获胜,第i个人肯定是禁止其后的第一个非本党人员投票。比如序列DRDRR:
第一个D如果杀其后的第一个R:

  1. DXDRR
  2. DXDXR
  3. XXDXR
  4. XXDXX

Dire胜利;第一个D如果杀其后的第二个R:

  1. DRDXR
  2. DRXXR
  3. XRXXR

Radiant胜利。
这其实很好理解,因为是round-based的投票方式,对于D来说,他必须首先把其后的第一个R杀掉,要不然很快就会轮到这个R杀己方人员了。
round-based的方式是用%n的方式实现,代码如下:

class Solution {
public:
	string predictPartyVictory(string senate) {
		int r_cnt = 0, d_cnt = 0, n = senate.size();
		for (int i = 0; i < n; ++i) {
			if (senate[i] == 'R')
				++r_cnt;
			else
				++d_cnt;
		}
		int pos = 0;
		while (r_cnt > 0 && d_cnt > 0) {
			if (senate[pos] == 'X') {
				pos = (pos + 1) % n;
				continue;
			}
			int pos_next = (pos + 1) % n;
			while (senate[pos_next] == senate[pos] || senate[pos_next] == 'X')
				pos_next = (pos_next + 1) % n;
			if (senate[pos_next] == 'R')
				--r_cnt;
			else
				--d_cnt;
			senate[pos_next] = 'X';
			pos = (pos + 1) % n;
		}
		return r_cnt == 0 ? "Dire" : "Radiant";
	}
};

本代码提交AC,用时752MS。

LeetCode 4 Keys Keyboard

LeetCode 4 Keys Keyboard
Imagine you have a special keyboard with the following keys:
Key 1: (A): Prints one 'A' on screen.
Key 2: (Ctrl-A): Select the whole screen.
Key 3: (Ctrl-C): Copy selection to buffer.
Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.
Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.
Example 1:

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A

Example 2:

Input: N = 7
Output: 9
Explanation:
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

Note:

  1. 1 <= N <= 50
  2. Answers will be in the range of 32-bit signed integer.

给定四个按键,有四种操作:

  • A: 打印一个字符A
  • Ctrl-A: 全选
  • Ctrl-C: 复制
  • Ctrl-V: 粘贴

问通过n次按键操作,最多可以打印出多少个字符。
稍微分析一下,增加字符比较快的方法是用Ctrl-V,连带着需要Ctrl-C和Ctrl-A的配合,所以要想快速增加字符,必须要以Ctrl-A, Ctrl-C, Ctrl-V结尾,这就需要3个操作。当n比较小时,这3个操作相对来说比较耗时,通过分析可知,当N<=6时,直接用N次Print(A)操作能得到最多的字符。
假设dp[i]表示使用i次操作能得到的最多字符,显然dp[i]=i,当i<=6时。
当i>6时,我们可以考虑用Ctrl-A, Ctrl-C, Ctrl-V,所以结尾我们至少要空出3个操作来使用技能,也就是我们最多只能在i-3的地方开始释放Ctrl-A, Ctrl-C, Ctrl-V技能,假设释放技能的位置是b,则b<=i-3;下界是我们可以在一开始只有一个字符时使用技能,即b>=1。所以我们遍历[1,i-3]的地方释放技能,则我们可以有i-b-2个Ctrl-V结尾,再加上释放技能的位置已经有一个dp[b]了,所以总字符数是dp[b]*(i-b-1)。使用贪心策略求最大值。
完整代码如下:

class Solution {
public:
	int maxA(int N) {
		if (N <= 6)return N;
		vector<int> dp(N + 1, 0);
		for (int i = 1; i <= 6; ++i)dp[i] = i;
		for (int i = 7; i <= N; ++i) {
			for (int b = i - 3; b >= 1; --b) {
				dp[i] = max(dp[i], dp[b] + dp[b] * (i - b - 2));
			}
		}
		return dp[N];
	}
};

本代码提交AC,用时0MS。

LeetCode 2 Keys Keyboard

LeetCode 2 Keys Keyboard
Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

  1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
  2. Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.
Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Note:

  1. The n will be in the range [1, 1000].

一个记事本中原本只有一个字符A,每次可以做两种操作中的一种,分别是全选和粘贴。问要得到n个字符A,至少需要经过多少次操作。
这一题我一开始想到用BFS来做,两种操作相当于两条搜索路径,所以很容易能写出BFS的代码:

class Solution {
private:
	struct Node {
		int presented_cnt_; // 现在有多少个字符
		int copied_cnt_; // 剪切板中有多少个字符
		int step_; // 走过多少步了
		Node(int p, int c, int s) :presented_cnt_(p), copied_cnt_(c), step_(s) {};
	};
public:
	int minSteps(int n) {
		queue<Node> q;
		Node node(1, 0, 0);
		q.push(node);
		while (!q.empty()) {
			Node cur = q.front();
			q.pop();
			if (cur.presented_cnt_ == n)
				return cur.step_;
			if (cur.presented_cnt_ > n)continue;
			Node copy_node(cur.presented_cnt_, cur.presented_cnt_, cur.step_ + 1); // 全选
			q.push(copy_node);
			if (cur.copied_cnt_ != 0) { // 粘贴
				Node paste_node(cur.presented_cnt_ + cur.copied_cnt_, cur.copied_cnt_, cur.step_ + 1);
				q.push(paste_node);
			}
		}
	}
};

预料到了,本代码提交TLE。
搜索会超时的,用DP一般都不会超时。设dp[i]表示要得到i个字符A,至少需要的操作数。显然,dp[1]=0。
假设已经求到了dp[1,...,i-1],现在要求dp[i]。要得到i个字符,最多的操作数是i,即先复制一个A,然后粘贴i-1次,总共需要i次操作。比较快的方法是,如果i是偶数,则可以从i/2个字符开始,全选粘贴就能得到i个字符。
所以我们遍历i前面的所有j,如果i能整除j,则可以全选j,然后粘贴i/j-1次得到i个字符,即操作数是1+(i/j-1)=i/j,当然还需要加上到达i的操作数,所以dp[j]=dp[i]+i/j。
完整代码如下:

class Solution {
public:
	int minSteps(int n) {
		vector<int> dp(n + 1, INT_MAX);
		dp[1] = 0;
		for (int i = 2; i <= n; ++i) {
			dp[i] = i;
			for (int j = i - 1; j >= 1; --j) {
				if (i%j == 0) {
					dp[i] = min(dp[i], dp[j] + i / j);
				}
			}
		}
		return dp[n];
	}
};

本代码提交AC,用时79MS。
还有一种解法类似于素数筛法,我们首先知道dp[1]=0,如果我们对1个字符先全选,然后不停粘贴,则能得到2,3,4,...个字符,且操作数是2,3,4,...;下一次,我们知道dp[2]=2,如果我们对2个字符全选,然后不停粘贴,则能得到4,6,8,...个字符,且操作数是4,5,6,...。每一轮我们都只保留最小操作数。最终筛完之后,就是全局最优结果了。
完整代码如下:

class Solution {
public:
	int minSteps(int n) {
		vector<int> dp(n + 1, INT_MAX);
		dp[1] = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = 2 * i, k = 2; j <= n; j += i, ++k) {
				dp[j] = min(dp[j], dp[i] + k);
			}
		}
		return dp[n];
	}
};

本代码提交AC,用时3MS,速度飞快,因为越到后面,循环倍数越少。