花花酱 LeetCode 769. Max Chunks To Make Sorted

By zxi on February 2, 2018

题目大意：给你一个0 ~ n-1的排列，问你最多能分成几组，每组分别排序后能够组成0 ~ n-1。

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk. After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Input: arr = [4,3,2,1,0]

Output: 1

Explanation:

Splitting into two or more chunks will not return the required result.

For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

Input: arr = [1,0,2,3,4]

Output: 4

Explanation:

We can split into two chunks, such as [1, 0], [2, 3, 4].

However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

Note:

arr will have length in range [1, 10].
arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

Solution 1: Max so far / Set

Time complexity: O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

int ans = 0;

set<int> s;

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

s.insert(arr[i]);

if (*s.rbegin() == i) ++ans;

}

return ans;

}

};

Solution 2: Max so far

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int maxChunksToSorted(vector<int>& arr) {

int ans = 0;

int m = 0;

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

m = max(m, arr[i]);

if (m == i) ++ans;

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 5 ms

class Solution {

public int maxChunksToSorted(int[] arr) {

int max = 0;

int ans = 0;

for (int i = 0; i < arr.length; ++i) {

max = Math.max(max, arr[i]);

if (max == i) ++ans;

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 53 ms

"""

class Solution:

def maxChunksToSorted(self, arr):

m = 0

ans = 0

for i, n in enumerate(arr):

if n > m: m = n

if m == i: ans += 1

return ans

花花酱 LeetCode 766. Toeplitz Matrix

By zxi on February 2, 2018

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.
Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]

Output: True

Explanation:

1234

5123

9512

In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.

Example 2:

Input: matrix = [[1,2],[2,2]]

Output: False

Explanation:

The diagonal "[1, 2]" has different elements.

Note:

matrix will be a 2D array of integers.
matrix will have a number of rows and columns in range [1, 20].
matrix[i][j] will be integers in range [0, 99].

Idea:

Check m[i][j] with m[i-1][j-1]

Solution: Brute Force

Time complexity: O(n*m)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

bool isToeplitzMatrix(vector<vector<int>>& matrix) {

for (int i = 1; i < matrix.size(); ++i)

for (int j = 1; j < matrix[0].size(); ++j)

if (matrix[i][j] != matrix[i - 1][j - 1]) return false;

return true;

}

};

Java

// Author: Huahua

// Running time: 29 ms

class Solution {

public boolean isToeplitzMatrix(int[][] matrix) {

for (int i = 1; i < matrix.length; ++i)

for (int j = 1; j < matrix[0].length; ++j)

if (matrix[i][j] != matrix[i - 1][j - 1]) return false;

return true;

}

Python3

"""

Author: Huahua

Running time: 99 ms

"""

class Solution:

def isToeplitzMatrix(self, matrix):

m = len(matrix)

n = len(matrix[0])

for i in range(1, m):

for j in range(1, n):

if matrix[i][j] != matrix[i - 1][j - 1]: return False

return True

花花酱 LeetCode 771. Jewels and Stones

By zxi on February 2, 2018

题目大意：给你宝石的类型，再给你一堆石头，返回里面宝石的数量。

Problem:

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

S and J will consist of letters and have length at most 50.
The characters in J are distinct.

Solution 1: HashTable

Time complexity: O(|J| + |S|)

Space complexity: O(128) / O(|J|)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int numJewelsInStones(string J, string S) {

std::vector<int> f(128, 0);

int ans = 0;

for (const char j : J)

f[j] = 1;

for (const char s : S)

ans += f[s] & 1;

return ans;

}

};

C++ v2

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

int numJewelsInStones(const string& J, const string& S) {

std::set<char> f(J.begin(), J.end());

return std::count_if(S.begin(), S.end(),

[&f](const char c) { return f.count(c); });

}

};

Java

// Author: Huahua

// Running time: 18 ms

class Solution {

public int numJewelsInStones(String J, String S) {

int[] f = new int[128];

for (final char c : J.toCharArray())

f[c] = 1;

int ans = 0;

for (final char c : S.toCharArray())

ans += f[c];

return ans;

}

Python

"""

Author: Huahua

Running time: 43 ms

"""

class Solution(object):

def numJewelsInStones(self, J, S):

f = set(J)

return sum([s in f for s in S])

Posts published in February 2018

花花酱 LeetCode 769. Max Chunks To Make Sorted

花花酱 LeetCode 766. Toeplitz Matrix

花花酱 LeetCode 771. Jewels and Stones

Problem:

Example 1:

Example 2:

Solution 1: HashTable

C++

C++ v2

Java

Python