算法刷题记录(Day 61)

题目链接

解题思路:使用两个指针，分别指向数组的前端(指针i)和数组的后端(指针j)，当i指向的元素为偶数时，则不再移动i，当j指向的元素为奇数时，则不再移动j。然后交换i和j。

//测试样例
In:
5
1 2 3 4 5
Out:1 5 3 4 2

In:
6
1 2 3 4 5 6
Out:
1 5 3 4 2 6

In:
9
78 1278 91381 29 199 11 20 121 29
Out:
29 121 91381 29 199 11 20 1278 78

#include
#include
using namespace std;
#define NMAX 1000
int n;
int num[NMAX];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> num[i];
	int i = 0, j = n - 1;
	while (i < j) {
		while (num[i] % 2 == 1) i++;
		while (num[j] % 2 == 0) j--;
		if(i 
 
 
tip:
 1.注意条件的判断即什么时候进行交换，什么时候跳出循环
 
 
第二题 
解题思路:首先需要知道任一两个小区之间的最短路->使用floyd算法，但是时间复杂度为O(n3)。然后对于每列，需要计算最大值->时间复杂度为O(n2)。对于得到的n个最大值，再去寻找最小值，其所对应的小区编号，即为所求的解。
 
In:
3
0 1 2
1 0 3
2 3 0
Out:
0

In:
3
0 0 2
0 0 3
2 3 0
Out:
2

In:
4
0 7 2 5
7 0 0 2
2 0 0 1
5 2 1 0
Out:
2
 
#include
using namespace std;
#define NMAX 100
#define INF 0x3fffffff
int n;
int map[NMAX][NMAX];
int floyd[NMAX][NMAX];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j]) floyd[i][j] = map[i][j];
			else floyd[i][j] = INF;
		}
	}

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (floyd[i][j] > floyd[i][k] + floyd[k][j]) floyd[i][j] = floyd[i][k] + floyd[k][j];
			}
		}
	}
	int maxres = INF;
	int res=0;
	for (int i = 0; i < n; i++) {
		int maxcur = 0;
		for (int j = 0; j < n; j++) {
			if (floyd[i][j] > maxcur) maxcur = floyd[i][j];
		}
		if (maxcur < maxres) {
			maxres = maxcur;
			res = i;
		}
	}

	cout << res << endl;
}
 
 
 
tip：
 1.注意floyd的核心代码是对当前路径不是最小路径进行更新
 
 
第三题 
解题思路:
 动态规划,dp[i]代表走到位置i所需要的最少步数
 dp[i]=min(dp[i-1],dp[j])+1 ，其中j为i前面的和i的数字一样的位置。
 为了维护i和j的位置，需要设置一个数组，lot[i]数组存储的是数值为i的位置值。
 同时，在遍历的过程中，需要p[i]指针来指示当前已经遍历到lot[i]的哪一个位置。
 
In:
6
0 1 0 3 4 1
Out:
2

In:
6
0 1 2 3 4 5
Out:
5

In:
8
9 8 9 5 9 2 5 1
Out:
4

 
#include
#include
using namespace std;
#define NMAX 1000
int p[10];
vector > lot(10);
int n;
int num[NMAX], dp[NMAX];
int main() {
	memset(num, 0, sizeof(num));
	memset(dp, 0, sizeof(dp));
	memset(p, 0, sizeof(p));
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
		lot[num[i]].push_back(i);
	}
	dp[0] = 0;
	p[num[0]]++;
	for (int i = 1; i < n; i++) {
		dp[i] = dp[i - 1] + 1;
		if (p[num[i]]) dp[i] = min(dp[i], dp[lot[num[i]][p[num[i]] - 1]] + 1);
		p[num[i]]++;
	}
	cout << dp[n - 1] << endl;
}