Joyce' Blog
0%

发表于 更新于

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。1 ≤ m ≤ 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
26
27
28
29
30
ListNode* reverseBetween(ListNode* head, int m, int n) {
	if (m == n)return head;
	ListNode* prehead = new ListNode(0);
	prehead->next = head;
	int i = m;
	ListNode* front = prehead;
	while (i)
	{
		front = front->next;
		i--;
	}
	stack<int> s;
	ListNode* back;
	back = front;
	int k = n - m;
	while (k)
	{
		s.push(back->val);
		back = back->next;
		k--;
	}
	s.push(back->val);
	while (!s.empty())
	{
		front->val = s.top();
		s.pop();
		front = front->next;
	}
	return prehead->next;
}

看到官方题解里还有一些其他思路：

递归

对于反转字符串，可以创建两个指针，一个开头，一个结尾。不断地交换这两个指针指向的元素，并将两个指针向中间移动。但是对于反转链表，链表中没有向后指针，也没有下标。因此，我们需要使用递归来 模拟 向后指针。递归中的回溯可以帮助我们模拟一个指针从第n个结点向中心移动的移动过程。

反转指针

发表于 更新于

字符串匹配算法

给定主串A和模式串B，判断B是否是A的子串，并返回B在A中第一次出现的位置。

暴力算法BF算法

BruteForce的缩写。对主串和模式串进行逐个字符的对比。假设主串的长度是m，模式串的长度是n，需要m-n轮循环，每一轮里面，把模式串的位置右移一位，重新与主串对应位置进行匹配。

在某些极端情况下效率很低，例如：主串为aaaaaaaaaaaaaaab，模式串为aaab，在每一轮进行字符匹配时，模式串的前三个字符a都和主串中的字符相匹配，一直检查到模式串最后一个字符b，才发现不匹配。

在这种极端情况下，BF算法的最坏时间复杂度是O（mn）。

利用哈希值进行比较RK算法

Rabin-Karp的缩写。BF算法只是简单粗暴地对两个字符串的所有字符依次比较，而RK算法比较的是两个字符串的哈希值。没一个字符串都可以通过某种哈希算法，转换成一个整数型（hashcode）。

生成hashcode的算法

假设字符串只包含26个小写字母。

按位相加

a——1，b——2，c——3，……，把字符串的所有字符相加，结果作为hashcode。

做法简单但容易产生hash冲突，如abc、bac、cab的hashcode一样。两个hash值相等不一定两个字符串也相等，还需要进一步验证。

转换成26进制数

既然字符串只包含26个小写字母，可以把每一个字符串当成一个26进制数来计算。这样可以大幅减少hash冲突，但计算量较大，有可能出现超出整数范围的情况，因此需要对计算结果进行取模。

1
bce = 2*(26^2) + 3*26 + 5 = 1435

这里采用比较简单的按位相加的方法，代码如下

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
public static int rabinKarp(String str, String pattern){
	//主串长度
    int m = str.length();    
	//模式串的长度
	int n = pattern.length();    
	//计算模式串的hash值
    int patternCode = hash(pattern);
	//计算主串当中第一个和模式串等长的子串hash值
	int strCode = hash(str.substring(0, n));
	//用模式串的hash值和主串的局部hash值比较。
	//如果匹配，则进行精确比较；如果不匹配，计算主串中相邻子串的hash值。
	for(int i=0; i<m-n+1; i++){        
		if(strCode == patternCode && compareString(i, str, pattern)){           		return i;
		}
	//如果不是最后一轮，更新主串从i到i+n的hash值
        if(i<m-n){
            strCode = nextHash(str, strCode, i, n);
        }
	}  
	return -1;
}
private static int hash(String str){
	int hashcode = 0;
    //这里采用最简单的hashcode计算方式：
    //把a当做1，把b当中2，把c当中3.....然后按位相加
	for(int i = 0; i < str.length(); i++) {
        hashcode += str.charAt(i)-'a';
	}    
	return hashcode;
}
private static int nextHash(String str, int hash, int index, int n){
    hash -= str.charAt(index)-'a';
    hash += str.charAt(index+n)-'a';
	return hash;
}
private static boolean compareString(int i, String str, String pattern) {
    String strSub = str.substring(i, i+pattern.length());    
	return strSub.equals(pattern);
}
public static void main(String[] args){
    String str = "aacdesadsdfer";
    String pattern = "adsd";
    System.out.println("第一次出现的位置:"+rabinKarp(str, pattern));}

