# 2022-05-28

## 190. Reverse Bits

### Description

Reverse bits of a given 32 bits unsigned integer.

Note:

• Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.

• In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer `-3` and the output represents the signed integer `-1073741825`.

Example 1:

``````Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.``````

Example 2:

``````Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.``````

Constraints:

• The input must be a binary string of length `32`

Follow up: If this function is called many times, how would you optimize it?

### Solution

#### Approach #0

``````func reverseBits(num uint32) uint32 {
var res uint32
for i := 0; i < 32 && num > 0; i++ {
res |= num & 1 << (31 - i)
num >>= 1
}
return res
}``````

#### Approach #1: Divide And Conquer

Without reading the official solution, this approach will never come into my mind...

``````const (
m1 = 0x55555555 // 01010101010101010101010101010101
m2 = 0x33333333 // 00110011001100110011001100110011
m4 = 0x0f0f0f0f // 00001111000011110000111100001111
m8 = 0x00ff00ff // 00000000111111110000000011111111
)

func reverseBits(n uint32) uint32 {
n = n>>1&m1 | n&m1<<1
n = n>>2&m2 | n&m2<<2
n = n>>4&m4 | n&m4<<4
n = n>>8&m8 | n&m8<<8
return n>>16 | n<<16
}``````

## 136. Single Number

### Description

Given a non-empty array of integers `nums`, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

``````Input: nums = [2,2,1]
Output: 1``````

Example 2:

``````Input: nums = [4,1,2,1,2]
Output: 4``````

Example 3:

``````Input: nums = [1]
Output: 1``````

Constraints:

• `1 <= nums.length <= 3 * 10^4`

• `-3 * 10^4 <= nums[i] <= 3 * 10^4`

• Each element in the array appears twice except for one element which appears only once.

### Solution

#### Approach #0

``````func singleNumber(nums []int) int {
res := 0
for _, num := range nums {
res ^= num
}
return res
}``````

## 1021. Remove Outermost Parentheses

### Description

A valid parentheses string is either empty `""`, `"(" + A + ")"`, or `A + B`, where `A` and `B` are valid parentheses strings, and `+` represents string concatenation.

• For example, `""`, `"()"`, `"(())()"`, and `"(()(()))"` are all valid parentheses strings.

A valid parentheses string `s` is primitive if it is nonempty, and there does not exist a way to split it into `s = A + B`, with `A` and `B` nonempty valid parentheses strings.

Given a valid parentheses string `s`, consider its primitive decomposition: `s = P1 + P2 + ... + Pk`, where `Pi` are primitive valid parentheses strings.

Return `s` after removing the outermost parentheses of every primitive string in the primitive decomposition of `s`.

Example 1:

``````Input: s = "(()())(())"
Output: "()()()"
Explanation:
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".``````

Example 2:

``````Input: s = "(()())(())(()(()))"
Output: "()()()()(())"
Explanation:
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".``````

Example 3:

``````Input: s = "()()"
Output: ""
Explanation:
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".``````

Constraints:

• `1 <= s.length <= 105`

• `s[i]` is either `'('` or `')'`.

• `s` is a valid parentheses string.

### Solution

#### Approach #0

``````func removeOuterParentheses(s string) string {
var res, stack []rune
for _, ch := range s {
if ch == ')' {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 {
res = append(res, ch)
}
if ch == '(' {
stack = append(stack, ch)
}
}
return string(res)
}``````

## 34. Find First and Last Position of Element in Sorted Array

### Description

Given an array of integers `nums` sorted in non-decreasing order, find the starting and ending position of a given `target` value.

If `target` is not found in the array, return `[-1, -1]`.

You must write an algorithm with `O(log n)` runtime complexity.

Example 1:

``````Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]``````

Example 2:

``````Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]``````

Example 3:

``````Input: nums = [], target = 0
Output: [-1,-1]``````

Constraints:

• `0 <= nums.length <= 10^5`

• `-10^9 <= nums[i] <= 10^9`

• `nums` is a non-decreasing array.

• `-10^9 <= target <= 10^9`

