• 《腾讯精选练习50题》专题

    1. 力扣2 两数相加

    https://leetcode.cn/problems/add-two-numbers/

    1. class Solution {
    2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    3.         ListNode p1 = l1;
    4.         ListNode p2 = l2;
    5.         ListNode dummy = new ListNode(-1);
    6.         ListNode p3 = dummy;
    7.         boolean mark = false;
    8.         while(p1 != null || p2 != null){
    9.             int num1 = 0;
    10.             int num2 = 0;
    11.             if(p1 != null){
    12.                 num1 = p1.val;
    13.                 p1 = p1.next;
    14.             }
    15.             if(p2 != null){
    16.                 num2 = p2.val;
    17.                 p2 = p2.next;
    18.             }
    19.             int sum = num1 + num2;
    20.             if(mark){
    21.                 sum++;
    22.                 mark = false;
    23.             }
    24.             if(sum >= 10){
    25.                 mark = true;
    26.                 sum -= 10;
    27.             }
    28.             p3.next = new ListNode(sum);
    29.             p3 = p3.next;
    30.         }
    31.         if(mark){
    32.             p3.next = new ListNode(1);
    33.         }
    34.         return dummy.next;
    35.     }
    36. }

    2. 力扣4 寻找两个正序数组的中位数

    https://leetcode.cn/problems/median-of-two-sorted-arrays/

    思路：

        要求时间复杂度O(log(n))，不能排序，只能二分查找。

        没什么思路，参照官方题解写的。

    1. class Solution {
    2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    3.         int n = nums1.length + nums2.length;
    4.         int k = n / 2;
    5.         if(n % 2 == 1){
    6.             return findKthMin(nums1, nums2, k + 1);
    7.         } else{
    8.             return (findKthMin(nums1, nums2, k) + findKthMin(nums1, nums2, k + 1)) / 2.0;
    9.         }
    10.     }
    11.  
    12.     public double findKthMin(int[] nums1, int[] nums2, int k){
    13.         int n1 = nums1.length;
    14.         int n2 = nums2.length;
    15.         int p1 = 0;
    16.         int p2 = 0;
    17.         
    18.         while(true){
    19.             if(p1 == n1){
    20.                 return nums2[p2 + k - 1];
    21.             }
    22.             if(p2 == n2){
    23.                 return nums1[p1 + k - 1];
    24.             }
    25.             if(k == 1){
    26.                 return Math.min(nums1[p1], nums2[p2]);
    27.             }
    28.  
    29.             int ck = k / 2;
    30.             int k1 = Math.min(p1 + ck, n1) - 1;
    31.             int k2 = Math.min(p2 + ck, n2) - 1;
    32.             if(nums1[k1] <= nums2[k2]){
    33.                 k -= k1 - p1 + 1;
    34.                 p1 = k1 + 1;
    35.             } else{
    36.                 k -= k2 - p2 + 1;
    37.                 p2 = k2 + 1;
    38.             }
    39.         }
    40.     }
    41. }

    3. 力扣5 最长回文子串

    https://leetcode.cn/problems/longest-palindromic-substring/

    思路：

        暴力求解。

    1. class Solution {
    2.     public String longestPalindrome(String s) {
    3.         String res = "";
    4.         // 遍历字符串s
    5.         for(int i = 0; i < s.length(); i++){
    6.             String str1 = getPalindrome(s, i, i);
    7.             String str2 = getPalindrome(s, i, i + 1);
    8.             String str = str1.length() > str2.length() ? str1 : str2;
    9.             res = str.length() > res.length() ? str : res;
    10.         }
    11.         return res;
    12.     }
    13.  
    14.     /**
    15.      * 获得以某两点为中心的最长子回文串
    16.      */
    17.     public String getPalindrome(String s, int left, int right){
    18.         while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
    19.             left--;
    20.             right++;
    21.         }
    22.         return s.substring(left + 1, right);
    23.     }
    24. }

    4. 力扣7 整数反转

    https://leetcode.cn/problems/reverse-integer/

    思路：

        这道题的卡点在于判断结果是否超出有符号整数范围。

    1. class Solution {
    2.     public int reverse(int x) {
    3.         int res = 0;
    4.         while(x != 0){
    5.             if(res < Integer.MIN_VALUE / 10 || res > Integer.MAX_VALUE / 10){
    6.                 return 0;
    7.             }
    8.             int curr = x % 10;
    9.             res = res * 10 + curr;
    10.             x /= 10;
    11.         }
    12.         return res;
    13.     }
    14. }

    5. 力扣8 字符串转换整数

    https://leetcode.cn/problems/string-to-integer-atoi/

    1. class Solution {
    2.     boolean b2 = true;
    3.  
    4.     public int myAtoi(String s) {
    5.         String str1 = work1(s);
    6.         String str2 = work2(str1); 
    7.         String str3 = work3(str2);
    8.         long long4 = work4(str3);
    9.         int int5 = work5(long4);
    10.         
    11.         return int5;
    12.     }
    13.  
    14.     public String work1(String s){
    15.         return s.trim();
    16.     }
    17.  
    18.     public String work2(String s){
    19.         if("".equals(s)){
    20.             return s;
    21.         }
    22.         char c = s.charAt(0);
    23.         if(c == '-'){
    24.             b2 = false;
    25.         }
    26.         if(c == '-' || c == '+'){
    27.             return s.substring(1);
    28.         }
    29.         return s;
    30.     }
    31.  
    32.     public String work3(String s){
    33.         int n = s.length();
    34.         int i = 0;
    35.         boolean firstNot0 = false;
    36.         StringBuilder sb = new StringBuilder();
    37.         while(i < n){
    38.             char c = s.charAt(i);
    39.             if(c >= '0' && c <= '9'){
    40.                 if(c > '0'){
    41.                     firstNot0 = true;
    42.                  }
    43.                 if(c != '0' || firstNot0){
    44.                     sb.append(c);
    45.                 }
    46.                 i++;
    47.             } else{
    48.                 break;
    49.             }
    50.         }
    51.         if(sb.length() == 0){
    52.             sb.append('0');
    53.         }
    54.         return sb.toString();
    55.     }
    56.  
    57.     public long work4(String s){
    58.         // 防止s超出long类型的取值范围
    59.         if(s.length() > 10){
    60.             return b2 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
    61.         }
    62.         long l = Math.abs(Long.valueOf(s));
    63.         return b2 ? l : -l;
    64.     }
    65.  
    66.     public int work5(long l){
    67.         if(l < Integer.MIN_VALUE){
    68.             l = Integer.MIN_VALUE;
    69.         }
    70.         if(l > Integer.MAX_VALUE){
    71.             l = Integer.MAX_VALUE;
    72.         }
    73.         return (int) l;
    74.     }
    75. }

    6. 力扣9 回文数

    https://leetcode.cn/problems/palindrome-number/

    思路：

        将数字高低位倒过来，如果和原来的大小相等，就是回文数。

    1. class Solution {
    2.     public boolean isPalindrome(int x) {
    3.         if(x < 0){
    4.             return false;
    5.         }
    6.         int d = x;
    7.         int sum = 0;
    8.         while(x != 0){
    9.             int curr = x % 10;
    10.             sum = sum * 10 + curr;
    11.             x /= 10;
    12.         }
    13.         return sum == d;
    14.     }
    15. }

    7. 力扣11 盛最多水的容器

    https://leetcode.cn/problems/container-with-most-water/

    思路：

        双指针法。如果知道要使用双指针法，很容易写出代码，问题是，为什么这道题可以使用双指针法？

        对撞双指针，每次都让两个指针中指向的值较小的指针移动，因为，假如指向较小值的指针固定，无论另外一个指针移动多少步，得到的盛水量都不可能大于当前盛水量。

    1. class Solution {
    2.     public int maxArea(int[] height) {
    3.         int l = 0;
    4.         int r = height.length - 1;
    5.         int max = 0;
    6.         while(l <= r){
    7.             int curr = (r - l) * Math.min(height[l], height[r]);
    8.             if(curr > max){
    9.                 max = curr;
    10.             }
    11.             if(height[l] < height[r]){
    12.                 l++;
    13.             }else{
    14.                 r--;
    15.             }
    16.         }
    17.         return max;
    18.     }
    19. }

    8. 力扣14 最长公共前缀

    https://leetcode.cn/problems/longest-common-prefix/

    1. class Solution {
    2.     public String longestCommonPrefix(String[] strs) {
    3.         boolean f = true;
    4.         StringBuilder sb = new StringBuilder();
    5.         int k = 0;
    6.         while(f){
    7.             if(k >= strs[0].length()){
    8.                 break;
    9.             }
    10.             char c = strs[0].charAt(k);
    11.             for(int i = 1; i < strs.length; i++){
    12.                 if(k >= strs[i].length() || strs[i].charAt(k) != c){
    13.                     f = false;
    14.                     break;
    15.                 }
    16.             }
    17.             if(f){
    18.                 sb.append(c);
    19.                 k++;
    20.             }
    21.         }
    22.         return sb.toString();
    23.     }
    24. }

    9. 力扣15 三数之和

    https://leetcode.cn/problems/3sum/submissions/

    思路：

        先排序。定下第一个值，剩下两个值使用对撞指针。

    1. class Solution {
    2.     public List> threeSum(int[] nums) {
    3.         int n = nums.length;
    4.         List> res = new LinkedList();
    5.         Arrays.sort(nums);
    6.         int p1 = 0;
    7.         while(p1 < n - 2){
    8.             if(p1 > 0 && nums[p1] == nums[p1 - 1]){
    9.                 p1++;
    10.                 continue;
    11.             }
    12.             int target = -nums[p1];
    13.             int p2 = p1 + 1;
    14.             int p3 = n - 1;
    15.             while(p2 < p3){
    16.                 if(p2 > p1 + 1 && nums[p2] == nums[p2 - 1]){
    17.                     p2++;
    18.                     continue;
    19.                 }
    20.                 int sum = nums[p2] + nums[p3];
    21.                 if(target > sum){
    22.                     p2++;
    23.                 } else if(target < sum){
    24.                     p3--;
    25.                 } else{
    26.                     List list = new LinkedList();
    27.                     list.add(nums[p1]);
    28.                     list.add(nums[p2]);
    29.                     list.add(nums[p3]);
    30.                     res.add(list);
    31.                     p2++;
    32.                 }
    33.             }
    34.             p1++;
    35.         }
    36.         return res;
    37.     }
    38. }

    10. 力扣16 最接近的三数之和

    https://leetcode.cn/problems/3sum-closest/

    1. class Solution {
    2.     public int threeSumClosest(int[] nums, int target) {
    3.         int n = nums.length;
    4.         Arrays.sort(nums);
    5.         int res = Integer.MAX_VALUE;
    6.         int minDert = Integer.MAX_VALUE;
    7.         int p1 = 0;
    8.         while(p1 < n - 2){
    9.             int currTarget = target - nums[p1];
    10.             int p2 = p1 + 1;
    11.             int p3 = n - 1;
    12.             while(p2 < p3){
    13.                 int sum = nums[p2] + nums[p3];
    14.                 if(sum == currTarget){
    15.                     return target;
    16.                 }
    17.                 int dert = Math.abs(sum - currTarget);
    18.                 if(dert < minDert){
    19.                     minDert = dert;
    20.                     res = sum + nums[p1];
    21.                 }
    22.                 if(sum < currTarget){
    23.                     p2++;
    24.                 }
    25.                 if(sum > currTarget){
    26.                     p3--;
    27.                 }
    28.             }
    29.             p1++;
    30.         }
    31.         return res;
    32.     }
    33. }

    11. 力扣20 有效的括号

    https://leetcode.cn/problems/valid-parentheses/

    思路：

        使用栈。

    1. class Solution {
    2.     public boolean isValid(String s) {
    3.         int n = s.length();
    4.         Stack stack = new Stack();
    5.         for(int i = 0; i < n; i++){
    6.             char c = s.charAt(i);
    7.             if(c == '(' || c == '[' || c == '{'){
    8.                 stack.push(c);
    9.             } else{
    10.                 if(stack.isEmpty()){
    11.                     return false;
    12.                 }
    13.                 char d = stack.pop();
    14.                 if(c == ')' && d != '('){
    15.                     return false;
    16.                 }
    17.                 if(c == ']' && d != '['){
    18.                     return false;
    19.                 }
    20.                 if(c == '}' && d != '{'){
    21.                     return false;
    22.                 }
    23.             }
    24.         }
    25.         return stack.isEmpty();
    26.     }
    27. }

    12. 力扣21 合并两个有序链表

    https://leetcode.cn/problems/merge-two-sorted-lists/

    1. class Solution {
    2.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    3.         ListNode dummy = new ListNode(-1);
    4.         ListNode curr = dummy;
    5.         while(list1 != null && list2 != null){
    6.             if(list1.val <= list2.val){
    7.                 curr.next = list1;
    8.                 list1 = list1.next;
    9.             } else{
    10.                 curr.next = list2;
    11.                 list2 = list2.next;
    12.             }
    13.             curr = curr.next;
    14.         }
    15.         if(list1 != null){
    16.             curr.next = list1;
    17.         }
    18.         if(list2 != null){
    19.             curr.next = list2;
    20.         }
    21.         return dummy.next;
    22.     }
    23. }

    13. 力扣23 合并K个升序链表

    https://leetcode.cn/problems/merge-k-sorted-lists/

    思路：

        把所有链表放在一个队列中，每次取出两个链表进行合并，再将合并后的链表放回队列，直到剩下一个链表。

    1. class Solution {
    2.     public ListNode mergeKLists(ListNode[] lists) {
    3.         int n = lists.length;
    4.         ListNode res = null;
    5.         Queue queue = new LinkedList();
    6.         for(int i = 0; i < n; i++){
    7.             queue.offer(lists[i]);
    8.         }
    9.         while(!queue.isEmpty()){
    10.             ListNode node1 = queue.poll();
    11.             if(queue.isEmpty()){
    12.                 res = node1;
    13.                 break;
    14.             }
    15.             ListNode node2 = queue.poll();
    16.             queue.offer(mergeTwoLists(node1, node2));
    17.         }
    18.         return res;
    19.     }
    20.  
    21.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    22.         ListNode dummy = new ListNode(-1);
    23.         ListNode curr = dummy;
    24.         while(list1 != null && list2 != null){
    25.             if(list1.val <= list2.val){
    26.                 curr.next = list1;
    27.                 list1 = list1.next;
    28.             } else{
    29.                 curr.next = list2;
    30.                 list2 = list2.next;
    31.             }
    32.             curr = curr.next;
    33.         }
    34.         if(list1 != null){
    35.             curr.next = list1;
    36.         }
    37.         if(list2 != null){
    38.             curr.next = list2;
    39.         }
    40.         return dummy.next;
    41.     }
    42. }

    14. 力扣26 删除有序数组中的重复项

    https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

    思路：

        快慢指针。

    1. class Solution {
    2.     public int removeDuplicates(int[] nums) {
    3.         int n = nums.length;
    4.         int fast = 1;
    5.         int slow = 0;
    6.         while(fast < n){
    7.             if(nums[fast] != nums[slow]){
    8.                 swap(nums, slow + 1, fast);
    9.                 slow++;
    10.             }
    11.             fast++;
    12.         }
    13.         return slow + 1;
    14.     }
    15.  
    16.     public void swap(int[] nums, int a, int b){
    17.         int t = nums[a];
    18.         nums[a] = nums[b];
    19.         nums[b] = t;
    20.     }
    21. }

    15. 力扣33 搜索旋转排序数组

    https://leetcode.cn/problems/search-in-rotated-sorted-array/

    思路：

        二分搜索。每次取中点会将区间分成两部分，一部分有序，另一部分为旋转排序数组，如果target不在有序的一边，就在另一边，以此缩小区间。

    1. class Solution {
    2.     public int search(int[] nums, int target) {
    3.         int n = nums.length;
    4.         int left = 0;
    5.         int right = n - 1;
    6.         while(left <= right){
    7.             int mid = left + (right - left) / 2;
    8.             if(target == nums[mid]){
    9.                 return mid;
    10.             }
    11.             if(nums[mid] >= nums[left]){
    12.                 if(target < nums[mid] && target >= nums[left]){
    13.                     right = mid - 1;
    14.                 } else{
    15.                     left = mid + 1;
    16.                 }
    17.             } else{
    18.                 if(target > nums[mid] && target <= nums[right]){
    19.                     left = mid + 1;
    20.                 } else{
    21.                     right = mid - 1;
    22.                 }
    23.             }
    24.         }
    25.         return -1;
    26.     }
    27. }

    16. 力扣43 字符串相乘

    https://leetcode.cn/problems/multiply-strings/

    思路：

        十分暴力的暴力法。

    1. class Solution {
    2.     public String multiply(String num1, String num2) {
    3.         int[] intnum1 = strToIntArr(num1);
    4.         int[] intnum2 = strToIntArr(num2);
    5.  
    6.         String[] resArr = new String[intnum2.length];
    7.         for(int i = 0; i < intnum2.length; i++){
    8.             resArr[i] = intArrToString(multiplyOne(intnum1, intnum2[i]), i);
    9.         }
    10.  
    11.         String res = "";
    12.         for(int i = 0; i < resArr.length; i++){
    13.             res = strAdd(res, resArr[i]);
    14.         }
    15.  
    16.         return res;
    17.     }
    18.  
    19.     public String strAdd(String num1, String num2){
    20.         int[] intnum1 = strToIntArr(num1);
    21.         int[] intnum2 = strToIntArr(num2);
    22.         int size = Math.max(intnum1.length, intnum2.length) + 1;
    23.  
    24.         int[] res = new int[size];
    25.         int tmp = 0;
    26.         for(int i = 0; i < res.length; i++){
    27.             int addnum1 = i < intnum1.length ? intnum1[i] : 0;
    28.             int addnum2 = i < intnum2.length ? intnum2[i] : 0;
    29.             int sum = addnum1 + addnum2 + tmp;
    30.             res[i] = sum % 10;
    31.             tmp = sum / 10;
    32.         }
    33.         return intArrToString(res, 0);
    34.     }
    35.  
    36.     public int[] strToIntArr(String str){
    37.         int n = str.length();
    38.         int[] res = new int[n];
    39.         for(int i = 0; i < n; i++){
    40.             res[n - 1 - i] = str.charAt(i) - '0';
    41.         }
    42.         return res; // 倒序
    43.     }
    44.  
    45.     public int[] multiplyOne(int[] num, int k){
    46.         int n = num.length;
    47.         int tmp = 0;
    48.         int[] res = new int[n + 1];
    49.         for(int i = 0; i < n; i++){
    50.             int r = num[i] * k + tmp;
    51.             res[i] = r % 10;
    52.             tmp = r / 10;
    53.         }
    54.         res[n] = tmp;
    55.         return res;
    56.     }
    57.  
    58.     public String intArrToString(int[] num, int move){
    59.         StringBuilder sb = new StringBuilder();
    60.         int start = num.length - 1;
    61.         while(start >= 0){
    62.             if(num[start] == 0){
    63.                 start--;
    64.                 continue;
    65.             }
    66.             break;
    67.         }
    68.         while(start >= 0){
    69.             sb.append(num[start]);
    70.             start--;
    71.         }
    72.         while(move > 0){
    73.             sb.append('0');
    74.             move--;
    75.         }
    76.         if(sb.isEmpty()){
    77.             sb.append('0');
    78.         }
    79.         return sb.toString();
    80.     }
    81. }

    17. 力扣46 全排列

    https://leetcode.cn/problems/permutations/

    思路：

        一眼回溯。

    1. class Solution {
    2.     List> res;
    3.     List tool;
    4.     boolean[] used;
    5.  
    6.     public List> permute(int[] nums) {
    7.         res = new LinkedList();
    8.         tool = new LinkedList();
    9.         used = new boolean[nums.length];
    10.         backtrack(nums, used);
    11.         return res;
    12.     }
    13.  
    14.     public void backtrack(int[] nums, boolean[] used){
    15.         if(tool.size() == nums.length){
    16.             res.add(new LinkedList(tool));
    17.             return;
    18.         }
    19.         for(int i = 0; i < nums.length; i++){
    20.             if(!used[i]){
    21.                 tool.add(nums[i]);
    22.                 used[i] = true;
    23.                 backtrack(nums, used);
    24.                 tool.remove(tool.size() - 1);
    25.                 used[i] = false;
    26.             }
    27.         }
    28.     }
    29. }

    18. 力扣53 最大子数组和

    https://leetcode.cn/problems/maximum-subarray/

    思路：

        一次遍历，当sum<0时，重新将sum置为0。

    1. class Solution {
    2.     public int maxSubArray(int[] nums) {
    3.         int n = nums.length;
    4.         int res = Integer.MIN_VALUE;
    5.         int sum = 0;
    6.         for(int i = 0; i < n; i++){
    7.             sum += nums[i];
    8.             res = Math.max(res, sum);
    9.             if(sum < 0){
    10.                 sum = 0;
    11.             }
    12.         }
    13.         return res;
    14.     }
    15. }

    19. 力扣54 螺旋矩阵

    https://leetcode.cn/problems/spiral-matrix/

    1. class Solution {
    2.     public List spiralOrder(int[][] matrix) {
    3.         int h = matrix.length;
    4.         int w = matrix[0].length;
    5.         int upper_bound = 0;
    6.         int lower_bound = h - 1;
    7.         int left_bound = 0;
    8.         int right_bound = w - 1;
    9.         List res = new ArrayList();
    10.         while(res.size() < h * w){
    11.             if(upper_bound <= lower_bound){
    12.                 for(int i = left_bound; i <= right_bound; i++){
    13.                     res.add(matrix[upper_bound][i]);
    14.                 }
    15.                 upper_bound++;
    16.             }
    17.             if(right_bound >= left_bound){
    18.                 for(int i = upper_bound; i <= lower_bound; i++){
    19.                     res.add(matrix[i][right_bound]);
    20.                 }
    21.                 right_bound--;
    22.             }
    23.             if(lower_bound >= upper_bound){
    24.                 for(int i = right_bound; i >= left_bound; i--){
    25.                     res.add(matrix[lower_bound][i]);
    26.                 }
    27.                 lower_bound--;
    28.             }
    29.             if(left_bound <= right_bound){
    30.                 for(int i = lower_bound; i >= upper_bound; i--){
    31.                     res.add(matrix[i][left_bound]);
    32.                 }
    33.                 left_bound++;
    34.             }
    35.         }
    36.         return res;
    37.     }
    38. }

    20. 力扣59 螺旋矩阵II

    https://leetcode.cn/problems/spiral-matrix-ii/

    1. class Solution {
    2.     public int[][] generateMatrix(int n) {
    3.         int[][] res = new int[n][n];
    4.         int left = 0;
    5.         int right = n - 1;
    6.         int top = 0;
    7.         int bottom = n - 1;
    8.         
    9.         int curr = 1;
    10.         int i = 0;
    11.         int j = -1;
    12.         while(curr <= n * n){
    13.             if(i == top){
    14.                 while(j < right){
    15.                     j++;
    16.                     res[i][j] = curr;
    17.                     curr++;
    18.                 }
    19.                 top++;
    20.             }
    21.             if(j == right){
    22.                 while(i < bottom){
    23.                     i++;
    24.                     res[i][j] = curr;
    25.                     curr++;
    26.                 }
    27.                 right--;
    28.             }
    29.             if(i == bottom){
    30.                 while(j > left){
    31.                     j--;
    32.                     res[i][j] = curr;
    33.                     curr++;
    34.                 }
    35.                 bottom--;
    36.             }
    37.             if(j == left){
    38.                 while(i > top){
    39.                     i--;
    40.                     res[i][j] = curr;
    41.                     curr++;
    42.                 }
    43.                 left++;
    44.             }
    45.         }
    46.         return res;
    47.     }
    48. }

    21. 力扣61 旋转链表

    https://leetcode.cn/problems/rotate-list/

    思路：

        链表在特定位置的断开、重连。

    1. class Solution {
    2.     public ListNode rotateRight(ListNode head, int k) {
    3.         if(head == null){
    4.             return null;
    5.         }
    6.         ListNode countNode = head;
    7.         int count = 0;
    8.         while(countNode != null){
    9.             count++;
    10.             countNode = countNode.next;
    11.         }
    12.         int step = k % count;
    13.         ListNode p1 = head;
    14.         ListNode p2 = head;
    15.         for(int i = 0; i < step; i++){
    16.             p2 = p2.next;
    17.         }
    18.         while(p2.next != null){
    19.             p1 = p1.next;
    20.             p2 = p2.next;
    21.         }
    22.         p2.next = head;
    23.         head = p1.next;
    24.         p1.next = null;
    25.         return head;
    26.     }
    27. }

    22. 力扣62 不同路径

    https://leetcode.cn/problems/unique-paths/

    思路：

        基础的动态规划。

    1. class Solution {
    2.     public int uniquePaths(int m, int n) {
    3.         int[][] dp = new int[m][n];
    4.         for(int i = 0; i < m; i++){
    5.             for(int j = 0; j < n; j++){
    6.                 if(i == 0 || j == 0){
    7.                     dp[i][j] = 1;
    8.                 } else{
    9.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    10.                 }
    11.             }
    12.         }
    13.         return dp[m - 1][n - 1];
    14.     }
    15. }

    23. 力扣70 爬楼梯

    https://leetcode.cn/problems/climbing-stairs/

    1. class Solution {
    2.     public int climbStairs(int n) {
    3.         int[] dp = new int[n];
    4.         for(int i = 0; i < n; i++){
    5.             if(i == 0){
    6.                 dp[i] = 1;
    7.             } else if(i == 1){
    8.                 dp[i] = 2;
    9.             } else{
    10.                 dp[i] = dp[i - 1] + dp[i - 2];
    11.             }
    12.         }
    13.         return dp[n - 1];
    14.     }
    15. }

    24. 力扣78 子集

    https://leetcode.cn/problems/subsets/

    1. class Solution {
    2.     List> res;
    3.     List track;
    4.  
    5.     public List> subsets(int[] nums) {
    6.         res = new LinkedList();
    7.         track = new LinkedList();
    8.         backtrack(nums, 0);
    9.         return res;
    10.     }
    11.  
    12.     public void backtrack(int[] nums, int start){
    13.         res.add(new LinkedList(track));
    14.         for(int i = start; i < nums.length; i++){
    15.             track.add(nums[i]);
    16.             backtrack(nums, i + 1);
    17.             track.remove(track.size() - 1);
    18.         }
    19.     } 
    20. }

    25. 力扣88 合并两个有序数组

    https://leetcode.cn/problems/merge-sorted-array/

    1. class Solution {
    2.     public void merge(int[] nums1, int m, int[] nums2, int n) {
    3.         int p1 = m - 1;
    4.         int p2 = n - 1;
    5.         int curr = m + n - 1;
    6.         while(curr >= 0){
    7.             if(p1 < 0){
    8.                 nums1[curr] = nums2[p2];
    9.                 p2--;
    10.                 curr--;
    11.                 continue;
    12.             }
    13.             if(p2 < 0){
    14.                 nums1[curr] = nums1[p1];
    15.                 p1--;
    16.                 curr--;
    17.                 continue;
    18.             }
    19.             if(nums1[p1] >= nums2[p2]){
    20.                 nums1[curr] = nums1[p1];
    21.                 p1--;
    22.             } else{
    23.                 nums1[curr] = nums2[p2];
    24.                 p2--;
    25.             }
    26.             curr--;
    27.         }
    28.     }
    29. }

    26. 力扣89 格雷编码

    https://leetcode.cn/problems/gray-code/

    思路：

        没有思路，背公式。

    1. class Solution {
    2.     public List grayCode(int n) {
    3.         // 第i位格雷码：i / 2 ^ i
    4.         int pro = 1;
    5.         for(int i = 0; i < n; i++){
    6.             pro *= 2;
    7.         }
    8.         List res = new LinkedList();
    9.         for(int i = 0; i < pro; i++){
    10.             res.add(i / 2 ^ i);
    11.         }
    12.         return res;
    13.     }
    14. }

    27. 力扣104 二叉树的最大深度

    https://leetcode.cn/problems/maximum-depth-of-binary-tree/

    1. class Solution {
    2.     public int maxDepth(TreeNode root){
    3.         if(root == null){
    4.             return 0;
    5.         }
    6.         return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    7.     }
    8. }

    28. 力扣121 买卖股票的最佳时机

    https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

    思路：

        买卖股票的一系列题目都可以使用有限状态机来求解，对这道题来说有点小题大做。

    1. class Solution {
    2.     public int maxProfit(int[] prices) {
    3.         int n = prices.length;
    4.         int[] dp = new int[2];
    5.         // 0: 不持有, 1: 持有
    6.         dp[0] = 0;
    7.         dp[1] = -prices[0];
    8.         for(int i = 1; i < n; i++){
    9.             dp[0] = Math.max(dp[0], dp[1] + prices[i]);
    10.             // 只许买一次, 所以是-prices[i]而不是dp[0]-prices[i]
    11.             dp[1] = Math.max(dp[1], -prices[i]);
    12.         }
    13.         return dp[0];
    14.     }
    15. }

    29. 力扣122 买卖股票的最佳时机II

    https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

    1. class Solution {
    2.     public int maxProfit(int[] prices) {
    3.         int n = prices.length;
    4.         int[] dp = new int[2];
    5.         dp[0] = 0;
    6.         dp[1] = - prices[0];
    7.         for (int i = 1; i < n; i++) {
    8.             dp[0] = Math.max(dp[0], dp[1] + prices[i]);
    9.             dp[1] = Math.max(dp[1], dp[0] - prices[i]);
    10.         }
    11.         return dp[0];
    12.     }
    13. }

    30. 力扣124 二叉树中的最大路径和

    https://leetcode.cn/problems/binary-tree-maximum-path-sum/

    思路：

        遍历二叉树时，对每一个结点要做两件事：

        1. 计算以该结点为路径的一个端点的最大路径和，供其父结点进行计算。

        2. 计算以该结点为根结点的最大路径和，做全局比较。

        比较以每个结点为根结点的最大路径和，得到全局最大路径和。

    1. class Solution {
    2.     int res;
    3.  
    4.     public int maxPathSum(TreeNode root) {
    5.         res = Integer.MIN_VALUE;
    6.         getMaxPathSum(root);
    7.         return res;
    8.     }
    9.  
    10.     public int getMaxPathSum(TreeNode root){
    11.         if(root == null){
    12.             return 0;
    13.         }
    14.         int curr = root.val;
    15.         int left = getMaxPathSum(root.left);
    16.         int right = getMaxPathSum(root.right);
    17.         int maxPath = Math.max(Math.max(left, right), 0) + curr;
    18.         int currMax = Math.max(curr + left + right, maxPath);
    19.         if(currMax > res){
    20.             res = currMax;
    21.         }
    22.         return maxPath;
    23.     }
    24. }

    31. 力扣136 只出现一次的数字

    https://leetcode.cn/problems/single-number/

    思路：

        一个数字与0做异或操作，得到它本身，与本身做异或操作，得0。

    1. class Solution {
    2.     public int singleNumber(int[] nums) {
    3.         int res = 0;
    4.         for(int i : nums){
    5.             res ^= i;
    6.         }
    7.         return res;
    8.     }
    9. }

    32. 力扣141 环形链表

    https://leetcode.cn/problems/linked-list-cycle/

    1. class Solution {
    2.     public boolean hasCycle(ListNode head) {
    3.         if(head == null || head.next == null){
    4.             return false;
    5.         }
    6.         ListNode p1 = head;
    7.         ListNode p2 = head;
    8.         while(p1 != null && p1.next != null){
    9.             p1 = p1.next.next;
    10.             p2 = p2.next;
    11.             if(p1 == p2){
    12.                 return true;
    13.             }
    14.         }
    15.         return false;
    16.     }
    17. }

    33. 力扣142 环形链表II

    https://leetcode.cn/problems/linked-list-cycle-ii/

    思路：

        这里是使用哈希表解答。

        官方题解有另一种很巧妙的方法，使用快慢指针，两指针相遇时，从相遇点和起点各启动一个新的指针，两个新指针相遇的点就是进入环形链表的点。

    1. public class Solution {
    2.     public ListNode detectCycle(ListNode head) {
    3.         Set memo = new HashSet();
    4.         while(head != null){
    5.             if(memo.contains(head)){
    6.                 return head;
    7.             }
    8.             memo.add(head);
    9.             head = head.next;
    10.         }
    11.         return null;
    12.     }
    13. }

    34. 力扣146 LRU缓存

    https://leetcode.cn/problems/lru-cache/

    思路：

        使用哈希表+双向链表。

    1. class ListNode{
    2.     int key;
    3.     int val;
    4.     ListNode pre;
    5.     ListNode next;
    6.     public ListNode(int key, int val){
    7.         this.key = key;
    8.         this.val = val;
    9.     }
    10. }
    11.  
    12. class LRUCache {
    13.     int capacity;
    14.     Map map = new HashMap();
    15.     ListNode head = new ListNode(0, 0);
    16.     ListNode tail = new ListNode(0, 0);
    17.  
    18.     public LRUCache(int capacity) {
    19.         this.capacity = capacity;
    20.         head.next = tail;
    21.         tail.pre = head;
    22.     }
    23.     
    24.     public int get(int key) {
    25.         if(map.containsKey(key)){
    26.             ListNode node = map.get(key);
    27.             moveToFirst(node);
    28.             return node.val;
    29.         }
    30.         return -1;
    31.     }
    32.     
    33.     public void put(int key, int value) {
    34.         if(map.containsKey(key)){
    35.             ListNode node = map.get(key);
    36.             node.val = value;
    37.             moveToFirst(node);
    38.         } else{
    39.             if(map.size() == capacity){
    40.                 deleteLast();
    41.             }
    42.             ListNode newNode = new ListNode(key, value);
    43.             ListNode temp = head.next;
    44.             head.next = newNode;
    45.             newNode.pre = head;
    46.             newNode.next = temp;
    47.             temp.pre = newNode;
    48.             map.put(newNode.key, newNode);
    49.         }
    50.     }
    51.  
    52.     public void deleteLast(){
    53.         ListNode last = tail.pre;
    54.         last.pre.next = tail;
    55.         tail.pre = last.pre;
    56.         map.remove(last.key);
    57.     }
    58.  
    59.     public void moveToFirst(ListNode node){
    60.         node.pre.next = node.next;
    61.         node.next.pre = node.pre;
    62.         ListNode temp = head.next;
    63.         head.next = node;
    64.         node.pre = head;
    65.         node.next = temp;
    66.         temp.pre = node;
    67.     }
    68. }

    35. 力扣148 排序链表

    https://leetcode.cn/problems/sort-list/

    思路：

        将链表分割成n个升序链表，依次合并。

    1. class Solution {
    2.     public ListNode sortList(ListNode head) {
    3.         Queue queue = new LinkedList();
    4.         queue.offer(head);
    5.         ListNode pre = new ListNode(Integer.MIN_VALUE, head);
    6.         while(head != null){
    7.             if(head.val < pre.val){
    8.                 queue.offer(head);
    9.                 pre.next = null;
    10.             }
    11.             pre = head;
    12.             head = head.next;
    13.         }
    14.         while(!queue.isEmpty()){
    15.             ListNode node1 = queue.poll();
    16.             if(queue.isEmpty()){
    17.                 return node1;
    18.             } else{
    19.                 ListNode node2 = queue.poll();
    20.                 queue.offer(mergeTwoLists(node1, node2));
    21.             }
    22.         }
    23.         return null;
    24.     }
    25.  
    26.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    27.         ListNode dummy = new ListNode(-1);
    28.         ListNode curr = dummy;
    29.         while(list1 != null && list2 != null){
    30.             if(list1.val <= list2.val){
    31.                 curr.next = list1;
    32.                 list1 = list1.next;
    33.             } else{
    34.                 curr.next = list2;
    35.                 list2 = list2.next;
    36.             }
    37.             curr = curr.next;
    38.         }
    39.         if(list1 != null){
    40.             curr.next = list1;
    41.         }
    42.         if(list2 != null){
    43.             curr.next = list2;
    44.         }
    45.         return dummy.next;
    46.     }
    47. }

    36. 力扣155 最小栈

    https://leetcode.cn/problems/min-stack/

    思路：

        维护两个栈，一个记录真实数值，另一个记录最小值。

    1. class MinStack {
    2.     Stack stack;
    3.     Stack minStack;
    4.  
    5.     public MinStack() {
    6.         stack = new Stack();
    7.         minStack = new Stack();
    8.     }
    9.     
    10.     public void push(int val) {
    11.         stack.push(val);
    12.         minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek()));
    13.     }
    14.     
    15.     public void pop() {
    16.         stack.pop();
    17.         minStack.pop();
    18.     }
    19.     
    20.     public int top() {
    21.         return stack.peek();
    22.     }
    23.     
    24.     public int getMin() {
    25.         return minStack.peek();
    26.     }
    27. }

    37. 力扣160 相交链表

    https://leetcode.cn/problems/intersection-of-two-linked-lists/

    思路：

        使用两个指针分别从两个链表的头部出发，当指针走到链表尾部时，移到另一个链表的头部，两指针相遇点即链表交点。

    1. class Solution {
    2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    3.         ListNode p1 = headA;
    4.         ListNode p2 = headB;
    5.         while(p1 != p2){
    6.             if(p1 != null){
    7.                 p1 = p1.next;
    8.             } else{
    9.                 p1 = headB;
    10.             }
    11.             if(p2 != null){
    12.                 p2 = p2.next;
    13.             } else{
    14.                 p2 = headA;
    15.             }
    16.         }
    17.         return p1;
    18.     }
    19. }

    38. 力扣169 多数元素

    https://leetcode.cn/problems/majority-element/

    1. class Solution {
    2.     public int majorityElement(int[] nums) {
    3.         int n = nums.length;
    4.         Map memo = new HashMap();
    5.         for(int i = 0; i < n; i++){
    6.             memo.put(nums[i], memo.getOrDefault(nums[i], 0) + 1);
    7.             if(memo.get(nums[i]) > n / 2){
    8.                 return nums[i];
    9.             }
    10.         }
    11.         return -1;
    12.     }
    13. }

    39. 力扣206 反转链表

    https://leetcode.cn/problems/reverse-linked-list/

    1. class Solution {
    2.     public ListNode reverseList(ListNode head) {
    3.         if(head == null || head.next == null){
    4.             return head;
    5.         }
    6.         ListNode node = reverseList(head.next);
    7.         head.next.next = head;
    8.         head.next = null;
    9.         return node;
    10.     }
    11. }

    40. 力扣215 数组中的第K个最大元素

    https://leetcode.cn/problems/kth-largest-element-in-an-array/

    思路：

        没有梦想，用的人家的轮子。

    1. class Solution {
    2.     public int findKthLargest(int[] nums, int k) {
    3.         int n = nums.length;
    4.         PriorityQueue minHeap = new PriorityQueue();
    5.         for(int i = 0; i < n; i++){
    6.             minHeap.offer(nums[i]);
    7.             if(minHeap.size() > k){
    8.                 minHeap.poll();
    9.             }
    10.         }
    11.         return minHeap.poll();
    12.     }
    13. }

    41. 力扣217 存在重复元素

    https://leetcode.cn/problems/contains-duplicate/

    1. class Solution {
    2.     public boolean containsDuplicate(int[] nums) {
    3.         Set set = new HashSet();
    4.         for(int i : nums){
    5.             if(set.contains(i)){
    6.                 return true;
    7.             }
    8.             set.add(i);
    9.         }
    10.         return false;
    11.     }
    12. }

    42. 力扣230 二叉搜索树中第K小的元素

    https://leetcode.cn/problems/kth-smallest-element-in-a-bst/

    思路：

        深度优先遍历，在中序位置计数。

    1. class Solution {
    2.     int count = 0;
    3.     int res = 0;
    4.  
    5.     public int kthSmallest(TreeNode root, int k) {
    6.         traverse(root, k);
    7.         return res;
    8.     }
    9.  
    10.     public void traverse(TreeNode root, int k){
    11.         if(root == null){
    12.             return;
    13.         }
    14.         traverse(root.left, k);
    15.         count++;
    16.         if(count == k){
    17.             res = root.val;
    18.         }
    19.         traverse(root.right, k);
    20.     }
    21. }

    43. 力扣231 2的幂

    https://leetcode.cn/problems/power-of-two/

    思路：

        位运算，2的幂只有一位是1，其他位都是0，2的幂减一的每个位都是1，且比2的幂少一位，两者做与运算得0。

    1. class Solution {
    2.     public boolean isPowerOfTwo(int n) {
    3.         return n > 0 && (n & (n - 1)) == 0;
    4.     }
    5. }

    44. 力扣235 二叉搜索树的最近公共祖先

    https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

    思路：

        公共祖先比一个结点的值大，比另一个结点的值小，或者就是两个结点之一。从根结点向下遍历即可。

    1. class Solution {
    2.     TreeNode mark;
    3.  
    4.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    5.         traverse(root, p.val, q.val);
    6.         return mark;
    7.     }
    8.  
    9.     public void traverse(TreeNode root, int p, int q){
    10.         if(root == null){
    11.             return;
    12.         }
    13.         if(p < root.val && q < root.val){
    14.             traverse(root.left, p, q);
    15.         } else if(p > root.val && q > root.val){
    16.             traverse(root.right, p, q);
    17.         } else{
    18.             mark = root;
    19.         }
    20.     }
    21. }

    45. 力扣236 二叉树的最近公共祖先

    https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

    思路：

        对每个结点来说，在其左子树上找p或q，然后再在其右子树上找p或q，如果在一棵子树上找到了p，在另一棵子树上找到了q，说明该结点是最近公共祖先。如果在同一棵子树上找到了p和q，说明该结点是公共祖先，但不是最近的，再去判断找到p和q的子树的根结点是否是最近公共祖先。

    1. class Solution {
    2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    3.         return traverse(root, p, q);
    4.     }
    5.  
    6.     public TreeNode traverse(TreeNode root, TreeNode p, TreeNode q){
    7.         if(root == null){
    8.             return root;
    9.         }
    10.         if(root == p || root == q){
    11.             return root;
    12.         }
    13.         TreeNode left = traverse(root.left, p, q);
    14.         TreeNode right = traverse(root.right, p, q);
    15.         if(left != null && right != null){
    16.             return root;
    17.         } else{
    18.             return left != null ? left : right;
    19.         }
    20.     }
    21. }

    46. 力扣237 删除链表中的结点

    https://leetcode.cn/problems/delete-node-in-a-linked-list/

    思路：

        官方题解不讲武德，是在下输了。

    1. class Solution {
    2.     public void deleteNode(ListNode node) {
    3.         node.val = node.next.val;
    4.         node.next = node.next.next;
    5.     }
    6. }

    47. 力扣238 除自身以外数组的乘积

    https://leetcode.cn/problems/product-of-array-except-self/

    思路：

        正序计算累乘积数组，再倒序计算累乘积数组，结果数组的每个元素一定是两个累乘积数组中的元素的乘积。

    1. class Solution {
    2.     public int[] productExceptSelf(int[] nums) {
    3.         int n = nums.length;
    4.         int[] arr1 = new int[n + 1];
    5.         int[] arr2 = new int[n + 1];
    6.         arr1[0] = 1;
    7.         for(int i = 1; i < n + 1; i++){
    8.             arr1[i] = arr1[i - 1] * nums[i - 1];
    9.         }
    10.         arr2[n] = 1;
    11.         for(int j = n - 1; j >= 0; j--){
    12.             arr2[j] = arr2[j + 1] * nums[j];
    13.         }
    14.         int[] answer = new int[n];
    15.         for(int k = 0; k < n; k++){
    16.             answer[k] = arr1[k] * arr2[k + 1];
    17.         }
    18.         return answer;
    19.     }
    20. }

    48. 力扣292 Nim游戏

    https://leetcode.cn/problems/nim-game/

    1. class Solution {
    2.     public boolean canWinNim(int n) {
    3.         return n % 4 != 0;
    4.     }
    5. }

    49. 力扣344 反转字符串

    https://leetcode.cn/problems/reverse-string/

    1. class Solution {
    2.     public void reverseString(char[] s) {
    3.         int n = s.length;
    4.         int mid = n / 2;
    5.         for(int i = 0; i <= mid - 1; i++){
    6.             swap(s, i, n - i - 1);
    7.         }
    8.     }
    9.  
    10.     public void swap(char[] s, int a, int b){
    11.         char temp = s[a];
    12.         s[a] = s[b];
    13.         s[b] = temp;
    14.     }
    15. }

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

    https://leetcode.cn/problems/reverse-words-in-a-string-iii/

    1. class Solution {
    2.     public String reverseWords(String s) {
    3.         String[] ss = s.split(" ");
    4.         int n = ss.length;
    5.         for(int i = 0; i < n; i++){
    6.             ss[i] = reverseString(ss[i]);
    7.         }
    8.         StringBuilder sb = new StringBuilder();
    9.         for(int i = 0; i < n; i++){
    10.             if(i != 0){
    11.                 sb.append(" ");
    12.             }
    13.             sb.append(ss[i]);
    14.         }
    15.         return sb.toString();
    16.     }
    17.  
    18.     public String reverseString(String s) {
    19.         char[] cs = s.toCharArray();
    20.         int n = cs.length;
    21.         int mid = n / 2;
    22.         for(int i = 0; i <= mid - 1; i++){
    23.             swap(cs, i, n - i - 1);
    24.         }
    25.         return new String(cs);
    26.     }
    27.  
    28.     public void swap(char[] cs, int a, int b){
    29.         char temp = cs[a];
    30.         cs[a] = cs[b];
    31.         cs[b] = temp;
    32.     }
    33. }

  • 相关阅读:
    Vue3无缝滚动----vue3-seamless-scroll
    stl 输入输出流
    11、综合应用案例
    Python定义函数
    归并排序（10分）
    python代码中激活Anaconda虚拟环境并执行
    HTML之如何下载网页中的音频(二)
    ctf-pikachu-xxe
    [附源码]SSM计算机毕业设计中小型便民药店管理论文JAVA
    03-Swing程序设计
  • 原文地址：https://blog.csdn.net/qq_42082161/article/details/128059263