Joyce' Blog
0%

rotate-list & unique-paths

发表于 更新于

题目描述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

题解

倒不是很难，但是怎么让效率高一些？最初的想法是新创建一个链表，利用原链表的值，找对应关系，完成新链表；后来觉得也可以直接改变next指针，毕竟两个子链表内部的顺序是不变的。

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
ListNode* rotateRight(ListNode* head, int k) {
	if (!head)return head;
	int len = 1;
	ListNode* t = head;
	while (t->next)
	{
		len++;
		t = t->next;
	}
	k = k % len;
	if (!k)return head;
	t->next = head;

	t= head;
	int start = len - k;
	while (start > 1)
	{
		t = t->next;
		start--;
	}
	head = t->next;
	t->next = NULL;

	return head;
}

执行用时 :8 ms, 在所有 C++ 提交中击败了86.96%的用户

内存消耗 :8.9 MB, 在所有 C++ 提交中击败了58.02%的用户

果然不错。

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

说明：m 和 n的值均不超过 100。

题解

动态规划，用一个二维数组记录路径数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int uniquePaths(int m, int n) {
	int **a = new int*[n];
	for (int i = 0; i < n; i++)
	{
		a[i] = new int[m];
		a[i][m - 1] = 1;
	}
	for (int i = 0; i < m-1; i++)
		a[n - 1][i] = 1;
	for (int i = n-2; i >=0; i--)
	{
		for (int j = m-2; j >=0; j--)
		{
			a[i][j] = a[i + 1][j] + a[i][j + 1];
		}
	}
	return a[0][0];
}

时间我很满意。

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

题解

思路与上一题相同，细节上做了一些修改。

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
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
	int n = obstacleGrid.size();
	int m = obstacleGrid[0].size();
	if (obstacleGrid[0][0]||obstacleGrid[n - 1][m - 1])return 0;
	long **a = new long*[n];
	for (int i = n - 1; i >= 0; i--)
		a[i] = new long[m];
	a[n - 1][m - 1] = 1;
	for (int i = n - 2; i >= 0; i--)
	{
		if (obstacleGrid[i][m - 1])
			a[i][m - 1] = 0;
		else
			a[i][m - 1] = a[i + 1][m - 1];
	}
	for (int i =m-2; i >=0; i--)
	{
		if (obstacleGrid[n - 1][i])
			a[n - 1][i] = 0;
		else
			a[n - 1][i] = a[n - 1][i + 1];
	}
		
	for (int i = n - 2; i >= 0; i--)
	{
		for (int j = m - 2; j >= 0; j--)
		{
			if (obstacleGrid[i][j])
				a[i][j] = 0;
			else
				a[i][j] = a[i + 1][j] + a[i][j + 1];
		}
	}
	return a[0][0];
}