2024/12月算法刷题

发表于 | 分类于

刷的是leetcode上面的题

https://leetcode.cn/studyplan/top-interview-150/

数组/字符串

合并两个有序数组

错误的尝试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] r = nums1;
        int i=0;
        for(int x=0;x<m;x=x+1){
            for(int y=0;y<n;y=y+1){
                if(nums1[x] <= nums2[y]){
                    continue;
                }
                else{
                    for(int z=m;z>x;z=z-1){
                        r[z]=r[z-1];
                    }
                    r[x] = nums2[y];
                    i++;
                }
            }
        }
        for (int j=i;j<=0;j--){
            if(n==0||m == 0){
                break;
            }
            r[m-j]=nums2[n-j];
        }
    }
}

循环过于复杂，多余的数组，未能得到正确的结果。

正确的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1;
        int j = n-1;
        int k = m+n-1;
        while (i>=0 && j>=0){
            if(nums1[i]<=nums2[j]){
                nums1[k--] = nums2[j--];
            }
            else{
                nums1[k--] = nums1[i--];
            }
        }
        //防止nums2还没写入进去
        while(j>=0){
            nums1[k--] = nums2[j--];
        }
    }
}

移除元素

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int index = 0; // 用于存放非 val 的元素
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) { // 保留非 val 元素
                nums[index] = nums[i];
                index++;
            }
        }
        return index; // 返回修改后数组的长度
    }
}

删除有序数组中的重复项

错误的尝试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 0;
        for(int i = 0;i<nums.length;i++){
            for(int j = 0;j<nums.length-1;j++){
                if(nums[j] != nums[i]){
                    nums[index]=nums[i];
                    index++;
                }
            }
        }
        return index;
    }
}

错误使用了双循环，导致index的值多次错误增加，下面是双循环的正确写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 0;
        for(int i = 0;i<nums.length;i++){
            boolean flag = false;
            for(int j = 0;j<i;j++){
                if(nums[j] == nums[i]){
                    flag = true;
                    break;
                }
            }
            if(flag == false){
                nums[index] = nums[i];
                index++;
            }
        }
        return index;
    }
}

或者本题有更简单的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int index = 1; // 第一个元素默认已在数组中
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) { // 如果当前元素与前一个元素不相等
                nums[index] = nums[i]; // 更新数组
                index++; // 增加新位置
            }
        }
        return index; // 返回去重后的数组长度
    }
}

删除有序数组中的重复项 II

错误的尝试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 0;
        int flag = 0;
        for(int i = 0;i<nums.length;i++){
            if(flag<2){
                if(nums[index] == nums[i]){
                    flag++;
                }
                nums[index] = nums[i];
                index++;
            }
            else{
                if(nums[index] == nums[i]){
                    continue;
                }
                else{
                    flag = 0;
                    nums[index] = nums[i];
                    index++;
                }
            }
        }
        return index;
    }
}

image-20241205205244739

第一个能过第二个过不了。。。。

因为flag的更新不及时，如果刚好是两个元素则会跳过下一组，需要单独将计数器逻辑放到一起，后面根据计数器的值来进行值的存放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int removeDuplicates(int[] nums) {
                if (nums.length == 0) return 0;  // 如果数组为空，返回0
        
        int index = 1;  // 从第二个元素开始
        int flag = 0;  // 记录当前元素出现的次数
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                flag++;  // 如果当前元素和前一个元素相同，计数器加1
            } else {
                flag = 0;  // 否则，重置计数器
            }
            
            if (flag < 2) {  // 如果该元素的计数不超过2个，允许保留
                nums[index] = nums[i];  // 把该元素放到当前index位置
                index++;  // 移动到下一个位置
            }
        }
        return index;  // 返回修改后的数组的长度
    }
}

多数元素