时间复杂度为O(n)。如果冲突太多的话，RK算法会退化为BF算法。

尽量减少比较次数的BM算法

Bob Boyer 和 JStrother Moore 发明。

BF算法中有许多无谓的比较，BM算法是对BF算法的改进。借助“坏字符规则”和“好后缀规则”，在每一轮比较是，让模式串尽可能多地右移，减少比较次数。

坏字符规则

坏字符是指模式串和子串当中不匹配的字符。

BM算法的检测顺序相反，是从字符串最右侧向最左侧检测，反向检测的好处稍后会提到。

当检测到第一个坏字符之后，并不需要让模式串一位一位地向后移动和比较，因为：只有模式串坏字符对齐的位置也是字符T的情况下，两者才有匹配的可能。所以遇到坏字符T后，在模式串中向前找，直接把模式串当中的字符T和主串的坏字符对齐，进行下一轮的比较。

坏字符的位置越靠右，下一轮模式串的挪动跨度就可能越长，节省的比较次数也就越多。这就是BM算法从右向左检测的好处。

接下来，我们继续逐个字符比较，直到又遇到一个坏字符，按照上面的方式，找到模式串中相同的字符，与坏字符对齐后进行下一轮比较。

如果坏字符在模式串中不存在，直接把模式串挪到主串坏字符的下一位。

按照以上规则，已经能比较有效地找出下标了，代码如下：

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
//在模式串中，查找index下标之前的字符是否和坏字符匹配
private static int findCharacter(String pattern,char badCharacter,int index){
	for(int i = index-1;i>=0;i--) {
		if(pattern.charAt(i)==badCharacter) {
			return i;
		}
	}
	//模式串不存在该字符，返回-1
	return -1;
}
public static int boyerMoore(String str,String pattern){
	int strLength = str.length();
	int patternLength = pattern.length();
	//模式串的起始位置
	int start=0;
	while(start<=strLength-patternLength){
		int i;
		//从后向前，逐个字符比较
		for(i=patternLength-1;i>=0;i--){
			if(str.charAt(start+i)!=pattern.charAt(i))
				//发现坏字符，跳出比较，i记录了坏字符的位置
				break;
		}
		if(i<0){
			//匹配成功，返回第一次匹配的下标位置
			return start;
		}
		//寻找坏字符在模式串中的对应
		int charIndex = findCharacter(pattern,str.charAt(start+i),i);
		//计算坏字符产生的位移
		int bcOffset = charIndex>=0?i-charIndex:i+1;
		start += bcOffset;
	}
    return -1;

}
public static void main(String[]args){
	String str = "GTTATAGCTGGTAGCGGCGAA";
	String pattern = "GTAGCGGCG";
	int index = boyerMoore(str,pattern);
	System.out.println("首次出现位置："+index);
}

但对于某些情况仍有不足，因此需要用到好后缀规则。

好后缀规则

好后缀是指模式串和子串当中相匹配的后缀。

在下面的例子中，仅使用坏字符规则（G—A），模式串仅能向后移动一位。下面介绍好后缀的用法：

例如，主串： CTGGGCGAGCGGAA，模式串：GCGAGCG

在第一轮比较中，发现主串和模式串都有共同的后缀“GCG”，即“好后缀”。如果模式串其他位置也包含与“GCG”相同的片段，那么就可以移动模式串，使这一片段与好后缀对齐，进行下一轮的比较。

采用好后缀规则能够让模式串向后移动更多位，节省了更多无谓的比较。

如果模式串中并不存在其他与好后缀相同的片段，不能直接把模式串移到好后缀的后面，还需要判断一种特殊情况：模式串的前缀是否和好后缀的后缀相匹配，免得移过头了。

两种规则的结合：可以在每一轮字符比较之后，按照坏自读和好后缀规则分别计算相应的移动距离，选用更长的距离。代码有些复杂，暂时不涉足。

KMP算法

由D.E.Knuth、J.H.Morris和V.R.Pratt提出。与BM算法类似，试图减少无谓的字符串比较。为了实现这一点，KMP算法把专注点放在了已匹配的前缀上。

KMP算法和BF算法的“开局”是一样的，同样是把主串和模式串的首位对齐，从左到右对逐个字符进行比较。直到遇到一个坏字符时停下来。

