当前位置: 首页 > >

LeetCode算法题个人笔记【数组】【简单6-10】【c++】

发布时间:

**


第六题:还是杨辉三角

**


和 118 题 一样,依旧是杨辉三角。区别在于之前是输出所有层的数,这道题只需要输出第 k 层的数。


意思是说,我们只用一行vector< int> 就行,不断更新这一个,(1 )->( 1,1) ->(1,2,1)因为根据上一题我们可以知道反正都是根据上一行得到当前行,动态规划对吧。


且注意这题条件有所不同


输入: 3
输出: [1,3,3,1]


这里的rowIndex不是指行数,而是指索引



class Solution {
public:
vector getRow(int rowIndex)
{
vector result;
for(int i=0;i<=rowIndex;i++)
{
result.push_back(1);
for(int j=i-1;j>0;j--)//从后往前,从倒数第二个(i-1)到第二个(1)
{
result[j]+=result[j-1];
}
}
return result;
}
};

高,实在是高


方法二:数学法


0!=1,n!=(n-1)!×n。




Cnk?=n!/(k!(n?k)! ) = ((n?k+1)* (n-k) *…(n-2)(n-1)(n))/k!


举例rowIndex=3;很容易理解


class Solution {
public:
vector getRow(int rowIndex)
{
vector ans;
int n=rowIndex;
for(int k=0;k<=n;k++)
{
ans.push_back(Combination(n,k));
}
return ans;
}
int Combination(int n,int k)
{
long result=1;//细
for(int i=1;i<=k;i++)//阶乘,1到k,不久是!k呗
{
result=result*(n-k+i)/i;
}
return (int)result;
}
};

**


第七题:买卖股票的最佳时机

**


给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。


如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。


注意:你不能在买入股票前卖出股票。


输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。


输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。


似乎有点类似之前的最长公共子串,确实这题同样有个解法是动态规划


评论区:


动态规划 前i天的最大收益 = max{前i-1天的最大收益,第i天的价格-前i-1天中的最小价格}
同时随时间更新最小价格
存在只有一天的情况,此时利润为0


DP (dynamic programming)
DP的思路: 利用原问题与子问题的关系,将其变成 大问题的解 = 小问题的解的函数, 从而将问题变成size的扩展即可,当size到达最大后,原问题解决了


暴力法已经见怪不怪了,现在看到什么题目我第一反应都是遍历。。
果然这题也是可以的


