package com.demo.s5;

/**
 * 最长回文子串
 */
public class Solution {
    public String longestPalindrome(String s) {
        //定义回文子串的起始
        int start = 0;
        int end = 0;
        //遍历字符串字符
        for(int i = 0; i< s.length(); i++) {
            //以当前字符为中心点扩展
            int len1 = expandAroundCenter(s, i, i);
            //以当前字符和下一个字符为中心点扩展
            int len2 = expandAroundCenter(s, i, i + 1);
            //取两种方式扩展最大长度
            int max = Math.max(len1, len2);
            if(max > end -start + 1) {
                //-1防止 当前字符和下一个字符为中心点扩展 导致的问题
                start = i - (max-1) / 2;
                end = i + max /2;
            }
        }
        return s.substring(start,  end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        //左右相等则扩展
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left --;
            right ++;
        }
        //返回扩展的子串长度
        return right - left -1;
    }
}

package com.demo.s49;

import java.util.*;

/**
 * 字母异位词分组
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 *
 * 字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/group-anagrams
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

package com.demo.s48;

/**
 *  旋转图像
 *  给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
 *
 * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/rotate-image
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public void rotate(int[][] matrix) {
        if(matrix.length == 0 || matrix.length != matrix[0].length) {
            return;
        }
        int nums = matrix.length;
        for (int i = 0; i < nums; ++i){
            for (int j = 0; j < nums - i; ++j){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[nums - 1 - j][nums - 1 - i];
                matrix[nums - 1 - j][nums - 1 - i] = temp;
            }
        }
        for (int i = 0; i < (nums >> 1); ++i){
            for (int j = 0; j < nums; ++j){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[nums - 1 - i][j];
                matrix[nums - 1 - i][j] = temp;
            }
        }
    }
}

package com.demo.s470;


/**
 * 给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
 *
 * 你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。
 *
 * 每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/implement-rand10-using-rand7
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class SolBase {
    public int rand7() {
        return (int)(Math.random() * 10 % 7);
    }
}
public class Solution extends SolBase {

    //随机产生01
    private int random01() {
        int i = rand7();
        //通过4分割 123 -> 0 ;567 -> 1 如果刚好是4 就重来
        if(i< 4) {
            return 0;
        } else if( i > 4){
            return 1;
        } else {
            return random01();
        }
    }

    //随机10 通过4位二进制标识
    public int rand10() {
        int x = 0;
        //
        for(int i = 0; i < 4;i++) {
            int i1 = random01();
            int i2 = i1 << i; //左移i位
            x = x + i2;
        }
        //如果超出了 [1, 10] 重新来
        if(x>=1 && x<= 10) {
            return x;
        } else {
            return rand10();
        }
    }
}

package com.demo.s47;

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

/**
 * 全排列 II
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 */
public class Solution {
    boolean[] vis;
    public List<List<Integer>> permuteUnique(int[] nums) {
        //返回值
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        //对原数组排序
        Arrays.sort(nums);
        //从下标0开始 回溯nums 中间结果存perm， 最终结果放到ans
        backtrack(nums, ans, 0, perm);
        return ans;
    }
    //回溯法
    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            //回溯过得本地不再回溯
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            //第二次开始重置为false
            vis[i] = false;
            perm.remove(idx);
        }
    }


}

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