package com.demo.s46;

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

/**
 * 全排列
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 */
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        //参数结果定义
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        //排列结果
        List<Integer> numbers = new ArrayList<Integer>();
        for (int n : nums) {
            //初始数组列表
            numbers.add(n);
        }
        //回溯 填空， 从 0 开始 填写  numbers.size() 个数字，结果写到 ret
        backtrack(numbers, ret, numbers.size(), 0);

        return ret;

    }

    /**
     * 回溯
     */
    public void backtrack(List<Integer> output, List<List<Integer>> res, int n, int try1) {
        //填完n个数后
        if (try1 == n) {
            //记录到res
            res.add(new ArrayList<Integer>(output));
        }
        for(int i = try1; i< n; i++) {
            //将i填写到try1位置
            Collections.swap(output, i, try1);
            //将i填写到try1 + 1位置
            backtrack(output, res, n, try1 + 1);
            //还原tray1位置的值，从i+1位置开始重新试填
            Collections.swap(output, try1, i);
        }
    }
}

package com.demo.s45;

/**
 * 跳跃游戏 II
 * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 *
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 *
 * 假设你总是可以到达数组的最后一个位置。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/jump-game-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;

    }
}

package com.demo.s44;

/**
 * 通配符匹配
 * 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
 *
 * '?' 可以匹配任何单个字符。
 * '*' 可以匹配任意字符串（包括空字符串）。
 * 两个字符串完全匹配才算匹配成功。
 *
 * 说明:
 *
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/wildcard-matching
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

package com.demo.s43;

/**
 * 字符串相乘
 * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
 *
 * 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/multiply-strings
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public String multiply(String num1, String num2) {
        //判断特殊值 0 的情况
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        //新建一个结果数据，存放临时结果
        int[] res = new int[num1.length() + num2.length()];
        //遍历字符串num1每个字符
        for (int i = num1.length() - 1; i >= 0; i--) {
            //转换成数字
            int n1 = num1.charAt(i) - '0';
            //遍历字符串num1每个字符
            for (int j = num2.length() - 1; j >= 0; j--) {
                //转换成数字
                int n2 = num2.charAt(j) - '0';
                //计算乘积
                int sum = (res[i + j + 1] + n1 * n2);
                //满10进1
                res[i + j + 1] = sum % 10;
                res[i + j] += sum / 10;
            }
        }
        //遍历结果数组 合并为字符串结果
        StringBuilder result = new StringBuilder();
        for(int i = 0;i < res.length;i++) {
            if(res[i] == 0 && result.length() == 0) {
                continue;
            } else {
                result.append(res[i]);
            }

        }

        return result.toString();

    }
}

package com.demo.s42;

/**
 * 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 */
public class Solution {
    public int trap(int[] height) {
        if(height.length == 0) {
            return 0;
        }
        //从左侧开始找最大值
        int[] maxLeft = new int[height.length];
        maxLeft[0] = height[0];
        for(int i = 1; i < height.length; i++) {
            maxLeft[i] = Math.max(maxLeft[i-1], height[i]);
        }
        //从右侧开始找最大值
        int[] maxRight = new int[height.length];
        maxRight[height.length -1] = height[height.length-1];
        for(int i = height.length-2; i >= 0; i--) {
            maxRight[i] = Math.max(maxRight[i + 1], height[i]);
        }

        int sum = 0;
        //统计所有雨水小矩形的大小
        for(int i = 0; i < height.length; i++) {
            //左右侧最大值的最小值累加
            sum += Math.min(maxLeft[i], maxRight[i]) - height[i];
        }
        return sum;
    }
}

package com.demo.s415;


