剑指Offer58-II.左旋转字符串
题目描述
网络异常，图片无法展示
|
解题思路
- 反转 0-n
- 反转 n-length
- 反转 0-length
代码展示
public String reverseLeftWords(String s, int n) { char[] chars = s.toCharArray(); int length = chars.length; int t = n; for (int i = 0; i < n; i++) { n--; char temp = chars[i]; chars[i] = chars[n]; chars[n] = temp; } for (int i = t; i < length; i++) { char temp = chars[i]; chars[i] = chars[length - 1]; chars[length - 1] = temp; length--; } length = chars.length; for (int i = 0; i < length; i++) { char temp = chars[i]; chars[i] = chars[length - 1]; chars[length - 1] = temp; length--; } return String.valueOf(chars); } 复制代码
提交结果
网络异常，图片无法展示
|
2022/9/3
28. 实现 strStr()
题目描述
网络异常，图片无法展示
|
解题思路
本体是采用了暴力破解的方式，但是这道题是 KMP算法的经典题目
在我的文章从 KMP算法到 Java的 String.indexOf(String str)方法 中介绍了KMP算法及其解题思路
代码展示
public static int strStr(String haystack, String needle) { char[] chars = haystack.toCharArray(); char[] chars1 = needle.toCharArray(); for (int i = 0; i < chars.length; i++) { int n = 0; int m = i; while(m < chars.length && n < chars1.length && chars[m] == chars1[n]){ m++; n++; } if (n == chars1.length && chars[m - 1] == chars1[n - 1]){ return i; } } return -1; } 复制代码
提交结果
网络异常，图片无法展示
|
459. 重复的子字符串
题目描述
网络异常，图片无法展示
|
解题思路
- 一样的，也是通过了KMP算法来做
代码展示
public boolean repeatedSubstringPattern(String s) { if (s.equals("")) return false; int len = s.length(); // 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了 s = " " + s; char[] chars = s.toCharArray(); int[] next = new int[len + 1]; // 构造 next 数组过程，j从0开始(空格)，i从2开始 for (int i = 2, j = 0; i <= len; i++) { // 匹配不成功，j回到前一位置 next 数组所对应的值 while (j > 0 && chars[i] != chars[j + 1]) j = next[j]; // 匹配成功，j往后移 if (chars[i] == chars[j + 1]) j++; // 更新 next 数组的值 next[i] = j; } // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值 if (next[len] > 0 && len % (len - next[len]) == 0) { return true; } return false; } 复制代码
提交结果
网络异常，图片无法展示
|
2022/9/4
232. 用栈实现队列
题目描述
网络异常，图片无法展示
|
解题思路
具体可以看我的文章 你有用过 java中的栈和队列吗？怎么用栈来实现队列呢
提交结果
网络异常，图片无法展示
|
225. 用队列实现栈
题目描述
网络异常，图片无法展示
|
解题思路
- 使用两个队列
- in队列模拟栈
- out队列保存临时数据
- 新增的时候，将数值存到 outQueue中
- 然后将 inQueue中的数据加入到 outQueue中
- 又将 outQueue赋值给 inQueue
代码展示
public class MyStack { Queue<Integer> inQueue ; Queue<Integer> outQueue ; public MyStack() { inQueue = new LinkedList<>(); outQueue = new LinkedList<>(); } public void push(int x) { outQueue.offer(x); while(!inQueue.isEmpty()){ outQueue.offer(inQueue.poll()); } Queue<Integer> temp ; temp = inQueue; inQueue = outQueue; outQueue = temp; } public int pop() { return inQueue.poll(); } public int top() { return inQueue.peek(); } public boolean empty() { return inQueue.isEmpty(); } } 复制代码
提交结果
网络异常，图片无法展示
|
20. 有效的括号
题目描述
网络异常，图片无法展示
|
解题思路
- 新建一个队列
- 遍历字符串
- 如果当前字符串为 左括号，则队列中存储右括号
- 如果当前字符串为 右括号，则判断当前队列是否为空，且队列首元素是否相等
- 弹出当前队列首元素
- 最后判断队列中是否还有值
- 有值则不匹配
这道题是完全借鉴了代码随想录，我自己写的方式和这个真的相差甚远，观感性太差了
代码展示
public boolean isValid(String s) { Deque<Character> deque = new LinkedList<>(); char ch; for (int i = 0; i < s.length(); i++) { ch = s.charAt(i); //碰到左括号，就把相应的右括号入栈 if (ch == '(') { deque.push(')'); }else if (ch == '{') { deque.push('}'); }else if (ch == '[') { deque.push(']'); // 栈为空或者栈顶元素与当前 ch不匹配，则返回 false } else if (deque.isEmpty() || deque.peek() != ch) { return false; }else { // 栈不为空，且栈顶元素与 ch一致 deque.pop(); } } //最后判断栈中元素是否匹配 return deque.isEmpty(); } 复制代码
提交结果
网络异常，图片无法展示
|
碎碎念
我都是先做的题目，最后统一总结的解题思路才发现，九月三号少做了一题，少了20积分，真的是出师不利
