Joyce' Blog

search-a-2d-matrix

发表于 2020-02-13 更新于 2020-02-24

题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

题解

先二分法找行，再二分法找列。

最后提交的版本：

bool searchMatrix(vector<vector<int>>& matrix, int target) {
	int row = matrix.size();
	if (!row)return false;
	int col = matrix[0].size();
	if (!col)return false;

	int up = 0, down = row-1, mid = 0;
	while (up <= down)
	{
		mid = (up + down) / 2;
		if (matrix[mid][0] == target)return true;
		else if (matrix[mid][0] > target)
			down = mid - 1;
		else if (matrix[mid][col - 1] < target)
		{
			up = mid + 1;
		}
		else
			break;
	}
	int left = 0, right = col-1, center;
	while (left <= right)
	{
		center = (left + right) / 2;
		if (matrix[mid][center] == target)return true;
		else if (matrix[mid][center] < target)left = center+1;
		else right = center-1;
	}
	return false;
}

下面是修改之前找行数的while循环。修改之后的明显时间上快了许多。

while (up <= down)
	{
		mid = (up + down) / 2;
		if (matrix[mid][0] > target)
			down = mid-1;
		else if (matrix[mid][0] < target)
		{
			if (mid<row - 1 && matrix[mid + 1][0]>target)
				break;
			up = mid+1;
		}
		else
			return true;
	}

edit-distance & set-matrix-zeroes

发表于 2020-02-12 更新于 2020-02-13

题目描述

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

题解

果然最近都是考动态规划！编辑距离我应该是会的，明天试试~

int minDistance(string word1, string word2) {
	int len1 = word1.length();
	int len2 = word2.length();
	int **dist = new int*[len1+1];
	for (int i = 0; i <= len1; i++)
		dist[i] = new int[len2 + 1];
	for (int i = 0; i <= len1; i++)
		dist[i][0] = i;
	for (int j = 0; j <= len2; j++)
		dist[0][j] = j;

	for (int i = 1; i <= len1; i++)
	{
		for (int j = 1; j <= len2; j++)
		{
			int a = dist[i - 1][j - 1];
			int t = word1[i - 1] == word2[j - 1] ? a : a + 1;
			int k = min(dist[i][j - 1], dist[i - 1][j]) + 1;
			dist[i][j] = min(t, k);
		}
	}
	return dist[len1][len2];
}

一遍过，正常发挥。

题目描述

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

进阶:

一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

题解

O(m + n) 的额外空间也就是两个数组，记录哪一行全1，哪一列全1吧，常数空间的话，看了下官方题解，是在原有的矩阵上做标记，m[i][j]=0，就把m[0][j]和m[i][0]都置为零。

emm……官方题解有问题，用特殊数字做标记行不通。就写 O(m + n) 的吧。

void setZeroes(vector<vector<int>>& matrix) {
	int m = matrix.size();
	int n = matrix[0].size();
	bool *row, *col;
	row = new bool[m];
	col = new bool[n];
	for (int i = 0; i < m; i++)
		row[i] = 1;
	for (int i = 0;i < n; i++)
		col[i] = 1;
 	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!matrix[i][j])
			{
				row[i] = 0;
				col[j] = 0;
			}
		}
	}
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!(row[i]&col[j]))
			{
				matrix[i][j] = 0;
			}
		}
	}
}

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

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

我觉得可以接受。

simplify-path

发表于 2020-02-12

题目描述

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

题解

或许需要用一个栈，遇到文件名压入，遇到“/../”弹出，遇到”/./“忽略，连续的斜杠只算一个，最后再把栈里剩下的连起来。

string simplifyPath(string path) {
	int len = path.length();
	if (len <= 1)return "/";
	stack<string> s;
	string str = "";
	int i = 1;
	while (i < len)
	{
		while (i < len&&path[i] == '/')i++;
		if (i<len&&path[i] == '.')
		{
			if (i + 1 < len&&path[i + 1] == '.')
			{
				if (i+2==len||i + 2<len&&path[i + 2] == '/')
				{
					if (!s.empty())s.pop();
					i += 3;
				}
				else if (i + 2<len)
				{
					while (i < len&&path[i] != '/')
					{
						str = str + path[i];
						i++;
					}
					s.push(str);
					str = "";
				}
			}
			else if (i + 1 == len || i + 1 < len&&path[i + 1] == '/')
				i += 2;
			else
			{
				while (i < len&&path[i] != '/')
				{
					str = str + path[i];
					i++;
				}
				s.push(str);
				str = "";
			}
		}
		else
		{
			while (i < len&&path[i] != '/')
			{
				str = str + path[i];
				i++;
			}
			if (str.length() > 0)
				s.push(str);
			str = "";
		}
	}
	string res = "";
	while (!s.empty())
	{
		string t = s.top();
		res = '/' + t + res;
		s.pop();
	}
	if (!res.length())
		return "/";
	return res;
}

