【小白刷题之路Day26】贪心法总结

 

1、leetcode717 1比特与2比特字符

常规解题思路：从头开始遍历数组，遇到1跳两位，遇到0跳一位，最后检查末尾是0还是10。

 

贪心法思路：无论是数字0还是数字10，都以0结尾，那么检察末尾数字0前面有多少位1，查看是否是2的倍数个即可。

虽然时间复杂度也是O(n)，但是很多例子中可明显降低遍历范围！

我的提交如下

class Solution { public: bool isOneBitCharacter(vector<int>& bits) { int n = bits.size(), count = 0; int i=n-1; while (i-1 >= 0){ if (bits[i-1] == 1){ ++count; --i; } else break; } if (count % 2 == 0) return true; else return false; } };

 

2、剑指offer 剪绳子

 

转载于:https://www.cnblogs.com/ACStrive/p/11584646.html

相关资源：JAVA上百实例源码以及开源项目