这是剑指offer 系列四部曲中的最后一部，因为有些算法题目类别数量太少就汇总到了”其他“, 比如位运算、正则匹配等。第一部关于字符串和数组，第二部是栈、队列、链表和树， 第三部递归、回溯和动态规划。
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
Tips：首先处理正数, bitwise and operation， 很简单。对于负数，需要转换成 正数然后进行处理，math。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def NumberOf1(self, n):
# write code here
if n == 0:
return 0
if n > 0:
counts = self.number_of_positive(n)
else:
n = abs(n) - 1
counts = 32 - self.number_of_positive(n)
return counts
def number_of_positive(self, n):
if n == 0:
return 0
counts = 0
while n:
counts += (n & 1)
n = n >> 1
return counts
|
这是c++ 实现。
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
|
#include<iostream>
using namespace std;
// positive
int number_of_1(int n)
{
int res =0;
while(n)
{
res += (n&1);
n =n/2;
}
return res;
}
int main()
{
int n;
cin >>n;
int res =0;
if(n >0)
res =number_of_1(n);
else
{
n =abs(n) -1;
res =32 -number_of_1(n);
}
cout << res<<endl;
return 0;
}
|
补数和补码，2 和8 对于10 就是互为补数。那么补码这个概念也是类似的，两个机器数相加等于 1000000（在二级制下非常整齐的数字）这样的树，然后两个数字就互为补数。在计算机里面，对于负数就是使用其对应的补码进行表示的。正数使用本身表示，负数使用绝对值的补码进行表示。
首先转换成一个无符号整数，如果是无符号，当使用右移操作的时候补上的是0；但是当如果是有符号整数的时候，右移操作补充的是1。这个就是两者的区别。从本质上数字并没有发生变化，但是解读的方式发生了变化。
对于正数是比较好处理的，负数的补码表示形式。如果是8位，那么使用 1位表示符号位，使用7位进行技术，那么就有$2^7 =128 $种可能性。因为包含0，所以只能是正负127。负数中，原码补码，反码转换关系参考这里
这个是我见过的最为简洁的代码了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
int NumberOf1(int _n) {
unsigned int n =_n;
int res =0;
while(n)
{
res += (n&1);
n = n>>1;
}
return res;
}
};
|
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
Tips: 次方使用乘法来进行累乘
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
|
class Solution:
"""
这个就是边界条件比较多而已，需要分别判断 base 和 exponent 的正负
"""
def Power(self, base, exponent):
# write code here
if base == 0 and exponent != 0:
return 0
if base != 0 and exponent == 0:
return 1
flag = 1
if base <= 0 and (exponent % 2 == 1):
flag = -1
base = abs(base)
result = 1
if exponent > 0:
reverse = 0
else:
reverse = 1
exponent = abs(exponent)
if exponent % 2 == 0:
result = base * base
for i in range(exponent // 2 - 1):
result = result * result
else:
result = base * base
for i in range(exponent // 2 - 1):
result = result * result
result = result * base
if reverse:
result = 1.0 / result
return result * flag
|
这个是需要看数据的范围，如果是在 $10^7$ 之内，那么可以直接使用 $O(n)$ 的做法。需要处理一个负号的情况。
谁说 c++ 中的代码是比较长的，关键是看谁写的。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
double Power(double base, int exponent) {
double res =1;
for(int i =0; i<abs(exponent); i++)
res *= base;
if( exponent <0) res =1/res;
return res;
}
};
|
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
Tips： 这个有点投机取巧了，使用了 “heapq” 的库函数。这个题目跟 第 K个 smallest 是有差别的，快排中的 partition 是找到了 一个数字在最后排序结果中的位置。对于有”累加“前 K个数字还是要使用常规的排序。比较好的就是堆排序。
1
2
3
4
5
6
7
8
9
|
class Solution:
# 想说的是既然是使用这种开源的库函数 那么就记住这种函数名字
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if len(tinput) < k:
return []
import heapq
res = heapq.nsmallest(k, tinput)
return res
|
The function partition puts the numbers smaller than nums[left] to its left and then returns the new index of nums[left]. The returned index is actually telling us how small nums[left] ranks in 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
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
left, right = 0, len(nums) - 1
while True:
pos = self.partition(nums, left, right)
# 这个在排序的时候，是把大的数字放到前面，而前面是pos 是从0 开始的，
# 所以这里是 k-1
if pos == k - 1:
return nums[pos]
# 左边的并不足以构成k 个， 那么在右边
elif pos < k - 1:
left = pos + 1
else:
right = pos - 1
def partition(self, nums, left, right):
# choose nums[left] as pivot
pivot = nums[left]
# p1, p2就类似 working 中的left right
p1, p2 = left + 1, right
while p1 <= p2:
if nums[p1] < pivot and nums[p2] > pivot:
nums[p1], nums[p2] = nums[p2], nums[p1]
p1, p2 = p1 + 1, p2 - 1
elif nums[p1] >= pivot:
p1 += 1
else: #nums[p2] <= pivot:
p2 -=1
nums[left], nums[p2] = nums[p2], nums[left]
return p2
|
有两种解法，第一种思路是快排的思路，先是找到第 $K$大，然后 $O(n)$ 的时间，遍历一遍，保留 $K $个最大的元素。 这个是快速查找（quick_search） 而不是quick_sort 所以是不会修改数组的有序与否。
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
|
#include<iostream>
#include<vector>
using namespace std;
int partition(vector<int> arr, int l, int r)
{
int key =arr[r];
while(l< r)
{
while(l <r && arr[l] >= key) l +=1;
arr[r] =arr[l];
while(l <r && arr[r] <= key) r -=1;
arr[l] =arr[r];
}
arr[r] =key;
return l;
}
int find(vector<int> arr, int k)
{
if(arr.empty() || arr.size() < k) return -1;
int l =0, r =arr.size() -1;
while( true)
{
int pos =partition(arr, l, r);
if( pos == k-1) return arr[k];
else if (pos > k-1) r= pos -1;
else l =pos +1;
}
return -1;
}
int main()
{
vector<int> arr;
int n, k;
cin >>n >>k;
for(int i =0; i<n; i++)
{
int tmp ;
cin >> tmp;
arr.push_back(tmp);
}
int key = find(arr, k);
cout << key<< endl;
vector<int> res ;
for(auto a: arr)
{
if( a> key) res.push_back(a);
}
for(auto u: res)
cout << u<< " ";
cout<< endl;
}
|
第二种思路使用堆的思想。使用大根堆存储最小的k 个数，堆顶元素就是所有元素中最大的，那么如果弹出，就一定弹出堆顶的元素。
使用大根堆实现，时间复杂度是 $nlog(k)$， k是个数，n 是数组的长度。大根堆保存是k 个元素，其中堆顶是这k 个元素中最大的那个。
(卧槽，当时京东面试的时候，确实是可以使用大根堆进行实现的，现在有点想要哭，哈哈哈哈哈哈哈，)
stack只需要标记top下标，队列通过front和rear来标记队首和队尾。
.queue也是线性表，可以用数组(由于假溢出的原因使用循环数组)和链表来实现
使用c++ 中的大根堆的思想（求解最小的k 个数字使用 大根堆）
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
|
#include<iostream>
#include<queue>
#include<string>
using namespace std;
// 寻找的是 第k 小
vector<int> find_kth_largest(vector<int> &arr, int k)
{
if(arr.empty() || arr.size() < k) return vector<int>(-1);
priority_queue<int> q;
for(auto u: arr)
{
q.push(u);
if(q.size() >k) q.pop();
}
vector<int> res;
while( k--)
{
res.push_back(q.top());
q.pop();
}
return res;
}
int main()
{
vector<int> arr;
int n, k;
cin >>n >>k;
for(int i =0; i<n; i++)
{
int tmp;
cin >> tmp;
arr.push_back(tmp);
}
vector<int> res =find_kth_largest(arr, k);
for(auto u : res) cout << u<< " ";
cout<< endl;
cout<<"输出数字" << endl;
for(auto u: arr)
{
cout << u<< " ";
}
return 0;
}
|
- 整数中1出现的次数（从1到n整数中1出现的次数）(过)
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
Tips：math, 计数原理，按位统计该位为1时可能包含的数字总数.由低位向高位依次遍历数字n的每一位curn。记当前位数为c，curn左边（高位）的数字片段为highn，cur右边（低位）的数字片段为lown，lowc = 10 ^ c
- 若curn = 0，则高位范围为0 ~ highn - 1，低位0 ~ lowc - 1
- 若curn = 1，则高位范围为0 ~ highn - 1，低位0 ~ lowc - 1；或者 高位为highn， 低位0 ~ lown
- 若curn ＞ 1，则高位范围为0 ~ highn， 低位为0 ~ lowc - 1
一个小的例子 N= abcde,分别是各个位数上的数字。如果要统计 百位上出现 1的次数，那么他将受到三个因素的影响： 百位上的数字，百位以下的数字(低位) 和百位以上的数字( 高位)。
- 如果百位上的数字是 0 ， 高位数字 * 当前的数字
- 如果百位上的数字是1，高位数字 * 当前数字 + ( 低位数字+1)
- 如果百位数字大于1 (2-9), （高位数字+1 )* 当前的数字
初级版本: 通过不断的求余 和整除，计算每个位置上 1的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
int Count1InInteger(int n){
int counts =0;
while (n!=0) {
counts += (n%10) ==1? 1:0;
n/=10;
}
return counts;
}
int main(){
int total =0;
for (int i=0; i<N; i++)
{
total += Count1InInteger(i)
}
return total;
}
|
进阶版本：python 版本，思路见上面分析。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
# 数字的基本结构分成 weights +working_num + n%base 这三个部分
# 然后一个while 循环是处理一个数字
def NumberOf1Between1AndN_Solution(self, n):
# write code here
if n < 1:
return 0
num = n
counts = 0
base = 1
while num:
cur = num % 10
num = num // 10 #高位数字
counts += base * num
if cur == 1:
counts += (n % base) + 1
elif cur > 1:
counts += base
base *= 10
return counts
|
最优的时间复杂度是 $O(log N)$。下面的代码的时间复杂度是 $ O(log^2(N))$.
c++ 解法
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
|
class Solution {
public:
// 时间复杂度是 log^2(N)
// 经过讲解之后，只要得到 left right 这样的数字那么后面就比较好说了
int NumberOf1Between1AndN_Solution(int n)
{
if(!n) return 0;
vector<int> number;
// 把每一个数字单独的保存起来
// 很好的小的代码
// int 类型的数字，转换成 int 数组类型
while(n) number.push_back(n%10), n /=10;
int res =0;
for(int i =number.size() -1; i>=0; i--)
{
// t 是什么含义
auto left =0, right =0, t =1;
for(int j =number.size() -1; j>i; j--) left =left*10 +number[j];
for(int j =i-1; j>=0; j--) right =right *10+number[j], t *=10;
res += left *t;
if(number[i] ==1) res += right +1;
else if(number[i] >1) res += t;
}
return res;
}
};
|
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
Tips：使用sorted() 函数， string 类型的排序 和 int 类型的排序是一样的，在python 里面来说。
1
2
3
4
5
6
7
|
class Solution:
def PrintMinNumber(self, numbers):
# write code here
sorted_list = sorted(numbers, cmp=lambda a, b: cmp(str(a) + str(b), str(b) + str(a)))
# 这个时候已经排好序，然后只要一个个连接起来就行了
return ''.join(map(str, sorted_list))
|
这种方式是及其好用的。
1
2
|
list =["abc", "ad"]
print("".join(list))
|
凡是能够推出来的，都是比较简单的；凡是需要猜出来的，都是比较难的。对于这道题目，需要先定义一种排序方式，然后再获得最小的数字。主要是比较函数。
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
|
#include<iostream>
#include<string>
#include<vector>
using namespace std;
// 拼接出所有数字中最小的一个
bool cmp(int a, int b)
{
string sa =to_string(a), sb =to_string(b);
return sa +sb< sb+sa;
}
int main()
{
vector<int> arr;
int n ;
cin >>n;
for(int i =0; i< n; i++)
{
int tmp;
cin >>tmp;
arr.push_back(tmp);
}
sort(arr.begin(), arr.end(), cmp);
string res;
for(auto u: arr)
{
res += to_string(u);
}
cout << res<< endl;
return 0;
}
|
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
Tips：之后的丑数肯定是2，3或5 的倍数，分别单独计数，然后选择最小的。
注意两个版本再实现的时候稍微有一点不同。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution(object):
def getUglyNumber(self, n):
index =n
if index < 1: return 0
res = [1]
t2,t3,t5 = 0,0,0
while len(res) < index:
minNum = (min(res[t2]*2, res[t3]*3, res[t5]*5))
if minNum > res[-1]: res.append(minNum)
if (minNum == res[t2]*2): t2 += 1
elif (minNum == res[t3]*3): t3 += 1
else: t5 += 1
return res[-1]
|
使用c++ 实现。是需要有 $O(N)$ 的空间的，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include<iostream>
#include<string>
#include<vector>
using namespace std;
// 这个是比较有技巧的，使用 ijk 三个指针
int main()
{
int n;
vector<int> res(1,1);
cin >>n;
int i =0, j =0, k=0;
while (--n)
{
int min_v =min(res[i] *2, min(res[j] *3, res[k] *5 ));
res.push_back(min_v);
if(min_v == res[i] *2) i +=1;
if( min_v == res[j] *3 ) j+=1;
if(min_v ==res[k] *5) k +=1;
}
cout << res.back()<< endl;
return 0;
}
|
请实现一个函数用来匹配包括'.‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
Tips: dp 问题。转换方程 dp[i][j] i 表示 string 的index j表示 pattern 的index， dp[i][j] ==dp[i-1][j-1] or dp[i][j] =dp[i][j-2] or dp[i][j-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
|
class Solution:
# s, pattern都是字符串
# https://www.youtube.com/watch?v=l3hda49XcDE 心中一定要有这个表格, a[i][j] 这个更像是一种指针
def match(self, s, pattern):
if len(s) == 0 and len(pattern) == 0:
return True
dp = [[False for _ in range(len(pattern) + 1)] for _ in range(len(s) + 1)]
dp[0][0] = True
for j in range(1, len(pattern) + 1):
if pattern[j - 1] == "*":
dp[0][j] = dp[0][j - 2]
for i in range(1, len(s) + 1):
for j in range(1, len(pattern) + 1):
if pattern[j - 1] == s[i - 1] or pattern[j - 1] == ".":
dp[i][j] = dp[i - 1][j - 1]
elif pattern[j - 1] == "*":
dp[i][j] = dp[i][j - 2]
if s[i - 1] == pattern[j - 2] or pattern[j - 2] == ".":
dp[i][j] = dp[i][j] or dp[i - 1][j]
else:
dp[i][j] = False
return dp[len(s)][len(pattern)]
|
视频中讲解dp 使用的dfs 的思想，但是我更加喜欢使用方格的思想。所以这个是可以暂时的过去。
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
Tips：主要是体现了数据流，要求能够 insert 元素，然后基于当前的状态去 getmedian() ，是动态的，而不是静态的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
"""
对于数据流 这个应该是第二次接触了，需要使用一个全局变量
"""
# 虽然知道这个使用 堆的思想是更优的，搜索时间可以O（1）， 堆的调整是 O(log n)
# 但是没有什么很好的教程，所以我也没有学会啊
def __init__(self):
self.list1 = []
def Insert(self, num):
self.list1.append(num)
def GetMedian(self, ch):
length = len(self.list1)
# 我记得有一个更加快一些
self.list1 = sorted(self.list1)
if length % 2 == 0:
return (self.list1[length // 2] + self.list1[length // 2 - 1]) / 2.0
else:
return self.list1[length // 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
|
class Solution {
public:
// 大根堆在下面，小根堆在上面
// 小根堆存储大的数字，堆顶是小的元素，大根堆存储小的数字，堆顶是大的元素。
// 插入的时候优先往小根堆插入，如果发现两堆相差大于1，那么调整两个堆
// 总数是奇数，那么返回小根堆的堆顶；总数是偶数，返回两个堆的堆顶的均值
// 两个堆 如何进行维护呢？ 交换 if 逆序； 转移 if 小根堆比较多
priority_queue<int> max_heap; //
priority_queue<int, vector<int>, greater<int>> min_heap;
void Insert(int num)
{
max_heap.push(num);
// 如果是逆序
if(min_heap.size() && max_heap.top() > min_heap.top() )
{
auto maxv =max_heap.top(), minv= min_heap.top();
max_heap.pop(), min_heap.pop();
max_heap.push(minv),min_heap.push(maxv);
}
// 如果下面多
if(max_heap.size() > min_heap.size() +1)
{
min_heap.push(max_heap.top());
max_heap.pop();
}
}
double GetMedian()
{
if(max_heap.size() + min_heap.size() &1) return max_heap.top();
return (max_heap.top() + min_heap.top())/2.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
|
#include<iostream>
#include<string>
#include<queue>
using namespace std;
priority_queue<int> max_h; // heap 堆
priority_queue<int, vector<int>, greater<int>> min_h;
void insert(int val)
{
max_h.push(val);
// 处理逆序
if(min_h.size() && min_h.top() < max_h.top())
{
int minv =min_h.top(), maxv =max_h.top();
min_h.pop(), max_h.pop();
min_h.push(maxv), max_h.push(minv);
}
// 处理 diff > 1 的情况
if(max_h.size() > min_h.size() +1)
{
min_h.push(max_h.top());
max_h.pop();
}
}
double get_median()
{
if(max_h.size() + min_h.size() &1) return max_h.top();
return (max_h.top() +min_h.top())/2.0;
}
int main()
{
return 0;
}
|
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
Tips：使用max(list1) 这样的操作是可行的。
1
2
3
4
5
6
7
8
9
|
class Solution:
# 最简单的模拟滑动窗口 的过程
def maxInWindows(self, num, size):
slip = []
if not num or len(num) < size or size == 0:
return []
for i in range(len(num) - size + 1):
slip.append(max(num[i:i + size]))
return slip
|
c++ 中的deque 是双向队列。
这个在牛客网上通过的样例是 12.5%，估计是爆了内存之类吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
// 单调队列问题，单调在于队首到队尾是递减的。使用双向队列在于要支持队尾删除元素
// 使用队列是维持一个滑动窗口的概念，
vector<int> maxInWindows(vector<int>& nums, int k) {
deque<int > q;
vector<int> res;
for(int i =0; i< nums.size() ; i++)
{
while( q.size() && q.front() <= i -k) q.pop_front();// i 表示当前的遍历的index，q.front() 不可能比这个大
while(q.size() && nums[q.back()] <= nums[i]) q.pop_back();
q.push_back(i);
if(i >=k -1) res.push_back(nums[q.front()]);
}
return res;
}
};
|
求解连续子数组的最大和
c++ 代码
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
|
#include<iostream>
#include<vector>
using namespace std;
// 整数数组中元素有正有负，找出一个连续的子数组，要求连续子数组中各元素和和最大。
int maxSub(vector<int> arr, int n)
{
int now =0;
int max_v =INT_MIN;
for(auto u: arr)
{
now += u;
if (now <0) now =0; // 注意这里是求解最大的和
max_v =max(now, max_v);
}
return max_v;
}
int main()
{
vector<int> arr;
int n ;
cin >>n;
while(n --)
{
int tmp;
cin >>tmp;
arr.push_back(tmp);
}
int res =maxSub(arr, n);
cout << res<< endl;
return 0;
}
|
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
# 时间复杂度是 O(n), 空间是 O(1)
def largestSub(arr):
if not arr or len(arr) ==0: return
now =0
max_v =arr[0]
for i in range(len(arr)):
now += arr[i]
if(now <0) : now =0
max_v =max(now, max_v)
return max_v
arr =[2, 4, -7, 5, 2, -1, 2, -4, 3]
print(largestSub(arr))
|