LeetCode Weekly Contest 26
写的有点晚了。
我每次都是先看一下这里http://bookshadow.com/leetcode/的思路,然后再开始写我自己的。
1. 521. Longest Uncommon Subsequence I
说实话,看完就懵逼了,这怎么做,难道是dp,后仔细一想,不对啊,很简单啊。
只要2个字符串不相等,返回长度较长的那个就行了。
刚开始,考虑,如果其中之一为空串,我返回的-1,不知道怎么想的。这显然是错的。
class Solution {
public:
int findLUSlength(string a, string b) {
int n = a.size(), m = b.size();
if(a == b)
return -;
return max(n, m);
}
};
2. 522. Longest Uncommon Subsequence II
有了第一题的基础,这道题就比较好分析。
注意到每个字符串长度至多是10,显然这是个入手点,考虑从这里入手。
方法是简单:先找长度最长的,然后如果这个字符是唯一的,那就返回这个长度就可以了,这个长度可能有很多字符串,找只出现一次的字符串,否则,找长度较短的。然后找到唯一的以后,还有一种可能,
这个较短是比较长的里面的子串,必须进行check。(我这里才想起来,比它长度长的,每个字符串至少出现2次,通过set去重,可以减少比较的次数,我没有进行这个优化)。然后就可以过了。
然后先按照长度串起来。
int f[];
class Solution {
public: int fd(int x) {
if(x == f[x]) return x;
return f[x] = fd(f[x]);
}
int findCircleNum(vector<vector<int>>& a) {
int n = a.size();
int res = n;
for (int i = ; i <= n; i++) f[i] = i;
for (int i = ; i < n; i++) {
for (int j = ; j < n; j++) {
if(a[i][j] == ) {
int x = fd(i), y = fd(j);
if(x != y) {
res--;
f[x] = y;
}
}
}
}
return res;
}
};
3. 547. Friend Circles
刚开始以为是连通分量,准备用dfs扫呢,突然发现邻接关系不是很好,然后转一思考,这不是并查集么,然后就欢快的写代码了。
最开始的链接里面有dsu(disjoint, find and union), dfs or bfs, floyd-warshall的解法。
class Solution {
public:
bool check(string &a, string & b) {
int n = a.size(), m = b.size();
int i, j;
i = j = ;
while(i < n && j < m) {
if(a[i] == b[j]) {
i++; j++;
} else {
i++;
}
}
return j == m;
}
int findLUSlength(vector<string>& s) {
int n = s.size();
if(n == ) return -;
if(n == ) return s[].size();
vector<string> a[];
for (string t : s) {
a[t.size()].push_back(t);
}
int res = ;
for (int i = ; i >= ; i--) {
if(a[i].size() == ) continue;
map<string, int> ma;
for (string t : a[i])
ma[t]++;
for (string t : a[i]) {
if(ma[t] == ) {
bool f = ;
for (int j = i + ; j <= ; j++) {
for (string d : a[j]) {
bool td = check(d, t);
if(td) {
f = ; break;
}
}
if(!f) break;
}
if(f) return i;
}
}
}
return -;
}
};
4. 548. Split Array with Equal Sum
看到这道题,是有点想法的,因为我见过,但是那时候不知道怎么做。其实不知道怎么做的原因有:1.题目不给数据范围,那就很尴尬啊,我得猜,怎么才能过,那时候只有半小时,没写代码,只是大概思考了一下怎么做,其实是帮别人做的。-w-.
看到数据范围2000,然后所有数据和还不会爆int,然后n^2的解法肯定是可以过的,那就大胆的写了。
显然,要求区间和,然后利用前缀和维护,这个预处理是必须的,然后可以O(1)的得到任意区间的长度。
然后,题意是去掉3个数,使得每一部分都相等,显然,数组长度至少为7,这得考虑清楚。然后考虑中间的那个需要去掉的数(为什么需要这么考虑,这里其实是有套路的,叫做meet in the middle, 叫做中间相遇攻击之类的),然后依次考虑每一边。
然后也是有问题,对于左边的每一次分割,我都要遍历右边么?这显然会导致n^3的复杂度,我就考虑把左右结果用set存下来,看看有没有相等的,有的话,就是满足的,没有的话,再次枚举。这样,复杂度降到logn。总的复杂度是n^2logn。
int s[];
class Solution {
public: int f(int x, int y) {
return s[y + ] - s[x];
}
bool splitArray(vector<int>& nums) {
int n = nums.size();
if(n < ) return ;
s[] = ;
for (int i = ; i <= n; i++) {
s[i] = nums[i - ] + s[i - ];
}
for (int i = ; i < n - ; i++) {
set<int> se;
for (int x = ; x < i - ; x++) {
if(f(, x - ) == f(x + , i - )) {
se.insert(f(, x - ));
}
}
if(se.size() == ) continue;
for (int x = i + ; x < n - ; x++) {
if(f(i + , x - ) == f(x + , n - )) {
if(se.count(f(i + , x - )))
//cout << f(i + 1, x - 1);
return ;
}
}
}
return ; }
};
其实这个题目是我同学报阿里内推的时候测试的题目,我那时候没有做出来。
我那时候的题目,就是utf-8的转化,跟leetcode 的uff-8 valied差不多,我没做出来。我还是有原因的:1.不给样例,到做完题目我都没搞懂什么意思。 2. 不给数据范围,长度是多少,根本不知道。我感觉都是靠我自己瞎猜的,看自己理解的对不对。
更滑稽的是:后来阿里面试的时候,面到一道题目,是varint,(我不懂是什么),题目描述,有一些数,比如long long,64位,但是经常出现几千,几万的数,很大的数比较少,然后要求你压缩一下,能不能节省空间。我没想法,没有做出来。后来一查,就是前面这个uft-8的题目,用每个byte的最高位标记是否还有更多的byte,是1的话,下一byte也是这个数的一部分,0的话,代表此数结束。然后代价是:大的数需要比它原本的占用空间要多。看完题解,我恍然大悟,这不就是测试的时候,那道题目么!
最新文章
- jQ选择器学习片段(JavaScript 部分对应)
- 安装eclipse与pydev
- 【PHP编程之路-1】设置apache虚拟目录
- Fundamentals of speech signal processing
- Android Studio导入Project的方法
- hive到hbase的使用
- kthread_stop引起的OOP
- bzoj1934: [Shoi2007]Vote 善意的投票
- Class.forName的作用以及为什么要用它【转】
- JavaScript DOM编程艺术第一章:JavaScript简史
- css+js自动化开发之第十五天
- windows已安装solr
- python3基础(二)
- ASP.NET没有魔法——ASP.NET MVC Razor与View渲染
- 查询SQLSERVER执行过的SQL记录(历史查询记录)
- Devexpress中文语言包汉化
- WIN10在loadrunner安装或path4插件安装时遇到的管理员阻止程序运行---解决方案(可用)
- 成功清除 windows2008 内部版本7601 字眼
- 20 模块之 re subprocess
- IOS AES加密之ECB128模式