# 2022-05-28

## [190. Reverse Bits](https://leetcode.com/problems/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](https://en.wikipedia.org/wiki/Two's_complement). 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

```go
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...

```go
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](https://leetcode.com/problems/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

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

## [1021. Remove Outermost Parentheses](https://leetcode.com/problems/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

```go
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](https://leetcode.com/problems/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

```go
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

```go
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](https://leetcode.com/problems/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

```go
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](https://leetcode.com/problems/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:**

![](https://img.content.cc/a/2022/05/28/12-50-58-439-ccc80b991260d3c4cd95b328c1edf562-43c888.jpeg)

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

**Example 2:**

![](https://img.content.cc/a/2022/05/28/12-51-15-724-7adaf830e264910d53e5d9ed1aeef15b-49240d.jpeg)

```
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

```go
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

```go
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

```go
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
}
```