[数据结构与算法]力扣day04

今天偷个懒

20、有效的括号

很简单，用个栈即可
正常一般都这样想

  public boolean isValid(String s) {
        char[] chars = s.toCharArray();
        Deque<Object> stack = new ArrayDeque<>();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(' || chars[i] == '[' || chars[i] == '{') {
                stack.push(chars[i]);
            } else {
                switch (chars[i]){
                    case ')':chars[i]='(';break;
                    case ']':chars[i]='[';break;
                    case '}':chars[i]='{';break;
                    default:break;
                }
                if (!stack.isEmpty()&&chars[i]==(char)stack.peek()) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if (stack.isEmpty())return true;
        else return false;
    }

题解大佬巧妙的解法：只存右括号，因为如果匹配那么下一个字符肯定等于栈顶。

class Solution {
    public boolean isValid(String s) {
     if(s.isEmpty())
            return true;
        Stack<Character> stack = new Stack<Character>();
        //利用栈先进后出 stack 局部变量
        //当stack 压栈不成功后 后进去的括号自动弹出来 循环一次弹出一次
        //c!=stack.pop() 取反 相等就自动弹栈 一直弹到没有说明对上了
        for(char c:s.toCharArray()){
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c=='[')
                stack.push(']');
            else if(stack.empty()||c!=stack.pop())
                return false;
        }
        //循环完了 如果是空说明正确了 否则false
        if(stack.empty())
            return true;
        return false;
    }
}

21.合并两个有序链表

很简单，直接上代码

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode();
        ListNode cur = l3;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return l3.next;   
    }

26. 删除有序数组中的重复项

快慢指针问题

    public int removeDuplicates(int[] nums) {
       int low=0,fast=1;
       while (fast< nums.length){
           //如果重复接着往下找
           if(nums[low]==nums[fast]){
               fast++;
           }else {
               //不重复则把后面的放在前面
               nums[++low]=nums[fast++];
           }
       }
       return low+1;
    }

27.移除元素

类似26，设置双指针

    public int removeElement(int[] nums, int val) {
        int high = nums.length - 1;
        for (int low = 0; low <= high; low++) {
            if (nums[low] == val) {
                //题目给出不用在乎排序
                swap(nums, low--, high--);
            }
        }
        return high + 1;
    }
    private void swap(int[] nums, int low, int high) {
        int tmp = nums[low];
        nums[low] = nums[high];
        nums[high] = tmp;
    }

28. 实现 strStr()

先根据题目去掉特殊情况，然后正常判断

 public int strStr(String haystack, String needle) {
       if ("".equals(needle)) {
            return 0;
        }
        if (!haystack.contains(needle)) {
            return -1;
        }
        if (haystack.length() == 1) {
            return 0;
        }
        for (int i = 0; i < haystack.length(); i++) {
            if (haystack.charAt(i) == needle.charAt(0)) {
                int n=0;
                while (n<needle.length()){
                    if(haystack.charAt(i+n)==needle.charAt(n)){
                        n++;
                    }else {
                        break;
                    }
                }
                if (n==needle.length()){
                    return i;
                }
            }
        }
        return 0;
    }

这这里我也没想到能这么快，复杂度是O(m*n)
题解是KMP算法
算法讲解视频：KMP算法

 // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;
        
        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }

        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }

        return -1;
    }