class Solution{
public:
int maxProfit(vector& prices)
{
int n=(int )prices.size(),ans=0;
for(int i=0;i {
for(int j=i+1;j {
ans=max(ans,prices[j]-prices[i]);
}
}
return ans;
}
};

时间复杂度:O(n^2)。循环运行n (n-1)/2次。
空间复杂度:O(1)。只使用了常数个变量。


超时。。


方法二:


我们来假设自己来购买股票。随着时间的推移,每天我们都可以选择出售股票与否。那么,假设在第 i 天,如果我们要在今天卖股票,那么我们能赚多少钱呢?


显然,如果我们真的在买卖股票,我们肯定会想:如果我是在历史最低点买的股票就好了!太好了,在题目中,我们只要用一个变量记录一个历史最低价格 minprice,我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。


因此,我们只需要遍历价格数组一遍,记录历史最低点,然后在每一天考虑这么一个问题:如果我是在历史最低点买进的,那么我今天卖出能赚多少钱?当考虑完所有天数之时,我们就得到了最好的答案。


所以这里的历史最低价格其实不是很准确,应该说是区间的最低价格


class Solution{
public:
int maxProfit(vector& prices)
{
int minprice=1e9,maxprofit=0;

for(int price: prices)
{
maxprofit=max(maxprofit,price-minprice);
minprice=min(price,minprice);
}
return maxprofit;
}
};

1.什么是1e9
通常来说这是计算机中一种科学计数法的表示形式:
1e9 = 110^9 = 1000000000;
例如:9e8 = 910^8 = 900000000;
e表示10,e后面的数字表示次方,e的多少次方。


实际中遇到的一些问题,或者解决一些算法问题时,会遇到给某个变量初始化并赋值为1e9。接着后面会出现一些代码计算最小值。
这时,1e9的作用是给变量赋一个初始极大值,原因在于后面的代码中需要取此变量和其他变量的最小值。初始化为一个最大值,亦即初始化为无穷,便于后面极小值的比较和获取,属于初始化的目的。


这个和之前求最大子数组的也太像了8


感觉这个就是动态规划了啊


方法三:单调栈


有点难懂,学*中


class Solution{
public:
int maxProfit(vector& prices)
{
int ans=0;
vector St;
prices.emplace_back(-1);
for(int i=0;i {
while(!St.empty()&&St.back()>pirces[i])
{
ans=std::max(ans,St.back()-St.front());
St.pop_back();
}
St.emplace_back(prices[i]);
}
return ans;
}
};

emplace_back在容器尾部添加一个元素,这个元素原地构造,不需要触发拷贝构造和转移构造。而且调用形式更加简洁,直接根据参数初始化临时对象的成员。
就是类似于push_back


std是一个类(输入输出标准),它包括了cin成员和cout成员,“using name space std ;”以后才能使用它的成员


而且是用了vector来代替这个栈


一眼看过去,这个题本质就是要求某个数与其右边最大的数的差值,这符合了单调栈的应用场景 当你需要高效率查询某个位置左右两侧比他大(或小)的数的位置的时候,


首先我们要明确这个是在一个时间序列上的,因此我们不能简单的用 最大减最小解决问题,


ps:这里的意思就是不能简单的遍历最大值然后减去最小值,这和之前的最大子数组中的子数组这个条件类似


1 在 pricesprices 数组的末尾加上一个 哨兵????(也就是一个很小的元素,这里设为 0)),就相当于作为股市收盘的标记(后面就清楚他的作用了)(然而设的是-1)
2 假如栈空或者入栈元素大于栈顶元素,直接入栈
3 假如入栈元素小于栈顶元素则循环弹栈,直到入栈元素大于栈顶元素或者栈空
4 在每次弹出的时候,我们拿他与买入的值(也就是栈底)做差,维护一个最大值。


ps:哨兵是用来解决比如prices本身就是单调增的情况,


ps: 感觉没有作者说的这么复杂,因为栈的特点就是先进后出,用单调增的栈可以保证买入股票之后再卖出股票,


还是老一套,功能与需求分析,需求,也就是题目的要求是,找出最大利润,换成具体的,就是区间内的最大值减最小值,然后比较每个区间利润得到最大利润



和之前那个实在太像了,大问题其实就是从头到尾的整个时间段,就像之前的整个数组一样,而小问题就是每个时间区间,就像之前的子数组一样,


这里总有上升的区间和下降的区间,就和之前的正子串和负字串一样,,这里我们可以直接忽略下降的区间,直接得到的是最小值
和之前的不同在于这里要的是最大的差值,之前是最大的和


这就是将大问题化成了若干个小问题,像这里这种最大利润,只需更新每个小问题的利润就行。


而我们要求的时候,注意的地方就是每个区间分隔的条件要找到。这道题的话,显然最小值就是,价格降没问题,关键在于有没有降到让最小值更新



感谢这位单调栈的前辈,让我似乎对于动态规划有了点认识,


因为这里这个弹栈的条件,也就是卖出股票的条件,,就是我们划分区间的条件,


1 : 入栈,(假设增区间开始),将价格先进后出,
2 : 弹栈,模拟买卖,也就是计算差值,得到利润,栈顶减栈底
3 : 循环弹栈,为的是更新最小值,因为只要下降,就有可能会有新的最小值


DP的keypoint


一:转移方程(大问题与小问题的关系)
1)定义状态:定义一个状态,例如f(i) = 到a[i]为止到最小值
2)设计转移方程:根据如上状态方程定义,则有 f(i+1) = min(f(i), a[i+1])


tip:
转移方程的设计完全依赖于状态的定义,并不是什么样的状态定义,都能有状态转移方程,因此,状态定义决定了该DP方法能否实现


二:初始条件的设置: Dp本质还是迭代,总要有一个迭代的初值。 (指第一天价格?


三:特殊处理小size的问题:有些情况,由于size太小,没法带入转移方程中。


根据该问题,依次回答上述问题:


一:大问题与小问题的关系
状态定义:我们定义max_profit为第i天的最大收益
状态转移方程:
第i天的最大收益和第i-1天的最大收益之间的关系:
i) 最大收益不是第i天抛出的, ?最大收益和第i天的价格无关
ii)最大收益是在第i-1天前某天买入的,并在第i天抛出的, ?与第i天的价格有关


因此第i天的最大收益等于:第i天抛出所造成的最大收益 和 第i-1天之前的最大收益 中的最大值
即:
前i天的最大收益 = max{前i-1天的最大收益,第i天的价格-前i-1天中的最小价格}
其中:
前i-1天中的最小价格需时时更新并记录


ps:讲道理这个作者解释的很清楚,我们再简化一下总之:


大问题:从头到尾的最大利润,小问题:从第一天到第i天的最大利润
转移状态就是我们的大问题,转移方程就是我们的小问题的函数,当size最大后,原问题解决


这里的小问题的函数怎么写出应该就是唯一需要思考的了,本题而言,画个折线图就很清晰的知道小问题就是每个区间


