Joyce' Blog
0%

发表于

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

题解

有一说一，我是真的不喜欢递归。 
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
vector<vector<int>>res = {};
vector<int> candidates1;
int mymin;
void dfs(int target, vector<int>& keepin,int index)
{
	if (!target)
	{
		res.push_back(keepin);
		return;
	}
	if (target < mymin)return;
	for (int i=index;i<candidates1.size();i++)
	{
		keepin.push_back(candidates1[i]);
		dfs(target - candidates1[i], keepin,i);//index=i 不走回头路
		keepin.pop_back();
	}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
	candidates1= candidates;
	vector<int>::iterator myMin = min_element(candidates.begin(), candidates.end());
	mymin = *myMin;
	vector<int> keepin = {};
	dfs(target, keepin,0);
	return res;
}

问题描述

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

题解

和上面那道题的区别，不能有重复元素，那index每次就往前走一步，但问题是vector里面有重复元素，这样最后找出来的vector里面就会有重复的vector，暂时想到的方法是每找到一个vector，进行排序后加入set进行去重。

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
36
37
38
class Solution {
set<vector<int>>res = {};
vector<int> candidates1;
int mymin;
int v_size;
vector<int> tmp;
void dfs(int target, vector<int>& keepin, int index)
{
	if (!target)
	{
		tmp = keepin;
		sort(tmp.begin(), tmp.end());
		//在这里若直接对keepin排序后插入，那么在回到调用函数时pop会出错
		res.insert(tmp);
		return;
	}
	if (target < mymin)return;
	for (int i = index; i<v_size; i++)
	{
		keepin.push_back(candidates1[i]);
		dfs(target - candidates1[i], keepin, i+1);//index=i+1 用过不能再用
		keepin.pop_back();
	}
}
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        	candidates1 = candidates;
	vector<int>::iterator myMin = min_element(candidates.begin(), candidates.end());
	mymin = *myMin;
	v_size = candidates.size();
	vector<int> keepin = {};
	dfs(target, keepin, 0);
	vector<vector<int>> v;
	for (auto i = res.begin(); i != res.end(); i++)
		v.push_back(*i);
	return v;
    }
};

浪费在去重上面的时间太多了，先对candidates排序，然后在回溯之前，对下一位数字判断，如果是相同的，就舍弃；因而不会有重复的集合出现。而且数据没有丢失，这是因为它的上个数在递归过程中能用到它（若它满足条件）。

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
36
37
38
vector<vector<int>>res = {};
vector<int> candidates1;
int mymin,v_size;
void dfs(int target, vector<int>& keepin, int index)
{
	if (!target)
	{
		res.push_back(keepin);
		return;
	}
	if (target < mymin)return;
	for (int i = index; i<v_size; i++)
	{
		keepin.push_back(candidates1[i]);
		dfs(target - candidates1[i], keepin, i+1);//index=i+1 用过不能再用
		int j = i+1;
		while (j < v_size)
		{
			if (candidates1[i] == candidates1[j])
				i = j;
			else
				break;
			j++;
		}
		keepin.pop_back();
	}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
	candidates1 = candidates; 
	sort(candidates1.begin(), candidates1.end());
	v_size = candidates.size();
	if (!v_size)return res;
	vector<int>::iterator myMin = min_element(candidates.begin(), candidates.end());
	mymin = *myMin;
	vector<int> keepin = {};
	dfs(target, keepin, 0);
	return res;
}

发表于 更新于

题目描述

解数独。可以假设给定的数独只有唯一解。

题解

得用递归回溯了。递归之前可以先把那些只有一种可能的空填上，减少递归的次数。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
set<char> line[9], column[9], area[9];
bool dfs(vector<vector<char>>& board)
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			if (board[i][j] == '.')
			{
				set<char> t,c;
				set_intersection(line[i].begin(), line[i].end(), column[j].begin(), column[j].end(), inserter(t, t.begin()));//交集
				set_intersection(t.begin(), t.end(), area[(i / 3) * 3 + j / 3].begin(), area[(i / 3) * 3 + j / 3].end(), inserter(c, c.begin()));
				auto it = c.begin();
				while (it != c.end())
				{
					board[i][j] = *it;
					line[i].erase(*it);
					column[j].erase(*it);
					area[(i / 3) * 3 + j / 3].erase(*it);
					if (dfs(board))
						return true;
					board[i][j] = '.';
					line[i].insert(*it);
					column[j].insert(*it);
					area[(i / 3) * 3 + j / 3].insert(*it);
					it++;
				}
				return false;
			}
		}
	}
	return true;
}
void solveSudoku(vector<vector<char>>& board) {
	//初始化剩余可用数字
	set<char> k= { '1','2','3','4','5','6','7','8','9' };
	for (int i = 0; i < 9; i++)
	{
		line[i] = k;
		column[i] = k;
		area[i] = k;
	}
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			char t1 = board[i][j];
			if (t1!='.')
			{
				line[i].erase(t1);
				column[j].erase(t1);
				area[(i / 3) * 3 + j / 3].erase(t1);
			}
		}
	}
	
	//处理唯一数字的情况
	bool changed = true;
	while (changed)
	{
		changed = false;
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				if (board[i][j] == '.')
				{
					set<char> t,c;
					//将两个set<int>合并成一个set<int>且去重
					set_intersection(line[i].begin(), line[i].end(), column[j].begin(), column[j].end(), inserter(t, t.begin()));//交集
					set_intersection(t.begin(), t.end(), area[(i / 3) * 3 + j / 3].begin(), area[(i / 3) * 3 + j / 3].end(), inserter(c, c.begin()));
					if (c.size() == 1)
					{
						changed = true;
						char k = *c.begin();
						board[i][j] = k;
						line[i].erase(k);
						column[j].erase(k);
						area[(i / 3) * 3 + j / 3].erase(k);
					}
				}
			}
		}
	}
	
	//递归，深度优先搜索
	dfs(board);
}

set_intersection这个函数不太了解，在上面踩了两次坑。

char和int的运算时间也没什么差别，全局变量和局部变量的运行时间也没什么差别，那这程序我还真不知道怎么优化了。

但是不预处理一种可能的空，确实会慢很多。

或许用位运算会快一些，胜过用set数据结构的求交运算。

问题描述

输出外观数列的第 n 项

题解

妥妥的递归

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
string countAndSay(int n) {
	if (n == 1)return "1";
	string s = countAndSay(n - 1);
	int i = 0;
	string res = ""; 
	int k = s.length();
	while (i < k)
	{
		char c = s[i];
		int count = 1;
		while (i< k-1)
		{
			if (c == s[i + 1])
			{
				i++;
				count++;
			}
			else
				break;
		}
		res =res+ to_string(count) + c;
		i++;
	}
	return res;
}

发表于

题目描述

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

题解

集合判断某个元素是否在集合中时间复杂度是O(1),如果使用列表的话就是O(n)了。划分子区域使用的是 pos = (i/3)*3 + j/3.

set.insert返回了一个pair, first貌似是一个迭代器, 第二个是一个bool, 表示成功与否

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isValidSudoku(vector<vector<char>>& board) {
	set<char> line[9], column[9], area[9];
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			char item = board[i][j];
			if (item != '.')
			{
				if(!(line[i].insert(item).second && column[j].insert(item).second && area[(i / 3) * 3 + j / 3].insert(item).second))
					return false;
			}
		}
	}
	return true;
}

本题可以使用一个99位二进制数判断数字是否被访问。第kk位数为11代表已加入，为00代表未加入
更新方式(记九位数为valval，传入的数字为nn)：
判断是否加入：将九位数右移位nn位，与11进行与运算
结果为0：未加入，将传入的数字加入九位数
结果为1：已加入，返回false
将传入的数字加入九位数：将1左移位n位，与val异或即可
链接：https://leetcode-cn.com/problems/valid-sudoku/solution/java-wei-yun-suan-xiang-jie-miao-dong-zuo-biao-bia/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int sodokuer(int n, int val)
{
	return ((val >> n) & 1 )== 1 ? -1 : val ^ (1 << n);// ^异或
}
bool isValidSudoku1(vector<vector<char>>& board) {
	for (int i = 0; i < 9; i++)
	{
		int t1 = 0, t2 = 0, t3 = 0;
		for (int j = 0; j < 9; j++)
		{
			int line = board[i][j] - 48;
			int column = board[j][i] - 48;//在一个循环内遍历一整列，则j为行号
			int area = board[(i / 3) * 3 + j / 3][(i % 3) * 3 + j % 3] - 48;
			// .的ascii码为46
			if (line > 0)t1 = sodokuer(line, t1);
			if (column > 0)t2 = sodokuer(column, t2);
			if (area > 0)t3 = sodokuer(area, t3);
			if (t1 == -1 || t2 == -1 || t3 == -1)
				return false;
		}
	}
	return true;
}

发表于

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。

题解

左右加减找下标的想法比较简单，但时间复杂度是O(n). 整个数组都是target值，往两边延伸复杂度最差会变成O(n+logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> searchRange(vector<int>& nums, int target) {
	int left = 0;
	int right = nums.size() - 1;
	int mid;
	int position = -1;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (nums[mid] == target)
		{
			position = mid;
			break;
		}
		else if (nums[mid] < target)left = mid + 1;
		else right = mid - 1;
	}
	if (position == -1)return{ -1,-1 };
	int begin = position, end = position;
	while (begin > 0 && nums[begin-1] == target)begin--;
	while (end<nums.size()-1 && nums[end+1] == target)end++;
	return{ begin,end };
}

原来是有库函数的啊！

lower_bound(): 指向首个不小于 value 的元素的迭代器，或若找不到这种元素则为 last
upper_bound(): 指向首个大于 value 的元素的迭代器，或若找不到这种元素则为 last

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> searchRange1(vector<int>& nums, int target)
{
	auto begin = lower_bound(nums.begin(), nums.end(), target);
	auto end = upper_bound(nums.begin(), nums.end(), target);
	int t1 = -1, t2 = -1;
	if (begin != nums.end())
	{
		t1 = begin - nums.begin();
		if (nums[t1] != target)
		{
			return{ -1,-1 };
		}
	}
	t2 = end - nums.begin() - 1;
	if (t2 >= 0)
	{
		if (nums[t2] != target)
			return{ -1,-1 };
	}
	else
		t2 = t1;
	return{ t1,t2 };
}

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

题解

1
2
3
4
5
int searchInsert(vector<int>& nums, int target) {
	auto left = lower_bound(nums.begin(), nums.end(), target);
	int res = left - nums.begin();
	return res;
}

发表于

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

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

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

题解

主要是在确定target在哪半边，nums从中间分开，一定有一边是从小到大，另一边为乱序，两端的数字存在大小联系。

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
int search(vector<int>& nums, int target) {
	int right = nums.size()-1;
	int left = 0;
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (nums[mid] == target)return mid;
		else if (nums[mid] > nums[right])
		{//右侧为乱序
			if (nums[left]>target || nums[mid] < target)
				left = mid + 1;
			else
				right = mid - 1;
		}
		else
		{//右侧为顺序
			if (nums[mid] < target && nums[right] >= target)
				left = mid + 1;
			else
				right = mid - 1;
		}
	}
	return -1;
}

发表于

题目描述

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

题解

创建一个标记数组，默认值全部为-1；
遇到右括号，向前匹配左括号，找到则将右括号标记为2，左括号标记为0
最后找出 连续的 >= 0 的 标记之和最大序列 即为最长有效括号

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
36
37
38
39
40
41
42
int longestValidParentheses(string s) {
	int size = s.length();
	int* flag = new int[size];
	/*for (int i = 0; i < size; i++)
		flag[i] = -1;*/
	memset(flag, -1, size);
	for (int i = 0; i < size; i++)
	{
		//当前第一个右括号
		if (s[i] == ')')
		{//向前找
			int j = i - 1;
			while (j >=0)
			{
				if (flag[j] ==-1 && s[j] == '(')
				{
					flag[j] = 0;
					flag[i] = 2;
					break;
				}
				j--;
			}
		}
	}
	for (int i = 0; i < size; i++)
		cout << flag[i] << " ";
	//找最多的连续的0
	int res = 0;
	int con = 0;
	for (int i = 0; i < size; i++)
	{
		if (flag[i]==-1)
		{
			res = res > con ? res : con;
			con = 0;
		}
		else
			con++;
	}
	res = res > con ? res : con;
	return res;
}

发表于

题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题解

要找到需要替换的关键位置，即nums[i]<nums[i+1]，然后找出后半段中最小的 大于nums[i] 的数，剩下的只需从小到大重新放入。

时间上还是不错的，空间做的不够好。

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
36
37
38
39
40
void nextPermutation(vector<int>& nums) {
	int size = nums.size();
	if (size <= 1)return;
	int* tmp = new int[size];
	int i;
	tmp[size - 1] = nums.back();
	for (i = size - 1; i > 0; i--)
	{
		int j = nums[i];
		int k = nums[i - 1];
		tmp[i-1] = k;
		if (j > k)
		{
			sort(tmp + i - 1, tmp + size);
			for (int x = size; x >= i; x--)
				nums.pop_back();
			int x;
			for (x = size - 2; x >=0; x--)
			{
				if (tmp[x] == k)
				{
					k = tmp[x + 1];
					nums.push_back(k);
					break;
				}
			}
			int y = x + 1;
			for (x = i - 1; x < size; x++)
				if (x!=y)
					nums.push_back(tmp[x]);
			break;
		}
	}
	if (i == 0)
	{
		nums.clear();
		for (i = size-1; i >=0; i--)
			nums.push_back(tmp[i]);
	}
}

发表于 更新于

题目描述

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

题解

为什么强调长度相同呢？想到的两种比较暴力的方法：一种是找到s中各个单词的位置，组合起来选出符合要求的；一种是列出单词的全部组合，与s进行匹配。学习了别人的比较好的想法：

假设words数组长度为L，word单词长度为WL,遍历字符串s, 下标记做i，需要比对的单词起始坐标则为 [i, i+WL, i+2WL … i+(L-1)WL]如果i满足条件，各个单词的第k位之和一定相等
即：words[0][k] + words[1][k] + … + words[L-1][k] == s[i + k] + s[i+WL + k] + … + s[i+(L-1)WL + k]
反之，若对于i，满足后者条件的i则可能为正确结果，这个时候直接校验即可。

总结：先找出符合特征的下标，再对符合下标的结果进行校验，完全符合则输出。
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/jian-dan-you-xiao-lu-de-jie-fa-by-luqihang/

上面可能都是废话。还是好好学学别人的吧

先把存在的字符串，放到 hashmap ，可以快速比较，然后每一个位置都进行匹配
但这里会有很多的重复计算，就可以使用一个小技巧，先计算目标串的每个字母的 ASCII 和，
然后和当前要匹配的字符串的每个字母的 ASCII 进行比较，如果不相等就不用进行下面的匹配过程了
链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/bao-li-suan-fa-jia-ru-qu-zhong-you-hua-10bei-ti-su/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> findSubstring1(string s, vector<string>& words) {
	vector<int> res;
	if (words.size()<1 || s.size()<1 || s.size() < words[0].size()*words.size()) return res;
	int wordLen = words[0].size(), lens = wordLen * words.size(), target = 0, cur = 0;
	unordered_map<string, int> allWord;
	for (auto& it : words) {
		allWord[it]++;
		for (auto& i : it) target += i;
	}
	for (int i = 0; i<lens; i++) cur += s[i];
	// 先看当前字符串的 ASCII 码相加是否相等 方便去重
	for (int i = 0, j; i <= s.size() - lens; cur -= s[i], cur += s[lens + i++]) {
		// 快速去重
		if (cur != target) continue;
		// 确认一下，是否为真的匹配
		unordered_map<string, int> tem(allWord);
		for (j = i; j<i + lens; j += wordLen)
			if (tem[s.substr(j, wordLen)]-- == 0) break;
		if (j == i + lens) res.push_back(i);
	}
	return res;
}

我是真的菜。不过新年快乐！

s.substr(0,5); //获得字符串s中从第0位开始的长度为5的字符

发表于 更新于

题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。

说明:

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [$−2^{31}$, $2^{31}$ − 1]。本题中，如果除法结果溢出，则返回 $2^{31} − 1$。

题解

不能用乘除，那只能用加减？挨个减也太慢了，使用位运算显得比较合理。另外，$−2^{31}$取绝对值时需要单独处理，并且需要用到unsigned int。用异或来计算是否符号相异。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int divide(int dividend, int divisor) {
	int min_limit = 0x80000000;
	if (!dividend)return 0;
	//除法结果溢出的唯一情况：
	if (dividend == INT_MIN && divisor == -1)
		return INT_MAX;
	bool negative = (dividend^divisor) < 0;
	unsigned int t = dividend == INT_MIN ? min_limit : abs(dividend);
	unsigned int d = divisor == INT_MIN ? min_limit : abs(divisor);
	unsigned int result = 0;
	for (int i = 31; i >= 0; i--)
	{
		//找出足够大的数2^n*divisor
		if (t >> i >= d)
		{
			result += ((unsigned int)1) << i ;
			t -= d << i;
		}
	}
	if (result == min_limit)
		return INT_MIN;
	return negative ? -(int)result : (int)result;
}

发表于

题目描述

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1

当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf()) 定义相符。

解决方案

比较简单的想法如下，但是时空消耗是在有点看不过去，最主要的问题是，如果字符串中重复的字符比较多，该算法就显得很蠢。

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
int strStr(string haystack, string needle) {
	int len1 = haystack.length();
	int len2 = needle.length();
	if (!len2)
		return 0;
	else
	{
		if (!len1)
			return -1;
		int i = -1, j = 0, k = 0;
		while (true)
		{
			j = 0; i++;
			while (i<len1 && haystack[i] != needle[j])
				i++;
			k = i;
			while (k<len1 && j<len2 && haystack[k] == needle[j])
			{
				k++; j++;
			}
			if (j == len2)
				return k - len2;
			if (k >= len1)
				return -1;
		}
	}
}

动态规划是个好东西，可惜我没掌握。

明天大年三十，我还是偷个懒，不学别人的优秀解法了吧。听说KMP 算法（Knuth-Morris-Pratt 算法）是一个著名的字符串匹配算法，效率很高，但是有点复杂。