leecode刷题经验(java/C)持续更新

- 日理万妓 2024-02-22 04:33 11阅读 0赞

## 双指针 ##

### 例题1 ###

给你一个 **非严格递增排列** 的数组 `nums` ，请你\*\*[ 原地][Link 1]\*\* 删除重复出现的元素，使每个元素 **只出现一次** ，返回删除后数组的新长度。元素的 **相对顺序** 应该保持 **一致** 。然后返回 `nums` 中唯一元素的个数。

考虑 `nums` 的唯一元素的数量为 `k` ，你需要做以下事情确保你的题解可以被通过：

*  更改数组 `nums` ，使 `nums` 的前 `k` 个元素包含唯一元素，并按照它们最初在 `nums` 中出现的顺序排列。`nums` 的其余元素与 `nums` 的大小不重要。
 *  返回 `k` 。

class Solution {
        
        public int removeDuplicates(int[] nums) {
        
        /*    TreeSet<Integer> set = new TreeSet<>();
            for(int i=0;i<nums.length;i++){
                set.add(nums[i]);
            }
            Iterator<Integer> iterator = set.iterator();
            int temp=0;
            while(iterator.hasNext()){
                nums[temp] = iterator.next();
                temp++;
            }
    
            return set.size();
            */
            int p=0;
            int q = 1;
            if(nums==null||nums.length==0)return 0;
            while(q<nums.length){
        
                if(nums[p]!=nums[q]){
        
                    nums[p+1]=nums[q];
                    p++;
                }
                q++;
            }
            return p+1;
        }
    }

**复杂度分析：**

时间复杂度：**O(n)**。 空间复杂度：**O(1)**。

#### 优化思路 ####

![b29b9d59d9b516078e060f01465ccd53.png][]

*  **此数组没有重复元素,按照上面方法,每次比较`nums[p]`都不等于`nums[q]`,因此会将q指向的元素原地复制一遍,这个操作是没有必要的**
 *  **因此我们可以添加一个小判断,当`q-p>1`时,在进行复制 这样就可以避免没有必要的重复**

public int removeDuplicates(int[] nums) {
        
        if(nums == null || nums.length == 0) return 0;
        int p = 0;
        int q = 1;
        while(q < nums.length){
        
            if(nums[p] != nums[q]){
        
                if(q - p > 1){
        
                    nums[p + 1] = nums[q];
                }
                p++;
            }
            q++;
        }
        return p + 1;
    }

#### 思路如图 ####

![2cc828dd11b9ce6984a4d5f59dda3389.png][]

效率明显比使用树结构要高

### 例题2 ###

给定两个大小分别为 `m` 和 `n` 的正序（从小到大）数组 `nums1` 和 `nums2`。请你找出并返回这两个正序数组的 **中位数** 。

算法的时间复杂度应该为 `O(log (m+n))` 。

class Solution {
        
           /*public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int[] sumNums = new int[nums1.length+nums2.length];
            System.arraycopy(nums1,0,sumNums,0,nums1.length);
            System.arraycopy(nums2,0,sumNums,nums1.length,nums2.length);
            Arrays.sort(sumNums);
            if(sumNums.length%2==0){
                return (double) (sumNums[(int)sumNums.length/2-1]+sumNums[(int)sumNums.length/2])/2;
            }
            else{
                return (double)sumNums[(int)sumNums.length/2];
            }
    
        }*/
        public static double findMedianSortedArrays(int[] nums1, int[] nums2){
        
            if(nums1.length>nums2.length){
        
               //return findMedianSortedArrays(nums2,nums1);//这样占内存大
               int []temp = nums1;
               nums1 = nums2;
               nums2 = temp;
            }
            int m = nums1.length;
            int n = nums2.length;       
            int left = 0,right = m;
    
            //median1 前一部分的最大值
            //median2 后一部分的最小值
            int median1 = 0 , median2 = 0;
    
            while (left <= right){
        
                //前一部分包括nums1[0..i-1]& nums2[0..j-1];
                //后一部分包括nums1[i..m-1]& nums2[j..n-1];
                int i = ( left + right ) / 2;
                int j = ( m + n + 1 ) / 2 - i;
                
                //nums_im1,nums_i,nums_jm1,nums_j分别表示 nums1[i-1],nums1[i],nums2[j-1],nums2[j]
                int nums_im1 = (i==0? Integer.MIN_VALUE:nums1[i-1]);
                int nums_i = (i==m?Integer.MAX_VALUE:nums1[i]);
                int nums_jm1 = (j==0?Integer.MIN_VALUE:nums2[j-1]);
                int nums_j = (j==n?Integer.MAX_VALUE:nums2[j]);
    
                if(nums_im1<=nums_j){
        
                    median1 = Math.max(nums_im1,nums_jm1);
                    median2 = Math.min(nums_i,nums_j);
                    left = i + 1;
                }else{
        
                    right = i - 1;
                }
                
            }
            return ( m + n ) % 2 == 0 ? ( median1 + median2 ) / 2.0 : median1;
        }
    
    }

#### 思路 ####

使用划分的思想

