初级算法之数组

ゝ一世哀愁。 2024-03-31 03:37 78阅读 0赞

[删除有序数组中的重复项][Link 1]

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

**思路及代码**

遍历数组的每一个数,如果当前元素和下一个元素不一样,那么就加一.

class Solution {
        public int removeDuplicates(int[] nums) {
            int index=0;
            for(int i=0;i<nums.length;i++){
                if(nums[i]!=nums[index]){
                    if(nums[index+1]=nums[i];
                    index++;
                }
                return index+1;
            }
        }
    }

[买卖股票的最佳时机][Link 2]

给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

**思路及代码**

默认第一天买是价格最低的时候,最大利润为零.遍历数组,如果当前的价格低于初始的价格,就把当前加个赋值给最低价,否则就判断当前价格减去买入的最低价的差值和最大利润比较.

public class Solution {
        public int maxProfit(int prices[]) {
            int minprice = Integer.MAX_VALUE;
            int maxprofit = 0;
            for (int i = 0; i < prices.length; i++) {
                if (prices[i] < minprice) {
                    minprice = prices[i];
                } else if (prices[i] - minprice > maxprofit) {
                    maxprofit = prices[i] - minprice;
                }
            }
            return maxprofit;
        }
    }

[买卖股票的最佳时机 II][II]

给你一个整数数组 prices ，其中 prices\[i\] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

**思路及代码**

有一个讨巧的方法,只要后面的数字比前面的数字大就把两者的差值加起来

class Solution {
        public int maxProfit(int[] prices) {
            int ans=0;
            for(int i=1;i<=prices.length-1;i++){
                if(prices[i]>prices[i-1]){
                    ans+=prices[i]-prices[i-1];
                }
            }
            return ans;
        }
    }
    class Solution { // 动态规划
        public int maxProfit(int[] prices) {
            // [天数][是否持有股票]
            int[][] dp = new int[prices.length][2];
    
            // bad case
            dp[0][0] = 0;
            dp[0][1] = -prices[0];
    
            for (int i = 1; i < prices.length; i++) {
                // dp公式
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            }
    
            return dp[prices.length - 1][0];
        }
    }

[力扣][Link 3]

给你一个数组，将数组中的元素向右轮转 k个位置，其中 k是非负数。

**思路及代码**

创建一个临时数组,赋值,然后统一对原数组进行取余赋值

//方法一  
    //一次交换
    class Solution {
        public void rotate(int nums[], int k) {
            int length = nums.length;
            int temp[] = new int[length];
            //把原数组值放到一个临时数组中，
            for (int i = 0; i < length; i++) {
                temp[i] = nums[i];
            }
            //然后在把临时数组的值重新放到原数组，并且往右移动k位
            for (int i = 0; i < length; i++) {
                nums[(i + k) % length] = temp[i];
            }
        }
    }
    
    //方法二  
    //多次交换
    class Solution {
    	public void rotate(int[] nums, int k) {
            int length = nums.length;
            k %= length;
            reverse(nums, 0, length - 1);//先反转全部的元素
            reverse(nums, 0, k - 1);//在反转前k个元素
            reverse(nums, k, length - 1);//接着反转剩余的
        }
    
        //把数组中从[start，end]之间的元素两两交换,也就是反转
        public void reverse(int[] nums, int start, int end) {
            while (start < end) {
                int temp = nums[start];
                nums[start++] = nums[end];
                nums[end--] = temp;
            }
        }
    }

[Link 1]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
[Link 2]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
[II]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
[Link 3]: https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2skh7/