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…

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()…

背景

标题是anpu Guan Yu Wo Ai Ni的一句最有名的歌词。全部歌词谷歌“关于我爱你 歌词” 可得。对于歌词的最初来源可以看中anpu的碎碎念。个人以为这里讲的是得到和失去的关系,人生中大概率失去小概率的到,所以失去才是常态(人生),得到的便是幸运(侥幸)。一直不太完全理解这句歌词,直到有一天,想到这里,且若是能够把歌词略作改动:

我拥有的都是侥幸呀,我失去的是人生。

会变的更庸俗一点,不过这刚好让我可以更加容易懂这句话的意思。

计算机模型BERT 怎么看

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

显然在训练bert模型的时候,bert读过了这个歌词。通过学习人类的语言,bert好似也已经明白了这个道理。参考如下:


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…

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;
}
};

Problem

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…

Introduction

We know that DP can be solved by building toplogical sort graph. If you are not very clear about this, please check

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

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…

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 

Or you can

git remote set-url origin 

Then everything works.

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store