当前位置:网站首页>有效的括号字符串[贪心练习]
有效的括号字符串[贪心练习]
2022-07-30 17:00:00 【REN_林森】
前言
贪心最考察分析能力,且训练变通能力,往往不和经典的死知识点挂钩,而是寻找贪心点,再用代码把自己的想法实现。所以不能发呆,需稳步快想!
一、有效的括号字符串
二、寻找贪心点
package everyday.greed;
// 有效的括号字符串。
public class CheckValidString {
/* target:不要发呆!稳步快想。 采用一般的栈思想来括号匹配,碰到*号怎么办? 用数组+len实现栈,当碰到 ')' 时,取把 ‘*’ 号前面 ‘(' 变为 ’*‘ ,为什么这样做? 试想一下,此时的 ’*‘ 可变 ’)‘ ,也可变 '(' ,也可当作 空串,是局部信息不能做出正确判定的时候! 如果缺'(',留住*号后面让它变;如果缺右,留着*号后面让它变。空串同理。 贪心核心:把*留到最后,防止前期用错了,毕竟它是万能的,可左右不万能,先让固定括号匹配去对消左右括号。 */
public boolean checkValidString(String s) {
int[] sk = new int[100];
int len = 0;
for (char c : s.toCharArray()) {
if (c == '(') sk[len++] = 1;
if (c == '*') sk[len++] = 0;
if (c == ')') {
if (len == 0) return false;
// 寻找前面的 ’(‘ 号
int i = len - 1;
while (i >= 0 && sk[i] != 1) --i;
if (i >= 0) sk[i] = 0;// 将左括号变星号。
len--;
}
}
// 拿到全局信息,可以来做正确的判定了。
// 看看后面的 星号 是否能足够填充前面的 左括号。
int m = 0;// 代表后面星号的个数。注:这里其实有以前练习的抽象思想,我们不关心这一个个号,我们关心这一组符号有多少,将数量m抽象出来。
for (int i = len - 1; i >= 0; i--) {
if (sk[i] == 1 && m == 0) return false;
if (sk[i] == 0) ++m;
else --m;
}
return true;
}
}
总结
1)练习贪心问题,可锻炼分析能力,数据结构巧妙运用能力。
2)不要发呆,稳步快想!
3)训练抽象能力,否则不能巧妙的将现实问题转化为代码,或者说很难转换。转换问题(配合数据结构&算法&循环分支&抽象能力)是解决问题的大方向之一,还有一类就是复杂性比较高,需要有拆解问题的能力,再联系相关知识点进行组合。
4)总的来说,就是抽象派 & 复杂组件派,对应抽象能力 & 知识点组合协调能力。
参考文献
边栏推荐
猜你喜欢
随机推荐
How does the new retail saas applet explore the way to break the digital store?
huato hot update environment construction (DLL method hot update C# code)
中文字符集编码Unicode ,gb2312 , cp936 ,GBK,GB18030
为人处世之道,与君共勉!
新零售saas小程序如何探索数字化门店的破局之路?
深度学习区分不同种类的图片
简易的命令行入门教程
HUAWEI CLOUD data governance production line DataArts, let "data 'wisdom' speak"
探究CSAPP实验二-bomb lab-第一节
Rounding out the most practical way of several DLL injection
华为云数据治理生产线DataArts,让“数据'慧'说话”
FP6606CMP5 CPC-16L USB类型-C和PD充电控制器 百盛电子代理商
DTSE Tech Talk丨第2期:1小时深度解读SaaS应用系统设计
Tensorflow中实现正则化
LeetCode167:有序数组两数之和
查询表中开始日期与结束日期
第六章:决胜秋招
大厂面试官眼中的好简历到底长啥样
Mongoose模块
olap——入门ClickHouse