牛客网
算法周周练
用bitset
题目来源：牛客网 ==》 链接
一共有 n个数，第 i 个数是 xi， xi可以取 [ li, ri] 中任意的一个值。 S=Σxi2，求 S 种类数。
输入描述：第一行一个数 n。 然后 n 行，每行两个数表示 li, ri。
输出描述：输出一行一个数表示答案。
备注:1 ≤ n , li , ri≤ 100。
优质答案 ==》 链接
#pragma GCC optimize(3,"Ofast","inline") //G++
#include<bits/stdc++.h>
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << ": " << x << endl;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fcout cout<<setprecision(4)<<fixed
using namespace std;
typedef long long ll;
//======================================
namespace FastIO{
char print_f[105];void read() {}void print() {putchar('\n');}
template <typename T, typename... T2>
inline void read(T &x, T2 &... oth){x = 0;char ch = getchar();ll f = 1;while (!isdigit(ch)){if (ch == '-')f *= -1;ch = getchar();}while (isdigit(ch)){x = x * 10 + ch - 48;ch = getchar();}x *= f;read(oth...);}
template <typename T, typename... T2>
inline void print(T x, T2... oth){ll p3=-1;if(x<0) putchar('-'),x=-x;do{print_f[++p3] = x%10 + 48;}while(x/=10);while(p3>=0) putchar(print_f[p3--]);putchar(' ');print(oth...);}} // namespace FastIO
using FastIO::print;
using FastIO::read;
//======================================
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int maxn = 1e6+5;
bitset<1000005>pre,ans;
int main() {
#ifndef ONLINE_JUDGE
freopen("H:\\code\\in.in", "r", stdin);
freopen("H:\\code\\out.out", "w", stdout);
clock_t c1 = clock();
#endif
//**************************************
int n;
read(n);
pre[0]=1;
for(int i=1;i<=n;i++){
int l,r;
read(l,r);
ans.reset();
for(int i=l;i<=r;i++){
ans|=pre<<(i*i);
}
pre=ans;
}
print(ans.count());
//**************************************
#ifndef ONLINE_JUDGE
cerr << "Time:" << clock() - c1 << "ms" << endl;
#endif
return 0;
}
力扣leetcode
#1 两数之和
（暴力循环 ,map，最优解） ==》链接
暴力循环：执行用时：736 ms（defeat11.09%）,内存消耗：7.2 MB（defeat100%）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n=nums.size();
vector<int> res;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(nums[i]+nums[j]==target){
res.push_back(i);
res.push_back(j);
}
}
}
return res;
}
};
使用map：执行用时：24 ms（defeat52.7%）,内存消耗：8.2 MB（defeat100%）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n=nums.size();
map<int,int> mp;
vector<int> res;
for(int i=0;i<n;i++){
int t=target-nums[i];
if(mp.count(t)){
res.push_back(mp[t]);
res.push_back(i);
break;
}
else mp[nums[i]]=i;
}
return res;
}
};
网站最优解：执行用时：12 ms（defeat85.62%）,内存消耗：8 MB（defeat100%）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
if(nums.size()<=1)
return res;
unordered_map<int,int> myMap;
for(int i=0;i<nums.size();i++){
int rest_val=target-nums[i];
if(myMap.find(rest_val)!=myMap.end()){
int index=myMap[rest_val];
if(index==i)
continue;
if(index<i){
res.push_back(index);
res.push_back(i);
return res;
}else{
res.push_back(i);
res.push_back(index);
return res;
}
}
myMap[nums[i]]=i;
}
return res;
}
};
#2 两数相加
（链表，考虑进位） ==》链接
链表操作：执行用时：28 ms（defeat69.2%）,内存消耗：9.3MB（defeat100%）
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head=new ListNode(-1);//存放结果的链表
ListNode* h=head;//移动指针
int sum=0;//每个位的加和结果
bool carry=false;//进位标志
while(l1!=NULL||l2!=NULL){
sum=0;
if(l1!=NULL){
sum+=l1->val;
l1=l1->next;
}
if(l2!=NULL){
sum+=l2->val;
l2=l2->next;
}
if(carry) sum++;
h->next=new ListNode(sum%10);
h=h->next;
carry=sum>=10?true:false;
}
if(carry) h->next=new ListNode(1);
return head->next;
}
};
#3 无重复字符的最长子串
（哈希集合 hash set，256字符数组，动态规划） ==》 链接
哈希集合 hash set：执行用时：60 ms（defeat27%）,内存消耗：11.3MB（defeat39.7%）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);
}
return ans;
}
};
256字符数组：执行用时：8 ms（defeat93.02%）,内存消耗：8.5MB（defeat100%）
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int start = 0, n = s.size();
vector<int> pos(256, -1);
int res = 0;
for(int i = 0; i < n; ++i){
if(pos[s[i]] >= start) start = pos[s[i]] + 1;
pos[s[i]] = i;
res = max(res, i - start + 1);
}
return res;
}
};
动态规划：执行用时：8 ms（defeat93.02%）,内存消耗：7.1MB（defeat100%）
动态规划解法解题思路：
状态：
dp[i]表示以第i个字符结尾的无重复字符子串的长度。
比如 abcbc :
dp[0] = 1; “a”
dp[1] = 2; “ab”
dp[2] = 3; “abc”
dp[3] = 2; “cb”
dp[4] = 2; “bc”
初始值：对于第一个字符，dp[0] = 1
状态转移：
对于第i个字符，如果在dp[i-1]所代表的子串中出现，那么从所出现的位置j的下一个位置到i，构成了以i结尾的不重复子串。即dp[i] = i-j;
如果第i个字符不在前面的dp[i-1]子串中出现，那么i-1子串加上i字符构成了i子串，因此 dp[i] = dp[i-1]+1；
那么需要担心j位置后又出现了字符i吗？不需要，因为前面的子串本身就是不重复的，不可能存在两个字符i。
最大值： 返回 max(dp[i]) 即可
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int size = (int)s.size();
if(size==0){
return 0;
}
int lastLen = 1;
int max = 1;
int curLen = 0;
for(int i=1; i<size; ++i){
curLen = 0;
for(int j=i-lastLen; j<=i-1; ++j){
if(s[j]==s[i]){
curLen = i-j;
break;
}
}
if(curLen==0){
curLen = lastLen + 1;
}
if(curLen>max){
max = curLen;
}
lastLen = curLen;
}
return max;
}
};
京公网安备 11010502036488号