Array Problems

Made by Mike_Zhang

数据结构与算法主题：

1 Introduction of Array

Array is a collection of items.

1.1 Array Creation

1
int[] intArr = new int[5];

1.2 Array Writing

1
intArr[2] = 3; // put 3 in the third place of the Array

1.3 Array Reading

1
System.out.println(intArr[2]);

1.4 Array Slicing

1
int[] newArray = Arrays.copyOfRange(oldArray, startIndex, endIndex); // java.util.Arrays

1.5 Array Capacity

The number of items the Array could hold;

In Java, the capacity of an Array is checked by Array’s length attribute.

1
System.out.println(intArr.length);

1.6 Array Length

The number of items currently in the Array.

Array’s length need to be tracked by the programmer. 

1
2
3
4
5
6
7
8
9
10
11
int[] intArr = new int[5];

int len = 0;

for (int i = 0; i < 3; i++) {
    array[i] = i;
    len++;
}

System.out.println("Capacity: " + array.length);
System.out.println("Length: " + length);

Output:

1
2
Capacity: 5
Length: 3

Max Consecutive Ones

LeetCode Problem #485

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int count = 0;
        int maxCount = 0;
        for (int i : nums){
            count = (i == 1? count+1 : 0);
            maxCount = (count > maxCount ? count:maxCount);
        }
        return maxCount;
    }
}

Find Numbers with Even Number of Digits

LeetCode Problem #1295

1
2
3
4
5
6
7
8
9
class Solution {
    public int findNumbers(int[] nums) {
        int total = 0;
        for (int i : nums) {
            if (((int)Math.log10(i)+1) % 2 ==0) {total += 1;}
        }
        return total;
    }
}

Squares of a Sorted Array

LeetCode Problem #977

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] out = new int[nums.length];
        int left = 0;
        int right = nums.length-1;
        int index = nums.length-1;
        while (left <= right) {
            if (Math.abs(nums[left]) < Math.abs(nums[right])) {
                out[index] = nums[right] * nums[right];
                right -= 1;
            }
            else {
                out[index] = nums[left] * nums[left];
                left += 1;
            }
            index -=1;
        }
        return out;
    }
}

2 Array Inserting

Duplicate Zeros

LeetCode Problem #1089

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void duplicateZeros(int[] arr) {
        int len = arr.length;
        int zeroCnt = 0;
        for (int i : arr) {
            if (i == 0) {zeroCnt += 1;}
        }
        for (int j=len-1;j>=0;j--) {
            int index = j+zeroCnt;
            if (index < len) {
                arr[index]=arr[j];
            }
            if (arr[j]==0) {
                if(index-1<len) {arr[index-1]=0;}
                zeroCnt-=1;
            }
        }
    }
}

Merge Sorted Array

LeetCode Problem #88

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m-1;
        int p2 = n-1;
        int p = m+n-1;
        while (p2>=0) {
            if (p1>=0 && nums1[p1]>nums2[p2]) {
                nums1[p] = nums1[p1];
                p-=1;
                p1-=1;
            }
            else {
                nums1[p] = nums2[p2];
                p-=1;
                p2-=1;
            }  
        }
    }
}

3 Array Deleting

Remove Element

LeetCode Problem #27

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 removeElement(int[] nums, int val) {
        if (nums.length == 0 || (nums.length == 1 && val == nums[0])) {return 0;}
        int left = 0;
        int right = nums.length-1;
        int outLen = 0;
        while (left <= right) {
            if (nums[left] == val) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                right -= 1;
            }
            else {
                outLen += 1;
                left += 1; 
            }
        }
        return outLen;
    }
}

Remove Duplicates from Sorted Array

LeetCode Problem #26

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return nums.length;
        }
        int left = 0; // end guy
        int right = 1; // front guy
        while (right < nums.length) {
            if (nums[right]!=nums[left]) {
                left += 1; // end guy move only when differ from front guy
                nums[left] = nums[right]; // let front guy be thr next one to compare
            }
            right += 1; // front guy always keeps moving for getting each one compared
        }
        return left+1;
    }
}

4 Array Searching

Check If N and Its Double Exist

LeetCode Problem #1346

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean checkIfExist(int[] arr) {
        HashSet hs = new HashSet();
        for (int i : arr) {
            if (hs.contains(i*2) || (i%2==0 && hs.contains(i/2))) {
                return true;
            }
            hs.add(i);
        }
        return false;
    }
}

