1011打卡

1. 串联所有单词的子串（30）

 思想： 哈希表+滑动窗口

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
   int len = words.length;
        int wordlen = words[0].length();
        HashMap<String, Integer> map = new HashMap<>();
        ArrayList<Integer> res = new ArrayList<>();
        for (String word : words) {
            map.put(word,map.getOrDefault(word,0)+1);
        }

        for (int i = 0; i <s.length()-len*wordlen+1 ; i++) {
            HashMap<String, Integer> match = new HashMap<>();
            for (int j = i; j <i+len*wordlen ; j+=wordlen) {
                String word  =  s.substring(j,j+wordlen);
                if (!map.containsKey(word))break;
                match.put(word,match.getOrDefault(word,0)+1);
            }
            if (map.equals(match)){
                res.add(i);
            }
        }
        return res;
    }
}

2. 下一个排列（31）

class Solution {
    public void nextPermutation(int[] nums) {
   //数字找到左边升序右边降序的分界点，从右边找比他一点的较大数
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--; //找到第一个比nums[i]大的数
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);

    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }}

3. 最长有效括号（32）

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

class Solution {
    public int longestValidParentheses(String s) {
       Stack<Integer> stack = new Stack<>();
        int ans = 0;
        for (int i = 0,start = 0; i <s.length() ; i++) {
            if(s.charAt(i)=='(')
                stack.push(i);
            else {
                //是右括号
                if (!stack.isEmpty()){
                    //说明有左括号可以匹配
                    stack.pop();
                    if(stack.isEmpty()) {
                        ans = Math.max(i - start + 1, ans);
                    }else {
                        ans = Math.max(i-stack.peek(),ans);
                    }
                }else {
                    start = i+1;
                }
            }
        }
        return ans;
    }
}