package com.demo.s33;

/**
 * 搜索旋转排序数组
 * 整数数组 nums 按升序排列，数组中的值 互不相同 。
 *
 * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
 *
 * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
 *
 * 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/search-in-rotated-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int search(int[] nums, int target) {
        //数组大小判断
        if(nums.length == 0) {
            return -1;
        }
        //只有一个值情况判断
        if(nums.length == 1) {
            if(nums[0] == target) {
                return 0;
            }
            return -1;
        }

        int i = 0;
        int j = nums.length - 1;
        int mid = 0;
        //二分法 左右边界和中间值
        while(i <= j) {
            mid = (i + j) /2;
            //如果中间值 就是target 则返回mid
            if(nums[mid] == target) {
                return mid;
            }
            //如果0 ~mid 为上升，则mid在左升区间
            if(nums[0] <= nums[mid]) {
                //如果 target 在i ~ mid之间
                if(nums[i] <= target && target < nums[mid]) {
                    j = mid - 1;
                } else {
                    // target 在mid ~ j之间
                    i = mid + 1;
                }
                //如果0 ~mid 为下降，则mid在右降区间
            } else {
                //如果 target 在i ~ mid之间
                if(nums[mid] < target && target <= nums[nums.length - 1]) {
                    i = mid + 1;
                } else {
                    j = mid -1 ;
                }
            }
        }
        return -1;
    }
}

package com.demo.s322;

/**
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 *
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 *
 * 你可以认为每种硬币的数量是无限的。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/coin-change
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }
        return coinChange(coins, amount, new int[amount]);
    }

    int coinChange(int[] coins, int rem, int[] count) {
        if(rem < 0) {
            return -1;
        }

        if(rem ==0) {
            return 0;
        }

        if (count[rem - 1] != 0) {
            return count[rem - 1];
        }
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = coinChange(coins, rem - coin, count);
            if (res >= 0 && res < min) {
                min = 1 + res;
            }
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];

    }


}

package com.demo.s32;

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

/**
 * 最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 */
public class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        //新建一个栈 用来从左到右存括号字符串
        Deque<Integer> stack = new LinkedList<Integer>();
        //压一个初始长度-1
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            //如果是左括号 就压栈
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                //右括号就弹出
                stack.pop();
                //弹出后如果空了就压当前i的值，表示有效子串开始的位置
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    //不为空就比较下 有效子串是否为最长 ，更新maxans
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;

    }
}

package com.demo.s31;

/**
 * 下一个排列
 * 整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。
 *
 * 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
 * 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
 *
 * 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
 * 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
 * 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
 * 给你一个整数数组 nums ，找出 nums 的下一个排列。
 *
 * 必须 原地 修改，只允许使用额外常数空间。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/next-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public void nextPermutation(int[] nums) {

        int i = nums.length - 2;
        //从右到左找出开始递增的位置  1612354 中 3 就是
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        //如果找到了，再从右到左找出第一个大于nums[i]的值  1612354 中 4 就是
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            //交换两个数字位置 1612453
            swap(nums, i, j);
        }
        //翻转 i + 1 到 结束 也就是  53 变成 35
        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--;
        }
    }

}

package com.demo.s300;


/**
 *给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 *
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-increasing-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
public int lengthOfLIS(int[] nums) {
        if(nums.length == 0) {
        return 0;
        }
        int size = 1;
        //严格递增子序列数组
        int[] sub = new int[nums.length+1];
        //初始化第0个节点
        sub[size] = nums[0];
        int pos = 0;
        //遍历数组nums
        for(int i= 1; i< nums.length; i++) {
        //前一个小于后一个节点时，记录到sub数组
        if(sub[size] < nums[i]) {
        sub[++size] = nums[i];
        } else {
        //重置sub数组，分左右两个指针判断
        int l = 1;
        int r = size;
        //如果sub中找不到比nums[i]小的元素则从0开始替换
        pos = 0;
        //移动两边指针
        while(l <= r) {
        //取中间点
        int mid = (l + r) >> 1;
        //因为sub已经有序，所以二分法，找到满足升序的中间点pos，更新sub数组
        if(sub[mid] <  nums[i]) {
        l = mid + 1;
        pos = mid;
        } else {
        r = mid - 1;
        }
        }
        //更新sub数组
        sub[pos + 1] = nums[i];
        }
        }
        return size;
        }

        }

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;
    }
}