Valid Mountain Array

LeetCode Problem #941

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean validMountainArray(int[] arr) {
        if (arr.length < 3) {
            return false;
        }
        int left = 0;
        int right = arr.length-1;
        
        while (left <= arr.length-2 && arr[left]<arr[left+1]) {
            left += 1;
        }
        
        if (left == 0 || left == arr.length-1) {
            return false;
        }
        
        while (right >= 1 && arr[right]<arr[right-1]) {
            right -= 1;
        }
            
        return left == right;
    }
}

5 In-place Array Operations

Working directly in the input Array, and NOT creating a new Array, reducing space and time complexity.

Replace Elements with Greatest Element on Right Side

LeetCode Problem #1299

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int[] replaceElements(int[] arr) {
        int len = arr.length-1;
        int maxVal = -1;
        while (len>=0) {
            int temp = arr[len];
            arr[len] = maxVal;
            maxVal = temp>maxVal? temp:maxVal;
            len -= 1;
        }
        return arr;
    }
}

Move Zeroes

LeetCode Problem #283](https://leetcode.com/problems/move-zeroes/)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void moveZeroes(int[] nums) {
        int left = 0;
        int right = 0;
        while (right < nums.length) {
            if (nums[right] != 0) {
                nums[left] = nums[right];
                left +=1;
            }
            right += 1;
        }
        while (left < nums.length) {
            nums[left] =0;
            left += 1;
        }
    }
}

Sort Array By Parity

LeetCode Problem #905

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0;
        int right = 0;
        while (right<nums.length) {
            if (nums[right]%2==0) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left += 1;
            }
            right += 1;
        }
        return nums;
    }
}

6 Classic Problems

Height Checker

LeetCode Problem #1051](https://leetcode.com/problems/height-checker/)

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 heightChecker(int[] heights) {
        int[] expected = new int[heights.length];
        for (int u=0; u<expected.length;u++) {
            expected[u] = heights[u];
        }
        
        for (int i=0; i<expected.length;i++) {
            for (int j=0;j<expected.length-i-1;j++) {
                if (expected[j]>expected[j+1]) {
                    int temp = expected[j+1];
                    expected[j+1] = expected[j];
                    expected[j] = temp;
                }
            }
        }
        int diff = 0;
        for (int k=0; k < expected.length; k++) {
            if (expected[k]!=heights[k]) {
                diff +=1;
            }
        }
        return diff;
    }
}

Third Maximum Number

LeetCode Problem #414

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 thirdMax(int[] nums) {
        long fir = Long.MIN_VALUE;
        long sec = Long.MIN_VALUE;
        long thi = Long.MIN_VALUE;
        for (int i:nums) {
            if (i == fir || i == sec || i == thi){
                continue;
            }
            if (i>fir) {
                thi = sec;
                sec = fir;
                fir = i;
            }
            else if (i>sec) {
                thi = sec;
                sec = i;
            }
            else if (i>thi) {
                thi = i;
            }
        }
        return (int)((thi == Long.MIN_VALUE)? fir:thi);
    }
}

Find All Numbers Disappeared in an Array

LeetCode Problem #448

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i=0;i<nums.length;i++) {
            int val = Math.abs(nums[i])-1;
            nums[val] = nums[val]>0? -nums[val]:nums[val];
        }
        List<Integer> out = new ArrayList<>();
        for (int j=0;j<nums.length;j++) {
            if (nums[j]>0) {
                out.add(j+1);
            }
        }
        return out;
    }
}

Summary Ranges

LeetCode Problem #228

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
class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> out = new ArrayList<>();
        int size = nums.length;
        if (size == 0) {return out;}
        int slow = 0;
        for (int i=0;i<size-1;i++) {
            if (nums[i+1]-1>nums[i]) {
                if (nums[slow]!=nums[i]) {
                    out.add(nums[slow]+"->"+nums[i]);
                }
                else {
                    out.add(nums[slow]+"");
                }
                slow = i+1;
            }
        }
        if (size<2 || nums[size-1]-1>nums[size-2]) {
            out.add(nums[size-1]+"");
        }
        else {
            out.add(nums[slow]+"->"+nums[size-1]);
        }
        return out;
    }
}

