代码随想录学习笔记—字符串，栈与队列
四.字符串
1.[ 反转字符串](https://leetcode-cn.com/problems/reverse-string/)2.[反转字符串 II](https://leetcode-cn.com/problems/reverse-string-ii/)3.[剑指 Offer 05. 替换空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/)4.[翻转字符串里的单词](https://leetcode-cn.com/problems/reverse-words-in-a-string/)5.[剑指 Offer 58 - II. 左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)6.KMP 五.栈与队列
1.理论2.[用栈实现队列](https://leetcode-cn.com/problems/implement-queue-using-stacks/)3.[用队列实现栈](https://leetcode-cn.com/problems/implement-stack-using-queues/)4.[有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)5.[删除字符串中的所有相邻重复项](https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/)6.[逆波兰表达式求值](https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/)7.[滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/)8.[前 K 个高频元素](https://leetcode-cn.com/problems/top-k-frequent-elements/)
结合自身需求，主要偏重java
学习地址
前面部分请查看
代码随想录学习笔记—数组，链表，哈希表
class Solution {
public void reverseString(char[] s) {
for (int i = 0; i < s.length/2; i++) {
char temp;
temp=s[i];
s[i]=s[s.length-1-i];
s[s.length-1-i]=temp;
}
}
}
2.反转字符串 II
我的，太复杂了 不好
class Solution {
public String reverseStr(String s, int k) {
char[] chars=s.toCharArray();
for (int i = 0; i < chars.length; i+=2*k) {
if (i+k>chars.length-1) {
for (int l = i,r=chars.length-1; l < i+((chars.length-i)/2); l++,r--) {
char temp=chars[l];
chars[l]=chars[r];
chars[r]=temp;
}
break;
}
for (int l = i,r=i-1+k; l
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
// 1. 每隔 2k 个字符的前 k 个字符进行反转
for (int i = 0; i< ch.length; i += 2 * k) {
// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符 或正常情况。
if (i + k <= ch.length) {
reverse(ch, i, i + k -1);
continue;
}
// 3. 剩余字符少于 k 个，则将剩余字符全部反转
reverse(ch, i, ch.length - 1);
}
return new String(ch);
}
// 定义翻转函数
public void reverse(char[] ch, int i, int j) {
for (; i < j; i++, j--) {
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
}
}
3.剑指 Offer 05. 替换空格
//瞎搞
class Solution {
public String replaceSpace(String s) {
return s.replace(" ", "%20");
}
}
很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行 *** 作。
java字符串长度增加原理（体外话：本质，通过StringBuilder走中间过程，通过append方法实现）：String1=String1+String2;
class Solution {
public String replaceSpace(String s) {
//StringBuffer是线程安全的，而StringBuilder则没有实现线程安全功能，所以性能略高。
StringBuilder sb = new StringBuilder();
char[] chars = s.toCharArray();
int l= s.length(); //原来的长度
for (int i = 0; i < chars.length; i++) {
if (chars[i] == ' ') {
sb.append(" ");
}
}
if (sb.length() == 0 || s == null || s.length() == 0) {
return s;
}
s+=sb.toString();
chars = s.toCharArray();
int left=l-1;
int rigth=chars.length-1;
for (int i =l-1 ; i >= 0; i--) {
if (chars[i] ==' ') {
chars[rigth--]='0';
chars[rigth--]='2';
chars[rigth]='%';
}else {
chars[rigth]=chars[left];
}
rigth--;
left--;
}
return new String(chars);
}
}
class Solution {
public String replaceSpace(String s) {
//StringBuffer是线程安全的，而StringBuilder则没有实现线程安全功能，所以性能略高。
StringBuilder sb = new StringBuilder();
char[] chars = s.toCharArray();
int l= s.length();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == ' ') {
sb.append(" ");
}
}
if (sb.length() == 0 || s == null || s.length() == 0) {
return s;
}
s+=sb.toString();
chars = s.toCharArray();
int left=l-1;
int rigth=chars.length-1;
while(left>=0) {
if (chars[left] ==' ') {
chars[rigth--]='0';
chars[rigth--]='2';
chars[rigth]='%';
}else {
chars[rigth]=chars[left];
}
rigth--;
left--;
}
return new String(chars);
}
}
4.翻转字符串里的单词
class Solution {
public String reverseWords(String s) {
//trim()的作用是去掉字符串两端的多余的空格
s = s.trim();
String[] ss = s.split(" ");
s=new String();
for (int i = ss.length-1; i>=0; i--) {
//空格大量存在时 有的元素是空的。
if (!ss[i].equals("")) {
s+=ss[i];
System.out.println(s);
}
if(!ss[i].equals("") && i != 0){
s+=" ";
System.out.println(s);
}
}
return s;
}
}
class Solution {
public String reverseWords(String s) {
// System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
// 1.去除首尾以及中间多余空格
StringBuilder sb = removeSpace(s);
// 2.反转整个字符串
reverseString(sb, 0, sb.length() - 1);
// 3.反转各个单词
reverseEachWord(sb);
return sb.toString();
}
private StringBuilder removeSpace(String s) {
// System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') start++;
while (s.charAt(end) == ' ') end--;
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
// System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
return sb;
}
public void reverseString(StringBuilder sb, int start, int end) {
// System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
// System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
}
private void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}
5.剑指 Offer 58 - II. 左旋转字符串
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sBuilder =new StringBuilder();
for (int i = n; i < s.length(); i++) {
sBuilder.append(s.charAt(i));
}
for(int i = 0;i
6.KMP
前缀：包含第一个 不包含最后一个 的所有子串（有多个后缀最长相等前后缀 eg：
那么模式串 aabaaf 的前缀表（那么也就是next数组）是0 1 0 1 2 0
求next数组代码:
void getNext(int* next, const string& s){
int j = -1;
next[0] = j;
for(int i = 1; i < s.size(); i++) { // 注意i从1开始
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
j = next[j]; // 向前回退
}
if (s[i] == s[j + 1]) { // 找到相同的前后缀
j++;
}
next[i] = j; // 将j（前缀的长度）赋给next[i]
}
}
public void getNext(int[] next, String s){
int j = -1;
next[0] = j;
for (int i = 1; i=0 && s.charAt(i) != s.charAt(j+1)){
j=next[j];
}
if(s.charAt(i)==s.charAt(j+1)){
j++;
}
next[i] = j;
}
}
求next数组：1.初始化，2循环i，3. 不相同循环回退 相同j++ 最后赋值
class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() == 0) {
return 0;
}
int[] next=new int[needle.length()];
getNext(next, needle);
int j=-1;
for (int i = 0; i < haystack.length(); i++) {
while(j>=0&& haystack.charAt(i) != needle.charAt(j+1)) {
j=next[j];
}
if(haystack.charAt(i)==needle.charAt(j+1)){
j++;
}
if (j==needle.length()-1) {
return (i-needle.length()+1);
}
}
return -1;
}
public void getNext(int[] next, String s) {
int j=-1;
next[0]=j;
for(int i = 1 ;i=0&&s.charAt(i)!=s.charAt(j+1)) {
j=next[j];
}
if (s.charAt(i)==s.charAt(j+1)) {
j++;
}
next[i]=j;
}
}
}
public int strStr(String haystack, String needle) {
int m = needle.length();
// 当 needle 是空字符串时我们应当返回 0
if (m == 0) {
return 0;
}
int n = haystack.length();
if (n < m) {
return -1;
}
int i = 0;
int j = 0;
while (i < n - m + 1) {
// 找到首字母相等
while (i < n && haystack.charAt(i) != needle.charAt(j)) {
i++;
}
if (i == n) {// 没有首字母相等的
return -1;
}
// 遍历后续字符，判断是否相等
i++;
j++;
while (i < n && j < m && haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
}
if (j == m) {// 找到
return i - j;
} else {// 未找到
i -= j - 1;
j = 0;
}
}
return -1;
}
五.栈与队列
1.理论
public static void main(String[] args) {
//队列和栈 都可以用它
Deque deque = new ArrayDeque();
deque.add(1);
deque.add(2);
deque.add(3);
// 相当于 1 2 3
deque.addFirst(4); 4 1 2 3
int i =deque.getFirst(); 4
System.out.println(i);
i =deque.getLast(); 3
System.out.println(i);
i =deque.removeLast();3
System.out.println(i);
i =deque.getLast();2
System.out.println(i);
}
4
3
3
2
2.用栈实现队列
class MyQueue {
Deque stack_in = new ArrayDeque();
Deque stack_out = new ArrayDeque();
public MyQueue() {
}
public void push(int x) {
stack_in.addFirst(x);
}
public int pop() {
//一个空的队列不会调用 pop 或者 peek *** 作
if (stack_out.isEmpty()) {
while(!stack_in.isEmpty()) {
stack_out.addFirst(stack_in.removeFirst());
}
return stack_out.removeFirst();
}else {
return stack_out.removeFirst();
}
}
public int peek() {
if (stack_out.isEmpty()) {
while(!stack_in.isEmpty()) {
stack_out.addFirst(stack_in.removeFirst());
}
return stack_out.getFirst();
}else {
return stack_out.getFirst();
}
}
public boolean empty() {
return stack_in.isEmpty()&& stack_out.isEmpty();
}
}
3.用队列实现栈
Deque deque = new ArrayDeque();
public MyStack() {
}
public void push(int x) {
deque.addLast(x);
}
public int pop() {
for (int i = 0; i < deque.size()-1 ; i++) {
deque.addLast(deque.removeFirst());
}
return deque.removeFirst();
}
public int top() {
return deque.getLast();
}
public boolean empty() {
return deque.isEmpty();
}
4.有效的括号
class Solution {
public boolean isValid(String s) {
Stack stack = new Stack<>();
char[] chars = s.toCharArray();
for (char c : chars) {
if(c=='('||c== '{'||c=='['){
stack.push(c);
}else {
if(stack.empty()) return false;
if (c==')'&& stack.pop()!='(') return false;
if (c=='}'&& stack.pop()!='{') return false;
if (c==']'&& stack.pop()!='[') return false;
}
}
return stack.empty();
}
}
5.删除字符串中的所有相邻重复项
class Solution {
public String removeDuplicates(String s) {
Deque deque =new ArrayDeque();
StringBuffer stringBuffer = new StringBuffer();
for(int i = 0; i0; i--) {
stringBuffer.append(deque.removeLast());
}
return stringBuffer.toString();
}
}
6.逆波兰表达式求值
class Solution {
public static int evalRPN(String[] tokens) {
Deque deque = new ArrayDeque();
for (int i = 0; i < tokens.length; i++) {
if (tokens[i].equals("+") || tokens[i].equals("-") ||
tokens[i].equals("*") || tokens[i].equals("/")) {
int num=0;
int a = Integer.parseInt(deque.removeFirst());
int b = Integer.parseInt(deque.removeFirst());
if (tokens[i].equals("+")) {
num=b+a;
}else if (tokens[i].equals("-")) {
num=b-a;
}else if (tokens[i].equals("*") ) {
num=b*a;
}else if (tokens[i].equals("/")) {
//这里要注意 不是a/b哦
num=b/a;
}
deque.addFirst(String.valueOf(num));
}else {
deque.addFirst(tokens[i]);
}
}
return Integer.parseInt(deque.getFirst());
}
}
7.滑动窗口最大值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque deque =new ArrayDeque();
int[] res = new int[nums.length-k+1]; //一共窗口的次数
for (int right = 0; right < nums.length; right++) {
//进入队列
// 如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
// 直到，队列为空或当前考察元素小于新的队尾元素
while(!deque.isEmpty()&& nums[right]>=nums[deque.getLast()]) {
deque.removeLast();
}
// 存储元素下标
deque.addLast(right);
int left = right - k +1;
// 当队首元素的下标小于滑动窗口左侧边界left时
// 表示队首元素已经不再滑动窗口内，因此将其从队首移除
if (deque.getFirst() < left) {
deque.removeFirst();
}
// 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时
// 意味着窗口形成。此时，队首元素就是该窗口内的最大值
if (right +1 >= k) {
res[left] = nums[deque.getFirst()];
}
}
return res;
}
}
8.前 K 个高频元素
先用map统计 然后用优先队列统计前K个大的。 重点：优先队列统计前K个大
public int[] topKFrequent(int[] nums, int k) {
Map map =new HashMap();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i])+1);
}else {
map.put(nums[i], 1);
}
}
PriorityQueue queue =new PriorityQueue(new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return map.get(o1)-map.get(o2);
}
});
for (Integer key : map.keySet()) {
if (queue.size()
优先级队列PriorityQueue
我们都知道队列，队列的核心思想就是先进先出，这个优先级队列有点不太一样。优先级队列中，数据按关键词有序排列，插入新数据的时候，会自动插入到合适的位置保证队列有序。（顺序有两种形式：升序或者是降序）
优先级队列底层的数据结构其实是一颗二叉堆（一个完全二叉树）
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）