[4. 寻找两个正序数组的中位数 - 力扣（LeetCode）][4. _ - _LeetCode]

### 例题2 三数之和 ###

给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足 `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请

你返回所有和为 `0` 且不重复的三元组。

\*\*注意：\*\*答案中不可以包含重复的三元组。

class Solution {
        
      public List<List<Integer>> threeSum(int[] nums) {
        
           List<List<Integer>> ans = new ArrayList();
           int len = nums.length;
           if(nums == null||len<3) return ans;
           Arrays.sort(nums);
           for(int i=0;i<len;i++){
        
               if(nums[i]>0) break;//如果当前位置数值大于零则三数之和肯定大于零(因为排序过)
               if(i>0&&nums[i]==nums[i-1]) continue;
               int L = i+1;
               int R = len-1;
               while(L<R){
          //使用了双指针的方法
                   int sum = nums[i] + nums[L] + nums[R];
                   if(sum==0){
        
                       ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                       while (L<R && nums[L]==nums[L+1]) L++;
                       while (L<R && nums[R]==nums[R-1]) R--;
                       L++;
                       R--;
    
                   }
                   else if(sum<0)L++;
                   else if(sum>0)R--;
               }
               
           }
           return ans;
      }
    }

#### 思路 ####

*  **判断数组是否为空或长度是否满足**
 *  **对数组进行排序(关键)**
 *  **遍历排序后的数组**
    
     *  先判断第一个数的大小
        
         *  如果第一个数大于0,那么后面就不需要看(因为排序过)
     *  创建左右指针L和R去寻找后面两个数(L<R)
        
         *  如果sum=0;则继续判断L和R下一个位置是否与现在数值重复,如果重复L++,R - -;跳过重复值
         *  若sum大于0,说明右指针指的数值大,则左移,R–
         *  若sum小于0,说明左指针指的数值小,则右移,L++

#### 复杂度分析 ####

*  \**时间复杂度: O(n^2),数组排序O(N log N),遍历数组O(n),双指针遍历O(n),总体O(N log N)+O(n)O(n)*
 *  **空间复杂度:O(n),对数组进行了排序**

### 例题3 四数之和 ###

给你一个由 `n` 个整数组成的数组 `nums` ，和一个目标值 `target` 。请你找出并返回满足下述全部条件且**不重复**的四元组 `[nums[a], nums[b], nums[c], nums[d]]` （若两个四元组元素一一对应，则认为两个四元组重复）：

*  `0 <= a, b, c, d < n`
 *  `a`、`b`、`c` 和 `d` **互不相同**
 *  `nums[a] + nums[b] + nums[c] + nums[d] == target`

你可以按 **任意顺序** 返回答案 。

class Solution {
        
        public List<List<Integer>> fourSum(int[] nums, int target) {
        
            List<List<Integer>> list = new ArrayList<>();
            Arrays.sort(nums);//对数组进行排序处理
            int len = nums.length;//数组长度
            if (nums == null || len < 4) return list;
    
            for (int i = 0; i < len - 3; i++) {
        
                //if (nums[i] > target) break; 错误的,如果是负数,则会漏掉其他情况
                if (i > 0 && nums[i] == nums[i - 1]) continue;
                if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;//后面肯定大于target
                if ((long)nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) continue;
                for (int j = i + 1; j < len - 2; j++) {
        
                    if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                    if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                    if ((long)nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) continue;//提上已知数值要大于int,所以应该强制转换为long
    
                    int L = j + 1, R = len - 1;
                    while (L < R) {
        
                        long sum = (long)nums[i] + nums[j] + nums[L] + nums[R];
                        if (sum == target) {
        
                            list.add(Arrays.asList(nums[i], nums[j], nums[L], nums[R]));
                            while (L < R && nums[L] == nums[L + 1]) L++;
                            while (L < R && nums[R] == nums[R - 1]) R--;
                            L++;
                            R--;
                        }
                        else if(sum<target)L++;
                        else if(sum>target)R--;
                    }
                }
    
            }
    
            return list;
        }
    }

#### 思路 ####

*  与三数之和类似,多了一个for循环

#### 复杂度分析 ####

*  **时间复杂度:O(n^3),其中n是数组的长度,排序时间O(n log n),枚举四元组的时间复杂度是O(n3),因此总时间复杂度为O(n3+n log n) = O(n^3)**
 *  **空间复杂度:O(log n) ,其中n是数组长度.空间复杂度主要取决于排序额外使用的空间,此外排序修改了输入数组`nums`,实际情况中不一定允许,因此也可以看做成使用了一个额外数组存储`nums`,空间复杂度为O(n)**

## 递归 ##

### 概念 ###

**递归是指一个函数在其定义中调用自身的过程。简单来说，就是一个函数在执行过程中调用自身来解决问题的方法。**

### 例题1 合并双链表 ###

将两个升序链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

**示例 1：**

![img][]

public class ListNode {
        
            int val;
            ListNode next;
    
            ListNode() {
        
            }
    
            ListNode(int val) {
        
                this.val = val;
            }
    
            ListNode(int val, ListNode next) {
        
                this.val = val;
                this.next = next;
            }
        }
          
    
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        
            if (list1 == null) return list2;
            if (list2 == null) return list1;
            if (list1.val < list2.val) {
        
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
        
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }

#### 解题思路 ####

**使用递归思想**

**终止条件：当两个链表都为空时，表示我们对链表已合并完成。  
如何递归：我们判断`list1` 和`list2` 头结点哪个更小，然后较小结点的 `next`指针指向其余结点的合并结果。（调用递归）**

![f85b7410fec356507c09ca8621bcf9b8.jpeg][]

![f6f9e878855b2ecb33f77e8f0c6c7851.jpeg][]

![548039a1ee22acadae73c830d81a2c8d.jpeg][]

![87045e3cd74d3244ea3d8ba6c0a5e1d4.jpeg][]

**. . . . . . . .**

**重复下去…**

直到其中一个链表为null

## 枚举 ##

**`枚举`是一种`数据类型`，用于定义一组有限的命名常量。枚举类型可以包含多个枚举成员，每个枚举成员都有一个唯一的名称和一个对应的值。`枚举成员`的值可以是整数、字符或字符串等类型。枚举类型可以用于表示一组相关的常量，比如星期几、月份、颜色等。在编程中，枚举常常用于提高代码的可读性和可维护性，以及减少错误的可能性。**

### 例题1 统计一个圆中点的数目 ###

**给你一个数组 `points` ，其中 `points[i] = [xi, yi]`，表示第 i 个点在二维平面上的坐标。多个点可能会有 相同 的坐标。**

**同时给你一个数组 `queries`，其中 `queries[j] = [xj, yj, rj]`，表示一个圆心在`(xj, yj)`且半径为`rj` 的圆。**

**对于每一个查询 `queries[j]` ，计算在第 `j` 个圆 内 点的数目。如果一个点在圆的 边界上 ，我们同样认为它在圆 内 。**

**请你返回一个数组 `answer`，其中 `answer[j]`是第`j`个查询的答案。**

**URL:https://leetcode.cn/problems/queries-on-number-of-points-inside-a-circle/**

public int[] countPoints(int[][] points, int[][] queries) {
        
    
           //枚举
            int len = queries.length;
            int[] answer = new int[len];
            for(int j = 0;j<len;j++){
        
                int temp=0;
                for(int i=0;i< points.length;i++){
        
                    double x = Math.sqrt((points[i][0]-queries[j][0])*(points[i][0]-queries[j][0])+(points[i][1]-queries[j][1])*(points[i][1]-queries[j][1]));
                }
                answer[j]=temp;
            }
            return answer;
        }
    }
    //简单优化一下,减少对包的调用和对对象的创建
    int[] answer = new int[queries.length];
            for(int j = 0;j<queries.length;j++){
        
                int temp=0;
                for(int i=0;i< points.length;i++){
        
                    int x =((points[i][0]-queries[j][0])*(points[i][0]-queries[j][0])+(points[i][1]-queries[j][1])*(points[i][1]-queries[j][1]));
                      if(x<=queries[j][2]*queries[j][2]){
        
                          temp++;
                      }
                }
                answer[j]=temp;
            }
            return answer;
        }//时间减半

#### 思路 ####

**枚举每一个情况,使用数学中圆的公式去限制条件**  
 ( c x − p x ) 2 + ( c y − p y ) 2 < = c 2 (c\_x-p\_x)^2+(c\_y-p\_y)^2<=c^2 (cx−px)2\+(cy−py)2<=c2

#### 复杂度分析 ####

*  **时间复杂度 `O(mn)`,其中m与n是points和queries的长度**
 *  **空间复杂度:`O(1)`**

\[j\]\[1\])\*(points\[i\]\[1\]-queries\[j\]\[1\]));  
if(x<=queries\[j\]\[2\]\*queries\[j\]\[2\])\{  
temp++;  
\}  
\}  
answer\[j\]=temp;  
\}  
return answer;  
\}//时间减半

### 思路
    
    **枚举每一个情况,使用数学中圆的公式去限制条件**
    $$
    (c_x-p_x)^2+(c_y-p_y)^2<=c^2
    $$
    
    ### 复杂度分析
    
    - **时间复杂度 `O(mn)`,其中m与n是points和queries的长度**
    - **空间复杂度:`O(1)`**

[Link 1]: http://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
[b29b9d59d9b516078e060f01465ccd53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/6475d3030c874447b69225e47435c677.png
[2cc828dd11b9ce6984a4d5f59dda3389.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/3dc78e5db0c64eaca1863fbbbe11e4c8.png
[4. _ - _LeetCode]: https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/258842/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/38115bad20964e00858683869a01f48d.png
[f85b7410fec356507c09ca8621bcf9b8.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/8f9ab6d52c6b4002987480491fbc452c.png
[f6f9e878855b2ecb33f77e8f0c6c7851.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/de56443b7a70419099a927f5546084bb.png
[548039a1ee22acadae73c830d81a2c8d.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/59a9fae0b26647d08df2f1d70822e487.png
[87045e3cd74d3244ea3d8ba6c0a5e1d4.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/9bb5055726f74369b5c0835d9e9198d6.png