Meeting Rooms

LeetCode Problem #252

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
class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        
        // M2
        int size = intervals.length;
        int[] startArr = new int[size];
        int[] endArr = new int[size];
        
        for (int i=0;i<size;i++) {
            startArr[i] = intervals[i][0];
            endArr[i] = intervals[i][1];
        }
        Arrays.sort(startArr);
        Arrays.sort(endArr);
        
        for (int j=0;j<size-1;j++) {
            if (startArr[j+1]<endArr[j]) {
                return false;
            }
        }
        return true;
        
        
        // M1
        // int size = intervals.length;
        // HashMap<Integer,Integer> hm = new HashMap<>();
        // int[] intArr = new int[size];
        // for (int i=0;i<size;i++) {
        //     intArr[i] = intervals[i][0];
        //     hm.put(intervals[i][0],intervals[i][1]);
        // }
        // Arrays.sort(intArr);
        // for (int j=0;j<size-1;j++) {
        //     if (hm.get(intArr[j])>intArr[j+1]) {
        //         return false;
        //     }
        // }
        // return true;
    }
}

Missing Number

LeetCode Problem #268

1
2
3
4
5
6
7
8
class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = n*(n+1)/2;
        for (int i:nums) {sum -= i;}
        return sum;
    }
}

2022-10-02

Moving Average from Data Stream

LeetCode Problem #346

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MovingAverage {

    List<Double> vals = new ArrayList<>();
    
    int maxN = 0;
    public MovingAverage(int size) {
        maxN = size;
    }
    
    public double next(int val) {
        int n = 0;
        
        vals.add((double)val);
        double temp = 0;
        for(int i = Math.max(0, vals.size() - maxN); i < vals.size(); ++i) {
            temp+=vals.get(i);
            n+=1;
        }
        return temp/n;
    }
}

2022-10-03

Intersection of Two Arrays

LeetCode Problem #349

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
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> hs = new HashSet<>();
        for (int i: nums1) {
            hs.add(i);
        }
        
        List<Integer> out = new ArrayList<>();
        
        for (int j: nums2) {
            if (hs.contains(j)) {
                out.add(j);
                hs.remove(j);
            }
        }
        
        int size = out.size();
        int[] outArr = new int[size];
        int k = 0;
        for (Integer s:out) {
            outArr[k] = s;
            k+=1;
        }
        return outArr;
    }
}

2022-10-03

Intersection of Two Arrays II

LeetCode Problem #350

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
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        
        // M1 HashMap
        HashMap<Integer,Integer> hs = new HashMap<>();
        for (int i: nums1) {
            if (hs.containsKey(i)) {
                int temp = hs.get(i);
                hs.put(i,temp+1);
            }
            else {
                hs.put(i,1);
            }
            
        }
        
        List<Integer> out = new ArrayList<>();
        
        for (int j: nums2) {
            if (hs.containsKey(j) && hs.get(j)>0) {
                out.add(j);
                int temp = hs.get(j);
                hs.put(j,temp-1);
            }
        }
        
        int size = out.size();
        int[] outArr = new int[size];
        int k = 0;
        for (Integer s:out) {
            outArr[k] = s;
            k+=1;
        }
        return outArr;
    }
}

2022-10-05

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
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // M2 Sort & Two Pointer
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        List<Integer> out = new ArrayList<>();
        
        int s1 = nums1.length;
        int s2 = nums2.length;
        
        int p1 = 0;
        int p2 = 0;
        
        while (p1<s1 && p2<s2) {
            if (nums1[p1]==nums2[p2]) {
                out.add(nums1[p1]);
                p1++;
                p2++;
            }
            else if (nums1[p1]<nums2[p2]) {p1++;}
            else {p2++;}
        }
        int size = out.size();
        int[] outArr = new int[size];
        int k = 0;
        for (Integer s:out) {
            outArr[k] = s;
            k+=1;
        }
        return outArr;
    }
}

2022-10-06

Assign Cookies

LeetCode Problem #455

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int sizeG = g.length;
        int sizeS = s.length;
        int ptrG = 0;
        int ptrS = 0;
        int out = 0;
        while (ptrG < sizeG && ptrS < sizeS) {
            if (g[ptrG] <= s[ptrS]) {
                ptrG++;
                ptrS++;
                out++;
            }
            else {
                ptrS++;
            }
        }
        return out;
    }
}

