字节算法题

字符串

无重复字符的最长子串（3）- 543

// https://leetcode.cn/problems/longest-substring-without-repeating-characters/
// 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度
// 输入: s = "abcabcbb"
// 输出: 3 
// 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3 
// 输入: s = "bbbbb"
// 输出: 1
// 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1
class Solution {
    // 滑动窗口
    public int lengthOfLongestSubstring(String s) {
        // 窗口的最大长度
        int maxLength = 0;
        // 窗口集合
        Set<Character> window = new HashSet<>();
        int left = 0;       // 窗口的左边界
        int right = 0;      // 窗口的右边界
        while (right < s.length()) {
            // 如果窗口中包含当前元素，说明出现了重复，
            // 把窗口最左端的给移除掉，直到窗口不包含当前元素即可
            while (window.contains(s.charAt(right))){
                window.remove(s.charAt(left));
                left++;
            }
            // 把当前元素添加到窗口中
            window.add(s.charAt(right));
            // 更新窗口的长度
            maxLength = Math.max(maxLength, right - left + 1);
            right++;
        }
        return maxLength;
    }
    // 使用队列
    public int lengthOfLongestSubstring2(String s) {
        // 创建队列
        Queue<Character> queue = new LinkedList<>();
        int maxLength = 0;
        for (char ch : s.toCharArray()) {
            // 如果队列中有重复的就把最先添加的字符给移除，
            // 直到队列中没有重复元素为止
            while (queue.contains(ch))
                queue.poll();
            // 把当前字符添加到队列中
            queue.add(ch);
            // 记录最大值
            maxLength = Math.max(maxLength, queue.size());
        }
        return maxLength;
    }
}

最长回文子串（5）- 188

// https://leetcode.cn/problems/longest-palindromic-substring/
// 给你一个字符串 s，找到 s 中最长的回文子串。
// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串
// 输入：s = "babad"
// 输出："bab"
// 解释："aba" 同样是符合题意的答案
// 输入：s = "cbbd"
// 输出："bb"
class Solution {
    // 暴力解法：时间复杂度：两层for循环O(n²），for循环里边判断是否为回文O(n），所以时间复杂度为O(n³）
    // 空间复杂度：O(1），常数个变量
    public String longestPalindrome(String s) {
        String ans = "";
        int max = 0;
        int len = s.length();
        for (int i = 0; i < len; i++)
            for (int j = i + 1; j <= len; j++) {
                String test = s.substring(i, j);
                if (isPalindromic(test) && test.length() > max) {
                    ans = s.substring(i, j);
                    max = Math.max(max, ans.length());
                }
            }
        return ans;
    }
    public boolean isPalindromic(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }
}

22222 最长回文串（409）- 6

// https://leetcode.cn/problems/longest-palindrome/
// 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
// 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串
// 输入:s = "abccccdd"
// 输出:7
// 解释:
// 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7
// 输入:s = "a"
// 输入:1
class Solution {
    public static int longestPalindrome(String s) {
        int res = 0;
        // set存放字符个数为奇数的字符
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 若字符在集合中存在，则删除集合中的元素，同时不向集合中添加该元素（表明该元素的个数为偶数）
            if (!set.remove(c)) {
                set.add(c);
            }
        }
        // set.size() == 0表示整个字符串都是回文字符串
        // s.length() - set.size() + 1表示剔除奇数个字符后，所有偶数字符的个数，最后加上一个奇数字符放最中间
        return set.size() == 0 ? s.length() : s.length() - set.size() + 1;
    }
}

字符串相加（415）- 148

// https://leetcode.cn/problems/add-strings/
// 给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
// 你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
// 输入：num1 = "11", num2 = "123"
// 输出："134"
// 输入：num1 = "456", num2 = "77"
// 输出："533"
class Solution {
    public String addStrings(String num1, String num2) {
        // 指针i指向num1的末尾
        int i = num1.length() - 1;
        // 指针j指向num2的末尾
        int j = num2.length() - 1;
        // add 维护当前是否有进位
        int add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            // 获取num1第i位置上的字符，通过-'0'，转换为int
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            // ans只保留个位数
            ans.append(result % 10);
            // add表示十位数，要向后进位
            add = result / 10;
            // num1和num2都向前移
            i--;
            j--;
        }
        // 计算完以后的答案需要翻转过来
        ans.reverse();
        return ans.toString();
    }
}

