717. 1比特与2比特字符
有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。
现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。
示例 1:
输入:
bits = [1, 0, 0]
输出: True
解释:
唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
示例 2:
输入:
bits = [1, 1, 1, 0]
输出: False
解释:
唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。
注意:
1 <= len(bits) <= 1000.bits[i]总是0或1.
第一版,自己写的，速度较慢
执行用时 :8 ms, 在所有 cpp 提交中击败了54.05%的用户
内存消耗 :8.6 MB, 在所有 cpp 提交中击败了84.88%的用户
boolisOneBitCharacter(vector<int>&bits) {
intlow=0, high=bits.size()-2;
while (low<high) {
if (bits[low] ==1) {
low++;
if (bits[low] ==1||bits[low] ==0) low++;
}elseif (bits[low] ==0) low++;
}
if (low==high) {
if (bits[low] ==0&&bits[low+1] ==0)
returntrue;
else
returnfalse;
}
else
returnbits[low] ==0;
}
第二版，换了一个思路
执行用时 :4 ms, 在所有 cpp 提交中击败了90.45%的用户
内存消耗 :8.6 MB, 在所有 cpp 提交中击败了80.76%的用户
boolisOneBitCharacter(vector<int>&bits) {
if (bits[bits.size() -1] ==1) returnfalse;
intlow=0, high=bits.size();
while (low<high) {
if (bits[low] ==1) {
low+=2;
}
elseif (bits[low] ==0) {
if (low==high-1) break;
low++;
}
}
if (low==high-1) {
returntrue;
}
else
returnfalse;
}
674. 最长连续递增序列
给定一个未经排序的整数数组，找到最长且连续的的递增序列。
示例 1:
输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
示例 2:
输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
注意：数组长度不会超过10000。
第一版，自己写的，很慢啊，比较low
执行用时 :28 ms, 在所有 cpp 提交中击败了14.37%的用户
内存消耗 :25.3 MB, 在所有 cpp 提交中击败了5.21%的用户
intfindLengthOfLCIS(vector<int>&nums) {
stack<int>res;
size_tmaxLen=0;
for (auto&n : nums) {
if (res.empty() ||n>res.top())//为空或者当前值大于前面一个值
res.push(n);
else//小于等于当前top,千万记得要把这次的值放进去
{
maxLen= (res.size() >maxLen?res.size() : maxLen);
(stack<int>()).swap(res);
res.push(n);
}
}
maxLen= (res.size() >maxLen?res.size() : maxLen);
returnmaxLen;
}
第二版，自己改进了一下，不过性能还是不太行
执行用时 :16 ms, 在所有 cpp 提交中击败了70.37%的用户
内存消耗 :9.5 MB, 在所有 cpp 提交中击败了47.56%的用户
intfindLengthOfLCIS(vector<int>&nums) {
if (nums.empty()) return0;
inttemp=nums[0];
intmaxLen=0,tempLen=0;
for (auto&n : nums) {
if (n>temp)//为空或者当前值大于前面一个值
{
temp=n;
tempLen++;
}
else//小于等于当前top,千万记得要把这次的值放进去
{
maxLen= (tempLen>maxLen?tempLen : maxLen);
tempLen=1;
temp=n;
}
}
maxLen= (tempLen>maxLen?tempLen : maxLen);
returnmaxLen;
}