/**
 *给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
 *
 * 你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/add-strings
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public String addStrings(String num1, String num2) {
        //字符串拼接 StringBuilder
        StringBuilder builder = new StringBuilder();
        int m = num1.length();
        int n = num2.length();
        //num1 遍历 下标
        int i =1;
        //num2 遍历 下标
        int j =1;
        int carray = 0;

        while(i + j <= m + n + 1) {
            int numa = 0;
            //补0对齐位数
            if(i > m) {
                numa = 0;
            } else {
                //字符转数字 从右向左 取值
                numa = num1.charAt(m - i++) - '0';
            }
            int numb = 0;
            //补0对齐位数
            if(j > n) {
                numb = 0;
            } else {
                //字符转数字 从右向左 取值
                numb = num2.charAt(n - j++) - '0';
            }
            //从右向左 逐位数字相加
            int sum = numa + numb + carray;
            //满10 进一位
            carray = sum / 10;
            builder.append(sum % 10);
        }
        //最后一次相加后 如果有进位 则拼接到字符串
        if(carray != 0) {
            builder.append(carray);
        }
        //翻转字符串
        return builder.reverse().toString();
    }
}

package com.demo.s41;

/**
 * 缺失的第一个正数
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 *
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 */
public class Solution {
    public int firstMissingPositive(int[] nums) {

        int n = nums.length;
        //处理下负的值，把对应的值改成一个大于n的数字，因为找第一个正数，所以n+1 后面遍历会被忽略掉
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        // 把存在于 0 -n 之间的值 填到对应的下标处 也变成负值（表示未缺失），后面统计正的数就可以了
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        //找到第一个>0 数字的下标就是 第一个缺失的正数了，因为上一步已经把存在的值标记到对应下标的位置了（负的值表示存在）
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
}

package com.demo.s40;

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

/**
 * 组合总和 II
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 *
 * 注意：解集不能包含重复的组合。 
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/combination-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    List<int[]> freq = new ArrayList<int[]>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> sequence = new ArrayList<Integer>();


    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int num : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
                freq.add(new int[]{num, 1});
            } else {
                ++freq.get(size - 1)[1];
            }
        }
        dfs(0, target);
        return ans;
    }

    public void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.add(new ArrayList<Integer>(sequence));
            return;
        }
        if (pos == freq.size() || rest < freq.get(pos)[0]) {
            return;
        }

        dfs(pos + 1, rest);

        int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
        for (int i = 1; i <= most; ++i) {
            sequence.add(freq.get(pos)[0]);
            dfs(pos + 1, rest - i * freq.get(pos)[0]);
        }
        for (int i = 1; i <= most; ++i) {
            sequence.remove(sequence.size() - 1);
        }
    }
}

package com.demo.s4;

/**
 * 寻找两个正序数组的中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 *
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            if(nums1.length > nums2.length) {
                return findMedianSortedArrays(nums2, nums1);
            }
            int m = nums1.length;
            int n = nums2.length;
            int left = 0;
            int right = m;
            // i + j = m-i + n -j -1  j = m+n+1/2 -i m<n
            int median1 = 0;
            int median2 = 0;
            while(left <= right) {
                int i = (left + right) / 2;
                int j = (m + n + 1) / 2 - i;
                int mediana1 = (i == 0 ? Integer.MIN_VALUE : nums1[i-1]);
                int mediana2 = (i == m ? Integer.MAX_VALUE : nums1[i]);
                int medianb1 = (j == 0 ? Integer.MIN_VALUE : nums2[j-1]);
                int medianb2 = (j == n ? Integer.MAX_VALUE : nums2[j]);
                if(mediana1 <= medianb2) {
                    median1 = Math.max(mediana1, medianb1);
                    median2 = Math.min(mediana2, medianb2);
                    left = i + 1;
                } else {
                    right  = i - 1;
                }
            }
            return ( m + n) %2==0? (median1 + median2) / 2.0 : median1;
        }

}

package com.demo.s39;

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

/**
 * 组合总和
 * 给你一个 无重复元素 的整数数组candidates 和一个目标整数target，找出candidates中可以使数字和为目标数target 的 所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 *
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 *
 * 对于给定的输入，保证和为target 的不同组合数少于 150 个。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/combination-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> combine = new ArrayList<Integer>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine));
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
        }
    }
}