### Solution

#### Approach #0

``````func binarySearch(nums []int, target int, lower bool) (res int) {
res = len(nums)
for i, j := 0, len(nums)-1; i <= j; {
mid := (i + j) / 2
if nums[mid] > target || (lower && nums[mid] >= target) {
j = mid - 1
res = mid
} else {
i = mid + 1
}
}
return
}

func searchRange(nums []int, target int) []int {
low := binarySearch(nums, target, true)
high := binarySearch(nums, target, false) - 1
if low <= high && high < len(nums) && nums[low] == nums[high] {
return []int{low, high}
}
return []int{-1, -1}
}``````

#### Approach #1

``````func searchRange(nums []int, target int) []int {
low := sort.SearchInts(nums, target)
if low >= len(nums) || nums[low] != target {
return []int{-1, -1}
}
high := sort.SearchInts(nums, target+1) - 1
return []int{low, high}
}``````

## 33. Search in Rotated Sorted Array

### Description

There is an integer array `nums` sorted in ascending order (with distinct values).

Prior to being passed to your function, `nums` is possibly rotated at an unknown pivot index `k` (`1 <= k < nums.length`) such that the resulting array is `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]` (0-indexed). For example, `[0,1,2,4,5,6,7]` might be rotated at pivot index `3` and become `[4,5,6,7,0,1,2]`.

Given the array `nums` after the possible rotation and an integer `target`, return the index of `target` if it is in `nums`, or `-1` if it is not in `nums`.

You must write an algorithm with `O(log n)` runtime complexity.

Example 1:

``````Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4``````

Example 2:

``````Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1``````

Example 3:

``````Input: nums = [1], target = 0
Output: -1``````

Constraints:

• `1 <= nums.length <= 5000`

• `-10^4 <= nums[i] <= 10^4`

• All values of `nums` are unique.

• `nums` is an ascending array that is possibly rotated.

• `-10^4 <= target <= 10^4`

### Solution

#### Approach #0

``````func search(nums []int, target int) int {
n := len(nums)
if n == 0 {
return -1
}
if n == 1 {
if nums[0] == target {
return 0
}
return -1
}

for i, j := 0, n-1; i <= j; {
mid := (i + j) / 2
if nums[mid] == target {
return mid
}
if nums[0] <= nums[mid] {
if nums[0] <= target && target < nums[mid] {
j = mid - 1
} else {
i = mid + 1
}
} else {
if nums[mid] < target && target <= nums[n-1] {
i = mid + 1
} else {
j = mid - 1
}
}
}
return -1
}``````

## 74. Search a 2D Matrix

### Description

Write an efficient algorithm that searches for a value `target` in an `m x n` integer matrix `matrix`. This matrix has the following properties:

• Integers in each row are sorted from left to right.

• The first integer of each row is greater than the last integer of the previous row.

Example 1:

``````Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true``````

Example 2:

``````Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false``````

Constraints:

• `m == matrix.length`

• `n == matrix[i].length`

• `1 <= m, n <= 100`

• `-10^4 <= matrix[i][j], target <= 10^4`

### Solution

#### Approach #0

``````func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
i, j := -1, m-1
for i < j {
mid := (j-i+1)/2 + i
if matrix[mid][0] <= target {
i = mid
} else {
j = mid - 1
}
}
if i == -1 {
return false
}
for p, q := 0, n-1; p <= q; {
mid := (p-q)/2 + q
if matrix[i][mid] == target {
return true
}
if matrix[i][mid] > target {
q = mid - 1
} else {
p = mid + 1
}
}
return false
}``````

#### Approach #1

``````func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
row := sort.Search(m, func(i int) bool { return matrix[i][0] > target }) - 1
if row < 0 {
return false
}
column := sort.SearchInts(matrix[row], target)
return column < n && matrix[row][column] == target
}``````

#### Approach #2

``````func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
i := sort.Search(m*n, func(i int) bool { return matrix[i/n][i%n] >= target })
return i < m*n && matrix[i/n][i%n] == target
}``````

Last updated