Joyce' Blog
0%

发表于 更新于

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

题解

其实就是两个柱子之间的事情吧。进行组合选出最大值。

哈哈哈一次过！虽然时空效率不是很好，但至少证明抓住本质 困难题目也会变成简单题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int largestRectangleArea(vector<int>& heights) {
	int vsize = heights.size();
	if (!vsize)return 0;
	int res = heights[0];
	for (int i = 0; i < vsize; i++)
	{
		if (i&&heights[i - 1] >= heights[i])
			continue;
		int low = heights[i];
		for (int j = i; j < vsize; j++)
		{
			low = heights[j] < low ? heights[j] : low;
			int area = (j - i + 1)*low;
			res = area > res ? area : res;
		}
	}
	return res;
}

看了官方解析，觉得自己数据结构还是没学好。

单调递增栈操作规则

  1. 如果新的元素比栈顶元素大，就入栈
  2. 如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小

思路

  1. 对于一个高度，如果能得到向左和向右的边界
  2. 那么就能对每个高度求一次面积
  3. 遍历所有高度，即可得出最大面积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int largestRectangleArea(vector<int>& heights)
{
	int ans = 0;
	vector<int> st;
	heights.insert(heights.begin(), 0);
	heights.push_back(0);
	for (int i = 0; i < heights.size(); i++)
	{
		while (!st.empty() && heights[st.back()] > heights[i])
		{
			int cur = st.back();
			st.pop_back();
			ans = max(ans, (i-1 - st.back()) * heights[cur]);
		}
		st.push_back(i);
	}
	return ans;
}

发表于

题目描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* deleteDuplicates(ListNode* head) {
	if (!head || !head->next)return head;
	int value = head->val;
	ListNode* cur = head;
	while (cur&&cur->next)
	{
		value = cur->val;
		if (cur->next->val == value)
		{
			ListNode* tmp = cur->next;
			while (tmp&&tmp->val == value)
				tmp = tmp->next;
			cur->next = tmp;
		}
		cur = cur->next;
	}
	return head;
}

发表于

题目描述

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

题解

添加冗余的头节点！！！ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* deleteDuplicates(ListNode* head) {
	if (!head||!head->next)return head;
	ListNode*prehead;
	prehead = new ListNode(-1);
	prehead->next = head;
	ListNode* cur = prehead;
	while (cur->next&&cur->next->next)
	{
		if (cur->next->val == cur->next->next->val)
		{
			ListNode*tmp = cur->next;
			while (tmp->next&&tmp->val == tmp->next->val)
				tmp = tmp->next;
			cur->next = tmp->next;
		}
		else
			cur = cur->next;
	}
	return prehead->next;
}

发表于 更新于

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

题解

借鉴思路。链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/solution/zai-javazhong-ji-bai-liao-100de-yong-hu-by-reedfan/

本题是需要使用二分查找，怎么分是关键，举个例子：