其实应该是可以在原来的字符串上直接修改的。

while语句总是忘了写递增条件，这是什么坏毛病。

…居然是文件名？？太过分了，测试如下：

[root@iZm5efgntvp9yn8px32ud1Z ~]# cd ...
-bash: cd: ...: No such file or directory
[root@iZm5efgntvp9yn8px32ud1Z ~]# cd ....
-bash: cd: ....: No such file or directory
[root@iZm5efgntvp9yn8px32ud1Z ~]# cd ..
[root@iZm5efgntvp9yn8px32ud1Z /]# cd .
[root@iZm5efgntvp9yn8px32ud1Z /]#

sqrtx & climbing-stairs

发表于 2020-02-12

题目描述

实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

题解

二分法

int mySqrt(int x) {
	if (!x||x==1)return x;
	int left = 0, right = x;
	//left不应从1开始，否则right=INT_MAX时，left+right会越界
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (x / mid >= mid && x / (mid+1) < (mid + 1))return mid;
		else if (x / mid < mid)right = mid;
		else left = mid;
	}
	return left;
}

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

题解

动态规划

int climbStairs(int n) {
	if (n <= 2)return n;
	int step;
	int step1 = 1;
	int step2 = 2;
	int i = n - 3;
	while (i >= 0)
	{
		step = step1 +  step2;
		step2 = step1;
		step1 = step;
		i--;
	}
	return step;
}

plus-one & add-binary

发表于 2020-02-10 更新于 2020-02-11

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

题解

不适合转成整数加1后再存进去，如果数组太长的话，整型存不下。

vector<int> plusOne(vector<int>& digits) {
	int vsize = digits.size();
	int i = vsize - 1;
	if (digits[i] < 9)
	{
		digits[i] += 1;
		return digits;
	}
	digits[i] = 0;
	i--;
	while (i >= 0)
	{
		if (digits[i] < 9)
		{
			digits[i] += 1;
			return digits;
		}
		digits[i] = 0;
		i--;
	}
	if (!digits[i + 1])digits.insert(digits.begin(), 1);
	return digits;
}

题目描述

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

题解

逐位判断

string addBinary(string a, string b) {
	bool c = false;
	int lena = a.length();
	int lenb = b.length();
	string res="";
	int i = lena - 1; int j = lenb - 1;
	while (i >= 0 && j >= 0)
	{

		if (c)//有进位
		{
			if (a[i] == '1')
			{
				if (b[j] == '1')
					res = "1"+ res;
				else
					res = "0" + res;
			}
			else
			{
				if (b[j] == '0')
				{
					res = "1" + res;
					c = false;
				}
				else
					res = "0" + res;
			}
		}
		else
		{
			if (a[i] == '1')
				if (b[j] == '1')
				{
					res = "0" + res;
					c = true;
				}
				else
					res = "1" + res;
			else
				res = b[j] + res;
		}
		i--; j--;
	}
	
	while (i >= 0)
	{
		if (c)
			if (a[i] == '1')
				res = "0" + res;
			else
			{
				res = "1" + res;
				c = false;
			}
		else
			res = a[i] + res;
		i--;
	}
	while (j >= 0)
	{
		if (c)
		{
			if (b[j] == '1')
				res = "0" + res;
			else
			{
				res = "1" + res;
				c = false;
			}
		}
		else
			res = b[j] + res;
		j--;
	}
	if (c)return '1' + res;
	return res;
}

有点慢……改为位操作：首先计算两个数字的无进位相加结果和进位，然后计算无进位相加结果与进位之和。同理求和问题又可以转换成上一步，直到进位为 0 结束。

class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            x, y = x ^ y, (x & y) << 1
        return bin(x)[2:]
链接：https://leetcode-cn.com/problems/add-binary/solution/er-jin-zhi-qiu-he-by-leetcode/

minimum-path-sum & valid-number

发表于 2020-02-10

题目描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

题解

感觉，和62, 63题的思路没有区别。可不可以把二维数组缩减为一位数组呢？没想出来……下面这样其实也还不错。