2022-10-07

Next Greater Element I

LeetCode Problem #496

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // M1 Stack & HashMap
        HashMap<Integer,Integer> hm = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int n:nums2) {
            while (!stack.isEmpty() && stack.peek()<n) {
                hm.put(stack.pop(),n);
            }
            stack.push(n);
        }
        
        for (int i=0;i<nums1.length;i++) {
            if (hm.containsKey(nums1[i])) {nums1[i] = hm.get(nums1[i]);}
            else {nums1[i] = -1;}
        }
        return nums1;
    }
}
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
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // M2 HashMap
        HashMap<Integer,Integer> hm = new HashMap<>();
        int s2 = nums2.length;
        hm.put(nums2[s2-1],-1);
        for (int j=s2-2;j>=0;j--) {
            int n1 = nums2[j];
            int n2 = nums2[j+1];
            if (n1<n2) {
                hm.put(n1,n2);
            }
            else {
                int temp = hm.get(n2);
                while (temp < n1 && temp != -1) {
                    temp = hm.get(temp);
                }
                hm.put(n1,temp);
            }
            
        }
        int s1 = nums1.length;
        int[] out = new int[s1];
        for (int k=0;k<s1;k++) {
            out[k] = hm.get(nums1[k]);
        }
        return out;
    }
}

2022-10-08

Longest Harmonious Subsequence

LeetCode Problem #594

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findLHS(int[] nums) {
        
        // M1 Sorting
        Arrays.sort(nums);
        int maxVal = 0;
        int size = nums.length;
        for (int i=0;i<size-1;i++) {
            int j = i+1;
            while (j<size && nums[j]-nums[i]<=1) {
                j++;
            }
            if (i!=size && nums[j-1]!=nums[i]) {
                maxVal = (j-i)> maxVal? (j-i):maxVal;
            }
        }
        return maxVal;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findLHS(int[] nums) {
        
        // M2 HashMap
        HashMap<Integer, Integer> hm = new HashMap<>();
        int maxVal = 0;
        for (int num:nums) {
            hm.put(num, hm.getOrDefault(num, 0)+1);
            if (hm.containsKey(num+1)) {
                maxVal = Math.max(maxVal,hm.get(num)+hm.get(num+1));
            }
            if (hm.containsKey(num-1)) {
                maxVal = Math.max(maxVal,hm.get(num)+hm.get(num-1));
            }
        }
        return maxVal;
    }
}

2022-10-09

Minimum Index Sum of Two Lists

LeetCode Problem #599

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
class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        int s1 = list1.length;
        int s2 = list2.length;
        int minVal = s1+s2;
        List<String> out = new ArrayList<>();
        HashMap<String, Integer> hm = new HashMap<>();
        for (int i=0;i<s1;i++) {
            hm.put(list1[i], i);
        }
        for (int j=0;j<s2;j++) {
            int n;
            if (hm.containsKey(list2[j])) {
                n = hm.get(list2[j]);
                n+=j;
                hm.put(list2[j], n);
                    if (n<minVal) {
                        minVal = n;
                        out.clear();
                        out.add(list2[j]);
                    }
                    else if (n == minVal) {
                        out.add(list2[j]);
                    }
            }

        }
        return out.toArray(new String[out.size()]);
    }
}

2022-10-10

Can Place Flowers

LeetCode Problem #605

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int size = flowerbed.length;
        int out = 0;
        for (int i=0;i<size;i++) {
            if (flowerbed[i]==0) {
                if (i==0 && (size == 1 || flowerbed[i+1]==0)) { // at the head
                    flowerbed[i]=1;out++;
                } 
                else if (i==size-1 && flowerbed[i-1]==0) { // at the tail 
                    flowerbed[i]=1;out++;
                } 
                else if (i!=0 && i!=size-1 && flowerbed[i+1]==0 && flowerbed[i-1]==0) { // in between
                    flowerbed[i]=1;out++;
                } 
            }
            if (out >= n) {return true;}
        }
        return false;
    }
}

2022-10-11

Maximum Product of Three Numbers

