leetcode 数组

本次题解包括

  • 26. Remove Duplicates from Sorted Array
  • 27. Remove Element
  • 88. Merge Sorted Array
  • 209. Minimum Size Subarray Sum
  • 238. Product of Array Except Self
  • 713. Subarray Product Less Than K
  • 717. 1-bit and 2-bit Characters
  • 798. Smallest Rotation with Highest Score

26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn’t matter what you leave beyond the new length.

题目地址:leetcode Remove Duplicates from Sorted Array

题目大意: 给定一个排好序的数组,让你用O(1)的空间在原数组上删掉重复的元素,并返回新的长度。修改后的数组在新的长度后面可以为任意的字符。

思路:

其实就是双指针,一个指向当前不重复的位置len,另一个不断向后看不重复的就写到len的位置。

C++

Python

 


 

27. Remove Element

Given an array and a value, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

题目地址:leetcode Remove Element

题目大意:和26题差不多,给定一个数组和一个数val,要求删除数组中值为val的,并返回新的数组长度。

思路:和上题一样,双指针。

C++

Python

 


 

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

题目地址:leetcode Merge Sorted Array

题目大意:给定两个排好序的数组num1(长度m)和nums2(长度n),让你合并到nums1,nums1的容量>= m + n

思路:开一个额外的空间,类似归并排序合并过去,空间占用O(m+n),很简单。但是要in-place呢?不适用额外空间的话,可以倒着来。从m-1和n-1的位置比较,nums1[m-1]> nums2[n-1]就把nums1[m-1]放在m + n -1的位置即可,依次类推。

C++

Python

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

题目地址:leetcode Minimum Size Subarray Sum

题目大意: 给定一个正数组成的数组和一个整数s,求一个最小长度最小的子序列使得它的和>=s

思路

双指针法。

C++

Java

Python

 


 

238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

题目地址:leetcode Product of Array Except Self

题目大意:

  • 给定一个数组,对于每个元素求除了该元素的其他数的乘积。要求不用除法、时间复杂度O(1)
  • follow up: 要求空间复杂度O(1) ,这里不包括返回的数组空间。

思路

容易想到就是所有数的乘积然后除以每个数,就得到了答案。但是要求不用除法,因此可以:

分为left和right。left[i]代表i左边乘积(不包括i),right[i]代表i右边乘积(不包括i)。

容易写出:

C++

但可以做得更好。

我们可以用一个数组搞定,而这个数组就是答案,不计算额外的空间。

首先ans[i]代表i左边元素的乘积,遍历一遍后。然后从右向左遍历。每次用一个变量t * nums[i],得到右边的乘积。

C++

Java

Python

 

 

 


 

713. Subarray Product Less Than K

Your are given an array of positive integers nums.

Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k.

Example 1:

Note:

  • 0 < nums.length <= 50000.
  • 0 < nums[i] < 1000.
  • 0 <= k < 10^6.

题目地址:leetcode Subarray Product Less Than K

题目大意: 给定一个正数组成的数组,求有多少个乘积小于k的连续的子数组。

思路:

滑动窗口O(n)

我的做法是,start到第一个不满足乘积小于k的位置i,则[start,i-1]以start开头有i – start个子数组,然后/ nums[start],start+=1,继续看是不是满足条件。

注意需要看nums[i] 是否已经>= k了。

C++

官方的Solution思路类似,但是写得更好:

我上面的其实是以start开头的有多少种,而官方的是以end结尾的有多少种。

C++

Java

Python

 

 


 

717. 1-bit and 2-bit Characters

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Example 1:

Example 2:

Note:

  • 1 <= len(bits) <= 1000.
  • bits[i] is always 0 or 1.

题目地址:leetcode 1-bit and 2-bit Characters

题目大意: 给定一个数组,只能由0、 10或者11组成,问最后一个字符是否只能是单个字符组成的

思路:从前往后扫描,碰到1的+2,碰到0的+1,到倒数第二个字符看是否为1即可。

C++

 

 


 

798. Smallest Rotation with Highest Score

 Given an array A, we may rotate it by a non-negative integer K so that the array becomes A[K], A[K+1], A{K+2], … A[A.length – 1], A[0], A[1], …, A[K-1].  Afterward, any entries that are less than or equal to their index are worth 1 point.

For example, if we have [2, 4, 1, 3, 0], and we rotate by K = 2, it becomes [1, 3, 0, 2, 4].  This is worth 3 points because 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4 [one point].

Over all possible rotations, return the rotation index K that corresponds to the highest score we could receive.  If there are multiple answers, return the smallest such index K.

Example 1:
Input: [2, 3, 1, 4, 0]
Output: 3
Explanation:
Scores for each K are listed below:
K = 0, A = [2,3,1,4,0], score 2
K = 1, A = [3,1,4,0,2], score 3
K = 2, A = [1,4,0,2,3], score 3
K = 3, A = [4,0,2,3,1], score 4
K = 4, A = [0,2,3,1,4], score 3

So we should choose K = 3, which has the highest score.

Example 2:
Input: [1, 3, 0, 2, 4]
Output: 0
Explanation: A will always have 3 points no matter how it shifts.
So we will choose the smallest K, which is 0.

Note:

A will have length at most 20000.
A[i] will be in the range [0, A.length].

题目地址:leetcode Smallest Rotation with Highest Score

题目大意:给定一个数组A,当A[i] <= i的时候得一分。现在让你进行循环左移,求能获得的最高分的次数。

思路:

  • 当我们进行循环左移的时候,原本下标为0的元素变到n – 1,因为所有元素都<=N – 1,因此肯定有分数+1
  • 而我们需要做的事就是记录各个元素移动多少步之后分数-1
    • k = (i – A[i] + n) % n可以算出A[i]==i的元素下标,要是移动超过k步,就说明score应该-1
    • 统计各个数字的k即可
  • PS: 我们并不关心一开始是多少分,只关心最后谁最大即可。因此对于每个元素不用看最开始是否能得分,就看什么时候加分什么时候减分就行了。

参考https://leetcode.com/problems/smallest-rotation-with-highest-score/discuss/118725/Easy-and-Concise-5-lines-Solution-C++JavaPython

C++

Python

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 数组
本文地址:https://www.hrwhisper.me/leetcode-arrays/

您的支持将鼓励我继续创作!

Leetcode . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *