细语呢喃

技术改变生活

0%

leetcode 数组

发表于 分类于 ， 阅读次数： 评论数：

本次题解包括

  • 26. Remove Duplicates from Sorted Array
  • 27. Remove Element
  • 88. Merge Sorted Array
  • 189. Rotate Array
  • 209. Minimum Size Subarray Sum
  • 228. Summary Ranges
  • 238. Product of Array Except Self
  • 674. Longest Continuous Increasing Subsequence
  • 713. Subarray Product Less Than K
  • 717. 1-bit and 2-bit Characters
  • 798. Smallest Rotation with Highest Score
    1. 等价多米诺骨牌对的数量

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++ 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()) return 0;
        int len = 1;
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] != nums[i - 1])
                nums[len++] = nums[i];
        }
        return len;
    }
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        j = 1 if nums else 0
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                nums[j] = nums[i]
                j += 1
        return j

 

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++ 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != val)
                nums[len++] = nums[i];
        }
        return len;
    }
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        j = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[j] = nums[i]
                j += 1
        return j

 

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++ 

1
2
3
4
5
6
7
8
9
class Solution {
public:
	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
		int i = m - 1, j = n - 1, cur = m + n - 1;
		for (; j >= 0; --cur) {
			nums1[cur] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
		}
	}
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        i, j = m - 1, n - 1
        cur = m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[cur] = nums1[i]
                i -= 1
            else:
                nums1[cur] = nums2[j]
                j -= 1
            cur -= 1

189. 旋转数组

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

示例 1:

1
2
3
4
5
6
>输入: [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]

示例 2:

1
2
3
4
5
>输入: [-1,-100,3,99] 和 k = 2
>输出: [3,99,-1,-100]
>解释: 
>向右旋转 1 步: [99,-1,-100,3]
>向右旋转 2 步: [3,99,-1,-100]

说明:

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

方法1. 用个辅助的数组

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> temp(nums);
        for (std::size_t i = 0; i < n; ++i) {
            nums[(i + k) % n] = temp[i];
        }
    }
};

方法2. 数组翻转

1
2
3
4
[1,2,3,4,5,6,7]， K=3为例
[4,3,2,1,5,6,7]  //reverse(0, n - k - 1)
[4,3,2,1,7,6,5]  //reverse(n - k, n - 1)
[5,6,7,1,2,3,4]  //reverse(0, n - 1)

c++代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    void reverse(vector<int>&nums, int i, int j) {
        for (;i < j; ++i, --j) {
            swap(nums[i], nums[j]);
        }
    }
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);
    }
};

方法3. 循环替换。

方法1中之所以要开额外的数组是因为后面的元素会被替换掉，如果采用环状的替换呢？即nums[0]和nums[k]替换，nums[k]继续和nums[2k % n]替换直到回到原点。 但是可能有的元素没有替换到，如下面的情况

1
2
3
[1, 2, 3, 4] k =2
=> [1, 2, 1, 4]
=> [3, 2, 1, 4]

发现元素2和元素4没有被替换到！

那么怎么办呢？

首先考虑循环一次回到原点经过了多少元素，假设数组走了a圈，经过了b个元素，则有an = bk， 由于a和b都是整数，an是n、k的公倍数。由于我们取的是第一次回到原点就停止遍历，因此an是n、k的最小公倍数，记为lcm(n, k)，那么遍历的元素个数为 \(b = \frac{an}{k}= \frac{lcm(n,k)}{k}\)

那么我们需要遍历\(\frac{n}{b} = \frac{nk}{lcm(n,k)} = gcd(n, k)\)，因此可以用下面的代码，当遍历gcd次的时候停止即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        int end = gcd(n, k);
        for (int start = 0; start < end; ++start) {
            int i = start;
            int temp = nums[i];
            do {
                int next = (i + k) % n;
                swap(temp, nums[next]);
                i = next;
            } while (i != start);
        }
    }

    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

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++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
	int minSubArrayLen(int s, vector<int>& nums) {
		int start = 0;
		int cur_sum = 0;
		int ans = nums.size() + 1;
		for (int i = 0; i < nums.size(); i++) {
			cur_sum += nums[i];

			while (cur_sum >= s && cur_sum - nums[start] >= s && start <= i ) {
				cur_sum -= nums[start++];
			}

			if (cur_sum >= s && ans > i - start + 1)
				ans = i - start + 1;
		}
		return ans == nums.size() + 1? 0 : ans;
	}
};

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int start = 0;
        int curSum = 0;
        int ans = nums.length + 1;
        for (int i = 0; i < nums.length; i++) {
            curSum += nums[i];
            while (curSum >= s && curSum - nums[start] >= s && start <= i) {
                curSum -= nums[start++];
            }
            if (curSum >= s && ans > i - start + 1)
                ans = i - start + 1;
        }
        return ans == nums.length + 1 ? 0 : ans;
    }
}

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        ans = len(nums) + 1
        cur_sum = start = 0
        for i in range(len(nums)):
            cur_sum += nums[i]
            while cur_sum >= s and cur_sum - nums[start] >= s and start <= i:
                cur_sum -= nums[start]
                start += 1
            if cur_sum >= s and i - start + 1 < ans:
                ans = i - start + 1
        return ans if ans != len(nums) + 1 else 0

 

