package com.demo.s30;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 串联所有单词的子串
 * 给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
 *
 * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/substring-with-concatenation-of-all-words
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) return res;
        HashMap<String, Integer> map = new HashMap<>();
        int one_word = words[0].length();
        int word_num = words.length;
        int all_len = one_word * word_num;
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        for (int i = 0; i < s.length() - all_len + 1; i++) {
            String tmp = s.substring(i, i + all_len);
            HashMap<String, Integer> tmp_map = new HashMap<>();
            for (int j = 0; j < all_len; j += one_word) {
                String w = tmp.substring(j, j + one_word);
                tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1);
            }
            if (map.equals(tmp_map)) res.add(i);
        }
        return res;
    }
}

package com.demo.s3;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 */
public class Solution {

    public int lengthOfLongestSubstring(String s) {
        //字符串 字符数组
        char[] chars = s.toCharArray();
        //游标 子串
        int start = 0;
        //子串最大长度
        int max = 0;
        //出现字符 及对应的下标<字符， 最近一次出现的下标>
        Map<Character, Integer> cs = new HashMap<>();
        for(int i= 0; i < chars.length; i++) {
            //子串中字符上次出现位置
            Integer lastExist = cs.get(chars[i]);
            //如果已经出现过该字符且在子串中
            if(lastExist!=null && lastExist >= start) {
                // 则从字符出现重复后端下一个位置开始
                start = lastExist + 1;
                //如果字符长度大于目前记录的最大长度
            } else if(i - start + 1 > max) {
                //则更新最大长度记录
                max = i - start + 1;
            }
            //每次遍历把字符 及出现的下标记录下来
            cs.put(chars[i], i);
        }
        return max;
    }

    public static void main(String[] args) {

    }
}

package com.demo.s29;

/**
 * 两数相除
 * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 *
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 *
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/divide-two-integers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int divide(int dividend, int divisor) {

        if (dividend == -2147483648 && divisor == -1) return 2147483647;
        if (dividend == 2147483647 && divisor == 1) return 2147483647;
        // 对两种特殊情况的快速处理，大概算是偷鸡了吧
        int result = 0;
        boolean isNeg = (dividend < 0 ^ divisor < 0); // 异或运算确定结果正负性
        dividend = -Math.abs(dividend);
        divisor = -Math.abs(divisor);
        // 使用绝对值再取负，全部转化为负数进行运算
        // 特别的，在int范围内，-2147483648的正负数都是其自身，因此不会出错
        while (dividend <= divisor) {
            int d = divisor; // d为本轮所用的除数
            int cnt = 1; // cnt表示d为原除数的cnt倍
            while (dividend <= d && d >= -1073741824) {
                // 每次对d和cnt都进行翻倍，快速到达大于被除数的最小除数
                // 等效d=d*2，但题目禁用乘法，且位运算左移速度更快
                d = d << 1;
                cnt = cnt << 1;
            }
            // 当 dividend > d 时，表明此时d已经小于被除数了，不能继续
            // 当 d < -1073741824 时，表明此时d再翻倍会造成溢出，不能继续

            if (dividend <= d) {
                // 此时说明上一步d再翻倍会造成溢出
                // 可知d已经是大于被除数的最小除数，直接使用即可
                dividend -= d;
                result += cnt;
            } else {
                // 此时d是小于被除数的最大除数，需要右移补回一次
                // 才能成为大于被除数的最小除数，再进行使用
                dividend -= d >> 1;
                result += cnt >> 1;
            }
        }
        return isNeg ? -result : result;
        // result为所有倍数的和，需要补充正负性再返回

    }
}

package com.demo.s28;

/**
 * 移除元素
 * 实现 strStr()
 * 实现 strStr() 函数。
 *
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。
 *
 * 说明：
 *
 * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 *
 * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/implement-strstr
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;

    }
}

package com.demo.s27;

/**
 * 移除元素
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 *
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
 *
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
 *
 *  
 *
 * 说明:
 *
 * 为什么返回数值是整数，但输出的答案是数组呢?
 *
 * 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
 *
 * 你可以想象内部操作如下:
 *
 * // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
 * int len = removeElement(nums, val);
 *
 * // 在函数里修改输入数组对于调用者是可见的。
 * // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
 * for (int i = 0; i < len; i++) {
 *     print(nums[i]);
 * }
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/remove-element
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
}

package com.demo.s26;

/**
 *  删除有序数组中的重复项
 *  给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
 *
 * 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
 *
 * 将最终结果插入 nums 的前 k 个位置后返回 k 。
 *
 * 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 *
 * 判题标准:
 *
 * 系统会用下面的代码来测试你的题解:
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }

}

package com.demo.s25;

import java.util.ArrayList;
import java.util.List;

/**
 * K 个一组翻转链表
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 *
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 *
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/reverse-nodes-in-k-group
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    // 定一个数据结构，存放链表 分组
    class Pharse {
        //链表开始节点
        ListNode begin;
        //链表开始节点
        ListNode end;
        //链表是否需要翻转
        boolean reverse;

        public Pharse(ListNode begin, ListNode end, boolean reverse) {
            this.begin = begin;
            this.end = end;
            this.reverse = reverse;
        }

        public void reverseSubGroup() {
            //前置节点都未null
            ListNode pre = null;
            //当前节点为begin
            ListNode cur = begin;
            //开始翻转
            while(true) {
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                //需要判断翻转结束条件
                if(cur == end || tmp == null){
                    break;
                } else {
                    cur = tmp;
                }
            }
            //转向后给出新的交换后的 begin end
            ListNode tmp = begin;
            begin = end;
            end = tmp;
        }
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        //判断入参
        if(k == 1) {
            //一个元素直接返回
            return head;
        }
        //哑巴节点，标记头结点
        ListNode pre = new ListNode(0);
        //当前节点从head开始
        ListNode cur = head;
        //开始位置
        boolean flag = false;
        //链表分组
        List<Pharse> pharses = new ArrayList<>();
        //链表开始
        ListNode start = null;
        //链表结束
        ListNode end = null;
        //开始分组
        for(int i = 0; cur != null; i++) {
            //k个元素 开始的位置
            if(i % k == 0 && !flag) {
                start = cur;
                flag = true;
                //区间就一个元素了，开始即是结束
                if(cur.next == null) {
                    end = cur;
                    pharses.add(new Pharse(start, end, false));
                }
                //k个元素后 结束的位置
            } else if((i + 1) % k == 0 && flag) {
                end = cur;
                flag = false;
                pharses.add(new Pharse(start, end, true));
                //区间没有满k个元素，提前结束
            } else if(cur.next == null) {
                end = cur;
                pharses.add(new Pharse(start, end, false));
            }
            //下一个元素
            cur = cur.next;
        }
        ListNode ph = pre;
        for(Pharse pharse : pharses) {
            if(pharse.reverse) {
                //每个区间内翻转
                pharse.reverseSubGroup();
            }
            //多个区间指针反向修改
            ph.next = pharse.begin;
            ph = pharse.end;
        }

        return pre.next;

    }
}

package com.demo.s24;

/**
 * 两两交换链表中的节点
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
 *
 */

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {

    public ListNode swapPairs(ListNode head) {
        //新建哑巴节点，存放头结点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        //从哑巴节点开始 往后找到后两个节点
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;

            //交换节点
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummyHead.next;

    }
}

package com.demo.s239;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 *
 * 返回 滑动窗口中的最大值 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sliding-window-maximum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                //非最大值出队列
                deque.pollLast();
            }
            //找到k个最大值 对应的下标放到队列中
            deque.offerLast(i);
        }
        //定义结果数组
        int[] ans = new int[n - k + 1];
        //前面找到的那个第一次窗口k个最大值 放入数组
        ans[0] = nums[deque.peekFirst()];
        //继续遍历数组
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            //如果超过当前窗口范围 移出窗口
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            //把窗口最后一次的最大值放到结果数组中
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }

}

package com.demo.s236;


/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 *
 * 图示两个链表在节点 c1 开始相交：
 *
 *
 *
 * 题目数据 保证 整个链式结构中不存在环。
 *
 * 注意，函数返回结果后，链表必须 保持其原始结构 。
 *
 * 自定义评测：
 *
 * 评测系统 的输入如下（你设计的程序 不适用 此输入）：
 *
 * intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
 * listA - 第一个链表
 * listB - 第二个链表
 * skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
 * skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
 * 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/intersection-of-two-linked-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class Solution {
}