0 - 最长公共子序列（1143）- 97

// https://leetcode.cn/problems/longest-common-subsequence/description/
// 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0
// 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串
// 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列
// 输入：text1 = "abcde", text2 = "ace" 
// 输出：3  
// 解释：最长公共子序列是 "ace" ，它的长度为 3
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        // dp[i][j]表示text1[0:i] 和 text2[0:j]的最长公共子序列的长度
        int[][] dp = new int[m + 1][n + 1];
        // 边界情况：
        // 当i = 0时，text1[0:i]为空，空字符串和任何字符串的最长公共子序列的长度都是0，
        // 因此对任意 0 <= j <= n，有dp[0][j] = 0
        dp[0][j] = 0；
        dp[i][0] = 0;
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    // 当text1[0:i-1] = text2[0:j-1]的最长公共子序列再增加一个字符（即公共字符）即可得到text1[0:i]和text2[0:j]的最长公共子序列
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
// 时间复杂度：O(mn)，其中m和n分别是字符串text1和text2的长度。二维数组dp有m+1行和n+1列，需要对dp中的每个元素进行计算
// 空间复杂度：O(mn)，其中m和n分别是字符串text1和text2的长度。创建了m+1行n+1列的二维数组 dp
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        // 第一步：状态定义dp[i][j]：长度为[0, i-1]的字符串text1 与 长度为[0, j-1]的字符串text2的最长公共子序列
        int[][] dp = new int[m+1][n+1];
        // 第二步：初始化：text1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0。同理dp[0][j]也是0
        // 第四步：确定遍历顺序
        for(int i = 1; i <= m; i++){
            char char1 = text1.charAt(i-1);
            for(int j = 1; j <= n; j++){
                char char2 = text2.charAt(j-1);
                // 第三步：状态转移方程
                if(char1 == char2){
                    // 如果text1[i-1] 与 text2[j-1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i-1][j-1] + 1
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    // 如果text1[i-1] 与 text2[j-1]不相同，那就看看text1[0, i-2] 与 text2[0, j-1]的最长公共子序列 和 text1[0, i-1]与text2[0, j-2]的最长公共子序列，取最大的
                    dp[i][j] =Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        // 第五步：确定最大值
        return dp[m][n];
    }
}

11111 - 验证回文串（125）- 26

// 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串
// 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false
// 输入: s = "A man, a plan, a canal: Panama"
// 输出：true
// 解释："amanaplanacanalpanama" 是回文串
// https://leetcode.cn/problems/valid-palindrome/
class Solution {
    public boolean isPalindrome(String s) {
        char[] c = s.toLowerCase().toCharArray();
        int i = 0, j = c.length - 1;
        while(i < j){
            while(!isValid(c[i]) && i < j){
                i++;
            }
            while(!isValid(c[j]) && i < j){
                j--;
            }
            if(c[i] != c[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    private boolean isValid(char c){
        return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
    }
}

11111 - 验证回文串II（680）- 11

// https://leetcode.cn/problems/valid-palindrome-ii/description/
// 给你一个字符串s，最多可以从中删除一个字符
// 请你判断 s 是否能成为回文字符串：如果能，返回true ；否则，返回false
// 输入：s = "aba"
// 输出：true
// 输入：s = "abc"
// 输出：false
class Solution {
    public boolean validPalindrome(String s) {
        // 双指针
        int left = 0;
        int right = s.length()-1;
        while(left < right){
            int leftValue = s.charAt(left);
            int rightValue = s.charAt(right);
            // 若首尾字符相同，则移动前后指针
            if(leftValue == rightValue){
                left++;
                right--;
            }else{
                // 若首尾字符不同，则判断（首+1 与 尾）或者（首 与 尾+1）
                return valid(s, left + 1, right) || valid(s, left, right - 1);
            }
        }
        return true;
    }
    // 此方法判断回文字符串，完全匹配
    public boolean valid(String s, int left, int right){
        for(int i = left, j = right; i < j; i++, j--){
            int a = s.charAt(i); 
            int b = s.charAt(j);
            if(a != b) return false;
        }
        return true;
    }
}

22222 - 最长公共子串

https://blog.csdn.net/ly0724ok/article/details/119876759

22222 - 最小覆盖子串（76）- 77

// https://leetcode.cn/problems/minimum-window-substring/
// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 
// 困难：https://leetcode.cn/problems/minimum-window-substring/
// 输入：s = "ADOBECODEBANC", t = "ABC"
// 输出："BANC"
class Solution {
    public String minWindow(String s, String t) {
        // 1.维护两个map记录窗口中的符合条件的字符以及need的字符
        Map<Character, Integer> window = new HashMap<>();
        // need中存储的是需要的字符以及需要的对应的数量
        Map<Character, Integer> need = new HashMap<>();
        for(char c : t.toCharArray()){
            need.put(c, need.getOrDefault(c, 0) + 1);
        } 
        int left = 0, right = 0; //双指针
        int count = 0;      // count记录当前窗口中符合need要求的字符的数量,当count == need.size()时即可shrik窗口
        int start = 0;      // start表示符合最优解的substring的起始位序
        int len = Integer.MAX_VALUE;    // len用来记录最终窗口的长度，并且以len作比较，淘汰选出最小的substring的len
        // 一次遍历找“可行解”
        while(right < s.length()){
            // 更新窗口
            char c = s.charAt(right);
            right++;    // 窗口扩大
            // window.put(c,window.getOrDefault(c,0)+1);其实并不需要将s中所有的都加入windowsmap，只需要将need中的加入即可
            if(need.containsKey(c)){
                window.put(c, window.getOrDefault(c, 0) + 1);
                if(need.get(c).equals(window.get(c))){
                    count++;
                }
            }
            // System.out.println****Debug位置
            // shrink左边界，找符合条件的最优解
            while(count == need.size()){
                // 不断“打擂”找满足条件的len最短值, 并记录最短的子串的起始位序start
                if(right - left < len){
                    len = right - left;
                    start = left;
                }
                // 更新窗口——这段代码逻辑几乎完全同上面的更新窗口
                char d = s.charAt(left);
                left++;     //窗口缩小
                if(need.containsKey(d)){
                    //window.put(d,window.get(d)-1);——bug：若一进去就将window对应的键值缩小，就永远不会满足下面的if，while也会一直执行，知道left越界，因此，尽管和上面对窗口的处理几乎一样，但是这个处理的顺序还是很关键的！要细心！
                    if(need.get(d).equals(window.get(d))){
                        count--;
                    }
                    window.put(d,window.get(d)-1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
    }
}

给一个字符串，输出这个字符串的一个最短子串，这个子串重复拼接能形成整个字符串

1. （如字符串ababab，求得子串ab）若无这种子串，则输出整个字符串；写完有bug没调出来，就问整体思路，说思路是对的但细节有点问题
2. https://blog.csdn.net/taozhi867243023/article/details/124048733

反转字符串中的单词III（557）- 17

// https://leetcode.cn/problems/reverse-words-in-a-string-iii/
// 给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序
// 输入：s = "Let's take LeetCode contest"
// 输出："s'teL ekat edoCteeL tsetnoc"
// s 不包含任何开头或结尾空格
// s 中的所有单词都用一个空格隔开
class Solution {
    public String reverseWords(String s) {
        String[] split = s.split(" ");
        for (int i = 0; i < split.length; i++) {
            split[i] = new StringBuffer(split[i]).reverse().toString();
        }
        return String.join(" ", split);
    }
    public String reverseWords1(String s) {
        StringBuffer ret = new StringBuffer();
        int length = s.length();
        int i = 0;
        while (i < length) {
            int start = i;
            while (i < length && s.charAt(i) != ' ') {
                i++;
            }
            for (int p = start; p < i; p++) {
                ret.append(s.charAt(start + i - 1 - p));
            }
            while (i < length && s.charAt(i) == ' ') {
                i++;
                ret.append(' ');
            }
        }
        return ret.toString();
    }
}

最长连续递增序列（674）- 11

// https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
// 给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度
// 连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列
// 输入：nums = [1,3,5,4,7]
// 输出：3
// 解释：最长连续递增序列是 [1,3,5], 长度为3
// 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int maxlength = 1;
        int premax = 1;
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i+1] > nums[i]) premax++;
            else premax = 1;
            maxlength = Math.max(maxlength, premax);
        }
        return maxlength;
    }
    public int findLengthOfLCIS1(int[] nums) {
        int ans = 0;
        int n = nums.length;
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] <= nums[i - 1]) {
                start = i;
            }
            ans = Math.max(ans, i - start + 1);
        }
        return ans;
    }
}

字符串中找出连续最长的数字串

// https://blog.csdn.net/ren__wei_/article/details/116030619
// 读入一个字符串str，输出字符串str中的连续最长的数字串
// 给一个输入abc123nj5nk88990wze这里面最长的数字串是88990，并将其输出
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String cur = "";
        String result = "";
        for(int i = 0; i < str.length(); i++){
            char ch = str.charAt(i);
            // 当前字符是数字的话，就把这个字符放进cur中，加""的原因是变成字符串
            if(ch >= '0' && ch <= '9'){
                cur = cur + ch + "";
            }else{
                if(cur.length() > result.length()){
                    result = cur;
                }else{
                    cur = "";
                }
            }
        }
        // 循环结束后，再次进行判断，防止输入的字符串全是数字
        if(cur.length() > result.length()){
            result = cur;
        }
        System.out.println(result);
    }
}