228. Summary Ranges

You are given a sorted unique integer array nums.

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

  • "a->b" if a != b
  • "a" if a == b

Example 1:

1
2
3
4
5
6
>Input: nums = [0,1,2,4,5,7]
>Output: ["0->2","4->5","7"]
>Explanation: The ranges are:
>[0,2] --> "0->2"
>[4,5] --> "4->5"
>[7,7] --> "7"

Example 2:

1
2
3
4
5
6
7
>Input: nums = [0,2,3,4,6,8,9]
>Output: ["0","2->4","6","8->9"]
>Explanation: The ranges are:
>[0,0] --> "0"
>[2,4] --> "2->4"
>[6,6] --> "6"
>[8,9] --> "8->9"

Example 3:

1
2
>Input: nums = []
>Output: []

Example 4:

1
2
>Input: nums = [-1]
>Output: ["-1"]

Example 5:

1
2
>Input: nums = [0]
>Output: ["0"]

Constraints:

  • 0 <= nums.length <= 20
  • -231 <= nums[i] <= 231 - 1
  • All the values of nums are unique.
  • nums is sorted in ascending order.

每次遍历直到nums[j] != nums[j - 1]的时候就是一个区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        for (int i = 0; i < nums.size();) {
            int j = i + 1;
            while (j < nums.size() && nums[j] == nums[j - 1] + 1)
                ++j;
            --j;
            if (i != j)
                ans.emplace_back(to_string(nums[i]) + "->" + to_string(nums[j]));
            else
                ans.emplace_back(to_string(nums[j]));
            i = j + 1;
        }
        return ans;
    }
};

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++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
	vector<int> productExceptSelf(vector<int>& nums) {
		if (nums.empty()) return nums;
		vector<int> ans(nums.size(), 0),left(nums.size(), 1),right(nums.size(), 1);
		for (int i = 1; i < nums.size(); i++)
			left[i] = nums[i - 1] * left[i - 1];
		
		for (int i = nums.size() - 2; i >= 0; i--)
			right[i] = nums[i + 1] * right[i + 1];

		for (int i = 1; i < nums.size() - 1; i++)
			ans[i] = left[i] * right[i];
		ans[0] = right[0];
		ans[nums.size() - 1] = left[nums.size() - 1];
		return ans;
	}
};

但可以做得更好。

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

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

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
	vector<int> productExceptSelf(vector<int>& nums) {
		if (nums.empty()) return nums;
		vector<int> ans(nums.size(), 1);
		for (int i = 1; i < nums.size(); i++)
			ans[i] = nums[i - 1] * ans[i - 1];
		
		int t = nums[nums.size()-1];
		for (int i = nums.size() - 2; i >= 0; i--) {
			ans[i] *= t;
			t *= nums[i];
		}
		return ans;
	}
};

Java 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums.length == 0) return nums;
        int[] ans = new int[nums.length];
        Arrays.fill(ans, 1);
        for (int i = 1; i < nums.length; i++)
            ans[i] = ans[i-1] * nums[i-1];

        int t = nums[nums.length-1];
        for(int i= nums.length-2;i>=0;i--){
            ans[i] *= t;
            t *= nums[i];
        }
        return ans;
    }
}


Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums: return nums
        ans = [1] * len(nums)
        for i in range(1, len(nums)):
            ans[i] = ans[i - 1] * nums[i - 1]

        t = nums[-1]
        for i in range(len(nums) - 2, -1, -1):
            ans[i] *= t
            t *= nums[i]
        return ans


 

674. 最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