int minPathSum(vector<vector<int>>& grid) {
	int m = grid.size();//行
	int n = grid[0].size();//列
	int **a = new int*[m];
	for (int i = 0; i < m; i++)
		a[i] = new int[n];
	a[m - 1][n - 1] = grid[m - 1][n - 1];
	for (int i = m - 2; i >= 0; i--)
		a[i][n - 1] = a[i + 1][n - 1] + grid[i][n - 1];
	for (int i = n - 2; i >= 0; i--)
		a[m - 1][i] = a[m - 1][i + 1] + grid[m - 1][i];
	for (int i = m - 2; i >= 0; i--)
	{
		for (int j = n - 2; j >= 0; j--)
		{
			a[i][j] = grid[i][j] + min(a[i + 1][j], a[i][j + 1]);
		}
	}
	return a[0][0];
}

题目描述

验证给定的字符串是否可以解释为十进制数字。

说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表：

数字 0-9
指数 - “e”
正/负号 - “+”/“-“
小数点 - “.”

当然，在输入中，这些字符的上下文也很重要

题解

有种自动机的味道。

剩下的就是各种面向特殊样例编程的过程了。

int start = 0;
bool get_exp(string s, int & i, int len)
{
	i++;
	if (i == len)return false;
	if (s[i] == '-' || s[i] == '+')
	{
		i++;
		if (s[i] >= '0'&&s[i] <= '9')
		{
			while (i < len&&s[i] >= '0'&&s[i] <= '9')
			{
				i++;
			}
			if (i == len)return true;
		}
	}
	else if (i < len&&s[i] >= '0'&&s[i] <= '9')
	{
		while (i < len&&s[i] >= '0'&&s[i] <= '9')
		{
			i++;
		}
		if (i == len)return true;
	}
	return false;
}
bool get_frac(string s, int & i, int len)
{
	i++;
	if (i == len && i - 1 == start)return false;
	while (i<len&&s[i] >= '0'&&s[i] <= '9')
	{
		i++;
	}
	if (i == len)return true;
	else if (s[i] == 'e')
	{
		if (i - 1 == start)
			return false;
		else
			return get_exp(s, i, len);
	}
	return false;
}
bool isNumber(string s) {
	int len = s.length();
	if (!len)return false;
	int i = 0;
	while (s[i] == ' ') { i++; }
	start = i;
	while (s[len - 1] == ' ')len--;
	if (i < len)
	{
		if (s[i] == '-' || s[i] == '+')
		{
			i++;
			if (i == len)return false;
			if (s[i] >= '0'&&s[i] <= '9')
			{
				while (i < len&&s[i] >= '0'&&s[i] <= '9')
				{
					i++;
				}
				if (i == len)return true;
				else if (s[i] == '.')
				{
					return get_frac(s, i, len);
				}
				else if (s[i] == 'e')
				{
					return get_exp(s, i, len);
				}
			}
			else if (s[i] == '.')
			{
				return get_frac(s, i, len);
			}
		}
		else if (s[i] >= '0'&&s[i] <= '9')
		{
			while (i < len&&s[i] >= '0'&&s[i] <= '9')
			{
				i++;
			}
			if (i == len)return true;
			else if (s[i] == '.')
			{
				return get_frac(s, i, len);
			}
			else if (s[i] == 'e')
			{
				return get_exp(s, i, len);
			}
		}
		else if (s[i] == '.')
		{
			return get_frac(s, i, len);
		}
	}
	return false;
}

rotate-list & unique-paths

发表于 2020-02-09 更新于 2020-02-10

题目描述

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

题解

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

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。

题解

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

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。

题解

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

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];
}

spiral-matrix-ii & permutation-sequence

发表于 2020-02-09

题目描述

给定一个正整数 n，生成一个包含 1 到 $n^2$ 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

题解

与上次螺旋矩阵思路类似，还是按照顺时针的顺序，先把空填了，再按顺序读出来。看起来效率还不错。

vector<vector<int>> generateMatrix(int n) {
	vector<vector<int>> res;
	int **tmp = new int*[n];
	for (int i = 0; i < n; i++)
		tmp[i] = new int[n];
	int i = 0, j = 0;
	int base_i = 0, base_j = 0;
	int value = 1;
	int m = n;
	int p = n;

	while (true)
	{
		while (j < p)
		{
			tmp[i][j] = value++;
			j++;
		}
		j = p - 1;
		base_i++;
		if (base_i == m)break;
		i = base_i;
		while (i < m)
		{
			tmp[i][j] = value++;
			i++;
		}
		i = m - 1;
		p--;
		if (p == base_j)break;
		j = p - 1;
		while (j >= base_j)
		{
			tmp[i][j] = value++;
			j--;
		}
		j = base_j;
		m--;
		if (base_i == m)break;
		i = m - 1;
		while (i >= base_i)
		{
			tmp[i][j] = value++;
			i--;
		}
		i = base_i;
		base_j++;
		if (base_j == p)break;
		j = base_j;
	}
	for (int i = 0; i < n; i++)
	{
		vector<int> k;
		for (int j = 0; j < n; j++)
			k.push_back(tmp[i][j]);
		res.push_back(k);
	}
	return res;
}

题目描述

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”
“132”
“213”
“231”
“312”
“321”

给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。

题解

有一说一，我觉得我的思路不错。不用挨着找出每个排列，而是计算k与(n-1)! 的关系

int fac(int n)
{
	if (n == 1)return 1;
	return n * fac(n - 1);
}
string res = "";
void getNext(vector<char>& number, int n, int k)
{
	if (n == 1)
	{
		res = res + number[0];
		return;
	}
	int f = fac(n - 1);
	int w = (k - 1) / f;
	res = res + number[w];
	number.erase(number.begin() + w);
	getNext(number, n - 1, k-w*f);
}
string getPermutation(int n, int k) {
	vector<char> number;
	for (int i = 1; i <= n; i++)
		number.push_back('0'+i);
	getNext(number, n, k);
	return res;
}

insert-interval & length-of-last-word

发表于 2020-02-08 更新于 2020-02-09

题目描述

给出一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

题解

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
	int vsize = intervals.size();
	if (!vsize)return { newInterval };
	vector<vector<int>> res;

	int i = 0;
	while (i<vsize&&intervals[i][1] < newInterval[0])
	{
		res.push_back(intervals[i]);
		i++;
	}

	int j = i;
	if (i<vsize&&intervals[i][0] > newInterval[1])
	{
		res.push_back(newInterval);
	}
	else if (i == vsize && intervals[i - 1][1] < newInterval[0])
	{
		res.push_back(newInterval);
	}
	else
	{
		intervals[i][0] = min(intervals[i][0], newInterval[0]);

		while (j < vsize&&intervals[j][0] <= newInterval[1])j++;

		intervals[i][1] = max(intervals[j - 1][1], newInterval[1]);
		res.push_back(intervals[i]);
	}

	while (j < vsize)
	{
		res.push_back(intervals[j]);
		j++;
	}
	return res;
}

怎么觉得我的代码像一件缝缝补补的烂衣裳……

不过时间效率还是不错的。

题目描述

给定一个仅包含大小写字母和空格 ‘ ‘ 的字符串 s，返回其最后一个单词的长度。

如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词，请返回 0 。

说明：一个单词是指仅由字母组成、不包含任何空格的最大子字符串。

题解

用split()函数应该挺快的，不过C++没有。

int lengthOfLastWord(string s) {
	int len = s.length();
	while (len>0 && s[len - 1] == ' ')len--;
	int i = len - 1;
	while (i >= 0 && s[i] != ' ')
		i--;
	return len - i;
}

jump-game && merge-intervals

发表于 2020-02-08

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

题解

最先浮现在脑中的是一个图的结构。

其实是看起点最远能到达的点吧？动态规划：$dp[i]=max( \sum_{k=1}^{nums[i]}dp[i+k] ,i)$

更进一步，或许连dp数组都不需要呢？还没想出来，先要着吧。

在细节上做了一点修改。

bool canJump(vector<int>& nums) {
	int vsize = nums.size();
	bool* dp;
	dp = new bool[vsize];
	for (int i = 0; i < vsize - 1; i++)
		dp[i] = false;
	dp[vsize - 1] = true;
	int k = vsize - 2;
	while (k >= 0)
	{
		int step = nums[k];
		if (k + step >= vsize-1)
			dp[k] = true;
		else
		{
			while (!dp[k]&&step)
			{
				dp[k] = dp[k + step];
				step--;
			}
		}
		k--;
	}
	return dp[0];
}

倒是没出什么大问题，只不过时空效率低得没脸看……

题目描述

给出一个区间的集合，请合并所有重叠的区间。

题解

这个时候排序就很重要了。如果是一个二维数组，也可以是用sort，我们可以选择根据某一列来进行排序，如果我们不重写cmp函数，那么默认的是根据第一列来排序。

vector<vector<int>> merge(vector<vector<int>>& intervals) {
	int vsize = intervals.size();
	if (vsize <= 1)return intervals;
	sort(intervals.begin(), intervals.end());
	vector<vector<int>> res;
	res.push_back(intervals[0]);
	for (int i = 1; i < vsize; i++)
	{
		if (res.back()[1] >= intervals[i][0])//有重叠
			res.back()[1] = max(res.back()[1], intervals[i][1]);
		else//无重叠
			res.push_back(intervals[i]);
	}
	return res;
}