LeetCode Array101


Introduction

An Array is a collection of items. The items could be integers, strings, DVDs, games, books—anything really. The items are stored in neighboring (contiguous) memory locations. Because they’re stored together, checking through the entire collection of items is straightforward.

  • Accessing elements in arrays

  • Array capacity vs length


Max consecutive ones

Given a binary array nums, return the maximum number of consecutive 1’s in the array.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        maxCount = 0
        prevMaxCount = 0
        for num in nums:
            if num:
                maxCount += 1
            else:
                prevMaxCount = max(maxCount, prevMaxCount)
                maxCount = 0
        return max(prevMaxCount, maxCount)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int count = 0;
        int maxCount = 0;
        for (int num : nums){
            if (num) count++;
            else {
                maxCount = max(maxCount, count);
                count = 0;
            }
        }
        return max(maxCount, count);
    }    
};

Find Numbers with Even Number of Digits

Given an array nums of integers, return how many of them contain an even number of digits.

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
26
27
class Solution {
public:    
    int countEven(int num){
        int count = 0;
        while(true){
            if (num >= 10){
                num = num/10;
                count ++;
            }
            else {
                count ++;
                break;            
            }
            
        }
        if (count%2 == 0) return true;
        else return false;
    }    
    
    int findNumbers(vector<int>& nums) {
        int count = 0;
        for (int num : nums){
            if (countEven(num)) count++;
        }
        return count;        
    }
};

Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        //first find the minimum abs idx
        int least_abs = Solution::findLeastAbsolute(nums);
        //Register small squared value by comparing L/R pointers
        int Lp = least_abs;
        int Rp = least_abs;
        vector<int> output;
        int len = nums.size();
        output.push_back(pow(nums[Lp],2));
        while (true){
            if (Lp >0 && Rp <(len-1)){
                if (abs(nums[Lp-1]) < abs(nums[Rp+1])){
	                output.push_back(pow(nums[--Lp],2));
                }
                else output.push_back(pow(nums[++Rp],2));
            }
            else if (Lp ==0 && Rp <(len-1)){
                output.push_back(pow(nums[++Rp],2));
            }   
            else if (Lp > 0 && Rp == (len-1)){
                output.push_back(pow(nums[--Lp],2));
            }
            else break;
        }
        return output;
    }
    
  int findLeastAbsolute(vector<int>& nums) {
        int idx = 0;
        int len = nums.size();
        while (nums[idx] < 0) {
            idx++; 
            if (idx <0 or idx >= len) break;
        }
        // if idx == 0, all posive
        if (idx==0) return idx;
        // if idx == len, all negative => L-pointer only
        if (idx == len) return (idx-1);                
        // if idx <> len, neg-pos switch in the middle
        if (idx > 0 && abs(nums[idx]) <= abs(nums[idx-1])) return idx;
        if (idx > 0 && abs(nums[idx]) > abs(nums[idx-1])) return (idx-1);
        return idx;
    }
};

Reference

Notes Mentioning This Note

Table of Contents


Share on: