Posts published in “Algorithms”

花花酱 LeetCode 643. Maximum Average Subarray I

By zxi on July 16, 2018

Problem

题目大意：找出k长度的子数组的平均值的最大值。

https://leetcode.com/problems/maximum-average-subarray-i/description/

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].

Solution: Sliding Window

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 124 ms

class Solution {

public:

double findMaxAverage(vector<int>& nums, int k) {

const int n = nums.size();

int sum = 0;

int ans = INT_MIN;

for (int i = 0; i < n; ++i) {

if (i >= k) sum -= nums[i - k];

sum += nums[i];

if (i + 1 >= k) ans = max(ans, sum);

}

return static_cast<double>(ans) / k;

}

};

Problem

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n²).
There is only one duplicate number in the array, but it could be repeated more than once.

Solution1: Binary Search

Time complexity: O(nlogn)

Space complexity: O(1)

Find the smallest m such that len(nums <= m) > m, which means m is the duplicate number.

In the sorted form [1, 2, …, m1, m2, m + 1, …, n]

There are m+1 numbers <= m

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int findDuplicate(vector<int>& nums) {

int l = 1;

int r = nums.size();

while (l < r) {

int m = (r - l) / 2 + l;

int count = 0; // len(nums <= m)

for (int num : nums)

if (num <= m) ++count;

if (count <= m)

l = m + 1;

else

r = m;

}

return l;

}

};

Solution: Linked list cycle

Convert the problem to find the entry point of the cycle in a linked list.

Take the number in the array as the index of next node.

[1,3,4,2,2]

0->1->3->2->4->2 cycle: 2->4->2

[3,1,3,4,2]

0->3->4->2->3->4->2 cycle 3->4->2->3

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int findDuplicate(vector<int>& nums) {

int slow = 0;

int fast = 0;

while (true) {

slow = nums[slow];

fast = nums[nums[fast]];

if (slow == fast) break;

}

fast = 0;

while (fast != slow) {

slow = nums[slow];

fast = nums[fast];

}

return slow;

}

};

花花酱 LeetCode 704. Binary Search

By zxi on July 12, 2018

Problem

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

Note:

You may assume that all elements in nums are unique.
n will be in the range [1, 10000].
The value of each element in nums will be in the range [-9999, 9999].

Solution: Binary Search

Time complexity: O(logn)

Space complexity: O(1)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

int search(vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

int m = (r - l) / 2 + l;

if (nums[m] == target)

return m;

else if (nums[m] > target)

r = m;

else

l = m + 1;

}

return -1;

}

};

STL

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int search(vector<int>& nums, int target) {

auto it = lower_bound(nums.begin(), nums.end(), target);

if (it == nums.end() || *it != target) return -1;

return it - nums.begin();

}

};

花花酱 LeetCode 775. Global and Local Inversions

By zxi on July 9, 2018

Problem

We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.

Example 2:

Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.

Note:

A will be a permutation of [0, 1, ..., A.length - 1].
A will have length in range [1, 5000].
The time limit for this problem has been reduced.

Solution1: Brute Force (TLE)

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: TLE (208/208 test cases passed)

class Solution {

public:

bool isIdealPermutation(vector<int>& A) {

const int n = A.size();

int local = 0;

for (int i = 0; i < n - 1; ++i)

if (A[i] > A[i + 1]) ++local;

int global = 0;

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

if (A[i] > A[j] && ++global > local) return false;

return global == local;

}

};

Solution2: MergeSort

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 52 ms (<96.42%)

class Solution {

public:

bool isIdealPermutation(vector<int>& A) {

const int n = A.size();

int local = 0;

for (int i = 0; i < n - 1; ++i)

if (A[i] > A[i + 1]) ++local;

tmp = vector<int>(n);

int global = mergeSort(A, 0, n - 1);

return global == local;

}

private:

vector<int> tmp;

int mergeSort(vector<int>& A, int l, int r) {

if (l >= r) return 0;

const int len = r - l + 1;

int m = (r - l) / 2 + l;

int inv = mergeSort(A, l, m) + mergeSort(A, m + 1, r);

int i = l;

int j = m + 1;

int k = 0;

while (i <= m && j <= r) {

if (A[i] <= A[j]) {

tmp[k++] = A[i++];

} else {

tmp[k++] = A[j++];

inv += m - i + 1;

}

while (i <= m) tmp[k++] = A[i++];

while (j <= r) tmp[k++] = A[j++];

std::copy(tmp.begin(), tmp.begin() + len, A.begin() + l);

return inv;

}

};

// Author: Huahua

// Running time: 208 ms

public class Solution {

public bool IsIdealPermutation(int[] A) {

var n = A.Length;

var localInv = 0;

for (var i = 1; i < n; ++i)

if (A[i] < A[i - 1]) ++localInv;

tmp = new int[n];

var globalInv = MergeSort(A, 0, n - 1);

return localInv == globalInv;

}

private int[] tmp;

private int MergeSort(int[] A, int l, int r) {

if (l >= r) return 0;

int m = (r - l) / 2 + l;

int inv = MergeSort(A, l, m) + MergeSort(A, m + 1, r);

int i = l;

int j = m + 1;

int k = 0;

while (i <= m && j <= r) {

if (A[i] <= A[j]) {

tmp[k++] = A[i++];

} else {

inv += m - i + 1;

tmp[k++] = A[j++];

}

while (i <= m) tmp[k++] = A[i++];

while (j <= r) tmp[k++] = A[j++];

Array.Copy(tmp, 0, A, l, k);

return inv;

}

Solution3: Input Property

Input is a permutation of [0, 1, …, N – 1]

Time Complexity: O(n)

Space Complexity: O(1)

// Author: Huahua

// Running time: 40 ms (<99.26%)

class Solution {

public:

bool isIdealPermutation(vector<int>& A) {

for (int i = 0; i < A.size(); ++i)

if (abs(A[i] - i) > 1) return false;

return true;

}

};

花花酱 LeetCode 840. Magic Squares In Grid

By zxi on July 8, 2018

Problem

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).

Example 1:

Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15

Solution

Time complexity: O(m*n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int numMagicSquaresInside(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

int ans = 0;

for (int i = 0; i < m - 2; ++i)

for (int j = 0; j < n - 2; ++j)

ans += magic(grid, j, i);

return ans;

}

private:

int magic(const vector<vector<int>>& grid, int x, int y) {

vector<int> rows(3);

vector<int> cols(3);

vector<int> exps{15, 15, 15};

int dig = 0;

for (int i = 0; i < 3; ++i)

for (int j = 0; j < 3; ++j) {

int v = grid[y + i][x + j];

if (v <= 0 || v > 9) return 0; // must between 1 and 9

rows[i] += v;

cols[j] += v;

if (i == j) dig += v;

}

return rows == exps && cols == exps && dig == 15;

}

};

Posts published in “Algorithms”

花花酱 LeetCode 643. Maximum Average Subarray I

Problem

Solution: Sliding Window

Related Problems

花花酱 LeetCode 287. Find the Duplicate Number

Problem

Solution1: Binary Search

Solution: Linked list cycle

花花酱 LeetCode 704. Binary Search

Problem

Solution: Binary Search

花花酱 LeetCode 775. Global and Local Inversions

Problem

Solution1: Brute Force (TLE)

Solution2: MergeSort

Solution3: Input Property

花花酱 LeetCode 840. Magic Squares In Grid

Problem

Solution