基础知识
String StringBuilder 操作
public class StringOperation {
int startIndex;
int endIndex;
{
//初始容量为16个字符 主要做增删查改 索引包头不包尾
StringBuilder sb = new StringBuilder();
sb.append("str");
// 把原来index上的元素挪到新添加的元素位置后
sb.insert(1, "str");
sb.deleteCharAt(1);
sb.delete(1, 2);
sb.length();
sb.capacity();
sb.charAt(1);
// 找不到返回-1
sb.indexOf("char");
sb.indexOf("char", 1);
sb.lastIndexOf("str");
sb.lastIndexOf("str", 1);
sb.substring(1);
sb.substring(1,3);
sb.setCharAt(1,'c');
sb.reverse(); // String是final的，肯定没有reverse方法
sb.replace(1, 2, "str");
sb.toString();
}
{
// 做替换、大小写变换、分割、清除空格、字符数组互换
String str= new String();
String string= new String();
str.trim();
str.toLowerCase();
str.toUpperCase();
str.compareTo(string);
str.split(" ");
str.replace("old", "new");
str.replaceAll("%d","123");
str.substring(startIndex,endIndex);
str.substring(1);
List<Character> list = str.chars().mapToObj(c -> (char) c).collect(Collectors.toList());
str.chars().mapToObj(c -> (char) c).forEach(System.out::println);
Collections.frequency(list, 'a');
// 对字符串升序排列
char[] ar = str.toCharArray();
Arrays.sort(ar);
String str11 = String.valueOf(ar);
}
}LeetCode 20. 有效的括号
分析1.0
三种括号，22匹配，遇到左括号入栈，遇到右括号出栈
class Solution {
public boolean isValid(String s) {
HashMap map = new HashMap();
map.put(')','(');
map.put('}','{');
map.put(']','[');
ArrayDeque<Character> stack = new ArrayDeque();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i)==('(') || s.charAt(i)==('{') || s.charAt(i)==('[')){
stack.push(s.charAt(i));
}else if(s.charAt(i)==(')') || s.charAt(i)==('}') || s.charAt(i)==(']')){
if(stack.isEmpty()){
return false;
}else{
if(map.get(s.charAt(i)).equals(stack.pop())){
continue;
}else{
return false;
}
}
}
}
return stack.isEmpty() ? true : false;
}
}失误
Map、Stack这种容器里存放的都是封装类，比较相等时要使用equals，基本数据类型的比较使用==
return stack.isEmpty() ? true : false; 直接返回stack.isEmpty()就行
LeetCode 1047. 删除字符串中的所有相邻重复项
分析1.0
删除相邻重复项，删除之后索引总长度会改变
失误
我的思路是想再原来的String上操作，但这样是错误的，最后的结果应该是在Stack里头
class Solution {
public String removeDuplicates(String s) {
if(s == null || s.length() < 2){
return s;
}
//StringBuilder sb = new StringBuilder(s);
ArrayDeque<Character> stack = new ArrayDeque();
for(int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
if(stack.isEmpty()){
stack.push(ch);
continue;
}
if(ch == stack.peek()){
stack.pop();
//sb.deleteCharAt(i); // delete后sb长度改变
}else{
stack.push(ch);
}
}
StringBuilder res = new StringBuilder();
while(!stack.isEmpty()){
res.append(stack.pop());
}
return res.reverse().toString();
}
}这种拼接还挺有意思的 省了reverse
while (!deque.isEmpty()) {
str = deque.pop() + str;
}LeetCode 150. 逆波兰表达式求值
分析1.0
逆波兰表达式（后缀表达式）主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
思路
① 如何识别算符和数字 ② 延伸 0-9的ascll字符如何比较大小、实现 char 与 int 转换（这种时候可以打印日志 | 判断元素类型）③ 单个字符如何实现String 与 char 转换 charAt() toCharArray()
失误
// char ch = tokens[i].charAt(0); 两位数就完犊子了 数字字符可能有多位，而算符只能是一位
分析2.0
class Solution {
public int evalRPN(String[] tokens) {
ArrayDeque<Integer> stack = new ArrayDeque();
for(int i = 0; i < tokens.length; i++){
// char ch = tokens[i].charAt(0); 两位数就完犊子了
String str = tokens[i];
if(str.equals("+")){
stack.push(stack.pop() + stack.pop());
}else if(str.equals("-")){
stack.push(0 - stack.pop() + stack.pop());
}else if(str.equals("*")){
stack.push(stack.pop() * stack.pop());
}else if(str.equals("/")){
int a = stack.pop();
stack.push(stack.pop() / a);
}else{
stack.push(Integer.parseInt(str));
}
}
return stack.pop();
}
}总结
- Map、Stack这种容器里存放的都是封装类，比较相等时要使用equals，基本数据类型的比较使用==
22成对出现且涉及查找等相关操作时，注意使用Map或栈
匹配问题——栈、Map
栈能保存上一个访问过的元素
String.charAt(i)是一个char 不是一个String
char ch = tokens[i].charAt(0); 两位数就完犊子了 数字字符可能有多位，而算符只能是一位
ASCLL 字符阿拉伯数组的int值 int val = '9' - '0'
Integer.parseInt(s)是把字符串解析成int基本类型，Integer.valueOf(s)是把字符串解析成Integer对象类型。jdk规定，每次要创建一个value值在-128~127之间的Integer对象时，直接从缓存中拿到这个对象，所以value值相同的Integer对象都是对应缓存中同一个对象。-128~127之外的整数值用的不是太频繁，每次创建value值相同的Integer对象时，都是重新创建一个对象
常用变量名增量更新
size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end、flag、ch
