力扣题解(持续更新)

一、双指针27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

package leetCodePractice;/** * @Date 2023/9/11 17:56 * @Author 郜宇博 */public class Solution27 {    public static int removeElement(int[] nums, int val) {        if (nums.length == 0 || nums == null) return 0;        int firstIndex = 0;        int secondIndex = nums.length-1;        while (firstIndex <= secondIndex){            if (nums[firstIndex] == val){                swap(nums,firstIndex,secondIndex--);            }else {                firstIndex++;            }        }        return secondIndex + 1;    }    private static void swap(int[] nums, int firstIndex, int secondIndex) {        int temp;        temp = nums[firstIndex];        nums[firstIndex] = nums[secondIndex];        nums[secondIndex] = temp;    }}

58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

输入：s = "Hello World"输出：5解释：最后一个单词是“World”，长度为5。

示例 2：

输入：s = "   fly me   to   the moon  "输出：4解释：最后一个单词是“moon”，长度为4。

示例 3：

输入：s = "luffy is still joyboy"输出：6解释：最后一个单词是长度为6的“joyboy”。

package leetCodePractice;/** * @Date 2023/9/11 19:14 * @Author 郜宇博 */public class Solution58 {    public int lengthOfLastWord(String s) {        String[] s1 = s.split(" ");        return s1[s1.length-1].length();    }    public int lengthOfLastWord2(String s) {        //存在为空格 则去除        char[] charArray = s.toCharArray();        int end = charArray.length-1;        while (end >=0 && charArray[end] == ' '){            end--;        }        int start = end;        while (start >= 0 && charArray[start] != ' '){            start--;        }        return end - start;    }}

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

class Solution {    public ListNode deleteDuplicates(ListNode head) {        if (head == null || head.next == null) return head;        ListNode tempNode = head.next;        ListNode pre = head;        while (tempNode != null){            if (tempNode.val == pre.val){                //重复了，需要删除                pre.next = tempNode.next;            }else{                pre = tempNode;            }                        tempNode = tempNode.next;        }        return head;    }}

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：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 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0输出：[1]解释：需要合并 [1] 和 [] 。合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1输出：[1]解释：需要合并的数组是 [] 和 [1] 。合并结果是 [1] 。注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

package leetCodePractice;import java.util.Arrays;/** * @Date 2023/9/13 11:36 * @Author 郜宇博 */public class Solution88 {    public static void main(String[] args) {        int[] n1 = new int[]{0};        int[] n2 = new int[]{1};        merge2(n1,0,n2,1);    }    public static void merge(int[] nums1, int m, int[] nums2, int n) {        int[] nums1Save = new int[m];        System.arraycopy(nums1, 0, nums1Save, 0, m);        int index1 = 0,index2 = 0;        int sortIndex = 0;        while (sortIndex < m + n && index1 < m && index2 < n){            if (nums1Save[index1] < nums2[index2]){                nums1[sortIndex++] = nums1Save[index1++];            }else {                nums1[sortIndex++] = nums2[index2++];            }        }        //num2元素还有剩余        if (index1 == m && index2 != n){            for (int i = index2; i < n; i++){                nums1[m+index2] = nums2[i];                index2++;            }        }else if (index1 != m && index2 == n){            //num1还有剩余            for (int i = index1; i = 0 && num2Index >= 0 && num1Index >= 0){            if (nums2[num2Index] >= nums1[num1Index] ){                nums1[mergeIndex] = nums2[num2Index--];            }else if ( nums1[num1Index] > nums2[num2Index]){                nums1[mergeIndex] = nums1[num1Index--];            }            mergeIndex--;        }        //num1还有剩余，不能使用num1Index判断，因为num1的长度有可能为0        if (num2Index >= 0){            System.arraycopy(nums2, 0, nums1, 0, num2Index);        }    }}

125. 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama"输出：true解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"输出：false解释："raceacar" 不是回文串。

示例 3：

输入：s = " "输出：true解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。由于空字符串正着反着读都一样，所以是回文串。

提示：

• 1 <= s.length <= 2 * 105
• s 仅由可打印的 ASCII 字符组成

class Solution {    public static boolean isPalindrome(String s) {        if (s.isEmpty() || s.length() == 1) return true;        int left = 0;        int right = s.length()-1;        //        s = s.toUpperCase();        while (left <= right){            while (left <= right && !testChar(s.charAt(left))){                //不属于字母表，跳过                left++;            }            while (left  right){                break;            }            //找到了字母，进行对比            if (s.charAt(left) == s.charAt(right)) {                left++;                right--;            }else{                return false;            }        }        return true;    }    //不属于字母    public static boolean testChar(char c){        return ('A'= c) || '0' = c;    }}

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19输出：true解释：12 + 92 = 8282 + 22 = 6862 + 82 = 10012 + 02 + 02 = 1

示例 2：

输入：n = 2输出：false

class Solution {    public static boolean isHappy(int n) {        /*         n       下个数最大值 `       9 :     81         99      2 * 81         999     3 * 81         ....    x * 81         因此对于任何一个数，都不会无限增大下去，有上线，因此如果最后结果不为1，就是进入某个循环中         判断是否进入循环可以采用两种方式         1.hash存储进入过的数，每次比较         2.快慢指针，快指针走两步，满指针走一步         */        int slow = n;        int fast = getNext(n);        while (fast != 1 && slow != fast){            slow = getNext(slow);            fast = getNext(getNext(fast));        }        return fast == 1;    }    public static int getNext(int number){        int result = 0;        while (number > 0){            int x = number % 10;            number /= 10;            result += Math.pow(x,2);        }        return result;    }}

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7输出：[]

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

双指针 pre.next = cur.next;

防止对头结点额外考虑，可以加入虚拟头结点。

public static ListNode removeElements(ListNode head, int val) {        if (head == null) return head;        ListNode preNode = head;        ListNode curNode = head;        while (curNode != null){            if (curNode.val == val){                //如果是头结点                if (curNode == head){                    head = head.next;                    preNode = head;                }                preNode.next = curNode.next;            }else {                preNode = curNode;            }            curNode = curNode.next;        }        return head;    }

public static ListNode removeElements(ListNode head, int val) {        if(head == null) return null;        //添加虚拟头结点        ListNode newHead = new ListNode(head.val);        newHead.next = head;        ListNode preNode = newHead;        ListNode curNode = newHead;        while (curNode != null){            if (curNode.val == val){                preNode.next = curNode.next;            }else {                preNode = curNode;            }            curNode = curNode.next;        }        return newHead.next;    }

228. 汇总区间

给定一个 无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

• "a->b" ，如果 a != b
• "a" ，如果 a == b

示例 1：

输入：nums = [0,1,2,4,5,7]输出：["0->2","4->5","7"]解释：区间范围是：[0,2] --> "0->2"[4,5] --> "4->5"[7,7] --> "7"

示例 2：

输入：nums = [0,2,3,4,6,8,9]输出：["0","2->4","6","8->9"]解释：区间范围是：[0,0] --> "0"[2,4] --> "2->4"[6,6] --> "6"[8,9] --> "8->9"

public List summaryRanges(int[] nums) {        int first = 0;        int second = 0;        List list = new ArrayList();        while (second <= nums.length-1){            while (second " + nums[second - 1]);                    }else {                list.add(String.valueOf(nums[first]));            }            first = second;        }        return list;    }

234. 回文链表(快慢指针+反转、赋值数组双指针)

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]输出：true

示例 2：

输入：head = [1,2]输出：false

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

两种方法：

public class Solution234 {    public static boolean isPalindrome(ListNode head) {        ListNode start = head;        ArrayList arrayList = new ArrayList();        while (start != null){            arrayList.add(start.val);            start = start.next;        }        int front = 0;        int back = arrayList.size()-1;        while (front < back){            if (! (arrayList.get(front++).equals(arrayList.get(back--)))){                return false;            }        }        return true;    }    public static boolean isPalindrome2(ListNode head){        //找到中间节点的位置        ListNode midNode =  getMidNode(head);        //反转链表        ListNode secondHead =  reverseList(midNode);        //比较        boolean flag = palindromeJudge(midNode,secondHead);        //还原        reverseList(midNode);        return flag;    }    private static boolean palindromeJudge(ListNode midNode, ListNode secondHead) {        ListNode node1 = midNode;        ListNode node2 = secondHead;        while (node2 != null){            if (node1.val != node2.val){                return false;            }            node1 = node1.next;            node2 = node2.next;        }        return true;    }    private static ListNode reverseList(ListNode midNode) {        ListNode preNode = null;        ListNode cur = midNode;        while (cur != null){            ListNode nextNode = cur.next;            cur.next = preNode;            preNode = cur;            cur = nextNode;        }        return preNode;    }    private static ListNode getMidNode(ListNode head) {        //快慢指针        ListNode slow = head;        ListNode fast = head;        while (slow.next != null && fast.next.next != null){            slow = slow.next;            fast = fast.next;        }        return slow;    }}

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]输出: [0]

public static void moveZeroes(int[] nums) {        int numIndex = 0;        //所有非负数都直接赋值到数组前面        for (int i = 0; i < nums.length; i++) {            if (nums[i] != 0){                nums[numIndex++] = nums[i];            }        }        for (int i = numIndex; i < nums.length; i++) {            nums[i] = 0;        }}

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]输出：["h","a","n","n","a","H"]

public void reverseString(char[] s) {        int left = 0;        int right = s.length-1;        while (left < right){            char temp = s[left];            s[left] = s[right];            s[right] = temp;            left++;            right--;        }    }

345. 反转字符串中的元音字母

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。

示例 1：

输入：s = "hello"输出："holle"

示例 2：

输入：s = "leetcode"输出："leotcede"

class Solution {    public String reverseVowels(String s) {        int left = 0;        int right = s.length()-1;        char[] charArray = s.toCharArray();        while (left < right){            while (left < right && noYuan(charArray[left]) ){                left++;            }            while (left < right && noYuan(charArray[right]) ){                right--;            }            if (left < right){                char temp = charArray[left];                charArray[left] = charArray[right];                charArray[right] = temp;            }            left++;            right--;        }        return String.valueOf(charArray);    }    public boolean noYuan(Character character){        return character != 'a' &&                character != 'e' &&                character != 'i' &&                character != 'o' &&                character != 'u' &&                character != 'A' &&                character != 'E' &&                character != 'I' &&                character != 'O' &&                character != 'U';    }}

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：

输入：s = "abc", t = "ahbgdc"输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"输出：false

public boolean isSubsequence(String s, String t) {        if (s.length() > t.length()) return false;        int sIndex = 0;        int tIndex = 0;        while (sIndex < s.length() && tIndex < t.length()){            if (s.charAt(sIndex) == t.charAt(tIndex)){                sIndex++;                tIndex++;            }else {                tIndex++;            }        }        return sIndex==s.length();    }

541. 反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2输出："bacd"

提示：

• 1 <= s.length <= 104
• s 仅由小写英文组成
• 1 <= k <= 104

public static String reverseStr(String s, int k) {        //余数        int remainder = s.length() % (k << 1);        //商        int quotient = s.length() / (k << 1);        StringBuilder stringBuilder = new StringBuilder();        for (int i = 0; i < quotient; i++) {            char[] chars = reverseString(s.substring(i * 2 * k, i * 2 * k + k));            stringBuilder.append(chars);            stringBuilder.append(s, i * 2 * k + k, (i + 1) * 2 * k);        }        if (remainder = 0; i--) {            array[str.length() - 1 - i] = str.charAt(i);        }        return array;    }    public String reverseStr1(String s, int k) {        char[] chars = s.toCharArray();        for (int i = 0; i < s.length(); i += 2*k){            //Math.min(i+k, s.length()) 可以保证最后不足k时，全反转            reverse(chars,i,Math.min(i+k, s.length()) -1);        }        return String.valueOf(chars);    }    public void reverse(char[] chars, int left ,int right){        while (left < right){            char temp = chars[left];            chars[left] = chars[right];            chars[right] = temp;            left++;            right--;        }    }

557. 反转字符串中的单词 III

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序

示例 1：

输入：s = "Let's take LeetCode contest"输出："s'teL ekat edoCteeL tsetnoc"

示例 2:

输入： s = "God Ding"输出："doG gniD"

 public static String reverseWords(String s) {        StringBuilder stringBuilder = new StringBuilder();        String[] words = s.split(" ");        for (String word : words) {            stringBuilder.append(reverseWord(word)).append(" ");        }        stringBuilder.deleteCharAt(stringBuilder.length()-1);        return stringBuilder.toString();    }    public static char[] reverseWord(String word) {        char[] wordCharArray = word.toCharArray();        int left = 0;        int right = word.length() - 1;        char temp;        while (left < right) {            temp = wordCharArray[left];            wordCharArray[left++] = wordCharArray[right];            wordCharArray[right--] = temp;        }        return wordCharArray;    }

31. 下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，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 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

示例 1：

输入：nums = [1,2,3]输出：[1,3,2]

两种方法1.

1. 先倒序遍历数组, 找到第一个 nums[i] (前一个数比后一个数小的位置) (即nums[i] < nums[i+1]);
2. 这个时候我们不能直接把后一个数nums[i+1] 跟前一个数nums[i]交换就完事了; 还应该从nums[i+1]–>数组末尾这一段的数据中 找出最优的那个值( 如何最优? 即比nums[i]稍微大那么一丢丢的数, 也就是 nums[i+1]-->数组末尾中, 比nums[i]大的数中最小的那个值)
3. 找到之后, 跟num[i]交换, 这还不算是下一个排列, num[i]后面的数值还不够小, 所以还应当进升序排列

public static void nextPermutation(int[] nums) {        for (int i = nums.length-1; i > 0; i--){            if (nums[i-1] < nums[i]){                //找到一个最小的与i-1交换                int minNum = Integer.MAX_VALUE;                int minIndex = 0;                for (int j = i; j < nums.length;j++){                    if (nums[j]  nums[i-1]){                        minNum = nums[j];                        minIndex = j;                    }                }                int temp = nums[minIndex];                nums[minIndex] = nums[i-1];                nums[i-1] = temp;                Arrays.sort(nums,i,nums.length);                return;            }        }        Arrays.sort(nums);    }    

方法2.

public static void nextPermutation1(int[] nums) {        int i = nums.length-2;        while (i >= 0){            if (nums[i+1] > nums[i]) break;            i--;        }        if (i >= 0){            for (int j = nums.length-1;j >=0; j--){                if (nums[j] > nums[i]) {                    swap(nums,i,j);                    break;                }            }        }        reverseArr(nums,i+1,nums.length-1);    }    public static void swap(int[] nums,int index1,int index2){        int temp = nums[index1];        nums[index1] = nums[index2];        nums[index2] = temp;    }    public static void reverseArr(int[] nums,int start,int end){        while (start < end){            swap(nums,start++,end--);        }    }

二、二分法35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7输出: 4

package leetCodePractice;/** * @Date 2023/9/11 18:41 * @Author 郜宇博 */public class Solution35 {    public static int searchInsert(int[] nums, int target) {        int firstIndex = 0;        int secondIndex = nums.length-1;        while (firstIndex = target) return firstIndex;            if (nums[secondIndex] == target) return secondIndex;            if (nums[secondIndex] < target) return secondIndex+1;            firstIndex++;            secondIndex--;        }        return firstIndex;    }    public static int searchInsert2(int[] nums, int target) {        int left = 0;        int right = nums.length-1;        int mid = (left+right)/2;        while (left <= right){            mid = (left+right)/2;            if (nums[mid] == target) return mid;            if (nums[mid] < target){                left = mid + 1;            }else {                right = mid - 1;            }        }        return left;    }}

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

package leetCodePractice;/** * @Date 2023/9/13 10:46 * @Author 郜宇博 */public class Solution69 {    public static int mySqrt(int x) {        if ((long) x == 0) return 0;        if ((long) x < 4) return 1;        for (long i = 2; i  (long) x) return (int) (i - 1);        }        return -1;    }    public static int mySqrt1(int x){        if ( x == 0) return 0;        if ((x < 4)) return 1;        int left = 0;        int right = x / 2;        while (left > 1;            if (mid == x / mid){                return mid;            }            if (mid > x / mid){                right = mid - 1;            }else {                left = mid + 1;            }        }        return left -1;    }}

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4输出：4解释：调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1输出：1

public int firstBadVersion(int n) {        int left = 0;        int right = n;        int mid = left + ((right - left)>>1);        while (left >1);            if (isBadVersion(mid)){                right = mid - 1;            }else {                if (isBadVersion(mid+1)){                    return mid+1;                }else {                    left = mid + 1;                }            }        }        return mid;    }

367. 有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16输出：true解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入：num = 14输出：false解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

public static boolean isPerfectSquare(int num) {        if (num == 1 ) return true;        //二分法        int left = 0;        int right = num;        int mid = left + ((right - left) >> 1);        while (left > 1);            //使用除法防止越界， <= 0判断防止除0            if (mid <= 0 ) return false;            if ( mid  == num / mid && num % mid == 0){                return true;            }else if (mid  < num / mid){                left = mid + 1;            }else {                right = mid - 1;            }        }        return left * left == num;    }

374. 猜数字大小

猜数字游戏的规则如下：

• 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
• 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

• -1：我选出的数字比你猜的数字小 pick < num
• 1：我选出的数字比你猜的数字大 pick > num
• 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

返回我选出的数字。

示例 1：

输入：n = 10, pick = 6输出：6

示例 2：

输入：n = 1, pick = 1输出：1

public class Solution extends GuessGame {    public int guessNumber(int n) {        int left = 0;        int right = n;        int mid;        while (left > 1);            int guess = guess(mid);            if (guess == 0){                return mid;            }else if (guess == -1){                right = mid -1;                            }else {                left = mid + 1;            }        }        return left;    }}

441. 排列硬币

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

示例 1：

输入：n = 5输出：2解释：因为第三行不完整，所以返回 2 。

示例 2：

输入：n = 8输出：3解释：因为第四行不完整，所以返回 3 。

方法一：枚举

方法二：二分

public int arrangeCoins(int n) {        for (long i = 1; i > 1 > n){                return (int) (i -1);            }        }        return n;    }    public int arrangeCoins1(int n) {        long left = 1;        long right = n;        long mid = 0;        while (left > 1);            if ( ((1 + mid) * mid ) >> 1   == n){                return (int) mid;            }            if ( ((1 + mid) * mid ) >> 1  > n  ){                if ( ((1 + mid-1) * (mid -1) ) >> 1 > 1  < n){                left = mid + 1;            }        }        return (int) left;    }

33. 搜索旋转排序数组

整数数组 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) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0输出：4

public int search(int[] nums, int target) {        //二分法查找，如果查找的目标比数组最左还小，说明在右边，left = mid +1        int left = 0, right = nums.length -1;        while (left > 1);            if (nums[mid] == target) return mid;            //left - mid是顺序区间            if (nums[left ] = nums[left] && target < nums[mid]){                    right = mid - 1;                }else {                    //在mid右边                    left = mid + 1;                }            }else {//mid - right是顺序区间                if (target  nums[mid]){                    left = mid + 1;                }else {                    right = mid -1;                }            }        }        return -1;    }

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6输出：[-1,-1]

示例 3：

输入：nums = [], target = 0输出：[-1,-1]

public int[] searchRange(int[] nums, int target) {        if (nums.length != 0){            int left = 0;            int right = nums.length-1;            while (left > 1);                if (target == nums[mid]){                    int start = mid,end = mid;                    while (start >= 0 && nums[start] == nums[mid]){                        start--;                    }                    while ( end < nums.length && nums[end] == nums[mid]){                        end++;                    }                    return new int[]{start+1,end-1};                } else if (target < nums[mid]){                    right = mid-1;                }else {                    left = mid + 1;                }            }        }        return new int[]{-1,-1};    }

三、数学(取余,二进,异或,进制)66. 加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]输出：[1,2,4]解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]输出：[4,3,2,2]解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]输出：[1]

class Solution {     public static int[] plusOne(int[] digits){        //元素值=0; i--){            digits[i] = (digits[i] +1) % 10;            //有一位不为9,可以退出了            if (digits[i] != 0){                return digits;            }        }        //一直进位到了d[0]位置，需要新建数组        digits = new int[digits.length+1];        digits[0] = 1;        //数组创建默认元素为0，因此后面不需要赋值        return digits;    }}

67. 二进制求和

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：

输入:a = "11", b = "1"输出："100"

示例 2：

输入：a = "1010", b = "1011"输出："10101"

package leetCodePractice;/** * @Date 2023/9/11 20:58 * @Author 郜宇博 */public class Solution67 {    public String addBinary(String a, String b) {        /*        1010        1011        0001        1 1         */        StringBuilder stringBuilder = new StringBuilder();        //int up = 0;        int sum = 0;        for (int i = a.length()-1, j = b.length()-1; i>=0 || j >=0;i--,j--){            if (i >=0){                sum  += a.charAt(i) - '0';            }            if (j >= 0){                sum += b.charAt(j) - '0';            }            stringBuilder.append(sum % 2);            //需要计算进位，只有和为2需要进位            sum /= 2;        }        if (sum != 0){            stringBuilder.append("1");        }        return stringBuilder.reverse().toString();    }}

136. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]输出：4

示例 3 ：

输入：nums = [1]输出：1

提示：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

public static int singleNumber(int[] nums) {    //异或本身会等于0        if (nums.length == 1) return nums[0];        int ans = nums[0];        for (int i = 1; i < nums.length; i++){            ans ^= nums[i];        }        return ans;    }

168. Excel表列名称

相关企业

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

A -> 1B -> 2C -> 3...Z -> 26AA -> 27AB -> 28 ...

示例 1：

输入：columnNumber = 1输出："A"

示例 2：

输入：columnNumber = 28输出："AB"

示例 3：

输入：columnNumber = 701输出："ZY"

示例 4：

输入：columnNumber = 2147483647输出："FXSHRXW"

提示：

• 1 <= columnNumber <= 231 - 1

class Solution {    public static String convertToTitle(int columnNumber) {        /*        A - 1        B- 2        AA 26 + 1        ZY =         */        if (columnNumber  0){            columnNumber--;            char addStr =  (char) ('A' + columnNumber % 26);            stringBuilder.append(addStr);            columnNumber /= 26;        }        return stringBuilder.reverse().toString();    }}

171. Excel 表列序号

给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。

例如：

A -> 1B -> 2C -> 3...Z -> 26AA -> 27AB -> 28 ...

示例 1:

输入: columnTitle = "A"输出: 1

示例 2:

输入: columnTitle = "AB"输出: 28

示例 3:

输入: columnTitle = "ZY"输出: 701

提示：

• 1 <= columnTitle.length <= 7
• columnTitle 仅由大写英文组成
• columnTitle 在范围 ["A", "FXSHRXW"] 内

public static int titleToNumber(String columnTitle) {        int result = 0;        int count = 0;        int pow = 0;        for (int i = columnTitle.length()-1 ; i >= 0 ; i--){            char c = (char) (columnTitle.charAt(i) + 1);            count = (c - 'A');            count *= Math.pow(26,pow++);            result  += count;        }        return result;    }//方法二：变种：因为有 26 个字母，所以相当于 26 进制，每 26 个数则向前进一位//所以每遍历一位则ans = ans * 26 + num    public static int titleToNumber2(String s) {        int ans = 0;        for(int i=0;i<s.length();i++) {            int num = s.charAt(i) - 'A' + 1;            ans = ans * 26 + num;        }        return ans;    }

190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：

输入：n = 00000010100101000001111010011100输出：964176192 (00111001011110000010100101000000)解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：n = 11111111111111111111111111111101输出：3221225471 (10111111111111111111111111111111)解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

public class Solution {    public static int reverseBits(int n) {        int result = 0;        for (int i = 0; i < 32 && n != 0; i++){            result |= (n & 1) <>>= 1;        }        return  result;11    }}

191. 位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：n = 00000000000000000000000000001011输出：3解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'

public static int hammingWeight(int n) {        int count = 0;        while(n != 0){            // -1会将最后一个1后面的0 变为1， 再&自己，会将这些1消除            n &= (n-1);            count++;        }        return count;    }

231. 2 的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

public boolean isPowerOfTwo(int n) {        if (n > 0){            //二进制表示是否只有一个1            return (n & (n - 1)) == 0;        }        return false;}

326. 3 的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

class Solution {    public boolean isPowerOfThree(int n) {        while(n > 0 && (n % 3 == 0)){            n /= 3;        }        return n == 1;    }}

342. 4的幂

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

示例 1：

输入：n = 16输出：true

示例 2：

输入：n = 5输出：false

示例 3：

输入：n = 1输出：true

两种方式：

public boolean isPowerOfFour(int n) {        while (n > 0 && n % 4 == 0){            n /= 4;        }        return n == 1;    }    public boolean isPowerOfFour1(int n) {        // 0xaaaaaaaa = 1010101010101010, 0都在偶数位上，保证n的1也在偶数位上，就是4的倍数        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;    }

258. 各位相加

示例 1:

输入: num = 38输出: 2 解释: 各位相加的过程为：38 --> 3 + 8 --> 1111 --> 1 + 1 --> 2由于 2 是一位数，所以返回 2。

示例 2:

输入: num = 0输出: 0

public static int addDigits(int num) {        if (num = 10){            int result = 0;            while (num > 0){                result += num % 10;                num /= 10;            }            num = result;        }        return num;    }

263. 丑数

丑数 就是只包含质因数 2、3 和 5 的正整数。

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：n = 6输出：true解释：6 = 2 × 3

示例 2：

输入：n = 1输出：true解释：1 没有质因数，因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。

示例 3：

输入：n = 14输出：false解释：14 不是丑数，因为它包含了另外一个质因数 7 。

public static boolean isUgly(int n) {        if (n == 1 || n == 2 || n == 3 || n == 5) return true;        while (n > 0){            if ( (n & 1) == 0){                n /= 2;            }else {                if (n % 5 == 0){                    n /= 5;                }                else if (n % 3 == 0){                    n /= 3;                }else {                    return false;                }            }            if (inUgly(n)){                return true;            }        }        return false;    }    public static boolean inUgly(int n){        return n == 1 || n == 2 || n == 3 || n == 5;    }

268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]输出：2解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]输出：2解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]输出：8解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]输出：1解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

public static int missingNumber(int[] nums) {        int sum = -nums.length;        for (int i = 0; i < nums.length; i++){            sum += nums[i];            sum -= i;        }        return  Math.abs(sum);    }

389. 找不同

给定两个字符串 s 和 t ，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例 1：

输入：s = "abcd", t = "abcde"输出："e"解释：'e' 是那个被添加的字母。

示例 2：

输入：s = "", t = "y"输出："y"

第二种方法：问题转换成求字符串中出现奇数次的字符。类似于「136. 只出现一次的数字」，使用位运算的技巧

第三种方法：求和，再相减

public char findTheDifference(String s, String t) {        int[] letterFlag = new int[26];        for (int i = 0; i < s.length(); i++){            letterFlag[s.charAt(i) - 'a']++;        }        for (int i = 0; i < t.length(); i++){            if (--letterFlag[t.charAt(i) - 'a'] < 0){                return t.charAt(i);            }        }        return ' ';    }    public char findTheDifference1(String s,String t){        int result = 0;        for (int i = 0; i < s.length(); i++){            result ^= s.charAt(i);        }        for (int i = 0; i < t.length(); i++){            result ^= s.charAt(i);        }        return (char)result;    }    public char findTheDifference2(String s, String t) {        int as = 0, at = 0;        for (int i = 0; i < s.length(); ++i) {            as += s.charAt(i);        }        for (int i = 0; i < t.length(); ++i) {            at += t.charAt(i);        }        return (char) (at - as);    }

401. 二进制手表

二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。

• 例如，下面的二进制手表读取 "4:51" 。

给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。

小时不会以零开头：

• 例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。

分钟必须由两位数组成，可能会以零开头：

• 例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。

示例 1：

输入：turnedOn = 1输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

public List readBinaryWatch(int turnedOn) {        //一共10个 二进制位 前4个代表hour,后6个代表minutes        //因此将10个二进制位遍历，如果加和为turnedOnd 并且 hour<12,minutes<60 则添加一个结果        // 10个二进制位，有pow(2,10)的可能        List list = new ArrayList();        for (int i = 0; i > 6;            //低六位            int minute = i & 63;            if (hour < 12 && minute < 60 && Integer.bitCount(i) == turnedOn) {                if (minute < 10) {                    list.add(hour + ":0" + minute);                } else {                    list.add(hour + ":" + minute);                }            }        }        return list;    }

405. 数字转换为十六进制数

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

注意:

1. 十六进制中所有字母(a-f)都必须是小写。
2. 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0'来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
3. 给定的数确保在32位有符号整数范围内。
4. 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例 1：

输入:26输出:"1a"

示例 2：

输入:-1输出:"ffffffff"

 public static String toHex(int num) {        if (num == 0) return "0";        int groupNum = 0;        StringBuilder stringBuilder = new StringBuilder();        //32位分为八组，每组4位，所以每组最大值为15，总共拼8次        for (int i = 7; i >=0; i--){            //获得每组的值            groupNum = (num >> (i * 4)) & 0x0000000f;            if (groupNum > 0 || stringBuilder.length() > 0){                char digit = groupNum < 10 ? (char) ('0' + groupNum) : (char) ('a' + groupNum - 10);                stringBuilder.append(digit);            }        }        return stringBuilder.toString();    }

461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4输出：2解释：1   (0 0 0 1)4   (0 1 0 0)       ↑   ↑上面的箭头指出了对应二进制位不同的位置。

public int hammingDistance(int x, int y) {        int n = x ^ y;        int count = 0;        while (n > 0){            n &= (n-1);            count++;        }        return count;    }

476. 数字的补数

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

• 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。

给你一个整数 num ，输出它的补数。

示例 1：

输入：num = 5输出：2解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

示例 2：

输入：num = 1输出：0解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。

public int findComplement(int num) {        //获取最高位的1        int highBit = 0;        for (int i = 1; i = 1 << i) {                //一直赋值，防止出现Integer的最大值                highBit = i;            } else {                break;            }         }        //获取mask , 用全是1的掩码 异或 num可以得到反码        //int 最大值为：0111 1111 1111 1111 1111 1111 1111 1111,所以用该值当做最大掩码        int mask = Integer.MAX_VALUE;        if (highBit < 30){            mask = (1  << (highBit + 1)) - 1;        }        return mask ^ num;    }

492. 构造矩形

作为一位web开发者， 懂得怎样去规划一个页面的尺寸是很重要的。 所以，现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：

1. 你设计的矩形页面必须等于给定的目标面积。
2. 宽度 W 不应大于长度 L ，换言之，要求 L >= W 。
3. 长度 L 和宽度 W 之间的差距应当尽可能小。

返回一个 数组 [L, W]，其中 L 和 W 是你按照顺序设计的网页的长度和宽度。

示例1：

输入: 4输出: [2, 2]解释: 目标面积是 4， 所有可能的构造方案有 [1,4], [2,2], [4,1]。但是根据要求2，[1,4] 不符合要求; 根据要求3，[2,2] 比 [4,1] 更能符合要求. 所以输出长度 L 为 2， 宽度 W 为 2。

示例 2:

输入: area = 37输出: [37,1]

 /*    从 sqrt(area) 往后遍历     */public int[] constructRectangle(int area) {        for (int i = (int) Math.sqrt(area); i >=1; i--){            if (area % i == 0){                return new int[]{area/i,i};            }        }        return new int[]{area,1};    }

504. 七进制数

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

示例 1:

输入: num = 100输出: "202"

示例 2:

输入: num = -7输出: "-10"

public String convertToBase7(int num) {        boolean negative = num  0){            stringBuilder.append(num % 7);            num /= 7;        }        if (negative){            stringBuilder.append('-');        }        return stringBuilder.reverse().toString();    }

507. 完美数

对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。

给定一个 整数 n， 如果是完美数，返回 true；否则返回 false。

示例 1：

输入：num = 28输出：true解释：28 = 1 + 2 + 4 + 7 + 141, 2, 4, 7, 和 14 是 28 的所有正因子。

示例 2：

输入：num = 7输出：false

public boolean checkPerfectNumber(int num) {        int sum = 0;        for (int i = 1; i > 1; i++){            if (num % i  == 0){                sum += i;            }        }        return sum == num;    }

598. 范围求和 II

给你一个 m x n 的矩阵 M ，初始化时所有的 0 和一个操作数组 op ，其中 ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时， M[x][y] 应该加 1。

在 执行完所有操作后 ，计算并返回 矩阵中最大整数的个数 。

示例 1:

输入: m = 3, n = 3，ops = [[2,2],[3,3]]输出: 4解释: M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。

示例 2:

输入: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]输出: 4

示例 3:

输入: m = 3, n = 3, ops = []输出: 9

public int maxCount(int m, int n, int[][] ops) {        if (ops.length == 0){            return m * n;        }        /*        求最小横、纵坐标         */        int minX = Integer.MAX_VALUE,minY = Integer.MAX_VALUE;        for (int[] op : ops){            minX = Math.min(op[0],minX);            minY = Math.min(op[1],minY);        }        if (minX == 0 || minY == 0){            return minX ==0?minY:minX;        }        return minX * minY;    }

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]输出：[8,9,9,9,0,0,0,1]

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        int carry = 0,sumNoCarry;        ListNode root = new ListNode(0);        ListNode cur = root;        while (l1 != null || l2 != null){            int x = l1 == null?0: l1.val;            int y = l2 == null?0: l2.val;;            sumNoCarry = carry;            sumNoCarry += x + y;            carry = sumNoCarry / 10;            cur.next = new ListNode(sumNoCarry % 10);            cur = cur.next;            if (l1 != null) l1 = l1.next;            if (l2 != null) l2 = l2.next;        }        if (carry != 0){            cur.next = new ListNode(carry);        }        return root.next;    }

7. 整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123输出：321

示例 2：

输入：x = -123输出：-321

示例 3：

输入：x = 120输出：21

class Solution { public static int reverse(int x) {      boolean sign = x > 0;      x = Math.abs(x);      int result = 0,a;      while (x > 0){          a = x % 10;          x /= 10;          if ((result == Integer.MAX_VALUE/10 && a < Integer.MAX_VALUE % 10) || result < Integer.MAX_VALUE/10){              result = result * 10 + a;          }else {              return 0;          }      }      return sign?result:result*-1;  }}

四、分治法108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]输出：[0,-3,9,-10,null,5]解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]输出：[3,1]解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

/** * @Date 2023/9/13 18:31 * @Author 郜宇博 */public class Solution108 {    public TreeNode sortedArrayToBST(int[] nums) {        return DFS(0,nums.length-1,nums);    }    public static TreeNode DFS(int left, int right, int[] nums){        //出口        if (left > right){            return null;        }        int mid = left + (right - left) >> 1;        int val = nums[mid];        TreeNode curRoot = new TreeNode(val);        curRoot.left = DFS(left,mid-1,nums);        curRoot.right = DFS(mid+1,right,nums);        return curRoot;    }}

五、摩尔投票法 求众数

这里我们需要理解摩尔投票中何为占多数元素，也就是元素总占比超过一个比例。\

如果是选出占比最多的一个元素，那么占比需要是大于1/2。``如果是选出占比最多的两个元素，那么各个元素占比均需要大于1/3。``如果是选出占比最多的m个元素，那么各个元素占比需要是大于1/(m + 1)。

算法思路

第一步，初始化候选人们candidates以及候选人的票数。
第二步，扫描arrays：
扫描过程中候选人的替换以及票数增减规则如下

1. 如果与某个候选人匹配，该候选人票数加1，继续扫描arrays，重新开始匹配。
2. 如果与所有候选人都不匹配，检查候选人票数，如果为0，替换该候选人，不再往下检查。
3. 如果与所有候选人都不匹配，检查候选人票数，如果不为0，继续检查一个候选人。 第三步，扫描结束以后，检查所有候选人的票数是否大于1/（candidates.length + 1）加以验证。如果大于，则候选人成立，不大于则候选人剔除掉。

从算法思路上来看，其实摩尔投票算法的核心思想就是相互抵消。
下面就是摩尔投票算法的典型代表题目。

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]输出：2

class Solution {    public int majorityElement(int[] nums) {        if (nums.length == 1) return nums[0];        /*               众数： 占据一半以上的元素               因此可以维持一个变量用于统计元素出现的次数，和假设的众数               假设每个数都有可能是众数，遇到自己就投票，变量+1，               不是自己就变量-1               变量减到0的时候设置众数为自己               原理：每个元素都投自己一票，不属于自己的就-1，由于众数的数量大于一半，因此肯定是众数获胜         */        int major = nums[0];        int count = 0;        for (int i = 0; i < nums.length; i++){            //众数是自己            if (nums[i] == major){                count++;            }            //众数不是自己            if (nums[i] != major){                if (count == 1){                    major = nums[i];                }else{                    count--;                }            }        }        return major;    }}

六、Hash存储205. 同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add"输出：true

示例 2：

输入：s = "foo", t = "bar"输出：false

示例 3：

输入：s = "paper", t = "title"输出：true

class Solution {    public static boolean isIsomorphic(String s, String t) {        if (s.length() == 1 ) return true;        HashMap map = new HashMap();        HashMap map2 = new HashMap();        for (int i = 0; i < s.length();i++){            if (map.containsKey(s.charAt(i)) && map.get(s.charAt(i)) != t.charAt(i)){                return false;            }else if (!map.containsKey(s.charAt(i))){                map.put(s.charAt(i),t.charAt(i));            }        }        for (int i = 0; i < s.length();i++){            if (map2.containsKey(t.charAt(i)) && map2.get(t.charAt(i)) != s.charAt(i)){                return false;            }else if (!map2.containsKey(t.charAt(i))){                map2.put(t.charAt(i),s.charAt(i));            }        }        return true;    }}

217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]输出：true

示例 2：

输入：nums = [1,2,3,4]输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]输出：true

class Solution {    public static boolean containsDuplicate(int[] nums) {        HashMap map = new HashMap();        if (nums.length == 1 ) return false;        for (int num : nums) {            if (!map.containsKey(num)){                map.put(num,1);            }else if (map.get(num) == 1){                return true;            }        }        return false;    }}

242. 有效的字母异位词

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

注意：若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"输出: true

示例 2:

输入: s = "rat", t = "car"输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104
• s 和 t 仅包含小写字母

两种方法，一种用hash表存储，一种用26个char[]存储

public static boolean isAnagram(String s, String t) {        if (s.length() != t.length()) return false;        HashMap map = new HashMap();        //存储s的字母出现次数        for (int i = 0; i < s.length(); i++){            if (!map.containsKey(s.charAt(i))){                map.put(s.charAt(i),1);            }else {                map.put(s.charAt(i),map.get(s.charAt(i))+1);            }        }        for (int i = 0; i < t.length(); i++){            if (!map.containsKey(t.charAt(i)) || map.get(t.charAt(i)) == 0){                return false;            }else {                map.put(t.charAt(i),map.get(t.charAt(i))-1);            }        }        return true;    }    public static boolean isAnagram1(String s, String t) {        if (s.length() != t.length()) return false;        char[] letters = new char[26];        for (int i = 0; i < s.length(); i++){            int letterIndex = s.charAt(i) - 'a';            letters[letterIndex]++;        }        for (int i = 0; i < t.length(); i++){            int letterIndex = t.charAt(i) - 'a';            if (letters[letterIndex] == 0){                return false;            }            letters[letterIndex]--;        }        return true;    }

290. 单词规律

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", s = "dog cat cat dog"输出: true

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"输出: false

public static boolean wordPattern(String pattern, String s) {        char[] chars = pattern.toCharArray();        String[] str = s.split(" ");        if (chars.length != str.length) return false;        HashMap map = new HashMap();        for (int i = 0; i < chars.length; i++) {            if (!map.containsKey(chars[i])) {                map.put(chars[i], str[i]);            } else {                if (!str[i].equals(map.get(chars[i]))) {                    return false;                }            }        }        HashMap map2 = new HashMap();        for (int i = 0; i < str.length; i++) {            if (!map2.containsKey(str[i])) {                map2.put(str[i], chars[i]);            } else {                if (chars[i] != map2.get(str[i])) {                    return false;                }            }        }        return true;    }    public static boolean wordPattern2(String pattern, String s) {        //存储字符和字符串存在的位置        HashMap