Week 8 - 338.Counting Bits & 413. Arithmetic Slices
#338.Counting Bits - Medium
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example:
For num = 5
you should return [0,1,1,2,1,2]
.
Follow up:
- It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
- Space complexity should be O(n).
- Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
Credits:
Special thanks to @ syedee for adding this problem and creating all test cases.
my solution:
#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
vector<int> countBits(int num) {
vector<int> result;
result.push_back(0);
for (int i = 1; i <= num; i++) {
result.push_back(result[i&(i-1)] + 1);
}
return result;
}
};
这道题的主要想法是,每个数和前一个数做按位与再加一就能得到1的个数。这道题要求不高,暴力地数1的个数也能AC。。。
#413. Arithmetic Slices - Medium
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 ⇐ P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
my solution:
#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int count = 0;
vector<int> dp(A.size(), 0);
for (int i = 2; i < A.size(); i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp[i] = dp[i - 1] + 1;
count += dp[i];
}
}
return count;
}
};
这道题的大意是返回给定数组中不同的等差数列的个数。这道题我的解法是:一个项数为n的等差数列(n >= 3),每多一项,它的子等差数列的数量就多(n-2)项。这个子等差数列数量构成的数列也是一个等差数列。
最新文章
- /etc/ppp/chap-secrets
- 劈荆斩棘:Gitlab 部署 CI 持续集成
- MySQL分区总结
- css不常用重要属性
- Azure 删除VHD时报错:There is currently a lease on the blob and no lease ID was specified in the request
- 使用ftp软件上传下载php文件时换行丢失bug
- EasyUI——弹窗展示数据代码
- 解决Android抽屉被击穿问题
- Chapter12&;Chapter13:程序实例
- unison + inotify 实现文件实时双向同步部署步骤
- python学习笔记16(错误、异常)
- sql 时间格式化
- 等待与希望,.NET Core 的发展壮大
- vue小白快速入门
- java一个大接口拆用多线程方式拆分成多个小接口
- dao层、service和action的运用和区别
- Jquery 字符串转数字
- 51nod 1295 XOR key 可持久化01字典树
- js实现瀑布流以及加载效果
- bzoj3601