第一类
1011110111 和 1110111101 这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
第二类
22 33 44 55 66 77 11 这种，也就是 nums[start] < nums[mid]。此例子中就是 2 < 5；
这种情况下，前半部分有序。因此如果 nums[start] <=target<nums[mid]，则在前半部分找，否则去后半部分找。
第三类
66 77 11 22 33 44 55 这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2；
这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找，否则去前半部分找。

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
bool search(vector<int>& nums, int target) {
	int right = nums.size() - 1;
	int left = 0;
	int mid = (left + right) / 2;
	while (left <= right)
	{
		while (left<mid&&nums[left] == nums[mid])left++;
		mid = (left + right) / 2;
		if (nums[mid] == target)return true;
		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 false;
}

发表于

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

题解

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
int removeDuplicates(vector<int>& nums) {
	int res = nums.size();
	if (res < 3)return res;
	bool twice = false;
	int pre = nums[0];
	auto it = nums.begin() + 1;
	while( it !=nums.end())
	{
		if (*it == pre)
		{
			if (twice)
			{
				it=nums.erase(it);
				res--;
			}
			else
			{
				twice = true;
				it++;
			}
		}
		else
		{
			pre = *it;
			twice = false;
			it++;
		}
	}
	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
class Solution {
    bool dfs(vector<vector<bool>>& avail,vector<vector<char>>& board, string word,int index,int si,int sj)
{
	if (index == word.length())return true;
	char k = word[index];
	bool flag[4] = { 0,0,0,0 };
	if (avail[si - 1][sj] && board[si - 1][sj] == k)
	{
		avail[si - 1][sj] = false;
		flag[0]=dfs(avail,board, word, index + 1, si - 1, sj);
		if (flag[0])
			return true;
		avail[si - 1][sj] = true;
	}
	if (avail[si][sj - 1] && board[si][sj - 1] == k)
	{
		avail[si][sj - 1] = false;
		flag[1] = dfs(avail,board, word, index + 1, si, sj - 1);
		if (flag[1])
			return true;
		avail[si][sj - 1] = true;
	}
	if (avail[si + 1][sj] && board[si + 1][sj] == k)
	{
		avail[si + 1][sj] = false;
		flag[2] = dfs(avail,board, word, index + 1, si + 1, sj);
		if (flag[2])
			return true;
		avail[si + 1][sj] = true;
	}
	if (avail[si][sj + 1]&&board[si][sj + 1] == k)
	{
		avail[si][sj + 1] = false;
		flag[3] = dfs(avail,board, word, index + 1, si, sj + 1);
		if (flag[3])
			return true;
		avail[si][sj + 1] = true;
	}
	return false;
}
public:
    bool exist(vector<vector<char>>& board, string word) {
	int row = board.size();
	int col = board[0].size();
	for (int i = 0; i < row; i++)
	{
		board[i].insert(board[i].begin(),'#');
		board[i].insert(board[i].end(), '#');
	}
	vector<char> tmp;
	for (int i = 0; i < col + 2; i++)
		tmp.push_back('#');
	board.insert(board.begin(), tmp);
	board.insert(board.end(), tmp);
	

	int len = word.length();
	if (len < 1)return false;
	char c = word[0];
	vector<pair<int,int>> start;
	for (int i = 1; i <= row; i++)
		for(int j=1;j<=col;j++)
			if (board[i][j] == c)
				start.push_back(pair<int,int>(i,j));

    vector<vector<bool>> avail;
    for (int i = 0; i < row + 2; i++)
    {
        vector<bool> t;
        for (int j = 0; j < col + 2; j++)
            t.push_back(true);
        avail.push_back(t);
    }
	for (int i = 0; i < start.size(); i++)
	{
		int index = 1;
		int si = start[i].first;
		int sj = start[i].second;
		avail[si][sj] = false;
		if (dfs(avail,board, word, 1, si, sj))return true;
		avail[si][sj] = true;
	}
	return false;
    }
};

发表于 更新于

题目描述

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

题解

排列组合的性质C(m,n)=C(m-1,n)+C(m-1,n-1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<vector<int>> combine(int n, int k) {
	//C(m,n)=C(m-1,n)+C(m-1,n-1)
	vector<vector<int>> comb;
	if (k == 0 || n < k)return comb;
	if (k == 1) {
		for (int i = 1; i <= n; i++)
			comb.push_back({ i });
		return comb;
	}
	if (n == k)
	{
		vector<int> t;
		for (int i = 1; i <= n; i++)
			t.push_back(i);
		return { t };
	}
	vector<vector<int>> c1 = combine(n - 1, k);
	vector<vector<int>> c2 = combine(n - 1, k - 1);
	for (int i = 0; i < c2.size(); i++)
		c2[i].push_back(n);
	c1.insert(c1.end(), c2.begin(), c2.end());
	return c1;
}

这个惨痛的经历告诉我们，学好数学是多么的重要。

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

题解

遍历nums，对于现有的res中的每一个vector，将当前nums的元素附加在其后得到一个新的vector，放入res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<int>> subsets(vector<int>& nums) {
	vector<vector<int>> res = { {} };
	for (int i = nums.size() - 1; i >= 0; i--)
	{
		int item = nums[i];
		int rsize = res.size();
		for (int j = 0; j < rsize; j++)
		{
			vector<int> tmp = res[j];
			tmp.push_back(item);
			res.push_back(tmp);
		}
	}
	return res;
}

发表于 更新于

题目描述

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

说明：

  • 如果 S 中不存这样的子串，则返回空字符串 ""。
  • 如果 S 中存在这样的子串，我们保证它是唯一的答案。

题解

滑动窗口、unordered_map

比较棘手的问题：如何判断 window 即子串 s[left…right] 是否符合要求，是否包含 t 的所有字符呢？

参考：https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-tong-yong-si-xiang-by-/

可以用两个哈希表当作计数器解决。用一个哈希表 needs 记录字符串 t 中包含的字符及出现次数，用另一个哈希表 window 记录当前「窗口」中包含的字符及出现的次数，如果 window 包含所有 needs 中的键，且这些键对应的值都大于等于 needs 中的值，那么就可以知道当前「窗口」符合要求了，可以开始移动 left 指针了。

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
#include<unordered_map>
string minWindow(string s, string t) {
	int start = 0, len = s.length()+1;//截取的开始位置与长度
	int left = 0, right = 0;
	unordered_map<char, int> window;//由s获得的字符及次数
	unordered_map<char, int> needs;//由t获得的字符及次数
	for (char c : t)needs[c]++;
	int match = 0;
	while (right < s.length())
	{
		char c = s[right];
		if (needs.count(c))
		{//命中
			window[c]++;
			if (window[c] == needs[c])
				match++;
		}
		right++;
		while (match == needs.size())
		{//更新截取结果，当始终包含t的字符时，left右移
			if ((right - left) < len)
			{
				start = left;
				len = right - left;
			}
			char k = s[left];
			if (needs.count(k))
			{//可能left移到了非关键字母上
				window[k]--;
				if(window[k] < needs[k])//可能有重复积累的
					match--;
			}
			left++;
		}
	}
	if (len > s.length())return "";
	else
		return s.substr(start, len);
}
1
size_type count ( const key_type& key ) const

count函数用以统计key值在unordered_map中出现的次数。c++ unordered_map不允许有重复的key。因此，如果key存在，则count返回1，如果不存在，则count返回0.

Tomorrow：

PA1报告、项目总结书、心理学视频。

发表于

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

题解

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。（说实话我一开始没想到这方法……）

仅使用常数空间的一趟扫描算法：

用三个指针（p0, p2 和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。沿着数组移动 curr 指针，若nums[curr] = 0，则将其与 nums[p0]互换；若 nums[curr] = 2 ，则与 nums[p2]互换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void sortColors(vector<int>& nums) {
	int vsize = nums.size();
	int p = 0, q = vsize - 1;
	while (p < vsize&&nums[p] == 0)p++;
	while (q >= 0 && nums[q] == 2)q--;
	int cur = p;
	while (cur <= q)
	{
		if (nums[cur] == 0)
		{
			swap(nums[cur], nums[p]);
			p++;
			cur++;
		}
		else if (nums[cur] == 2)
		{
			swap(nums[cur], nums[q]);
			q--;
		}
		else
			cur++;
	}
}


重点在于找边界！！

2.26：

  • 并行：代码性能测试、报告
  • ICS：报告

发表于 更新于

设置Vmware自动调整窗口大小

  1. 安装Vmware Tools，重启无效，则：

  2. 手工安装Vmware tools：终端窗口命令如下：
    sudo apt-get autoremove open-vm-tools
    sudo apt-get install open-vm-tools
    sudo apt-get install open-vm-tools-desktop

  3. 如果上面的命令执行并重启之后仍然没有效果：关机–>设置–>硬件–>显示器：

    指定监视器设置：数量设为1，分辨率为主机(我是win)的分辨率，关闭拉伸模式。开机，在“查看”中可以进行屏幕自适应设置。

Write a “Hello World” program, compile it, then run it under GNU/Linux.

输入 gcc hell.c
输入 ./a.out

Write a Makefile to compile the “Hello World” program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
CC      = gcc
CFLAGS  = -g
RM      = rm -f


default: all

all: Hello

Hello: Hello.c
    $(CC) $(CFLAGS) -o Hello Hello.c

clean veryclean:
    $(RM) Hello

GDB的基本使用

next和 step类似于vs中的f10和f11

基本命令：

1
2
3
4
5
6
gdb <executable name>   开始调试
break <source code line number>  打断点
run   运行
continue
watch <var>   当变量值改变时会被通知
quit   退出

git log –name=1711436 过滤查看手动修改过的记录

how to use tmux

tmux一种需要学习成本的Linux终端的分屏方式。

All commands in Tmux start with a prefix, which by default is ctrl+b.

离开tmux返回shell：Ctrl+b d

get a list of the currently running sessions type:tmux ls

attach to session 0: tmux attach-session -t 0

  • Ctrl+b c Create a new window (with shell)
  • Ctrl+b w Choose window from a list
  • Ctrl+b 0 Switch to window 0 (by number )
  • Ctrl+b , Rename the current window
  • Ctrl+b % Split current pane horizontally into two panes
  • Ctrl+b " Split current pane vertically into two panes
  • Ctrl+b o Go to the next pane
  • Ctrl+b ; Toggle between the current and previous pane
  • Ctrl+b x Close the current pane

git

When you want to commit the change, type

1
2
git add .
git commit --allow-empty

The --allow-empty option is necessary, because usually the change is already committed by development tracing system. Without this option, git will reject no-change commits.

ctags

vim提供了强有力的函数跳转的插件功能

首先要安装ctags， 在ubuntu下直接输入

1
sudo apt-get install exuberant-ctags

接着，在源文件目录树执行如下命令：

1
ctags -R

即可在目录下生成一个tags文件， 这个文件就是所有函数和变量的索引列表。(通过ls可以看见)

若E257:cstag:找不到tag，解决：在.vimrc中增加：

1
2
set tags=tags;
set autochdir

make的时候可以make -j4，4线程编译可以加快速度