一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 1117|回复: 5
收起左侧

[Leetcode] 刷题心得:别人最高vote的最优解不一定好解释

[复制链接] |试试Instant~ |刷题, leetcode
我的人缘0

分享帖子到朋友圈
cvg | 显示全部楼层 |阅读模式
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   81% (49)
 
 
18% (11)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
https://leetcode.com/problems/re ... a-dfs-3-ms-solution
有感于这道题的DFS最优解。虽然非常棒。我觉得面试的时候很难短时间给面试官解释清楚

[C++] 纯文本查看 复制代码
class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> res;
        dfs(s, 0, 0, {'(', ')'}, res);
        return res;
    }
    
    void dfs(string s, int lastProStrPos, int lastRemPos, vector<char> p, vector<string>& res){
        int count=0;
        // start from the last processed string's position 
        for (int i=lastProStrPos; i<s.size(); i++){
            if (s[i]==p[0])
                count++;
            else if (s[i]==p[1]){ 
                //Note how this is different the isValid function in BFS solution
                    count--;
            }
            
            // if there's no right parenthesis to remove, continue;
            if (count>=0)   
                continue;
            // j starts from the last removed position and iterating till i
            for (int j=lastRemPos; j<=i; j++){
                if (s[j]==p[1] && (j==lastRemPos || (j>0&&s[j]!=s[j-1]))){
                    dfs(s.substr(0,j)+s.substr(j+1), i, j, p, res);
                }
            }
            //Note this return! if it's not there, there will be errors
            return;
        }
        
        //reverse to remove the extra '('
        reverse(s.begin(), s.end());
        
        if (p[0]=='('){            
            dfs(s, 0, 0, {')','('}, res);
        }
        else
            res.push_back(s);
    }
};



相比之下BFS要清楚得多。有同感的朋友欢迎分享大米。

[C++] 纯文本查看 复制代码
//1. BFS use unordered_set to remove duplicates
class Solution {
public:
	vector<string> removeInvalidParentheses(string s) {
		queue<string> q;
		vector<string> res;
		//To filter out the duplicated new strings generated in the process of parenthesis removal
		unordered_set<string> visitedStrs;

		q.push(s);

		while (q.size()){
			auto oldStr = q.front();
			q.pop();

			if (visitedStrs.count(oldStr))
				continue;

			if (isValid(oldStr))
				res.push_back(oldStr);

			visitedStrs.insert(oldStr);

			if (res.empty()){
				for (int i = 0; i<oldStr.size(); i++){
					if (oldStr[i] == '(' || oldStr[i] == ')'){
						string newStr = oldStr.substr(0, i) + oldStr.substr(i + 1);
						q.push(newStr);

					}
				}
			}
		}

		return res;
	}

	bool isValid(string s){
		int left = 0;

		for (auto sc : s){
			if (sc == '(')
				left++;
			else if (sc == ')'){
				if (left <= 0)
					return false;
				else
					left--;
			}
		}

		return left == 0;
	}
};


//2. BFS Avoid generating duplicates
/*
We can speed up and get rid of the hash table by generating unique strings only. There are two types of duplicates. First is due to removing the same set of characters in different order. For example, "(()(()", remove 0th then 3rd or remove 3rd then 0th both generates "()()". So we can enforce an order by keeping the last removal index and remove after it only. The other is handling consecutive same chars, say, "(()". We get the same string by removing either the 0th or 1st '('. We can just remove the 0th.
*/
class Solution {
public:
	vector<string> removeInvalidParentheses(string s) {
		queue<pair<string, int>> q;
		vector<string> res;
		// push the last removed char's position with the string
		q.push(make_pair(s, 0));

		while (q.size()){
			auto element = q.front();
			auto oldStr = element.first;
			q.pop();

			int lastRemPos = element.second;

			if (isValid(oldStr))
				res.push_back(oldStr);
			else if (res.empty()){
				for (int i = lastRemPos; i<oldStr.size(); i++){
					if ((oldStr[i] == '(' || oldStr[i] == ')') && (i == lastRemPos || (i>0 && oldStr[i] != oldStr[i - 1]))){
						string newStr = oldStr.substr(0, i) + oldStr.substr(i + 1);
						q.push(make_pair(newStr, i));
					}
				}
			}
		}

		return res;
	}

	bool isValid(string s){
		int left = 0;

		for (auto sc : s){
			if (sc == '(')
				left++;
			else if (sc == ')'){
				if (left <= 0)
					return false;
				else
					left--;
			}
		}

		return left == 0;
	}
};


评分

参与人数 1大米 +3 收起 理由
codedayday + 3 给你点个赞!

查看全部评分


上一篇:428 LeetCode 求解一行代码
下一篇:出一个leetcode会员 2020年9月到期
我的人缘0
不要说话 2020-4-3 03:45:21 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (295)
 
 
0% (0)    👎
这道题是exponential time complexity 还是BFS直观容易理解 DFS不好写不说 面试的时候解释都解释不清楚
回复

使用道具 举报

我的人缘0
codedayday 2020-4-6 13:36:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (187)
 
 
10% (23)    👎
看到你这个题目,我就在猜它的题号是不是301题, 结果一查,竟然猜对了。。。。。 (我借助 video 来学习代码,所以听的遍数多了,就记住了:在youtube.com  里 用 huahua 301 就能搜到  https://www.youtube.com/watch?v=2k_rS_u6EBk&t=36s
赞同楼主说的,BFS 借助iteration 线性展开,符合人的直观思维。
DFS 结组  super problem -- sub problem的自我相似性,嵌套了 egg-chick-egg 的 折叠性思维,考验抽象思维。
所以比较好的是 开始前询问一下 出题人 期待什么样的解决方案。

If my post make you laugh, please 加米 给我啊 :)
回复

使用道具 举报

我的人缘0
 楼主| cvg 2020-4-7 08:05:47 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   81% (49)
 
 
18% (11)    👎
codedayday 发表于 2020-4-6 13:36
看到你这个题目,我就在猜它的题号是不是301题, 结果一查,竟然猜对了。。。。。 (我借助 video 来学习代 ...

请问怎么加米呢?谢谢

评分

参与人数 1大米 +3 收起 理由
codedayday + 3 每一个楼层的右下角有“评分”项,

查看全部评分

回复

使用道具 举报

我的人缘0
codedayday 2020-4-7 12:15:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (187)
 
 
10% (23)    👎
cvg 发表于 2020-4-7 08:05
请问怎么加米呢?谢谢
每一个楼层的右下角有“评分”项,
回复

使用道具 举报

我的人缘0
codedayday 2020-4-7 12:15:38 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   89% (187)
 
 
10% (23)    👎
cvg 发表于 2020-4-7 08:05
请问怎么加米呢?谢谢

每一个楼层的右下角有“评分”项,点击评分项目就可以送大米了 :)

评分

参与人数 1大米 +1 收起 理由
cvg + 1 给你点个赞!只能让加1, 不知道为啥

查看全部评分

回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (26)
 
 
7% (2)    👎
想请教大家 这个题bfs和dfs哪个更高效呢?我的理解是bfs和dfs其实都是相当于暴力搜索,所以应该时间复杂度差不多,不过楼主贴的那个最高票解里用到了一些剪枝 所以可能比bfs快一些,不知道理解对不对?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-5-30 19:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表