「日更刷题」第一周,链表和哈希表(三)

简介: 「日更刷题」第一周,链表和哈希表

剑指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积分,真的是出师不利

目录
相关文章
|
2月前
|
存储 缓存
【每日一题Day336】LC146最近最少使用缓存 | 哈希表+链表
【每日一题Day336】LC146最近最少使用缓存 | 哈希表+链表
22 0
|
2月前
|
索引
【每日一题Day281】LC142链表 Ⅱ| 快慢指针 哈希表
【每日一题Day281】LC142链表 Ⅱ| 快慢指针 哈希表
10 0
|
2月前
|
存储 索引
【每日一题Day280】LC141环形链表 | 快慢指针 哈希表
【每日一题Day280】LC141环形链表 | 快慢指针 哈希表
14 0
|
2月前
【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和
【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和
14 0
|
3月前
|
存储 算法 Python
python算法(二)—栈、队列、链表、哈希
python算法(二)—栈、队列、链表、哈希
41 0
|
7月前
|
机器学习/深度学习 存储 Cloud Native
817. 链表组件:哈希表+flag
这是 力扣上的 817. 链表组件,难度为 中等。
|
9月前
LeetCode剑指 Offer 35—复杂链表的复制(哈希表/递归)
LeetCode剑指 Offer 35—复杂链表的复制(哈希表/递归)
复杂链表的复制(剑指offer35 力扣138)java哈希表/原地拼接
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
|
索引
力扣142 - 环形链表||【二重双指针+哈希表】
灵活运用双指针,带您一探环形链表的奥秘
72 0
力扣142 - 环形链表||【二重双指针+哈希表】
|
1月前
【Leetcode 2487】从链表中移除节点 —— 单调栈
解题思路:维持一个单调递增栈,当栈为空时,记录当前节点为头节点;否则当前节点为栈顶节点的后继节点