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

Note: This question is the same as 1991: https://leetcode.com/problems/find-the-middle-index-in-array/

解法(Java)

題目要找一個陣列中的中樞點，也就是中樞點左邊和右邊元素的總和相等，這聽起來簡單，但卻不是直觀的左邊和右邊不斷相加就好，原本想跑一次迴圈解決，但多了很多判斷卻還是有些例外情況，最後只好上網找解答，原來是要跑兩次迴圈，第一次算總和，第二次判斷中樞點位置。

Runtime: 1 ms (98.86%)
Memory Usage: 43.6 MB (89.96%)

class Solution {
    public int pivotIndex(int[] nums) {
		int size = nums.length, sum = 0;
		for (int i = 0; i < size; i++) {
			sum += nums[i];
		}
		
		int leftSum = 0;
		for (int i = 0; i < size; i++) {
			if (sum - leftSum - nums[i] == leftSum) return i;
			else leftSum += nums[i];
		}
		
		return -1;
    }
}

747. Largest Number At Least Twice of Others

題目

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

Determine 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, or return -1 otherwise.

Example 1:

Input: nums = [3,6,1,0]
Output: 1
Explanation: 6 is the largest integer.
For every other number in the array x, 6 is at least 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 less than twice the value of 3, so we return -1.

Constraints:

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

解法(Java)

這題就比上一題簡單多了，簡單講就是要判斷陣列中最大的值是不是第二大值的兩倍，所以目標找出前兩大的元素索引值就好了。

Runtime: 0 ms (100%)
Memory Usage: 40.3 MB (41.92%)

class Solution {
    public int dominantIndex(int[] nums) {
        int size = nums.length, maxIndex = 0, thirdIndex = 1;
        
        for (int i = 1; i < size; i++) {
            if (nums[i] > nums[maxIndex]) {
                thirdIndex = maxIndex;
                maxIndex = i;
            }
            else if (nums[i] > nums[thirdIndex]) {
                thirdIndex = i;
            }
        }
        
        return nums[maxIndex] >= nums[thirdIndex] * 2 ? maxIndex : -1;
    }
}

66. Plus One

題目

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.

Example 1:

Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Incrementing by one gives 123 + 1 = 124.
Thus, the result should be [1,2,4].

Example 2:

Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
Incrementing by one gives 4321 + 1 = 4322.
Thus, the result should be [4,3,2,2].

Example 3:

Input: digits = [9]
Output: [1,0]
Explanation: The array represents the integer 9.
Incrementing by one gives 9 + 1 = 10.
Thus, the result should be [1,0].

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9
• digits does not contain any leading 0's.

解法(Java)

想像陣列是一個數字然後加上1，這應該不用多作解釋，反正最後發現要進位就建一個新的陣列，不用進位的話就直接回傳。

Runtime: 0 ms
Memory Usage: 40.8 MB (67.32%)

class Solution {
    public int[] plusOne(int[] digits) {
        int size = digits.length, num = 0, carry = 1;
        
        for (int i = size - 1; i >= 0; i--) {
            num = digits[i] + carry;
            digits[i] = num % 10;
            carry = num / 10;
        }
        
        if (carry > 0) {
            int[] result = new int[size + 1];
            result[0] = carry;
            for (int i = 1; i < size + 1; i++) {
                result[i] = digits[i - 1];
            }
            return result;
        } else {
            return digits;
        }
    }
}

小結

本來看到724. Find Pivot Index還以為很簡單，但做了一下發現思路還沒有很靈活，有時候只想跑一次迴圈，就會一股腦的寫判斷，殊不知只跑一次迴圈根本沒辦法解決問題...