LeetCode:[26,122,189]

码不停题

26. 删除排序数组中的重复项

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

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

示例:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解题:

//C#
public class Solution {
    public int RemoveDuplicates(int[] nums) {
        if(nums.Length==0)
            return 0;
        int sum=0;
        for(int i=0;i<nums.Length;i++){
            if(nums[i]!=nums[sum])
            {
                sum++;
                nums[sum]=nums[i];
            }
        }
        sum+=1;
        return sum;
    }
}

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

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

解题:

//C#
public class Solution {
    public int MaxProfit(int[] prices) {
        if(prices.Length==0)
            return 0;
        int num=0;
        for(int i=1;i<prices.Length;i++)
        {
            if(prices[i]>prices[i-1])
                num+=prices[i]-prices[i-1];
        }
        return num;
    }
}

189. 旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

示例:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

说明:

  • 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
  • 要求使用空间复杂度为 O(1) 的原地算法。

解题:

  • 方法#1 暴力破解法[超出时间限制]
    • 复杂性分析:
      • 时间复杂度: 为O(n * K)。所有数字都移动了一步O (n ))k次(O (k ))
      • 空间复杂度:O (1 )。没有使用额外的空间。
//C#
public class Solution
    {
        public void Rotate(int[] nums, int k)
        {
            int temp, previous;

            for (int i = 0; i < k; i++)
            {
                previous = nums[nums.Length - 1];
                for (int j = 0; j < nums.Length; j++)
                {
                    temp = nums[j];
                    nums[j] = previous;
                    previous = temp;
                }
            }
        }
    }

 

  • 方法#2 使用额外的数组
    • 算法:使用一个额外的数组,将数组中的每个元素放在正确的位置,即索引处的数字 。在原始数组中放置在索引处(i + k ) 。
    • 复杂性分析:
      • 时间复杂度: O (n )。一次传递用于将数字放入新数组中。另一个传递将新阵列复制到原始阵列。
      • 空间复杂度: O (n )。使用相同大小的另一个阵列。
//C#
public class Solution
    {
        public void Rotate(int[] nums, int k)
        {
            int[] a = new int[nums.Length];

            for (int i = 0; i < nums.Length; i++)
            {
                a[(i + k) % nums.Length] = nums[i];
            }

            for (int i = 0; i < nums.Length; i++)
            {
                nums[i] = a[i];
            }
        }
    }

 

  • 方法#3 使用循环替换
    • 算法:我们可以直接将每个数组的数组放在所需的正确位置。但如果这样做,就会破坏原始元素。因此,我们需要存储被替换的数字到 temp。然后,我们可以将替换的数值(temp)放置在正确位置上等等,n次,其中n是数组的长度。我们选了n作为替换数,是因为我们必须移动数组的所有元素(即n)。但是,这种方法可能存在一个问题,如果n,k=k(因为k的值大于n最终导致了k等于k)。在这种情况下,虽然取出的数字被放置在正确的位置上,但最终将达到我们最初开始的数字。因此,在这种情况下,当我们再次点击原始数字的索引时,我们将以后面的数字开始相同的过程。现在让我们看一下上述方法如何工作的。假设,我们有n作为数组中元素的数量和,所需移动次数k。进一步假设n。现在,当我们开始将元素放在它们正确的位置时,在第一个循环中,所有索引为i的数字满足我被放在它们需要的位置。发生这种情况是因为当我们每次跳k步时,我们只会将k个步数分开。我们从索引 i= 0 开始,有i个。因此,我们在第一个循环中执行满足上述条件的所有数字。当我们回到原始索引时,我们已经放置了i个元素位于正确的位置,因为我们只在第一个周期中执行了那么多元素。现在,我们增加索引以替换数字。这一次,我们放置 i=k 个元素在正确的位置,不同于在第一个周期中正确放置的元素,因为这次我们点击所有数字满足条件 一世一世。当我们再次点击起始编号时,我们增加索引并重复相同的过程I = 1对于满足所有指标,i=1一世一世。这种情况发生在我们用索引达到数字之前一世一世 再次,这发生了 我= K我= k。我们将在总共k个周期后达到这样的数字。现在,位于其正确位置的数字专用号码的总数将是k \ times \ frac {n} {k} = nk ×ķñ= n。因此,所有数字都将被放置在正确的位置。请查看以下示例以阐明该过程: nums: [1, 2, 3, 4, 5, 6] k: 2

Share

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Post comment