例如，主串：GTGTGAGCTGGTGTGTGCFAA，模式串：GTGTGCF

为了有效利用已匹配的前缀 “GTGTG” ，可以发现，在前缀“GTGTG”当中，后三个字符“GTG”和前三位字符“GTG”是相同的。

在下一轮的比较时，只有把这两个相同的片段对齐，才有可能出现匹配。这两个字符串片段，分别叫做最长可匹配后缀子串和最长可匹配前缀子串。把模式串向后移动两位，继续从主串的坏字符A开始进行比较。这时，主串的A仍是坏字符，并且此时的匹配前缀缩短为GTG，最长可匹配前缀子串是G，右移模式串，使两个G对齐，继续从刚才主串的坏字符A开始进行比较

整体思路：在已匹配的前缀当中寻找到最长可匹配后缀子串和最长可匹配前缀子串，在下一轮直接把两者对齐，从而实现模式串的快速移动。找两个子串的方法：在next数组中缓存。

next数组

next数组是一个一维整型数组，数组下标表示“已匹配前缀的下一个位置”，元素的值表示“最长可匹配的前缀子串的下一个位置”。对于上面的例子，next数组为：

i 0 1 2 3 4 5 6
next[i] 0 0 0 1 2 3 0
字符串前缀 无 G GT GTG GTGT GTGTG GTGTGC

可以通过已匹配前缀的下一个位置（坏字符位置）快速寻找到最长可匹配前缀的下一个位置，然后把这两个位置对齐。

当模式串的第一个字符就和主串不匹配时，并不存在已匹配前缀子串，对应next[0]=0。如果已匹配前缀是G、GT、GTGTGC，并不存在最长可匹配前缀子串，对应next[1]=next[2]=next[6]=0。GTG的最长可匹配前缀是G，对应next[3]=1。

生成next数组

由于已匹配前缀数组在主串和模式串当中是相同的，所以我们仅仅依据模式串，就足以生成next数组。最简单的方法是从最长的前缀子串开始，把每一种可能情况都做一次比较。假设模式串的长度是m，最大总比较次数是1+2+3+4+……+m-2 次，这种方法效率太低。

另外一种方法是动态规划：

  1. 初始状态：next[0]和next[1]的值是0，因为这时候不存在前缀子串；

  2. 状态转移方程：当模式串当中 pattern[j] = pattern[i-1]时，next[i] = next[i-1]+1;

    对于i=6，可以把计算“GTGTGC”最长可匹配前缀子串的问题，转化成计算“GTGC”最长可匹配前缀子串的问题。这样的问题转化，也就相当于把变量j回溯到了next[j]。

1. 对模式串预处理，生成next数组

2. 进入主循环，遍历主串

​ 2.1. 比较主串和模式串的字符

​ 2.2. 如果发现坏字符，查询next数组，得到匹配前缀所对应的最长可匹配前缀子串，移动模式串到对应位置

​ 2.3.如果当前字符匹配，继续循环

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
// KMP算法主体逻辑。str是主串，pattern是模式串
public static int kmp(String str, String pattern) {
    //预处理，生成next数组
    int[] next = getNexts(pattern);
    int j = 0;
    //主循环，遍历主串字符
    for (int i = 0; i < str.length(); i++){
        while (j > 0 && str.charAt(i) != pattern.charAt(j)){
            //遇到坏字符时，查询next数组并改变模式串的起点
            j = next[j];        
		}
        if (str.charAt(i) == pattern.charAt(j)){
            j++;
        }
        if (j == pattern.length()){
            //匹配成功，返回下标
            return i - pattern.length()+ 1;
        }
    }
    return -1;
}
// 生成Next数组
private static int[] getNexts(String pattern) {
    int[] next = new int[pattern.length()];    
	int j = 0;
    for (int i=2; i<pattern.length(); i++){        
        while (j != 0 && pattern.charAt(j) != pattern.charAt(i-1)) {
            //从next[i+1]的求解回溯到 next[j]
            j = next[j];
        }
        if (pattern.charAt(j) == pattern.charAt(i-1)){
            j++;
        }
        next[i] = j;
    }
    return next;
}
public static void main(String[] args){
    String str = "ATGTGAGCTGGTGTGTGCFAA";
    String pattern = "GTGTGCF";
    int index = kmp(str, pattern);
    System.out.println("首次出现位置："+ index);
}

空间复杂度：O(m)

