Press "Enter" to skip to content

Posts published in May 2018

花花酱 LeetCode 830. Positions of Large Groups

Problem

In a stringĀ SĀ of lowercase letters, these letters form consecutive groups of the same character.

For example, a string likeĀ S = "abbxxxxzyy"Ā has the groupsĀ "a",Ā "bb",Ā "xxxx",Ā "z"Ā andĀ "yy".

Call a groupĀ largeĀ if it has 3 or more characters.Ā  We would like the starting and ending positions of every large group.

The final answer should be in lexicographic order.

Example 1:

Input: "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the single large group with starting 3 and ending positions 6.

Example 2:

Input: "abc"
Output: []
Explanation: We have "a","b" and "c" but no large group.

Example 3:

Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]

 

Note:Ā Ā 1 <= S.length <= 1000

Solution: Brute Force

Time complexity: O(n)

Space complexity: O(n)

C++

 

花花酱 LeetCode 832. Flipping an Image

Problem

Given a binary matrixĀ A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed.Ā  For example, flippingĀ [1, 1, 0]Ā horizontally results inĀ [0, 1, 1].

To invert an image meansĀ that eachĀ 0Ā is replaced byĀ 1, and eachĀ 1Ā is replaced byĀ 0.Ā For example, invertingĀ [0, 1, 1]Ā results inĀ [1, 0, 0].

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

  • 1 <= A.length = A[0].length <= 20
  • 0 <= A[i][j]Ā <=Ā 1

Solution 1: Brute Force

Time complexity: O(m*n)

Space complexity: O(m*n)

C++

 

花花酱 LeetCode 810. Chalkboard XOR Game

Problem

We are given non-negative integers nums[i] which are written on a chalkboard.Ā  Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first.Ā  If erasing a number causesĀ the bitwise XOR of all the elements of the chalkboard to becomeĀ 0, then that player loses.Ā  (Also, we’ll say the bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.)

Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example:
Input: nums = [1, 1, 2]
Output: false
Explanation: 
Alice has two choices: erase 1 or erase 2. 
If she erases 1, the nums array becomes [1, 2]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose. 
If Alice erases 2 first, now nums becomes [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.

Notes:

  • 1 <= N <= 1000.
  • 0 <= nums[i] <= 2^16.

Solution: Math

Time complexity: O(n)

Space complexity: O(1)