LeetCode
想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

https://leetcode.com

NO.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]);
}
// 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;
    }
}

NO.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;
    }
}

NO.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];
            }
        }
    }

-EOF-