Skip to content

Instantly share code, notes, and snippets.

View xmyqsh's full-sized avatar
🏠
Working from home

xmyqsh

🏠
Working from home
View GitHub Profile
@xmyqsh
xmyqsh / LeetCode_1515. 服务中心的最佳位置
Last active March 29, 2021 02:47
(自创)25点法求最短欧式距离选址问题;该方法可轻松扩展为经典的m个最佳位置的选址问题,能够在O(25^m * log(最大距离/精度) * m * n)的时间内找到最优解,其中n为待服务地点数,m为最佳选址位置数;优势:1. 方便GPU加速,2. 最优解保证 3. 相比于基于4点的3分法在二维上的扩展解法,该25点法可轻松扩展为m个最佳位置的选址问题,而前者不能
class Solution {
public:
double getMinDistSum(vector<vector<int>>& positions) {
double minX = 200, maxX = -1, minY = 200, maxY = -1;
for (const auto& p : positions) {
double x = p[0], y = p[1];
minX = min(minX, x);
maxX = max(maxX, x);
minY = min(minY, y);
maxY = max(maxY, y);
@xmyqsh
xmyqsh / LintCode_1684.K-wolf数.cpp
Last active February 23, 2021 13:37
数位dp,注意状态的定义和caching策略,给ringBuff点赞:)
/*
Alice认为整数 x是K-wolf数,如果x的十进制表示中的每k个相邻数字都是不同的。
给定(l,r,k),请计算在[l,r]范围内有多少个K-Wolf数。
样例
样例 1:
输入: l=1,r=1,k=2
输出: 1
解释:
@xmyqsh
xmyqsh / LintCode_1693.小财迷走迷宫.cpp
Last active February 24, 2021 10:18
BFS计算邻接矩阵,DFS+回溯暴力搜索,可以状态caching进一步优化,状态定义:[源节点][长度为node数的01字符串表示结点的访问状态],但是,重叠子问题比较少,只能做到常数级别的优化,相应的,状态空间庞大,呈阶乘级别增长
/* 题目描述:
给定一个 n * m 的迷宫 maze, 其中:
. 表示空地
S 表示起点
T 表示终点
* 表示障碍物
0~9 表示不同的宝物
请问从起点开始, 在拿到所有宝物之后走到终点, 最少需要多少步? 如果无法拿到全部的宝物并走到终点, 返回 -1.
样例
样例 1:
@xmyqsh
xmyqsh / minAnd.cpp
Last active June 28, 2020 12:13
n个数里面选k个,使得k个数相与结果最小,n<=40, 0<=每个数字<2^60
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
TrieNode() {
next[0] = next[1] = 0;