Introduction to Array

發表於 Disqus：
文章字數： 3k 所需閱讀時間 ≈ 5 分鐘

本文蒐集

LeetCode 724: Find Pivot Index

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Example 1: 

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11
Example 2: 
Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.
Example 3: 
Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints:

  • 1 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000

我的解法

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        left2right = [0]
        right2left = [0]
        
        for i in range(len(nums)):
            left2right.append(left2right[i]+nums[i])
            right2left.append(right2left[i]+nums[len(nums)-i-1])
        right2left.reverse()

        for i in range(len(left2right)-1):
            if left2right[i] == right2left[i+1]:
                return i
        
        return -1

LeetCode 747: Largest Number At Least Twice of Others

You are given an integer array nums where the largest integer is unique.

Find whether the largest element in the array is at least twice as much as every other number in the array. If it is, return the index of the largest element, otherwise, return -1.

Example 1: 

Input: nums = [3,6,1,0]
Output: 1
Explanation: 6 is the largest integer and for every other number in the array x,
6 is more than twice as big as x.
The index of value 6 is 1, so we return 1.
Example 2: 
Input: nums = [1,2,3,4]
Output: -1
Explanation: 4 is not at least as big as twice the value of 3, so we return -1.
Constraints:

  • 1 <= nums.length <= 50
  • 0 <= nums[i] <= 100
  • The largest element in nums is unique.

我的解法

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        max1 = -1
        max_index = 0
        for i in range(len(nums)):
            nums[i] = nums[i] * 2
            if nums[i] > max1:
                max1 = nums[i]
                max_index = i
        flag = 0
        for i in range(len(nums)):
            if max1 - nums[i] < nums[i] and i != max_index:
                return -1
        return max_index

LeetCode 66: Plus One

Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1: 

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2: 
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Example 3: 
Input: digits = [0]
Output: [1]
Constraints:

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

我的解法

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        i = -1
        while (digits[i]+1) // 10:
            digits[i] = 0
            i -= 1
            if i == -len(digits)-1:
                digits = [1] + digits
                break
        else:
            digits[i] += 1
        return digits