LeetCode Problem #628

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maximumProduct(int[] nums) {
        
        // M1 Sorting N(nlogn)
        int size = nums.length;
        Arrays.sort(nums);
        return Math.max(nums[0]*nums[1]*nums[size-1], nums[size-3]*nums[size-2]*nums[size-1]);
        
    }
}
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
class Solution {
    public int maximumProduct(int[] nums) {
        
        // M2 Looping O(n)
        int min1 = Integer.MAX_VALUE; // the smallest
        int min2 = Integer.MAX_VALUE; // the second smallest
        
        int max1 = Integer.MIN_VALUE; // the largest
        int max2 = Integer.MIN_VALUE; // the second largest
        int max3 = Integer.MIN_VALUE; // the third largest
        
        for (int n:nums) {
            if (n<=min1) { // n become the new smallest
                min2 = min1;
                min1 = n;
            } else if (n<=min2) { // n become the new second smallest
                min2 = n;
            }
            
            if (n>=max1) { // n become the new largest
                max3 = max2;
                max2 = max1;
                max1 = n;
            }
            else if (n>=max2) { // n become the new second largest
                max3 = max2;
                max2 = n;
            }
            else if (n>=max3) { // n become the new third largest
                max3 = n;
            }
        }
        
        return Math.max(min1*min2*max1, max3*max2*max1);    
    }
}

2022-10-12

Maximum Average Subarray I

LeetCode Problem #643

Sliding Window method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int size = nums.length;
        double kSum = 0;
        for (int i=0;i<k;i++) {
            kSum += nums[i];
        }
        double maxSum = kSum;
        for (int j=k;j<size;j++) {
            kSum += nums[j];
            kSum -= nums[j-k];
            maxSum = Math.max(maxSum,kSum);
        }
        return maxSum/k;
    }
}

2022-10-13

Set Mismatch

LeetCode Problem #645

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[] findErrorNums(int[] nums) {
        HashMap<Integer, Integer> hm = new HashMap<>();
        int dep=0;
        int missing=0;
        for (int n:nums) {
            hm.put(n, hm.getOrDefault(n,0)+1);
        }
        for (int i=1;i<nums.length+1;i++) {
            if (hm.containsKey(i)) {
                if (hm.get(i)==2) {
                    dep = i;
                }
            }
            else {
                missing = i;
            }
        }
        return new int[]{dep,missing};
    }
}

2022-10-14

Valid Word Square

LeetCode Problem #422

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public boolean validWordSquare(List<String> words) {
        if(words == null || words.size() == 0){
            return true;
        }
        int n = words.size();
        for(int i=0; i<n; i++){
            for(int j=0; j<words.get(i).length(); j++){
                if(j >= n ||  i >= words.get(j).length() || words.get(j).charAt(i) != words.get(i).charAt(j))
                    return false;
            }
        }
        return true;
    }
}

2022-10-15

Find Common Characters

LeetCode Problem #1002

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
class Solution {
    public List<String> commonChars(String[] words) {
        
        int[] prev = count(words[0]);
        
        for (int i=1;i<words.length;i++) {
            prev = intersection(prev,count(words[i]));
        }
        
        List<String> out = new ArrayList<>();
        for (int i =0;i<26;i++) {
            if (prev[i]!=0) {
                char a = 'a';
                a += i;
                String str = String.valueOf(a);
              
                int temp = prev[i];
                while (temp != 0) {
                    out.add(str);
                    temp--;
                }
            }
        }
        return out;
    }

    private int[] intersection(int[] inA, int[] inB) {
        int[] out = new int[26];
        for (int i=0;i<26;i++) {
            out[i] = Math.min(inA[i], inB[i]);
        }
        return out;
    }
    
    
    private int[] count (String inStr) {
        int[] out = new int[26];
        for (char c: inStr.toCharArray()) {
            out[c-'a']++;
        }
        return out;
    }
}

2022-10-23

Max Consecutive Ones II

LeetCode Problem #487

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 findMaxConsecutiveOnes(int[] nums) {
        // M1: Two pointer
        int size = nums.length;
        int slow = 0;
        int fast = 0;
        int nextFast = 0;
        boolean fliped = false;
        int out = 0;
        while (fast<size) {
            if (nums[fast] == 0 && !fliped) {
                fliped = true;
                nextFast = fast;
            }
            else if (nums[fast] == 0 && fliped) {
                int temp = fast-slow;
                out = Math.max(temp,out);
                slow = nextFast+1;
                fliped = false;
                fast = nextFast+1;
                continue;
            }
            fast++;
        }
        return Math.max(fast-slow,out);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        // M2: DP
        int max = 0;
        int curr = 0; // #of ones after prev 0
        int prev = 0; // #of ones before prev 0
        int seenZero = 0; // whether see a zero

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) { // if see a zero
                seenZero = 1; // see
                prev = curr; // now become the past
                curr = 0; // new start
            } else {
                curr++; // else keep life going on
            }

            max = Math.max(max, curr + prev + seenZero); // now + past +(allow one miss)
        }
        return max;
    }
}