22222 - 根据字符出现频率排序（451）- 6

// https://leetcode.cn/problems/sort-characters-by-frequency/
// 给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数
// 返回 已排序的字符串 。如果有多个答案，返回其中任何一个
// 输入: s = "Aabb"
// 输出: "bbAa"
// 解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的
// 注意'A'和'a'被认为是两种不同的字符
class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        int maxFreq = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            int frequency = map.getOrDefault(c, 0) + 1;
            map.put(c, frequency);
            maxFreq = Math.max(maxFreq, frequency);
        }
        StringBuffer[] buckets = new StringBuffer[maxFreq + 1];
        for (int i = 0; i <= maxFreq; i++) {
            buckets[i] = new StringBuffer();
        }
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            char c = entry.getKey();
            int frequency = entry.getValue();
            buckets[frequency].append(c);
        }
        StringBuffer sb = new StringBuffer();
        for (int i = maxFreq; i > 0; i--) {
            StringBuffer bucket = buckets[i];
            int size = bucket.length();
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < i; k++) {
                    sb.append(bucket.charAt(j));
                }
            }
        }
        return sb.toString();
    }
}
// 时间复杂度：O(n + k)
// 空间复杂度：O(n + k)

1. 求一个字符串中的出现最大次数的字符并返回该次数
2. 驼峰子串的去除，如字符串AaADdDEeEbcvQv，AaA、DdD、EeE和vQv均为驼峰，需要去除，输出结果bc，使用栈进行一次遍历即可
3. 给一个String字符串abcabcdabddd……………iii…….iii，然后给abc iii abcd ab，根据下面的去切分上面的字符串，输出结果abc|abcd|ab|iii|iii
4. 代码题：一串字符串，判断第一个不重复的单词
5. 编程：完整的括号，能否完全配对
6. 检查字符串是否满足ipv4的要求

