Joyce' Blog

bytedancer-interview-note

发表于 2020-07-03 更新于 2020-07-06

search-in-rotated-sorted-array

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

阅读全文 »

小兔的棋盘

发表于 2020-07-01 更新于 2020-07-06

题目描述

棋盘，从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?

阅读全文 »

way-in-matrix

发表于 2020-07-01

题目描述

设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。

题解

深度优先搜索

bool find(vector<vector<char>>& board, bool** access, string s, int index, int x, int y)
{
	if (index == s.length())return true;
	if (access[x][y + 1] && board[x - 1][y] == s[index])
	{
		access[x][y + 1] = false;
		bool ext = find(board, access, s, index + 1, x - 1, y);
		if (ext)return true;
		access[x][y + 1] = true;
	}
	if (access[x + 2][y + 1] && board[x + 1][y] == s[index])
	{
		access[x + 2][y + 1] = false;
		bool ext = find(board, access, s, index + 1, x + 1, y);
		if (ext)return true;
		access[x + 2][y + 1] = true;
	}
	if (access[x + 1][y] && board[x][y - 1] == s[index])
	{
		access[x + 1][y] = false;
		bool ext = find(board, access, s, index + 1, x, y - 1);
		if (ext)return true;
		access[x + 1][y] = true;
	}
	if (access[x + 1][y + 2] && board[x][y + 1] == s[index])
	{
		access[x + 1][y + 2] = false;
		bool ext = find(board, access, s, index + 1, x, y + 1);
		if (ext)return true;
		access[x + 1][y + 2] = true;
	}
	return false;
}
bool exist(vector<vector<char>>& board, string word) {
	//深度优先搜索
	int len = word.length(); if (!len)return true;
	//m行n列
	int m = board.size();
	if (!m)return false;
	int n = board[0].size();
	bool** access = new bool*[m + 2];
	for (int i = 0; i<m+2; i++)
		access[i] = new bool[n + 2];
	for (int i = 1; i<m + 1; i++)
		for (int j = 1; j<n + 1; j++)
			access[i][j] = true;
	for (int i = 0; i<m + 2; i++)
	{
		access[i][0] = false;
		access[i][n + 1] = false;
	}
	for (int i = 0; i<n + 2; i++)
	{
		access[0][i] = false;
		access[m + 1][i] = false;
	}
	for (int i = 0; i<board.size(); i++)
	{
		for (int j = 0; j<board[0].size(); j++)
		{
			if (board[i][j] == word[0])
			{
				access[i + 1][j + 1] = false;
				bool ext = find(board, access, word, 1, i, j);
				if (ext)return true;
				access[i + 1][j + 1] = true;
			}
		}
	}
	return false;
}

min-num-in-spinning-array

发表于 2020-07-01

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。

题解

最小元素所在的位置就是旋转点。

int minArray(vector<int>& numbers) {
	int size = numbers.size();
	if (!size)return -1;
	int left = 0, right = size - 1;
	while (left < right)
	{
		int m = (left + right) / 2;
		if (numbers[m] > numbers[right])
			left = m + 1;
		else if (numbers[m] < numbers[right])
			right = m;
		else
			right--;
	}
	return numbers[left];
}

一开始也想用二分法解决来着……但是没有写出来……还是要多学习。

rebuild-bintree

发表于 2020-06-30 更新于 2020-07-01

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

题解

明明都知道要用递归来建左子树和右子树，却一直写不对递归的参数。唉。

TreeNode * makeTree(vector<int>& preorder, vector<int>& inorder, int index, int left, int right)
{
	if (left > right)return nullptr;
	TreeNode* root = new TreeNode(preorder[index]);
	if (left == right)return root;
	int i = left;
	while (inorder[i] != preorder[index])i++;
	root->left = makeTree(preorder, inorder, index + 1, left, i - 1);
	root->right = makeTree(preorder, inorder, index + i - left + 1, i + 1, right);
	return root;
}

TreeNode * buildTree(vector<int>& preorder, vector<int>& inorder) {
	int right = inorder.size();
	if (!right)return nullptr;
	return makeTree(preorder, inorder, 0, 0, right-1);
}

注意什么时候返回nullptr。

re-num-in-array

发表于 2020-06-29 更新于 2020-07-01

题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

题解

可以借助set数据结构，使用它的count()和insert()两个功能：

int findRepeatNumber(vector<int>& nums) {
	//使用set数据结构
	set<int> s;
	for (int i = 0; i < nums.size(); i++)
	{
		if (s.count(nums[i]))
			return nums[i];
		else
			s.insert(nums[i]);
	}
	return 0;
}

另一种时间复杂度更低的解法：

如果没有重复的话，数值i应该在第i个位置上，所以，从前往后遍历数组，当遇到num[i] = m != i时，将nums[i]与nums[m]互换，直到num[i]==i，如果中途遇到相同的值，就立即返回。

int findRepeatNumber(vector<int>& nums) {
	for (int i = 0; i < nums.size(); i++)
	{
		while (nums[i] != i)
		{
			int m = nums[i];
			if (nums[m] == m)
				return m;
			nums[i] = nums[m];
			nums[m] = m;
		}
	}
	return -1;
}

reverse-words-in-a-string

发表于 2020-06-20 更新于 2020-06-21

题目描述

给定一个字符串，逐个翻转字符串中的每个单词。

说明：

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

题解

先放一个空间复杂度为O(n)的：

string reverseWords(string s) {
	string word = "";
	int i = 0, j = 0;
	stack<string> stk;
	while (s[i] == ' ')
		i++;
	j = i;
	while (i < s.length())
	{
		while (j<s.length()&&s[j] != ' ')j++;
		if (j == s.length())
		{
			if(j>i)
				stk.push(s.substr(i, j - i));
			break;
		}
		stk.push(s.substr(i, j - i));
		while (s[j] == ' ')
			j++;
		i = j;
	}
	string res = " ";
	while (!stk.empty())
	{
		word = stk.top();
		stk.pop();
		res =res+ word+" ";
	}
	if (res.length() == 1)return "";
	return res.substr(1, res.length() - 2);
}

不过效率太低了。睡一觉再改吧。

先将字符串整个反转一下，然后再反转单个单词就行了。这其中可以去掉空格。

string reverseWords(string s)
{
	reverse(s.begin(), s.end());
	int n = s.size();
	int idx = 0;
	for (int i = 0; i < n; i++)
	{
		if (s[i] != ' ')
		{
			if (idx != 0)
				s[idx++] = ' ';
			int j = i;
			while (j < n&&s[j] != ' ')
			{
				s[idx++] = s[j++];
			}
			reverse(s.begin() + idx - (j - i), s.begin() + idx);
			i = j;
		}
	}
	s.erase(s.begin() + idx, s.end());
	return s;
}

evaluate-reverse-polish-notation

发表于 2020-06-15

题目描述

根据逆波兰表示法，求表达式的值。（即后缀表达式）

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

题解

要用到栈的结构吧，遇到一个操作符就弹出两个操作数，然后压入计算结果。

int evalRPN(vector<string>& tokens) {
	stack<int> st;
	int num = tokens.size();
	int res = 0;
	for (int i = 0; i < num; i++)
	{
		string tk = tokens[i];
		if (tk == "+")
		{
			int op1 = st.top();
			st.pop();
			int op2 = st.top();
			st.pop();
			op1 += op2;
			st.push(op1);
		}
		else if(tk=="-")
		{
			int op1 = st.top();
			st.pop();
			int op2 = st.top();
			st.pop();
			op2 -= op1;
			st.push(op2);
		}
		else if (tk == "*")
		{
			int op1 = st.top();
			st.pop();
			int op2 = st.top();
			st.pop();
			op1 *= op2;
			st.push(op1);
		}
		else if (tk == "/")
		{
			int op1 = st.top();
			st.pop();
			int op2 = st.top();
			st.pop();
			op2 /= op1;
			st.push(op2);
		}
		else
		{
			int tmp = stoi(tk);
			st.push(tmp);
		}
	}
	return st.top();
}

max-points-on-a-line

发表于 2020-06-13 更新于 2020-06-14

题目描述

给定一个二维平面，平面上有 n 个点，求最多有多少个点在同一条直线上。

题解

对于每一个定点，向后面遍历每一个点，就得到一条直线，找在这条直线上最多的点数。

斜率如果是小数的话就会存在精度问题，不能做key，因此对分数进行约分，保存为特殊字符串：”分子@分母”。约分的话需要找出最大公约数gcd，计算gcd需要使用辗转相除法。

还要考虑重复的点。

inline int gcd(int a, int b)
{
	while (b != 0) {
		int temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}
int maxPoints(vector<vector<int>>& points) {
	int number = points.size();
	if (number < 3)return number;
	int res = 0;
	for (int i = 0; i < number - 1; i++)
	{
		int dup = 0;
		int Max = 0;//保存经过当前点的直线中，最多的点
		unordered_map<string, int>m;
		for (int j = i + 1; j < number; j++)
		{
			int x = points[i][0] - points[j][0];
			int y = points[i][1] - points[j][1];
			if (x == 0 && y == 0)
			{
				dup++;
				continue;
			}
			if (x < 0) { x = -x; y = -y; }
			int i = gcd(x, y);
			x /= i; y /= i;
			string s = to_string(x);
			s = s + "@" + to_string(y);
			if (!m.count(s))m[s] = 1;
			else m[s]++;
			if (Max < m[s])
				Max = m[s];
		}
		res = max(res, Max + dup + 1);
	}
	return res;
}

怎么办啊我太菜了。

sort-list

发表于 2020-06-12

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

题解

ListNode merge(ListNode h1, ListNode* h2) 双路归并
ListNode cut(ListNode h, int n) 断链
dummy Head

常数级空间复杂度，不能使用递归，使用bottom-to-up的算法。先两个两个的 merge，完成一趟后，再 4 个4个的 merge，直到结束。

ListNode* merge(ListNode* h1, ListNode* h2)
{
	ListNode dummy(0);
	ListNode* p = &dummy;
	while (h1&&h2)
	{
		if (h1->val > h2->val)
		{
			p->next = h2;
			h2 = h2->next;
			p = p->next;
		}
		else
		{
			p->next = h1;
			h1 = h1->next;
			p = p->next;
		}
	}
	p->next = h1 ? h1 : h2;
	return dummy.next;
}
ListNode* cut(ListNode* h, int n)
{
	ListNode* p = h;
	while (--n&&p)
		p = p->next;
	if (!p)return nullptr;
	ListNode* nh = p->next;
	p->next = nullptr;
	return nh;
}
ListNode* sortList(ListNode* head) {
	ListNode dummyHead(0);
	dummyHead.next = head;
	ListNode *current = dummyHead.next;
	ListNode *tail = &dummyHead;
	int length = 0;
	ListNode*tmp = head;
	while (tmp)
	{
		tmp = tmp->next;
		length++;
	}
	ListNode *left, *right;
	for (int step = 1; step < length; step<<1)
	{
		current = dummyHead.next;
		tail = &dummyHead;
		while (current)
		{
			left = current;
			right = cut(current, step);
			current = cut(right, step);
			tail->next = merge(left, right);
			while (tail->next)
			{
				tail = tail->next;
			}
		}
	}
	return dummyHead.next;
}

或许可以恢复状态了。