查看: 2324|回复: 19
收起左侧

亚麻OA 9月新题

  |只看干货
本楼: 👍   100% (6)
 
 
0% (0)   👎
全局: 👍   100% (8)
 
 
0% (0)    👎

2021(7-9月) 码农类General 硕士 全职@Amazon - 猎头 - 在线笔试  | WaitList | 在职跳槽

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

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

x
OA一道新题。 判断一个string是否Valid。条件1:在一个valid的string头尾加相同字母, 比如 AA 是valid 那么 BAAB就是valid。空是valid。
条件2:两个valid的string的concatenation是valid,比如AA和BB是valid,那么AABB就是valid。

例子: EABBA
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
.

求大神的解,求大米。给点大米不会扣你们的大米,我有大米会继续发之后的面经。谢谢各位。

评分

参与人数 13大米 +13 收起 理由
finding_alpha + 1 给你点个赞!
yansonghuang + 1 给你点个赞!
llh1996 + 1 很有用的信息!
abicuagb + 1 给你点个赞!
eshang + 1 给你点个赞!
拉拉的球 + 1 给你点个赞!
kechengchun + 1 很有用的信息!
naturalbeau + 1 很有用的信息!

查看全部评分


上一篇:doordash oa
下一篇:TuSimple OA
本楼: 👍   100% (8)
 
 
0% (0)   👎
全局: 👍   100% (13)
 
 
0% (0)    👎
这样子感觉就可以?
        public boolean isValid(String s) {
                Stack<Character> unPaired = new Stack<>();
                for (char c : s.toCharArray()) {
                        if (unPaired.peek() == c) {
                                unPaired.pop();
                        } else {
                                unPaired.add(c);
                        }
                }
                return unPaired.isEmpty();
        }
回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
flyest 发表于 2021-9-25 23:07
这样子感觉就可以?
        public boolean isValid(String s) {
                Stack unPaired = new Stack();

应该加上if (!unPaired.isEmpty() && unPaired.peek() == c)
回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
匿名者 发表于 2021-9-24 16:08
感谢您的详细解答。
我有个想法,如果我们每次仅仅比较s和stack.pop()是否相等(相等的话,stack.pop() ...

应该可以的,其实我发了贴之后也想到了这点,应该不需要去匹配最后一个因为如果a????a中间的问号都能匹配,那么这两个a最后都能匹配在一起。
我不确定的是这个算法的正确性或者有没有漏洞。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
input string 的长度范围是多少
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (56)
 
 
1% (1)    👎
valid base case 是空字符,然后收尾加相同字母或者concatenate两个相同字母都是valid。可以推断:
如果一个valid的string,在某个位置“去掉”两个相同字母,还会继续valid,因为这两个字母的左边两个,或者右边两个,或者一左一右都会是相同的。

思路:
先用一个指针 right 找到两个相同字母的位置,然后用两个指针 (left, right) 分别指向 “去掉” 的字母的左边和右边,然后每次检查 left 和 right 所在的字母是否相同,或者right 和 right + 1的字母是否相同。

时间复杂度 O(N),空间复杂度 O(1)
回复

使用道具 举报

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
应该可以用stack做。
如果一个字符串是合法的,那么s[i]的匹配字符会是s[i + 1]或者s[j],j > i + 1 && j < s.length()。
1. 如果s[i] == stack.top(),我们可以直接认为这两个是匹配的,可以直接消除掉。
2. 如果s[i] == s.back(),我们可以认为s[i]和s.back()匹配,消除它们。
3. 如果以上两种情况都不是,我们把s[i]存放在stack.
如果最后stack.size() > 0,那么就有不匹配的情况,这个不是一个valid string。

尝试证明为什么s[i] == stack.top() || s[i] == s.back()可以直接匹配。
1. a(a??a)a, 这种情况及时匹配了左边两个aa,右边两个aa也会匹配在一起,所以可以直接匹配左边的aa。
2. a(aa??)a,这种情况即使匹配了左边的aa,第三个aa和最后一个a也会匹配在一起,所以可以直接匹配左边的aa。
3. aa(????),左边两个aa就是在一起的,可以直接匹配。
4. a(??)a(????aa),原本第一个a和中间的a是一对,右边两个aa是一对,但我们可以把左边第一个a和最后一个a匹配掉,因为左边括号里的?是一个valid string,而中间的a和右边第二个a会包围着那4个?形成一个新的valid string,这种情况也是合法的。

不知道这种方式和推断是不是对的,有错的麻烦指出。
回复

使用道具 举报

地里的匿名用户
匿名用户-185  发表于 2021-9-25 01:51:13
本楼: 👍   0% (0)
 
 
0% (0)   👎
可不可以直接上Pattern.
回复

使用道具 举报

地里的匿名用户
匿名用户-46D  发表于 2021-9-25 04:08:10
本楼: 👍   0% (0)
 
 
0% (0)   👎
happywatercoder 发表于 2021-9-24 13:44
应该可以用stack做。
如果一个字符串是合法的,那么s的匹配字符会是s或者s[j],j > i + 1 && j < s.length ...

感谢您的详细解答。
我有个想法,如果我们每次仅仅比较s和stack.pop()是否相等(相等的话,stack.pop(),不相等的话,放到stack.push(s),最终检查stack.size() == 0),而不去比较s和s.back(),是不是也会产生相同的output呢?
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎
匿名者 发表于 2021-9-24 15:08
感谢您的详细解答。
我有个想法,如果我们每次仅仅比较s和stack.pop()是否相等(相等的话,stack.pop() ...

我也是这个解法,把知道对不对。
回复

使用道具 举报

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   91% (90)
 
 
8% (8)    👎
happywatercoder 发表于 2021-9-24 09:44
应该可以用stack做。
如果一个字符串是合法的,那么s的匹配字符会是s或者s[j],j > i + 1 && j < s.length ...

请问一下s.back()是啥?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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