数组

11111 - 非重复数字的全排列（46）- 181

// https://leetcode.cn/problems/permutations/
// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案
// 输入：nums = [1,2,3]
// 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> permute(int[] nums) {
        process(nums);
        return result;
    }
    public void process(int[] nums){
        // 此处不要加终止条件，根据纵向递归判断终止条件
        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
        }
        // 纵向递归：有终止条件
        for(int i = 0; i < nums.length; i++){
            // path中已存在，则跳过
            if(path.contains(nums[i])) continue;   
            path.add(nums[i]);
            process(nums);
            path.remove(path.size()-1);
        }
    }
}

22222 - 删除有序数组中的重复项（26）- 33

// https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
// 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致
// 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果
// 将最终结果插入 nums 的前 k 个位置后返回 k
// 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成
// 判题标准:
//     系统会用下面的代码来测试你的题解:
//         int[] nums = [...]; // 输入数组
//         int[] expectedNums = [...]; // 长度正确的期望答案
//         int k = removeDuplicates(nums); // 调用
//         assert k == expectedNums.length;
//         for (int i = 0; i < k; i++) {
//             assert nums[i] == expectedNums[i];
//         }
// 如果所有断言都通过，那么您的题解将被 通过
class Solution {
     public int removeDuplicates(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int slow = 0;
        int fast = 1;
        while(fast < nums.length){
            // 若慢指针指向的元素 与 快指针指向的元素不相等，表示慢指针指向元素不是重置项
            if(nums[slow] != nums[fast]){
                // 向后慢指针，并将快指针元素 赋值给 慢指针后一位元素，进入下一次循环判断
                slow++;
                nums[slow] = nums[fast];
            }
            // 每判断一次都向后移动快指针
            fast++;
        }
        return slow + 1;
    }
}
// 时间复杂度：O(n)。 空间复杂度：O(1)

