突发奇想&胡思乱想的一天
银行家算法证明错了并挂在黑板上的可怜希希
Num 53 最大子序和 Maximum Subarray
O(n)的算法实现了,分治法有空补
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int a[];
int ans=-;
int len=nums.capacity();
memset(a,,sizeof(a));
a[len-]=nums[len-];
ans=nums[len-];
for(int i=len-;i>=;i--)
{
a[i]=max(nums[i],nums[i]+a[i+]);
if(a[i]>ans)
ans=a[i];
}
return ans;
}
};
跳过了一个饶舌题,回头看
Num 58 最后一个单词的长度 Length of Last Word
注意有可能最后一个单词后面出现大段空格,更好的解决办法是倒序判断第一个非空格哦。
class Solution {
public:
int lengthOfLastWord(string s) {
int len=s.length();
int ans=;
for(int i=;i<=len-;i++)
{
if(s[i]==' ' && i!=len- && s[i+]!=' ') ans=;
else if(s[i]!=' ')ans++;
}
return ans;
}
};