day01

合并两个有序数组
1
2
3
4
5
6
7
8
9
10
11
12
/***
 * 给你两个按 非递减顺序 排列的整数数组 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 中的元素。
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class code1 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        while(n+m>0){
            //当n1 和 n2 都有元素时
            if(n!=0&&m!=0){
                //判断n1 n2 最后一个元素的大小 将大的那个 添加到最后一个位置
                nums1[n+m-1] = nums1[m-1]>nums2[n-1]?nums1[--m]:nums2[--n];
            }//当只有n2有元素时 将n2 的元素添加到n1
            else if(m==0){
                //将n2中的元素移到n1
                nums1[n+m-1] = nums2[--n];
            }//当只有n1有元素时
            else{
                //排好了
                return;
            }
    }
}
移除元素
1
2
3
4
5
6
7
8
/**
 * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元
 * 素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
 * 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
 * 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。
 * nums 的其余元素和 nums 的大小并不重要。
 * 返回 k。
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class code2 {

    public int removeElement(int[] nums, int val) {
        //慢指针
        int slow = 0;
        //遍历长度
        int len = nums.length;
        for(int fast = 0;fast < len;fast++){
            //当当前元素不是该目标元素 将他添加到慢指针的位置
             if(nums[fast]!=val){
                 nums[slow++] = nums[fast];
             }
        }
        return slow;
    }
}
删除有序数组中的重复项
1
2
3
4
5
6
7
8
9
10
11
/**
 * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，
 * 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
 * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
 * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。
 * nums 的其余元素与 nums 的大小不重要。
 * 返回 k
 * 输入：nums = [0,0,1,1,1,2,2,3,3,4]
 * 输出：5, nums = [0,1,2,3,4]
 * 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
 */
1
2
3
4
5
6
7
8
9
10
11
12
public class code3 {
    public int removeDuplicates(int[] nums) {
        int slow = 0;
        int len = nums.length;
        for(int fast = 0;fast<len;fast++){
            if(nums[slow]!=nums[fast]){
                num[++slow] = nums[fast];
            }
        }
        return slow+1;
    }
}
删除有序数组中的重复项
1
2
3
4
5
6
7
8
/**
 * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
 * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 * 输入：nums = [0,0,1,1,1,1,2,3,3]
 * 输出：7, nums = [0,0,1,1,2,3,3]
 * 解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。
 * 不需要考虑数组中超出新长度后面的元素。
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package com.orchids.leetcode_review.day01;

/**
 * @ Author qwh
 * @ Date 2024/7/15 9:36
 */
public class code4 {
    public int removeDuplicates(int[] nums) {
        //从第三个元素开始前两个元素肯定不用删除
        int slow = 2;
        int len = nums.length;
        for (int fast = 2; fast < len; fast++) {
            if (nums[fast]!=nums[slow-2]){
                nums[slow++] = nums[fast];
            }
        }
        return slow;

    }
}

多数元素
1
2
3
4
5
6
/**
     * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素
     */
//    [2,2,1,1,1,2,2]
    // 1 1 -1 -1 1 1
1
2
3
4
5
6
7
8
9
10
11
12
public int majorityElement(int[] nums) {
    int count = 0;
    Integer result = null;
    for (int num : nums) {
        if (count == 0) {
            result = num;
        }
        count += (result == num) ? 1 : -1;
    }
    return result;
    //将数组排序 在中间值就是 多数元素
}
轮转数组
1
2
3
4
5
6
7
/**
 * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
 * @param nums
 * @param k
 */
//[1,2,3,4,5,6,7]
//[5,6,7,1,2,3,4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void rotate(int[] nums, int k) {
    int len = nums.length;
    k = k% len;
    //整个反转
    reverse(nums,0,len-1);
    //前半部分反转
    reverse(nums,0,k-1);
    //后半部分反转
    reverse(nums,k,len-1);

}
public void reverse(int[] nums,int i,int j){
    while (i<j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
        j--;
    }
}

day02