11111 - 多数元素（169）- 60

// https://leetcode.cn/problems/majority-element/
class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if(map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }else {
                map.put(num, 1);
            }
        }
        Integer s = map.values().stream().max(Integer::compareTo).orElse(1);
        System.out.println(s);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue().equals(s)){
                return entry.getKey();
            }
        }
        return -1;
    }
    public int majorityElement1(int[] nums) {
        int cand_num = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (cand_num == nums[i])
                ++count;
            else if (--count == 0) {
                cand_num = nums[i];
                count = 1;
            }
        }
        return cand_num;
    }
    public int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

最大数（179）- 48

// https://leetcode.cn/problems/largest-number/
// 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数
// 输入：nums = [3,30,34,5,9]
// 输出："9534330"
class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] numsToWord = new String[n];
        for(int i = 0; i < n; i++){
            numsToWord[i] = String.valueOf(nums[i]);
        }
        // compareTo()方法比较的时候是按照ASCII码逐位比较的
        // 通过比较(a+b)和(b+a)的大小，就可以判断出a,b两个字符串谁应该在前面
        // 所以[3,30,34]排序后变为[34,3,30]
        // [233，23333]排序后变为[23333，233]
        Arrays.sort(numsToWord, (a, b)->{
            return (b + a).compareTo(a + b);
        });
        // 如果排序后的第一个元素是0，那后面的元素肯定小于或等于0，则可直接返回0
        if(numsToWord[0].equals("0")){
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++){
            sb.append(numsToWord[i]);
        }
        return sb.toString();
    }
}

把数组排成最小的数（面试题45）- 17

// https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
// 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个
// 输入: [3,30,34,5,9]
// 输出: "3033459"
class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }
}

1 - 合并两个有序数组（88）- 185

// https://leetcode.cn/problems/merge-sorted-array/description/
// 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
// 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
// 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 
// 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
// 输出：[1,2,2,3,5,6]
// 解释：需要合并 [1,2,3] 和 [2,5,6] 。
// 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] sorted = new int[m + n];
        // 双指针，p1指向nums1数组，p2指向nums2数组
        int p1 = 0, p2 = 0;
        // cur表示当前指针对应的元素值
        int cur;    
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                // nums1数组已经取完，此时完全取nums2数组的值即可
                cur = nums2[p2++];
            } else if (p2 == n) {
                // nums2数组已经取完，此时完全取nums1数组的值即可
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            // 由于上述步骤已经将p1或p2完成的+1，所以此处的下标要-1
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i < m + n; i++) {
            nums1[i] = sorted[i];
        }
    }
}

0 - 三数之和（15）- 267

// https://leetcode.cn/problems/3sum/
// 给你一个整数数组nums，判断是否存在三元组[nums[i],nums[j],nums[k]]，满足i != j、i != k且j != k，
// 同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为0且不重复的三元组
// 注意：答案中不可以包含重复的三元组
// 输入：nums = [-1,0,1,2,-1,-4]
// 输出：[[-1,-1,2],[-1,0,1]]
// 解释：
// nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
// nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
// nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
// 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
// 注意，输出的顺序和三元组的顺序并不重要
class Solution {
    // 定义三个指针，保证遍历数组中的每一个结果
    // 画图，解答
    public List<List<Integer>> threeSum(int[] nums) {
        // 定义一个结果集
        List<List<Integer>> res = new ArrayList<>();
        // 数组的长度
        int len = nums.length;
        // 当前数组的长度为空，或者长度小于3时，直接退出
        if(nums == null || len < 3){
            return res;
        }
        // 将数组进行排序
        Arrays.sort(nums);
        // 遍历数组中的每一个元素
        for(int i = 0; i<len;i++){
            // 如果遍历的起始元素大于0，就直接退出
            // 原因，此时数组为有序的数组，最小的数都大于0了，三数之和肯定大于0
            if(nums[i]>0){
                break;
            }
            // 去重，当起始的值等于前一个元素，那么得到的结果将会和前一次相同
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int l = i +1;
            int r = len-1;
            // 当 l 不等于 r时就继续遍历
            while(l < r){
                // 将三数进行相加
                int sum = nums[i] + nums[l] + nums[r];
                // 如果等于0，将结果对应的索引位置的值加入结果集中
                if(sum==0){
                    // 将三数的结果集加入到结果集中
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    // 在将左指针和右指针移动的时候，先对左右指针的值，进行判断
                    // 如果重复，直接跳过。
                    // 去重，因为 i 不变，当此时 l取的数的值与前一个数相同，所以不用在计算，直接跳
                    while(l < r && nums[l] == nums[l+1]) {
                        l++;
                    }
                    // 去重，因为 i不变，当此时 r 取的数的值与前一个相同，所以不用在计算
                    while(l< r && nums[r] == nums[r-1]){
                        r--;
                    } 
                    // 将 左指针右移，将右指针左移。
                    l++;
                    r--;
                    // 如果结果小于0，将左指针右移
                }else if(sum < 0){
                    l++;
                    // 如果结果大于0，将右指针左移
                }else if(sum > 0){
                    r--;
                }
            }
        }
        return res;
    }
}

