数据结构与算法笔记 | 分治

分治思想又被称为分类讨论,将复杂问题分为易于讨论的简单子问题,不仅是计算机学科,在解决数理问题中的应用都很广泛。

1. 分类讨论状态

LC 58 最后一个单词的长度

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
#define MAX_N 10002

char word[MAX_N];

class Solution {
public:
int lengthOfLastWord(string s) {
int N = s.size();
int state = 0; // 0:待读取字符串,1:字符串读取完毕,2:正在读取字符串
memset(word, 0, sizeof(word));
for(int i=0,j=0; i<N; ++i) {
if(s[i]==' ') {
if(state == 2) {
state = 1;
}
} else {
if(state == 0) {
word[j++] = s[i];
state = 2;
} else if(state == 1) {
memset(word, 0, sizeof(word));
j = 0;
word[j++] = s[i];
state = 2;
} else {
word[j++] = s[i];
}
}
}
return strlen(word);
}
};

2. 分类讨论余数r的情况

统计1-n的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
24
typedef long long ll;

class Solution {
public:
int countDigitOne(int n) {
int res = 0;
ll base = 1;
int rebuild = 0;
while(n > 0) {
int r = n % 10;
n /= 10;
rebuild += r*base;
if (r == 0) {
res += n*base;
} else if(r==1) {
res += n*base+(rebuild-base+1);
} else {
res += (n+1)*base;
}
base *= 10;
}
return res;
}
};
心理学效应在生活中的应用 C/C++ 开源项目构建

评论

You forgot to set the shortname for Disqus. Please set it in _config.yml.
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×