一遍过

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int majorityElement(int[] nums) {
        int flag = -1;
        int count = 1;
        int max = 1;
        for(int i = 0;i<nums.length;i++){
            for(int j = i+1;j<nums.length;j++){
                if(nums[i] == nums[j]){
                    count++;
                }
            }
            if(count>max){
                flag = nums[i];
                max = count;
            }
            count = 1;
        }
        return flag;
    }
}

提交过了又修改了一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int majorityElement(int[] nums) {
        int flag = -1;
        if(nums.length==1){
            flag = nums[0];
        }
        int count = 1;
        int max = 1;
        for(int i = 0;i<nums.length;i++){
            for(int j = i+1;j<nums.length;j++){
                if(nums[i] == nums[j]){
                    count++;
                }
                if(count>1024){
                    flag = nums[i];
                    break;
                }
            }
            if(count>max){
                flag = nums[i];
                max = count;
            }
            count = 1;
        }
        return flag;
    }
}

image-20241206144413849

时间太慢了

gpt写一个优化后的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0], count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    candidate = nums[i];
                    count = 1;
                }
            }
        }
        return candidate;
    }
}

投票算法，第一次听说。投票算法能够确保返回的候选元素是多数元素，前提是数组中确实有一个出现次数超过一半的元素。算法本质上通过频繁更新候选元素的方式，最终能够选出正确的多数元素。极速。

image-20241206144812464

轮转数组

错误的尝试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void rotate(int[] nums, int k) {
        if(nums.length==1){
            ;
        }
        else{
            int[] tmp = new int[k];
            for(int j = k-1;j>=0;j--){
                tmp[k-1-j] = nums[nums.length-1-j];
            }
            for(int i = nums.length-1;i>=k;i--){
                nums[i] = nums[i-k]; 
            }
            for(int a = 0;a<k;a++){
                nums[a]=tmp[a];
            }
        }
    }
}

image-20241206162855333

如果数组的长度小于位移的长度就会因为数组索引变成负数的情况出问题，这时候需要将k置为小于数组长度，k%length得到余数就可以解决这个问题，因为超过的元素会轮回回来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public void rotate(int[] nums, int k) {
        if(nums.length==1){
            ;
        }
        else{
            //修改
            k = k % nums.length;
            int[] tmp = new int[k];
            for(int j = k-1;j>=0;j--){
                tmp[k-1-j] = nums[nums.length-1-j];
            }
            for(int i = nums.length-1;i>=k;i--){
                nums[i] = nums[i-k]; 
            }
            for(int a = 0;a<k;a++){
                nums[a]=tmp[a];
            }
        }
    }
}

image-20241206163200521

买卖股票的最佳时机

寻找最低的值，在最低的值后寻找最高的值。

错误的尝试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxProfit(int[] prices) {
        int flag = prices.length-1;
        for(int i = prices.length-2;i>=0;i--){
            if(prices[i]<prices[flag]){
                flag = i ;
            }
        }
        if(flag == prices.length-1){
            for(int i = prices.length-2;i>=0;i--){
                if(prices[i]<prices[i+1]){
                    flag = i;
                }
            }
        }
        int index = prices[flag];
        for(int j = flag;j<prices.length;j++){
            if(prices[j]>index){
                index = prices[j];
            }
        }
        return index-prices[flag];
    }
}

正确解法：设置两个变量，最小值以及最大利润，遍历整个数组，根据条件更新值。因为是先买入再卖出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0; // 如果数据无效或不足以计算利润，返回 0
        }

        int minPrice = Integer.MAX_VALUE; // 当前最小价格
        int maxProfit = 0; // 最大利润

        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price; // 更新最小价格
            } else {
                maxProfit = Math.max(maxProfit, price - minPrice); // 计算当前利润，并更新最大利润
            }
        }

        return maxProfit;
    }
}

Integer.MAX_VALUE 是 Java 中整数类型的最大值（231−1=21474836472^{31} - 1 = 2147483647231−1=2147483647）。

在遍历 prices 数组时，任何实际价格都比 Integer.MAX_VALUE 小，因此第一次遇到的价格会更新 minPrice。