时间复杂度： O(m+n)

KMP没看懂，明天继续吧。

以上参考：小灰

发表于

题目描述

一条包含字母 A-Z 的消息通过以下方式进行了编码：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

题解

想到了动态规划，却没有想到状态转移方程会是f(n) = f(n-1) + f(n-2)。边界条件比较麻烦，f(n-1)表示s[index-1], s[index]分开解码，f(n-2)表示合并解码。

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
int numDecodings(string s) {
	int len = s.length();
	if (s[0] == '0')return 0;
	int f1 = 1, f2 = 0, f3 = 1;
	if (len == 1)return 1;
	int pre = s[0] - '0';
	if (s[1] != '0')
	{
		if (s[0] == '1')
		{
			f2 = 2;
			f3 = 2;
		}
		else if (s[0] == '2')
		{
			if (s[1] < '7')
			{
				f2 = 2;
				f3 = 2;
			}
			else
				f2 = 1;
		}
		else
			f2 = 1;
	}
	else
	{
		if (s[0] == '1' || s[0] == '2') {
			f2 = 1; f3 = 1;
		}
		else return 0;
	}
	int index = 2;
	while (index < len)
	{
		//f2表示s[index-1], s[index]分开解码，f1表示合并解码
		if (s[index] == '0')
		{
			if (s[index - 1] == '1' || s[index - 1] == '2')
				f3 = f1;
			else
				return 0;
		}
		else if (s[index - 1] == '1')
		{
			f3 = f2 + f1;
		}
		else if (s[index - 1] == '2')
		{
			if (s[index] < '7')
				f3 = f1 + f2;
			else
				f3 = f2;
		}
		else
			f3 = f2;

		f1 = f2;
		f2 = f3;
		index++;
	}
	return f3;
}

发表于

题目描述

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

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

题解

总得先排个序。

用set去重？或者vector去重的话也可以用unique函数。

虽然不算快，但也是一遍过，不错哦，就这样吧，可以去玩啦~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	vector<vector<int>> res = { {} };
	for (int i = 0; i < nums.size(); i++)
	{
		int k = res.size();
		while (k--)
		{
			res.push_back(res[k]);
			res[k].push_back(nums[i]);
		}
	}
	sort(res.begin(), res.end());

	res.erase(unique(res.begin(), res.end()), res.end());
	return res;
}

发表于

用C++编程的出来了一大堆结果，虽然没有必要，但是还是想用python画个图。

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
import matplotlib.pyplot as plt

#导入数据
x_axix=[]
m1=[]
m2=[]
f = open('E:\桌面\时光以南\Parallel并行\实验\work1\multi1.txt')  # 打开数据文件文件
lines = f.readlines()  # 把全部数据文件读到一个列表lines中
A_row = 0  # 表示矩阵的行，从0行开始
for line in lines:  # 把lines中的数据逐行读取出来
    list = line.strip('\n').split(' ')  # 处理逐行数据：strip表示把头尾的'\n'去掉，split表示以空格来分割行数据，然后把处理后的行数据返回到list列表中
    x_axix.append(list[0])
    m1.append(list[1])
    A_row += 1  # 然后方阵A的下一行接着读
f.close()

f = open('E:\桌面\时光以南\Parallel并行\实验\work1\multi2.txt')  # 打开数据文件文件
lines = f.readlines()  # 把全部数据文件读到一个列表lines中
A_row = 0  # 表示矩阵的行，从0行开始
for line in lines:  # 把lines中的数据逐行读取出来
    list = line.strip('\n').split(' ')  # 处理逐行数据：strip表示把头尾的'\n'去掉，split表示以空格来分割行数据，然后把处理后的行数据返回到list列表中
    m2.append(list[1])
    A_row += 1  # 然后方阵A的下一行接着读
f.close()

#开始画图
plt.title('Result Analysis')
plt.plot(x_axix, m1, color='red', label='multi1')
plt.plot(x_axix, m2, color='green', label='multi2')

plt.legend() # 显示图例
plt.xlabel('N')
plt.ylabel('time')
plt.show()

有一说一，python画图我大概是不会了，我画出来的图是真的丑。

在这里插入图片描述

所以为什么放着MATLAB不用呢？

