Recently, I found a source code about Bluetooth positioning and navigation. Through its analysis and research, I have a deep understanding of the positioning and navigation process of the entire Bluetooth algorithm. Learn about Bluetooth signal acquisition, distance estimation, positioning calculation, Kalman model and other aspects.

377. Combination Sum IV

This is also a full knapsack problem. It looks similar to the coins change ii, but the difference here is that we need to get the permutation of the solutions instead of combination. So in this case we need to iterate the knapsack space first, then iterate the items.

494. Target Sum

a. Brute-force DFS recursive solution

The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Dynamic Programming (commonly referred to as DP) is an algorithmic technique for solving a problem by recursively breaking it down into simpler subproblems and using the fact that the optimal solution to the overall problem depends upon the optimal solution to it’s individual subproblems. Here is an interesting Quora question How should I explain dynamic programming to a 4-year-old?.

56. Merge Intervals

Similar to other sgement related problems. The first thing we need to do is to sort the slice. Once we have a sorted segment slice, we can iterate over all items and merge them. Note there is one edge case we need to cover after the iteration, either we merged all segments into one or the last one can’t be merged into the previous segment.

1005. Maximize Sum Of Array After K Negations

To get a maximum sum, we need to convert as many negative numbers to positive ones. If there is still an odd times of converting number left, we just need to convert the smallest positive number to a negative one

55. Jump Game

a. Greedy solutions

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are best fit for Greedy.

Backtracking can also be used to solve chessboard problems.

51. N-Queens

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

func solveNQueens(n int) [][]string {
    result := [][]string{}
    board := make([][]string, n)
    for i := 0; i < n; i++ {
        board[i] = make([]string, n)
        for j := 0; j < n; j++ {
            board[i][j] = "."
        }
    }
    isValid := func(row, col int) bool {
        for i := 0; i < row; i++ {
            if board[i][col] == "Q" {
                return false
            }
        }
        for i := 0; i < col; i++ {
            if board[row][i] == "Q" {
                return false
            }
        }
        for i, j := row, col; i >= 0 && j >= 0; i, j = i - 1, j - 1 {
            if board[i][j] == "Q" {
                return false
            }
        }
        for i, j := row, col; i >= 0 && j < n; i, j = i - 1, j + 1 {
            if board[i][j] == "Q" {
                return false
            }
        }
        return true
    }
    var backtracking func(int)
    backtracking = func(row int) {
        if row == n {
            temp := make([]string, n)
            for i, boardRow := range board {
                temp[i] = strings.Join(boardRow, "")
            }
            result = append(result, temp)
            return
        }
        for col := 0; col < n; col++ {
            if isValid(row, col) {
                board[row][col] = "Q"
                backtracking(row + 1)
                board[row][col] = "."
            }
        }
    }
    backtracking(0)
    return result
}