# An interesting problem solved by Dijkstra

Dijkstra is an important algorithm can be used to solve the SSSP problem for graphs with positive weights. A template for can be found from .

## 882. Reachable Nodes In Subdivided Graph

The above problem can be solved by using exactly the Dijkstra algorithm. The basic idea is:

1. build a graph by using the weight as the cnt for each edge
2. compute the shortest path from 0 to each node
3. then for each edge ab, from a to pick up the maximum number of available moves to the direction of ab; from b to pick up the maximum number of available moves to the direction of…

# Rotate a Box Under Gravity

We can solve the problem by using two pointers. For each row, we use two pointers:

• left and right
• left indicate the box we shoud move
• right indicate the available location to be moved.

# Code

`vector<vector<string>> rotate(vector<vector<string>>& matrix){    const int n = matrix.size(), m = matrix[0].size();    vector<vector<string>> newmatrix(m, vector<string>(n));    for (int i = 0; i < n; ++i){        for (int j = 0; j < m; ++j){            newmatrix[j][n-i-1] = matrix[i][j];        }        }    return newmatrix;}vector<vector<string>> solve(vector<vector<string>>& matrix) {    if (matrix.empty() || matrix[0].empty()) return matrix;    const int n = matrix.size(), m = matrix[0].size()…`

# 背景

## 计算机模型BERT 怎么看

BERT是一种很fancy的基于计算机学习的一种模型，我们看看bert怎么看。以下结果来自

# Coding Case Styles: Camel, Snake and CamelSnake

If you are a SWE, you should be familar with Coding case styles like Camel. If you are a python programmer, you should use lots of Snake coding style to name your variables.

Here I am going to introduce the CamelSnake name style as shown in the following example

Suppose we have a Traveling salesman problem, we have the start city, end city and cost. We wanna save a dictionary (map) with the key as (start, end) and value as cost., we will have:

• Camel: startEndCost
• Snake: start_end_cost
• CamelSnake: startEnd_cost

Personally, I feel that the third way may be more…

# Naive DP

## High level explanation

The idea is pretty simple, kind of like , we have two possible actions:

• Take
• Not take.

Specifically,

`// take this start (i), the res will be profit + dp(j) where j is first non overlap index after i.// not take this start (i), the res will be dp(i+1)`

## Code

`typedef pair<int, int> PII;const int N = 5e4 + 10;int memo[N];class Solution {public:    int dp(vector<pair<PII, int>>& startEnd_pro, int i){        const int n = startEnd_pro.size();        if (i == n) return 0…`

# Such a nice two pointer problem

## 633. Sum of Square Numbers

`class Solution {public:    bool judgeSquareSum(int c) {        if (c < 0) return false;        long long left = 0, right = (long long)(sqrt(c));        while (left <= right){            long long sum = left*left + right*right;            if (sum == c) return true;            if (sum < c) left++;            if (sum > c) right--;        }        return false;      }};`

# Explanation

We can use coordinate compression to solve this probem. Detail explanation can be found .

Our idea is this: we’ll take all the `x` and `y` coordinates, and re-map them to `0, 1, 2, ...`etc. For example, if `rectangles = [[0,0,200,200],[100,0,200,300],[100,0,300,100]]`, we could re-map it to `[[0,0,2,2],[1,0,2,3],[1,0,3,1]]`. Then, we can solve the problem with brute force. However, each region may actually represent some larger area, so we'll need to adjust for that at the end. From [1]

# Code

`/*time complexity: O(n^3) where n is the number of rectangles.apace complexity: O(n^2)*/typedef long long int64;const int…`

# Problem and explanation

For the problem (It is in Chinese you may need google translate to understand the meaning of this question), we can solve it by first finding the topological sorting results and then from there, run a DP to solve the problem.

# Reference Code

`#include <iostream>#include <cstring>#include <algorithm>#include <queue>using namespace std;void  solve(int n, vector<vector<int>>& graph, vector<int> & indegree, string& code){    vector<int> cnt(26, 0);    for (auto c: code) cnt[c…`

# Binary search and two pointer

## binary search

We can use a binary search to solve this problem. The idea is pretty straightforward. Explore different legth to see whether it works. In order to speed up, prefix sum is also used.

58 is the scope of the acsii code from A to z.

`class Solution {public:    bool good(int mid,   vector<vector<int>> &frequency,  vector<int>& cnt){        for (int i = mid; i <frequency.size(); ++i){            bool found = true…`

# August 13, github requested URL 403

Today I got the following errors when accessing the github

`remote: Support for password authentication was removed on August 13, 2021. Please use a personal access token instead.remote: Please see https://github.blog/2020-12-15-token-authentication-requirements-for-git-operations/ for more information.fatal: unable to access 'https://github.com/XXX/XXX.git/': The requested URL returned error: 403`

My solution is firstly , and then using the following command to clone the repo, then it works.

`git clone https://<TOKEN>@github.com/<user_name>/<repo_name>.git`

Or you can

`git remote set-url origin https://<TOKEN>@github.com/<user_name>/<repo_name>.git`

Then everything works.

## Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Get the Medium app