最长公共前缀（14）- 56

// https://leetcode.cn/problems/longest-common-prefix/
// 编写一个函数来查找字符串数组中的最长公共前缀。
// 输入：strs = ["flower","flow","flight"]
// 输出："fl"
class Solution {
    public String longestCommonPrefix(String[] strs) {
        String shortest = strs[0];
        for (String str : strs) {
            if (str.length() < shortest.length()) {
                shortest = str;
            }
        }
        String res = shortest;
        for (int i = 0; i < shortest.length(); i++) {
            for (String str : strs) {
                if (!str.startsWith(res)) {
                    res = res.substring(0, res.length() - 1);
                }
            }
        }
        return res;
    }
}

最大子数组和（53）- 236

// https://leetcode.cn/problems/maximum-subarray/
// 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 子数组 是数组中的一个连续部分
// 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
// 输出：6
// 解释：连续子数组 [4,-1,2,1] 的和最大，为 6
class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        // 第一步：定义状态：dp[i]表示第i个元素为尾结点构成的子数组的和
        int[] dp = new int[len];
        // 第二步：初始化
        dp[0] = nums[0];
        int maxSum = dp[0];
        // 第四步：确定遍历顺序
        for(int i = 1; i < len; i++){
            // 第三步：状态转移
            // dp[i-1] > 0，则dp[i] = dp[i-1] + nums[i]。此处不能判断dp[i-1] + nums[i] > 0，需考虑dp[i-1]为负数场景
            // dp[i-1] <= 0，则dp[i] = nums[i];
            if(dp[i-1] > 0){
                dp[i] = dp[i-1] + nums[i];
            }else {
                dp[i] = nums[i];
            }
            maxSum = Math.max(maxSum, dp[i]);
        }
        // 第五步：确定最大值
        return maxSum;
    }
    public int maxSubArray1(int[] nums) {
        int ans = nums[0];    // 最终求出的连续子数组的最大和
        int sum = 0;          // 当前元素前面的连续子数组的最大和
        for(int num: nums) {
            if(sum > 0) {
                sum += num;   // 说明sum对结果有增益效果，则sum保留并加上当前遍历数字
            } else {
                sum = num;    // 说明sum对结果无增益效果，需要舍弃，则sum直接更新为当前遍历数字
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

0 - 最长重复子数组（718） - 58

// https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
// 给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
// 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
// 输出：3
// 解释：长度最长的公共子数组是 [3,2,1]
class Solution {
    public int findLength(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int maxLength = 0;
        // 第一步：定义状态：dp[i][j]表示A[i-1],B[j-1]重复子数组
        int[][] dp = new int[m+1][n+1];
        // 第二步：初始化
        // Arrays.fill(dp, 0);
        // 第四步：确认遍历顺序
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                // 第三步：状态转移
                // A[i-1] = B[j-1]，dp[i][j] = dp[i-1][j-1] + 1
                // A[i-1] != B[j-1]，dp[i][j] = 0
                if(A[i-1] == B[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
        // 第五步：确认最大值
        return maxLength;
    }
    public int findLength1(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        int[] dp = new int[n+1];
        int ans = 0;
        for(int i = m-1; i >= 0; i--){
            int p = 0;
            int q = 0;
            for(int j = n-1; j >= 0; j--){
                p = q;
                q = dp[j];
                dp[j] = (A[i] == B[j]) ? p + 1 : 0;      
                ans = Math.max(ans,dp[j]);
            }
        }
        return ans;
    }
}

1 - 二分查找（704）- 114

// 给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，
// 如果目标值存在返回下标，否则返回 -1
// https://leetcode.cn/problems/binary-search/
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length-1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(target == nums[mid]){            // 目标值刚好在中间位置
                return mid;
            }else if(target > nums[mid]) {      // 目标值在后半部分
                left = mid + 1;
            }else{
                right = mid - 1;                // 目标值在前半部分
            }
        }
        return -1;
    }
}
// 时间复杂度：O(log⁡n)，其中n是数组的长度
// 空间复杂度：O(1)

22222 - 长度为n的数组乱序存放着0至n-1，现在只能进行0与其他数的交换，完成数组排序

// 问题描述：长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的交换，完成数组排序
// 思路：由于乱序数组各元素亮亮不同，且已知数组内容即为0-（n-1），所以只要考虑将0-（n-1）这n个数依次填入数组array即可。
// 一个简单的思路是，由于数组最终内容是array[i]=i,考虑将0与数组第i个位置互换，然后将0与i互换，则i填入位置array[i]

22222 - 小于n的最大数

6. 给定一个数n,如23121;给定一组数字A如{2,4,9}求由A中元素组成的、小于n的最大数,如小于23121的最大数为22999.
7. 给一个数组a[]，一个数n 232342，求用数组a[]里面数字组合成最大的不大于n的数
// https://blog.csdn.net/weixin_42041027/article/details/125269790

分组的最大数量（2358）

// https://leetcode.cn/problems/maximum-number-of-groups-entering-a-competition/description/
// 给你一个正整数数组 grades ，表示大学中一些学生的成绩。你打算将 所有 学生分为一些 有序 的非空分组，其中分组间的顺序满足以下全部条件：
// 第 i 个分组中的学生总成绩 小于 第 (i + 1) 个分组中的学生总成绩，对所有组均成立（除了最后一组）
// 第 i 个分组中的学生总数 小于 第 (i + 1) 个分组中的学生总数，对所有组均成立（除了最后一组）
// 返回可以形成的 最大 组数
// 输入：grades = [10,6,12,7,3,5]
// 输出：3
// 解释：下面是形成 3 个分组的一种可行方法：
// - 第 1 个分组的学生成绩为 grades = [12] ，总成绩：12 ，学生数：1
// - 第 2 个分组的学生成绩为 grades = [6,7] ，总成绩：6 + 7 = 13 ，学生数：2
// - 第 3 个分组的学生成绩为 grades = [10,3,5] ，总成绩：10 + 3 + 5 = 18 ，学生数：3 
// 可以证明无法形成超过 3 个分组

搜索插入位置（35）- 4

// https://leetcode.cn/problems/search-insert-position/
// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置
// 请必须使用时间复杂度为 O(log n) 的算法
// 输入: nums = [1,3,5,6], target = 5
// 输出: 2
// 输入: nums = [1,3,5,6], target = 2
// 输出: 1
class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

11111 - 合并区间（56）- 106

// https://leetcode.cn/problems/merge-intervals/
// 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间
// 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
// 输出：[[1,6],[8,10],[15,18]]
// 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> result = new ArrayList<>();
        // 将数组中的每个子数组按照第一个元素大小进行排序
        Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0]));
        for(int[] interval : intervals){
            // 当前集合为空 或者 当前遍历数组的第一个元素 大于 集合中最后一个数组的第二个元素，表明此时数组不需要合并，加上该新数组即可
            if(result.size() == 0 || interval[0] > result.get(result.size()-1)[1]){
                result.add(interval);
            }else{
                // 当前遍历数组的第一个元素 不大于 集合中最后一个数组的第二个元素，表明此时两个数组会有重叠，需要合并这两个数组。第二个元素取较大值
                result.get(result.size()-1)[1] = Math.max(interval[1], result.get(result.size()-1)[1]);
            }
        }
        // 集合转数组
        return result.toArray(new int[result.size()][]);
    }
}
// 时间复杂度：O(nlog⁡n)
// 空间复杂度：O(nlog⁡n)