1
2
3
4
>输入：nums = [1,3,5,4,7]
>输出：3
>解释：最长连续递增序列是 [1,3,5], 长度为3。
>尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：

1
2
3
>输入：nums = [2,2,2,2,2]
>输出：1
>解释：最长连续递增序列是 [2], 长度为1。

提示：

  • 0 <= nums.length <= 104
  • -109 <= nums[i] <= 109

直接找不解释。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        std::size_t ans = 0;
        for (std::size_t i = 0; i < nums.size();) {
            std::size_t j = i + 1;
            while (j < nums.size() && nums[j - 1] < nums[j]) {
                ++j;
            }
            ans = std::max(ans, j - i);
            i = j;
        }
        return ans;
    }
};

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:

1
2
3
4
5
**Input:** nums = [10, 5, 2, 6], k = 100
**Output:** 8
**Explanation:** The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6].
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

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++ 

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:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(nums.empty()) return 0;
        int mul = 1, start = 0, ans = 0;
        for( int i = 0; i < nums.size(); i++){
            if(nums[i] >= k){
                ans += ((i - start + 1) * (i - start)) >> 1;
                start = i + 1;
                mul = 1;
                continue;
            }
            while(mul * nums[i] >= k && start <= i){
                ans += i - start;
                mul /= nums[start++];
                
            }
            mul *= nums[i];
        }
        for( ; mul < k && start < nums.size(); start++){
            ans += nums.size() - start;
        }
        return ans;
    }
};

官方的Solution思路类似，但是写得更好：

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

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(nums.empty()  k <= 1) return 0;
        int mul = 1, start = 0, ans = 0;
        for( int end = 0; end < nums.size(); end++){
            mul *= nums[end];
            while(mul >= k) mul /= nums[start++];
            ans += end - start + 1;
        }
        return ans;
    }
};

Java 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k <= 1) return 0;
        int mul = 1, start = 0, ans = 0;
        for(int end = 0; end < nums.length; end++){
            mul *= nums[end];
            while(mul >= k) mul /= nums[start++];
            ans += end - start + 1;
        }
        return ans;
    }
}

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def numSubarrayProductLessThanK(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if k <= 1: return 0
        start = ans = 0
        mul = 1
        for end in range(len(nums)):
            mul *= nums[end]
            while mul >= k:
                mul /= nums[start]
                start += 1
            ans += end - start + 1
        return ans

 

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:

1
2
3
4
5
6
**Input:** 
bits = [1, 0, 0]
**Output:** True
**Explanation:** 
The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.

Example 2:

1
2
3
4
5
6
**Input:** 
bits = [1, 1, 1, 0]
**Output:** False
**Explanation:** 
The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.

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++ 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0;
        for(; i < bits.size(); i++){
            if(bits[i] == 1){
                if(i == bits.size() - 2) return false;
                i++;
            }
        }
        return true;
    }
};

 

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++ 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
	int bestRotation(vector<int>& A) {
		int n = A.size();
		vector<int> score(n, 0);
		for (int i = 0; i < n; ++i) 
			--score[(i + n - A[i] + 1) % n];
		for (int i = 1; i < n; ++i)
			score[i] += score[i - 1] + 1;
		return distance(score.begin(), max_element(score.begin(), score.end()));
	}
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def bestRotation(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        n = len(A)
        score = [0] * n
        for i in range(n):
            score[(i + n - A[i] + 1) % n] -= 1
        for i in range(1, n):
            score[i] += score[i - 1] + 1
        return score.index(max(score))

 

1128. 等价多米诺骨牌对的数量

难度简单109

给你一个由一些多米诺骨牌组成的列表 dominoes。

如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。

形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。

在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

示例：

1
2
>输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
>输出：1

提示：

  • 1 <= dominoes.length <= 40000
  • 1 <= dominoes[i][j] <= 9

由于数据是1~9之间的，因此可以映射为100以内的两位数，然后计数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        vector<int> counter(100, 0);
        for (vector<int>& row : dominoes) {
            if (row[1] < row[0]) {
                std::swap(row[0], row[1]);
            }
            int key = row[0] * 10 + row[1];
            ++counter[key];
        }

        int ans = 0;
        for (std::size_t i = 0; i < counter.size(); ++i) {
           if (counter[i] > 1) {
               ans += (counter[i] * (counter[i] - 1)) >> 1;
           }
        }
        return ans;
    }
};

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

请我喝杯咖啡吧~