1
2
3
4
5
6
7
8
a = importdata('E:\桌面\时光以南\Parallel并行\实验\work1\multi1.txt');
x = a(:,1);
y = a(:,2);
plot(x,y,'r');hold on;
b = importdata('E:\桌面\时光以南\Parallel并行\实验\work1\multi2.txt');
m = b(:,1);
n = b(:,2);
plot(m,n,'g');hold off;

代码很简单，对图标的修改也是图形化操作，哦了。

明天去学一下字符串匹配算法吧。

发表于

题目描述

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

题解

设 n 阶格雷码集合为 G(n)，则 G(n+1) 阶格雷码为：
给 G(n) 阶格雷码每个元素二进制形式前面添加 0，得到 G’(n)；
设 G(n) 集合倒序（镜像）为 R(n)，给 R(n) 每个元素二进制形式前面添加 1，得到 R’(n)；
G(n+1) = G’(n) ∪ R’(n)拼接两个集合即可得到下一阶格雷码。
链接：https://leetcode-cn.com/problems/gray-code/solution/gray-code-jing-xiang-fan-she-fa-by-jyd/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> grayCode(int n) {
	if (!n)return { 0 };

	vector<string> v1;
	v1.push_back("");
	while (n--)
	{
		for (int i = v1.size() -1; i >=0;i--)
		{
			v1.push_back("1"+v1[i]);
			v1[i] = "0" + v1[i];
		}
	}
	vector<int> res;
	for (int i = 0; i < v1.size(); i++)
		res.push_back(stoi(v1[i], nullptr, 2));
	return res;
}

发表于

电脑屏幕黑了的原因及处理方法是：

  1. 显示器刷新率太高；
  2. 显卡驱动程序失败，处理方法是进入安全模式，重新安装显卡驱动；
  3. 电脑感染了病毒，处理方法是在安全模式下，使用杀毒软件进行杀毒操作。

强制开关机两次，第三次开机，会自动进入winre，之后依次点击疑难解答-高级选项，启动设置，选择重启，之后选择启动安全模式（强制关机：开机载入的时候长按电源键强制关机）

发表于 更新于

题目描述

给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。

题解

动态规划

状态：dp[i][j][len] 表示从字符串 S 中 i 开始长度为 len 的字符串是否能变换为从字符串 T 中 j 开始长度为 len 的字符串。

转移方程：dp[i][j][k]=${OR}_{1<=w<=k-1}${(dp[i][j][w]&&dp[i+w][j+w][k-w])||(dp[i][j+k-w][w]&&dp[i+w][j][k-w])}

初始状态：len<=1时，dp[i][j][1] = (s1[i] == s2[j])

返回结果：d[0][0][len]

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
bool isScramble(string s1, string s2) {
	int len = s1.length();
	if (len <= 1)return s1 == s2;
	bool*** dp;
	dp = new bool**[len];
	for (int i = 0; i < len; i++)
		dp[i] = new bool*[len];
	for (int i = 0; i < len; i++)
		for (int j = 0; j < len; j++)
			dp[i][j] = new bool[len+1];
	for (int i = 0; i < len; i++)
		for (int j = 0; j < len; j++)
			for (int k = 0; k<=len; k++)
				dp[i][j][k] = false;
	for (int i = 0; i < len; i++)
		for (int j = 0; j < len; j++)
			dp[i][j][1] = (s1[i] == s2[j]);
	for (int k = 2; k <= len; k++)
	{
		for (int i = 0; i <=len-k;i++)
		{
			for (int j = 0; j <= len - k; j++)
			{
				for (int w = 1; w <= k-1; w++)
				{
					if ((dp[i][j][w] && dp[i + w][j + w][k- w]) || (dp[i][j + k - w][w] && dp[i + w][j][k - w]))
					{
						dp[i][j][k] = true;
						break;
					}
				}
			
			}
		}
	}
	return dp[0][0][len];
}

加油呀。菜是原罪啊。

发表于

题目描述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

题解

虚拟头指针、双指针

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
ListNode* partition(ListNode* head, int x) {
	if (!head)return NULL;
	ListNode* prehead;
	prehead = new ListNode(x - 1);
	prehead->next = head;
	ListNode *t = prehead;
	while (t->next&&t->next->val < x)t = t->next;
	if (t->next == NULL)return head;

	ListNode *position = t;
	ListNode *current = t->next;
	while (current->next != NULL)
	{
		if (current->next->val < x)
		{
			ListNode *tmp = current->next;
			current->next = current->next->next;
			tmp->next = position->next;
			position->next = tmp;
			position = position->next;
		}
		else
			current = current->next;
	}
	return prehead->next;
}

发表于 更新于

题目描述

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

题解

暴力求解：主要的想法是，对于矩阵中的每一个元素，向上找：以其为右下顶点的矩形面积，找的过程中，矩形的长是这一列中最小的连续“1”的数量，宽是行数之差。需要一个辅助矩阵count，count[i][j]用来记录matrix[i][j]在i这一行前面连续的“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
31
32
33
34
35
36
37
38
39
int maximalRectangle(vector<vector<char>>& matrix) {
	int row = matrix.size();
	if (!row)return 0;
	int col = matrix[0].size();
	if (!col)return 0;
	vector<vector<int>> count;
	for (int i = 0; i < row; i++)
		count.push_back({ (matrix[i][0] - '0') });
	for (int i = 0; i < row; i++)
	{
		for (int j = 1; j < col; j++)
		{
			if (matrix[i][j - 1] == '0')
				count[i].push_back(matrix[i][j] - '0');
			else
				count[i].push_back(count[i][j - 1] + matrix[i][j] - '0');
		}
	}

	int res = count[0][0];
	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
		{
			if (matrix[i][j] == '1')
			{
				int width = count[i][j];
				for (int k = i; k >= 0; k--)
				{
					if (matrix[k][j] == '0')break;
					width = count[k][j] < width ? count[k][j] : width;
					int area = width * (i - k + 1);
					res = area > res ? area : res;
				}
			}
		}
	}
	return res;
}

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

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

借助单调栈：

1

还是用到了上面的count矩阵，从左往右竖着划分，可以看做有col个求最大矩形柱状面积的图。此时count[i][j]就表示在第j列时，第i个柱子的高度。

对于单个求largestRectangleArea的情况，可以借助单调递增栈来解决，当柱子的高度递增时，将i入栈，若当前高度更小，则需要将i弹出栈直到不违背递增性质。在弹出栈的过程中需要算面积。为了编程方便，可以在一开始将高度0插入到第一个柱子之前。

附

C++ template：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <int DIM, typename T>
class DotProduce{
    public:
    static T result (T* a, T* b){
        return *a * *b + DotProduce<DIM-1, T>::result(a+1, b+1);
    }
};

//The end criterion is the case of a one-dimensional vector:
template <typename T>
class DotProduce<1, T>{
    public:
    static T result (T* a, T* b){
        return *a * *b;
    }
};

Thus, for

1
dot_produce<3>(a,b)

the instantiation process computes the following:

1
2
3
4
DotProduce<3, int>::result(a, b)
    = *a * *b + DotProduce<2, int>::result(a+1, b+1)
    = *a * *b + (*(a+1) * *(b+1) + DotProduce<1, int>::result(a+2, b+2))
    = *a * *b + (*(a+1) * *(b+1) +(*(a+2) * *(b+2)))

元编程（Metaprogramming）是指某类计算机程序的编写，这类计算机程序编写或者操纵其他程序（或者自身）作为它们的数据，或者在运行时完成部分本应在编译时完成的工作。 很多情况下与手工编写全部代码相比工作效率更高。

volatile关键字是一种类型修饰符，用它声明的类型变量表示可以被某些编译器未知的因素更改。

题目描述

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

题解

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
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
	if (m == 0) { nums1 = nums2; return;}
	if (n == 0)return;
	vector<int> v;
	int k1 = 0, k2 = 0;
	while (true)
	{
		if (nums1[k1]<= nums2[k2])
		{
			v.push_back(nums1[k1]);
			k1++;
			if (k1 == m)break;
		}
		else
		{
			v.push_back(nums2[k2]);
			k2++;
			if (k2 == n)break;
		}
	}
	while (k2!=n)
		v.push_back(nums2[k2++]);
	while (k1 != m)
		v.push_back(nums1[k1++]);
	nums1 = v;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
	if (m == 0) { nums1 = nums2; return; }
	if (n == 0)return;
	int k = 0;
	auto it2 = nums2.begin();
	while (true)
	{
		if (*it2 <= nums1[k])
		{
			it2++;
			if (it2 == nums2.end())break;
		}
		else
		{
			it2 = nums2.insert(it2, nums1[k]);
			k++;
			if (k == m)break;
		}
	}
	while (k < m)nums2.push_back(nums1[k++]);
	nums1.clear();
	nums1 = nums2;
}