LeetCode2

发表于 更新于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 5 分钟

续LeetCode1

50.Pow(x, n)

题目地址

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例1： > 输入: 2.00000, 10
>输出: 1024.00000

示例2： > 输入: 2.10000, 3
>输出: 9.26100

示例3： > 输入: 2.00000, -2
>输出: 0.25000
>解释: \(2^{-2}\) = \(1/2^2\) = \(1/4\) = \(0.25\)

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数，其数值范围是 [\(−2^{31}\), \(2^{31} − 1\)] 。

begin

是不是有人就疑惑了，明明有pow可以用，为啥还有这题呢？是啊,但这样就考验到你对基础的理解了。

这里用到的是快速幂算法（使用了分治的思想），知道的都知道了，不知道的慢慢了解嘛。再加上负数的判断处理即可解。

一种java题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public double quickpow(double x, long n){
        double res=1.0;
        while(n>0){
            if(n%2==1) res*=x;
            x*=x;
            n/=2;
        }
        return res;
    }
    public double myPow(double x, int n) {
        long N=n;
        return N>=0? quickpow(x,N) : 1.0/quickpow(x,-N);
    }
}

详细题解

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

题目地址

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

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

示例1： > 给定数组 nums = [1,1,2],
>函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 >你不需要考虑数组中超出新长度后面的元素。

示例2： > 给定 nums = [0,0,1,1,1,2,2,3,3,4],
>函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
>你不需要考虑数组中超出新长度后面的元素。

说明:

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

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

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

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

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

begin

这道题应该是我目前解的最容易的了，原因就是上学期数据结构有个课后题和这个差不多。

解法就是双指针，k指向当前位置，l指向预备移入k+1位置的位置，while循环条件为l到数组末尾，若nums[k]==nums[l],l++，l向后移动；若不等，说明还未出现这个数可以存入数组中，nums[++k]=nums[l]可解决问题，最后返回当前下标k+1即新数组长度。

一种java题解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeDuplicates(int[] nums) {
        int k=0,l=1;
        while(l<nums.length){
            if(nums[k]==nums[l])
                l++;
            else
                nums[++k]=nums[l];
        }
        return k+1;
    }
}

详细题解

88.合并两个有序数组

题目地址

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明：

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
  • 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例1： > 输入:
>nums1 = [1,2,3,0,0,0], m = 3
>nums2 = [2,5,6], n = 3
>输出: [1,2,2,3,5,6]

begin

其实这个题与上面那个题有点类似，可参考着去做，但一定要注意数组范围和是否所有数以加入新数组中了。

官方题解给出了三种解法都用到了下面一个函数

1
2
System.arraycopy(dataType[] srcArray,int srcIndex,int destArray,int destIndex,int length)
//其中，srcArray 表示原数组；srcIndex 表示原数组中的起始索引；destArray 表示目标数组；destIndex 表示目标数组中的起始索引；length 表示要复制的数组长度。

方法一：合并后排序

简直了，官方这么玩，我直接懵逼。

官方方法一java

1
2
3
4
5
6
class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    System.arraycopy(nums2, 0, nums1, m, n);
    Arrays.sort(nums1);
  }
}

复杂度分析

  • 时间复杂度 : \(O((n + m)log(n + m))\)。
  • 空间复杂度 : \(O(1)\)。

方法二 : 双指针 / 从前往后

类似于前一个题，但要注意，前面说的是否所有数以加入新数组中了，还有这个方法需要内存存nums1的原数据。

官方方法二java

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
class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // Make a copy of nums1.
    int [] nums1_copy = new int[m];
    System.arraycopy(nums1, 0, nums1_copy, 0, m);

    // Two get pointers for nums1_copy and nums2.
    int p1 = 0;
    int p2 = 0;

    // Set pointer for nums1
    int p = 0;

    // Compare elements from nums1_copy and nums2
    // and add the smallest one into nums1.
    while ((p1 < m) && (p2 < n))
      nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];

    // if there are still elements to add
    if (p1 < m)
      System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
    if (p2 < n)
      System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
  }
}

复杂度分析

  • 时间复杂度 : \(O(n + m)\)。
  • 空间复杂度 : \(O(m)\)。

方法三 : 双指针 / 从后往前

想到这个也是绝了，虽然与方法二相比只是从头到尾变为从尾到前，但空间省下来了。

官方方法二java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // two get pointers for nums1 and nums2
    int p1 = m - 1;
    int p2 = n - 1;
    // set pointer for nums1
    int p = m + n - 1;

    // while there are still elements to compare
    while ((p1 >= 0) && (p2 >= 0))
      // compare two elements from nums1 and nums2 
      // and add the largest one in nums1 
      nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];

    // add missing elements from nums2
    System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
  }
}

复杂度分析

  • 时间复杂度 : \(O(n + m)\)。
  • 空间复杂度 : \(O(1)\)。

详细题解

总结

继续，有待提高。