10 - I 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1示例 2：
输入：n = 5
输出：5题解
class Solution {
public:
int fib(int n) {
int a = 0, b=1,sum;
for(int i=0;i<n;i++){
sum=(a+b)%1000000007;
a=b;
b=sum;
}
return a;
}
};836 矩形覆盖
矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。
如果相交的面积为 正 ，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。
示例 1：
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出：true示例 2：
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出：false示例 3：
输入：rec1 = [0,0,1,1], rec2 = [2,2,3,3]
输出：false提示：
rect1.length == 4rect2.length == 4-109 <= rec1[i], rec2[i] <= 109rec1和rec2表示一个面积不为零的有效矩形
题解
class Solution {
public:
bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
if(rec1[0]==rec1[2]||rec1[1]==rec1[3]||rec2[0]==rec2[2]||rec2[1]==rec2[3]){
return false;
}
return !(rec1[2]<=rec2[0]|| //1右在2左的左边（左）
rec1[3]<=rec2[1]|| //1上在2下的下边（下）
rec1[0]>=rec2[2]|| //1左在2右的右边（右）
rec1[1]>=rec2[3]); //1下在2上的上边（上）
}
};10 - II（70）跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2示例 2：
输入：n = 7
输出：21示例 3：
输入：n = 0
输出：1提示：
0 <= n <= 100
题解
/*070*/
class Solution {
public:
int climbStairs(int n) {
long long a = 1, b = 1, sum;
for(int i = 0;i < n; i++)
{
sum=a+b;
a=b;
b=sum;
}
return a;
}
};
/*10-II*/
class Solution {
public:
int numWays(int n) {
int a=1, b=1, sum;
for(int i=0;i<n;i++){
sum=(a+b)%1000000007;
a=b;
b=sum;
}
return a;
}
};42（53）连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为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
题解
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = nums[0];
for(int i=1;i<nums.size();i++)
{
nums[i] += max(nums[i-1],0);//dp 两种情况
res = max(res, nums[i]);
}
return res;
}
};47 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物提示：
0 < grid.length <= 2000 < grid[0].length <= 200
题解
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int m = grid.size(), n= grid[0].size();
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if(i==0&&j==0)continue;
if(i==0)grid[i][j]+=grid[i][j-1];
else if(j==0)grid[i][j]+=grid[i-1][j];
else grid[i][j] += max(grid[i][j-1], grid[i-1][j]);
}
}
return grid[m-1][n-1];
}
};48（3） 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。提示：
s.length <= 40000
题解
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> dic;//统计s[j]最后一次出现的索引
int i=-1, res=0;
for(int j=0;j<s.size();j++)
{
if(dic.find(s[j])!=dic.end())//若出现过s[j]
i=max(i, dic[s[j]]);//更新左指针，若有重复字符在i，j间则更新i
dic[s[j]]=j;//更新索引位置
res=max(res,j-i);//保证取得最长的i，j区间
}
return res;
}
};49（264） 丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。说明:
1是丑数。n不超过1690。
题解
class Solution {
public:
int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int dp[n];
dp[0]=1;
for(int i=1;i<n;i++){
int n2=dp[a]*2, n3=dp[b]*3, n5=dp[c]*5;
dp[i]=min(min(n2,n3),n5);
if(dp[i]==n2)a++;
if(dp[i]==n3)b++;
if(dp[i]==n5)c++;
}
return dp[n-1];
}
};我的一点理解： 在已有的丑数序列上每一个数都必须乘2， 乘3， 乘5， 这样才不会漏掉某些丑数。假设已有的丑数序列为[1, 2, 3, ..., n1, n2], 如果单纯的让每个丑数乘2， 乘3， 乘5顺序排列的话肯定会有问题，
比如如果按照这样的顺序排列下去肯定有问题[12, 13, 15, 22, 23, 25, 32, 33, 35, ... , n1 2, n1 * 3, n1 * 5, n2 * 2, n3 3, n2 5]，因为后面乘2的数据可能会比前面乘3乘5的数据要小，那这个乘2的数应该排在他们的前面， 后面乘3的数据也可能比前面乘5的数据要小，那这个乘3的数应该排在他们的前面。
那怎么办呢，每个数都必须乘2， 乘3， 乘5这样才能保证求出所有的丑数，而且还要保证丑数的顺序，这个改如何同时实现呢？
通过观察网上的各个题解，终于找到了办法，那就是记录每个丑数是否已经被乘2， 乘3， 乘5了， 具体的做法是
设置3个索引a, b, c，分别记录前几个数已经被乘2， 乘3， 乘5了，比如a表示前(a-1)个数都已经乘过一次2了，下次应该乘2的是第a个数；b表示前(b-1)个数都已经乘过一次3了，下次应该乘3的是第b个数；c表示前(c-1)个数都已经乘过一次5了，下次应该乘5的是第c个数；
对于某个状态下的丑数序列，我们知道此时第a个数还没有乘2(有没有乘3或者乘5不知道）， 第b个数还没有乘3(有没有乘2或者乘5不知道），第c个数还没有乘5(有没有乘2或者乘3不知道), 下一个丑数一定是从第a丑数乘2， 第b个数乘3， 第c个数乘5中获得，他们三者最小的那个就是下个丑数。
求得下个丑数后就得判断这个丑数是谁，是某个数通过乘2得到的，还是某个数乘3得到的，又或是说某个数通过乘5得到的。我们可以比较一下这个新的丑数等于究竟是等于第a个丑数乘2, 还是第b个数乘3， 还是第c个数乘5， 通过比较我们肯定可以知道这个新的丑数到底是哪个数通过乘哪个数得到的。假设这个新的丑数是通过第a个数乘2得到的，说明此时第a个数已经通过乘2得到了一个新的丑数，那下个通过乘2得到一个新的丑数的数应该是第(a+1)个数，此时我们可以说前 a 个数都已经乘过一次2了，下次应该乘2的是第 （a+1） 个数, 所以a++；如果新的丑数是通过第b个数乘3得到的, 说明此时第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数，此时我们可以说前 b 个数都已经乘过一次3了，下次应该乘3的是第 （b+1） 个数, 所以 b++；同理，如果这个这个新的丑数是通过第c个数乘5得到的, 那么c++;
但是注意，如果第a个数乘2后等于第b个数乘3，或者等于第c个数乘5， 说明这个新的丑数是有两种或者三种方式可以得到，这时应该给得到这个新丑数的组合对应的索引都加一，比如新丑数是第a个数乘2后和第b个数乘3得到的，那么 a 和 b都应该加一， 因为此时第a个数已经通过乘2得到了一个新的丑数，第b个数已经通过乘3得到了一个新的丑数, 只不过这两个数相等而已。所以我们给计数器加一的时候不能使用 if else else if， 而应该使用if, if, if, 这样才不会把应该加一的计数器漏掉
经过n次循环，就能得到第n 个丑数了。
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n]; // 使用dp数组来存储丑数序列
dp[0] = 1; // dp[0]已知为1
int a = 0, b = 0, c = 0; // 下个应该通过乘2来获得新丑数的数据是第a个， 同理b, c
for(int i = 1; i < n; i++){
// 第a丑数个数需要通过乘2来得到下个丑数，第b丑数个数需要通过乘2来得到下个丑数，同理第c个数
int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
dp[i] = Math.min(Math.min(n2, n3), n5);
if(dp[i] == n2){
a++; // 第a个数已经通过乘2得到了一个新的丑数，那下个需要通过乘2得到一个新的丑数的数应该是第(a+1)个数
}
if(dp[i] == n3){
b++; // 第 b个数已经通过乘3得到了一个新的丑数，那下个需要通过乘3得到一个新的丑数的数应该是第(b+1)个数
}
if(dp[i] == n5){
c++; // 第 c个数已经通过乘5得到了一个新的丑数，那下个需要通过乘5得到一个新的丑数的数应该是第(c+1)个数
}
}
return dp[n-1];
}
}60 n 个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]限制：
1 <= n <= 11题解
class Solution {
public:
vector<double> dicesProbability(int n) {
vector<double> dp(6, 1.0/6.0);
for(int i=2;i<=n;i++){
vector<double> tmp(5*i+1,0);
for(int j=0;j<dp.size();j++){
for(int k=0;k<6;k++){
tmp[j+k]+=dp[j]/6.0;
}
}
dp=tmp;
}
return dp;
}
};66 构建乘积数组
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]提示：
- 所有元素乘积之和不会溢出 32 位整数
a.length <= 100000
题解
/*超时做法*/
vector<int> res;
for(int i=0;i<a.size();i++)
{
int tmp=1;
for(int j=0;j<a.size();j++)
{
if(i==j)continue;
tmp*=a[j];
}
res.push_back(tmp);
}
return res;
/*dp*/
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
int len = a.size();
vector<int> b(len, 1);
if(len==0)return b;
int left=1, right=1;
for(int i=0;i<len;i++){
b[i]*=left;
left*=a[i];//持有左边所有数的乘积
b[(len-1)-i]*=right;
right*=a[(len-1)-i];//持有右边所有数的乘积
}
return b;
}
};
/*dp*/
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
int len = a.size();
if(len==0)return {};
vector<int> b(len, 1);
b[0]=1;
int tmp=1;
for(int i=1;i<len;i++){
b[i]=b[i-1]*a[i-1];//计算下三角
}
for(int i=len-1-1;i>=0;i--){
//计算上三角
tmp*=a[i+1];
b[i]*=tmp;
}
return b;
}
};