2022-11-10

Single Number

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int out = 0;
        for (int n: nums) {
            out ^=n;
        }
        return out;
    }
}

2022-11-22

Happy Number

LeetCode Problem #202

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> hs = new HashSet();
        while (n!=1) {
            int temp = 0;
            while (n != 0) {
                temp = temp + (int)Math.pow((n % 10),2);
                n = n / 10;
            }
            n = temp;
            if (hs.contains(n)) {
                return false;
            }
            else {
                hs.add(n);
            }
        }
        return true;
        
    }
}

2022-11-23

Minimum Index Sum of Two Lists

LeetCode Problem #599

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
class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        int s1 = list1.length;
        int s2 = list2.length;
        int minVal = s1+s2;
        List<String> out = new ArrayList<>();
        HashMap<String, Integer> hm = new HashMap<>();
        for (int i=0;i<s1;i++) {
            hm.put(list1[i], i);
        }
        for (int j=0;j<s2;j++) {
            int n;
            if (hm.containsKey(list2[j])) {
                n = hm.get(list2[j]);
                n+=j;
                hm.put(list2[j], n);
                    if (n<minVal) {
                        minVal = n;
                        out.clear();
                        out.add(list2[j]);
                    }
                    else if (n == minVal) {
                        out.add(list2[j]);
                    }
            }

        }
        return out.toArray(new String[out.size()]);
    }
}

2022-11-23

Contains Duplicate II

LeetCode Problem #219

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int size = nums.length;
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i=0;i<size; i++) {
            int temp = nums[i];
            if (hm.containsKey(temp) && i-hm.get(temp)<=k) {
                return true;
            }
            else {
                hm.put(temp,i);
            }
        }
        return false;
    }
}

2022-11-23

Group Anagrams

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
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hm = new HashMap();
        for (String str: strs) {
            String temp = sortString(str);
            if (hm.containsKey(temp)) {
                List<String> tempL = hm.get(temp);
                tempL.add(str);
                hm.put(temp,tempL);
            }
            else {
                List<String> slist = new ArrayList<>();
                slist.add(str);
                hm.put(temp,slist);
            }
        }
        List<List<String>> out = new ArrayList<>();
        for (List<String> ls:hm.values()) {
            out.add(ls);
        }
        return out;
        
    }
    private String sortString(String inStr) {
        char[] out = inStr.toCharArray();
        Arrays.sort(out);
        return new String(out);
    }
}

2022-11-23

Group Shifted Strings

LeetCode Problem #249

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
class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        HashMap<String, List<String>> hm = new HashMap();
        for (String str: strings) {
            String temp = hash(str);
            if (hm.containsKey(temp)) {
                List<String> tempL = hm.get(temp);
                tempL.add(str);
                hm.put(temp,tempL);
            }
            else {
                List<String> slist = new ArrayList<>();
                slist.add(str);
                hm.put(temp,slist);
            }
        }
        List<List<String>> out = new ArrayList<>();
        for (List<String> ls:hm.values()) {
            out.add(ls);
        }
        return out;
        
    }
    private String hash(String inStr) {
        char[] chars = inStr.toCharArray();
        char[] out = new char[chars.length];
        out[0] = 'a';
        for (int i=1;i<out.length;i++) {
            int temp = chars[i]-chars[0];
            out[i] = (char)((temp+26)%26+97);
        }
        return new String(out);
    }
}

2022-11-24

Last updated on 2022-11-24

References

Arrays 101 - Explore - LeetCode

写在最后

Array相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

原创文章，转载请标明出处
Made by Mike_Zhang




感谢你的支持
Data Structure and Algorithm > Problem Set
#Java #数据结构 #Array
Array Problems
https://ultrafish.io/post/array-problems/
Author
Mike_Zhang
Posted on
March 14, 2022
Licensed under