买卖股票的最佳时机 II

上帝视角，在跌之前卖出，哈哈哈哈，没有上帝视角永远没有最佳时机，所以看淡得失。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        int flag = 0;
        for(int i=0;i<prices.length-1;i++){
            if(prices[i+1]<prices[i]&&flag == 0){
                minPrice = prices[i+1];
                flag = 1;
            }
            else if(prices[i+1]<prices[i]&&flag == 1){
                maxProfit = maxProfit+prices[i]-minPrice;
                minPrice = prices[i+1];
            }
            else{
                maxProfit = prices[i]-prices[0];
            }
        }
        return maxProfit;
    }
}

正确解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0; // 如果数组长度不足，无法交易
        }

        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            // 如果今天的价格比昨天高，就可以计算利润
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }

        return maxProfit;
    }
}

我是我的代码总是复杂且错误？

跳跃游戏

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0; // 记录能到达的最远位置
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) { // 如果当前索引超过最远可达位置，说明无法继续前进
                return false;
            }
            maxReach = Math.max(maxReach, i + nums[i]); // 更新最远可达位置
        }
        return true; // 如果循环完成，说明可以到达最后
    }
}

跳跃游戏 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int jumps = 0;       // 记录跳跃次数
        int currentEnd = 0;  // 当前跳跃范围的结束位置
        int farthest = 0;    // 当前能到达的最远位置

        // 遍历数组（不包括最后一个位置）
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]); // 更新最远位置
            
            // 到达当前跳跃的结束位置
            if (i == currentEnd) {
                jumps++;                 // 增加跳跃次数
                currentEnd = farthest;   // 更新当前跳跃范围的结束位置
                
                // 如果能覆盖终点，直接返回
                if (currentEnd >= n - 1) {
                    break;
                }
            }
        }

        return jumps;
    }
}

选择等待而不是强制跳到，细水长流。

H 指数

龟速方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int hIndex(int[] citations) {
        int h =0;
        int tmp = 0;
        for(int i=1;i<=citations.length;i++){
            for(int j=0;j<citations.length;j++){
                if(citations[j]>=1&&h==0){
                    h = 1;
                }
                if(citations[j]>=i){
                    tmp++;
                }
            }
            if(tmp >= i){
                h = Math.max(i,h);
            }
            tmp =0;
        }
        return h;
    }
}

但是还是通过了

image-20241213114630953

nb方法，对原始数组动手，又是新思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;

class Solution {
    public int hIndex(int[] citations) {
        // 先对引用数组进行排序（升序）
        Arrays.sort(citations);
        int n = citations.length;

        // 倒序遍历，找到最大的 H 指数
        for (int i = 0; i < n; i++) {
            int h = n - i; // 当前尝试的 H 指数
            if (citations[i] >= h) {
                return h;
            }
        }

        return 0; // 若没有找到，返回 0
    }
}

O(1) 时间插入、删除和获取随机元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class RandomizedSet {
    private Set<Integer> randomizedSet;
    private List<Integer> list; // For efficient random access
    private Random rand;

    public RandomizedSet() {
        randomizedSet = new HashSet<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (randomizedSet.add(val)) { // Add to set and check if it was not already present
            list.add(val); // Maintain a list for random access
            return true;
        }
        return false;
    }

    public boolean remove(int val) {
        if (randomizedSet.remove(val)) { // Remove from set
            list.remove((Integer) val); // Remove from list
            return true;
        }
        return false;
    }

    public int getRandom() {
        int randomIndex = rand.nextInt(list.size()); // Get a random index
        return list.get(randomIndex); // Return the value at that index
    }
}

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

题目要求时间复杂度为O(n)所以就不能使用嵌套循环了。

解决办法是先计算出从左到右自己左边所有数的乘积，再从右到左计算自己右边所有数的乘积。

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

        int suffixProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= suffixProduct;
            suffixProduct *= nums[i];
        }

        return answer;
    }
}