二:初始条件:
min 和 max_profit
min可以等于第一天的price
max_profit可以等于0, 因为最大收益的最小值就是0, 用人话叫,最低也不能赔了


ps:就是数据初始值呗。。


三:小于最小问题的特殊情况: 当list的长度为0 和 1 时, 没有办法带入转移公式中,需要特殊处理。


**


第八题:Best Time to Buy and Sell Stock II

**


Say you have an array prices for which the ith element is the price of a given stock on day i.


Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).


Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).


官方题解写得好多,还不如评论区的简洁明了


方法一:贪心算法


首先要知道第0天买入,第3天卖出的利润:prices[3] - prices[0],相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + ()prices[1] - prices[0])


就比如 3 6 12 12-3=(6-3)+(12-6)=9


所以收集正利润就行,也就是只要几天比昨天大就做减法并将利润累加
贪心所贪的地方,就是只收集正利润


class Solution
{
public:
int maxProfit(vector& prices)
{
int result=0;
for(int i=1;i {
result=max(prices[i]-prices[i-1],0);
}
return result;
}
};

方法二:动态规划
不要上来就去看别人写的解,先自己思考


如果说大问题是从头到尾的总利润,那么和上一道题一样,转移状态就是总利润,而不是最大利润了,
小问题就变成了,每天的总利润,(且注意,我们仍旧只求出利润,不会亏损


不明白,先放着吧


**


第九题:Two Sum II - Input array is sorted

**


Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.


The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.


Note:


Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.


那么:当然可以直接暴力法或用哈希表,但是因为是有序数组,所以首先先考虑二分法和双指针法,


方法一:二分法


class Solution {
public:
vector twoSum(vector& numbers, int target) {
int right=numbers.size()-1;
for(int i=0;i {
int left=i+1;

while(left<=right)
{
int mid=(left+right)/2

if(numbers[mid]==target-numbers[i])
{
return {i+1,mid+1};
}
else if(numbers[mid] {
left=mid+1;
}
else
{
right=mid-1;
}
}
}
return {-1,-1};
}
};

最后记得此题返回索引+1;


讲道理很简单,从左往右取每个元素,然后在它之后的所有元素用二分法查找有没有,没有就取下一个,


关于二分法,每次要还是用数形结合,就像一个尺子,上面的刻度,然后移动刻度,


并且注意,如果没有目标值,最后一定是left=right=mid,然后移动了left或right跳出循环了(mid±1是让我们能跳出的,同时也是因为mid!=target不用取)


如果有目标值,可能在中间某次就target=mid跳出,最糟糕的情况就是taget=左边界或右边界,因为这样我们会达到二分的最大时间复杂度,不断移动左或右边界最后一定会到达的情况是left=right=mid=(right+left)/2=target然后返回,跳出循环。


方法二:双指针


class Solution {
public:
vector twoSum(vector& numbers, int target) {
int left=0,right=numbers.size()-1;
while(left {
if((numbers[left]+numbers[right])==target)
{
return {left+1,right+1};
}
else if((numbers[left]+numbers[right]) {
left++;
}
else
{
right--;
}
}
return {-1,-1};
}
};

简单,双指针有一头一尾和一快一慢,这里用一头一尾就行,和小于target时移动左指针,否则移动右指针,


**


第十题:Majority Element

**


Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.


You may assume that the array is non-empty and the majority element always exist in the array.


那么每个数组肯定有且仅有一个满足条件的元素,并且题目说一定存在


方法众多


方法一:哈希表


class Solution {
public:
int majorityElement(vector& nums) {
unordered_map counts;
int majority = 0, cnt = 0;
for (int num: nums) {
++counts[num];//这里就直接存入了?6的
if (counts[num] > cnt) {
majority = num;
cnt = counts[num];
}
}
return majority;
}
};

我们使用哈希映射(HashMap)来存储每个元素以及出现的次数。对于哈希映射中的每个键值对,键表示一个元素,值表示该元素出现的次数。
我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后,我们遍历哈希映射中的所有键值对,返回值最大的键。


也就是说majority,就是键,就是我们要求的次数最多的元素,而哈希表里的索引就是值


cnt呢就是当前最大的出现次数,关键就在于这个哈希表的值(索引)是可以变的,


方法二:排序


class Solution {
public:
int majorityElement(vector& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
};

没啥好说的


方法三:随机化


1、rand()不需要参数,它会返回一个从0到最大随机数的任意整数,最大随机数的大小通常是固定的一个大整数。


2、如果你要产生0~99这100个整数中的一个随机整数,可以表达为:int num = rand() % 100; //注意不取100


class Solution {
public:
int majorityElement(vector& nums) {
while (true) {
int candidate = nums[rand() % nums.size()];
int count = 0;
for (int num : nums)
if (num == candidate)
++count;
if (count > nums.size() / 2)
return candidate;
}
return -1;
}
};

方法四:分治


    分治法
    分治法的基本思想是:把一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破。

每一层递归上有三个步骤:


分解:将原问题分解为若干个规模较小,相互独立并且与原问题形式相同的子问题
解决:若子问题规模较小且容易被解决则直接解决,否则递归地解决各个子问题
合并:合并子问题的解为原问题的解


    二分法
    使用二分法的场景通常是数组中元素是有序的,然后根据中间元素的值和目标值进行比对,判断下一步应该在哪一半(舍弃另一半)查找,从而使得时间复杂度在O(log(n)).

二分法重点在于:


决定查找的边界,左闭右开或者左闭右闭,根据查找的区间来决定边界的更新以及循环结束的条件(区间中至少有一个元素或者已经找到了临界值)
要确定自己二分查找的结果的临界条件


class Solution {
int count_in_range(vector& nums, int target, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; ++i)
if (nums[i] == target)
++count;
return count;
}
int majority_element_rec(vector& nums, int lo, int hi) {
if (lo == hi)
return nums[lo];
int mid = (lo + hi) / 2;
int left_majority = majority_element_rec(nums, lo, mid);
int right_majority = majority_element_rec(nums, mid + 1, hi);
if (count_in_range(nums, left_majority, lo, hi) > (hi - lo + 1) / 2)
return left_majority;
if (count_in_range(nums, right_majority, lo, hi) > (hi - lo + 1) / 2)
return right_majority;
return -1;
}
public:
int majorityElement(vector& nums) {
return majority_element_rec(nums, 0, nums.size() - 1);
}
};

rec指递归recursion


我们使用经典的分治算法递归求解,直到所有的子问题都是长度为 1 的数组。长度为 1 的子数组中唯一的数显然是众数,直接返回即可。


每次像这种情况,代码一大堆的时候,就不要忘记了用需求功能分析法,我们的需求是什么,方法提供了什么功能,


所以分治是伴随着递归的对吗,那么递归我们就从最小情况开始看


关键在于知道这个count_in_range方法算的是什么,或者说,我们分治,先二分分到只有一个数



1,2,4的时候还另有说法,


1个数的时候,返回本身没问题,两个数时,左右皆可我们选择left,4个数时众数肯定是有3个的所以(0,3)内左半部分众数0,右半部分为2,取两个数肯定是可以一个为众数的,(我们这样的前题是这4个数里存在众数,当然也可能不存在,没关系,从大问题上看反正肯定是存在于某一边的)


不过到了8个数的时候就会发现本质上这样操作是依赖于数学原理的,题目已经告诉我们肯定存在众数,还是画图说明,假设我们先拍好序



总的众数必然是某一边的众数,想再多不如动手画个图


所以分治看起来就是二分加递归。。先二分到一个数,然后归一层,之后归的条件变为找出众数


方法五:Boyer-Moore 投票算法


用于查找子字符串的算法当中,BM(Boyer-Moore)算法被认为最高效的字符串搜索算法,它由Bob Boyer和J Strother Moore设计于1977年。 一般情况下,比KMP算法快3-5倍。


如果我们把众数记为 +1,把其他数记为 -1,将它们全部加起来,显然和大于 0,从结果本身我们可以看出众数比其他数多。


对于这个问题,分析的时候不要往复杂的想,其实任何问题都一样,永远尝试将复杂化简单,
我们就假设它是拍好序的,再来分析


class Solution {
public:
int majorityElement(vector& nums) {
int candidate = nums[0];
int count = 0;
for (int num : nums) {
if (num == candidate)
++count;
else if (--count < 0) {
candidate = num;
count = 1;
}
}
return candidate;
}
};

假设众数在前,最后count肯定为1啦,(放屁,众数又不是一定1/2+1,count是肯定>0才对)
假设所有非众数在前。
总之排好序分析就方便了


特殊情况往往便于分析
)
)
)
摩尔投票法:


核心就是对拼消耗。


玩一个诸侯争霸的游戏,假设你方人口超过总人口一半以上,并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。


那就大混战呗,最差所有人都联合起来对付你(对应你每次选择作为计数器的数都是众数),或者其他国家也会相互攻击(会选择其他数作为计数器的数),但是只要你们不要内斗,最后肯定你赢。


最后能剩下的必定是自己人。


)
)
所有众数在前的情况好说,即所有人联合,
如果是非众数,就像人口一样,每个数字的集合相当于一个国家,数字的个数相当于人口,当count<0时就是换国家记人口数了




友情链接: