桃李春风一杯酒，江湖夜雨十年灯。
剑指 Offer 41. 数据流中的中位数**
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
[“MedianFinder”,”addNum”,”addNum”,”findMedian”,”addNum”,”findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：
[“MedianFinder”,”addNum”,”findMedian”,”addNum”,”findMedian”]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
限制：
最多会对 addNum、findMedia进行 50000 次调用。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
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
| class MedianFinder {
public:
vector<int> nums;
MedianFinder() { }
void addNum(int num) {
nums.push_back(num);
for(int i=nums.size()-2;i>=0;i--) {
if(nums[i]>nums[i+1]) {
swap(nums[i],nums[i+1]);
}
}
}
double findMedian() {
int i=nums.size();
if(i%2) return nums[i/2];
else return (nums[i/2]+nums[i/2-1])/2.0;
}
};
class MedianFinder2 {
vector<int> store;
public:
void addNum(int num) {
if (store.empty())
store.push_back(num);
else
store.insert(lower_bound(store.begin(), store.end(), num), num);
}
double findMedian()
{
int n = store.size();
return n & 1 ? store[n / 2] : (store[n / 2 - 1] + store[n / 2]) * 0.5;
}
};
class MedianFinder3 {
public:
priority_queue<int, vector<int>> max;
priority_queue<int, vector<int>, greater<int>> min;
MedianFinder() {}
void addNum(int num) {
if(min.empty() || num>=min.top()) min.push(num);
else max.push(num);
if(min.size()==max.size()+2) {
max.push(min.top());
min.pop();
} else if(max.size()==min.size()+2) {
min.push(max.top());
max.pop();
}
}
double findMedian() {
if(max.size()==min.size()) return (max.top()+min.top())/2.0;
else if(max.size()>min.size()) return max.top();
else return min.top();
}
};
|
剑指 Offer 42. 连续子数组的最大和*
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
提示：
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int maxSubArray(vector<int> &nums) {
int len=nums.size();
int ans=nums[0];
for (int i=1; i<len; i++) {
if (nums[i-1] > 0) {
nums[i] += nums[i-1];
}
ans = max(nums[i], ans);
}
return ans;
}
};
|
剑指 Offer 43. 1～n整数中1出现的次数*
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5
示例 2：
输入：n = 13
输出：6
限制：
1 <= n < 2^31
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int countDigitOne(int n) {
long ans=0;
long i=1;
while(n/i) {
long high=(n/i)/10;
long cur=(n/i)%10;
if(!cur) {
ans+=high*i;
} else if(cur==1) {
ans += high*i + n-(n/i)*i+1;
} else {
ans += high*i+i;
}
i*=10;
}
return ans;
}
};
|
剑指 Offer 44. 数字序列中某一位的数字
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例 1：
输入：n = 3
输出：3
示例 2：
输入：n = 11
输出：0
限制：
0 <= n < 2^31
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof
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
| class Solution {
public:
int findNthDigit(int n) {
if(n<10) return n;
long wei=1;
long len=9;
long sum=9;
long num=1;
while(n>sum) {
num*=10;
wei+=1;
len=(len*10*wei)/(wei-1);
sum+=len;
}
sum-=len;
long n1=((n-sum)-1)/wei+1;
long n2=((n-sum)-1)%wei+1;
n2=wei-n2;
num+=(n1-1);
while(n2--) {
num/=10;
}
num%=10;
return num;
}
};
|
剑指 Offer 45. 把数组排成最小的数*
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: “102”
示例 2:
输入: [3,30,34,5,9]
输出: “3033459”
提示:
0 < nums.length <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
string minNumber(vector<int>& nums) {
vector<string> strs;
string res;
for(auto num:nums) strs.push_back(to_string(num));
sort(strs.begin(), strs.end(), helper);
for(auto str:strs) res+=str;
return res;
}
static bool helper(string &a, string &b) {
return a+b<b+a;
}
};
|
剑指 Offer 46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是”bccfi”, “bwfi”, “bczi”, “mcfi”和”mzi”
提示：
0 <= num < 2^31
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int translateNum(int num) {
int dp[20]={0};
dp[0]=1;
dp[1]=1;
int i=2;
int pre=num%10;
while(num/=10) {
int cur=num%10;
if(cur*10+pre<26 && cur*10+pre>9) {
dp[i]=dp[i-1]+dp[i-2];
} else {
dp[i]=dp[i-1];
}
pre=cur;
i++;
}
return dp[i-1];
}
};
|
剑指 Offer 47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
0 < grid.length <= 200
0 < grid[0].length <= 200
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
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
| class Solution {
public:
int m[200][200];
int maxValue(vector<vector<int>>& grid) {
int len1=grid.size();
if(!len1) return 0;
int len2=grid[0].size();
m[len1-1][len2-1]=grid[len1-1][len2-1];
for(int i=len1-2;i>=0;i--) m[i][len2-1]=m[i+1][len2-1]+grid[i][len2-1];
for(int i=len2-2;i>=0;i--) m[len1-1][i]=m[len1-1][i+1]+grid[len1-1][i];
for(int i=len1-2;i>=0;i--) {
for(int j=len2-2;j>=0;j--) {
if(m[i+1][j]>=m[i][j+1]) m[i][j]=grid[i][j]+m[i+1][j];
else m[i][j]=grid[i][j]+m[i][j+1];
}
}
return m[0][0];
}
};
class Solution2 {
public:
int m[205];
int maxValue(vector<vector<int>>& grid) {
int len1=grid.size();
if(!len1) return 0;
int len2=grid[0].size();
for(int i=0;i<len1;i++) {
for(int j=0;j<len2;j++) {
m[j+1]=grid[i][j]+max(m[j],m[j+1]);
}
}
return m[len2];
}
};
|
剑指 Offer 48. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
提示：
s.length <= 40000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof
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
| class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len=s.size();
if(!len) return 0;
if(len==1) return 1;
int l=0, r=0;
int ans=1;
set<char> flag;
flag.insert(s[0]);
while(r<len-1) {
int i=l;
r++;
if(flag.count(s[r])) {
for(;i<r;i++) {
if(s[i]==s[r]) break;
flag.erase(s[i]);
}
l=i+1;
} else {
flag.insert(s[r]);
}
if(ans<r-l+1) ans=r-l+1;
}
return ans;
}
};
|
剑指 Offer 49. 丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chou-shu-lcof
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int nthUglyNumber(int n) {
if(!n) return 0;
vector<int>num(n,0);
num[0]=1;
int p1=0,p2=0,p3=0;
for(int i=1;i<n;i++) {
int temp=min(num[p1]*2,min(num[p2]*3,num[p3]*5));
num[i]=temp;
if(temp==num[p1]*2) p1++;
if(temp==num[p2]*3) p2++;
if(temp==num[p3]*5) p3++;
}
return num[n-1];
}
};
|
剑指 Offer 50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例:
s = “abaccdeff”
返回 “b”
s = “”
返回 “ “
限制：
0 <= s 的长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof
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
| class Solution {
public:
char firstUniqChar(string s) {
int len=s.size();
if(!len) return ' ';
vector<int> vec(26,0);
for(int i=0;i<len;i++) {
int t=s[i]-'a';
if(!vec[t]) {
vec[t]=i+1;
} else if(vec[t]>0){
vec[t]=-1;
}
}
int ans=len+1;
for(int i=0;i<26;i++) {
if(vec[i]>0 && ans>vec[i]) {
ans=vec[i];
}
}
if(ans==len+1) return ' ';
return s[ans-1];
}
};
|
