2024-08-10



function longestCommonSubsequence(text1, text2) {
    let m = text1.length;
    let n = text2.length;
    let dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
 
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (text1[i - 1] === text2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
 
    return dp[m][n];
}
 
// 示例
console.log(longestCommonSubsequence("abcde", "ace")); // 输出应该是 3

这段代码首先定义了一个函数longestCommonSubsequence,它接受两个字符串参数text1text2,并返回它们的最长公共子序列的长度。函数内部,我们使用动态规划的方法创建了一个二维数组dp来存储中间结果。然后,我们遍历字符串text1text2的所有可能的子序列,并根据子序列是否相同来更新dp数组。最终,dp[m][n]存储的就是text1text2的最长公共子序列的长度。最后,我们打印出两个字符串的最长公共子序列长度。

2024-08-10



package main
 
import (
    "fmt"
    "github.com/bwmarrin/snowflake"
)
 
func main() {
    // 初始化一个雪花算法节点,如果你需要多个节点,可以为每个节点指定不同的节点标识符
    node, err := snowflake.NewNode(1)
    if err != nil {
        fmt.Println(err)
        return
    }
 
    // 生成一个唯一ID
    id := node.Generate()
    fmt.Printf("Generated Snowflake ID: %064b\n", id)
}

这段代码演示了如何在Go语言中使用bwmarrin/snowflake库来生成唯一的雪花算法ID。首先,我们初始化了一个雪花算法节点,然后通过调用Generate方法生成了一个ID并打印出来。这个例子简单明了地展示了如何在Go语言中应用雪花算法生成分布式唯一ID。

2024-08-10

在Flutter Web项目中,你可以使用Dart的package:js库来调用JavaScript代码,实现前端常用的算法。以下是10种常用算法的示例代码:

  1. 排序算法:快速排序



import 'package:js/js.dart';
 
@JS()
library js_quicksort_library {
  // 导入JavaScript的排序函数
  external void quickSort(List list);
}
 
void main() {
  List<int> numbers = [10, 2, 7, 4, 3, 5, 6, 8, 9, 1];
  js_quicksort_library.quickSort(numbers);
  print(numbers); // 输出排序后的数组
}
  1. 搜索算法:二分查找



import 'package:js/js.dart';
 
@JS()
library js_binarysearch_library {
  // 导入JavaScript的二分查找函数
  external int binarySearch(List list, num item);
}
 
void main() {
  List<num> numbers = [1, 3, 5, 7, 9, 11];
  int index = js_binarysearch_library.binarySearch(numbers, 7);
  print(index); // 输出7的索引,如果没找到则输出-1
}
  1. 哈希算法:哈希表操作



import 'package:js/js.dart';
 
@JS()
library js_hashtable_library {
  // 导入JavaScript的哈希表操作函数
  external void addItem(Object hashtable, var key, var value);
  external var getItem(Object hashtable, var key);
}
 
void main() {
  var hashtable = js_hashtable_library.JSHashtable();
  js_hashtable_library.addItem(hashtable, 'key1', 'value1');
  var value = js_hashtable_library.getItem(hashtable, 'key1');
  print(value); // 输出键对应的值
}
  1. 图算法:深度优先搜索



import 'package:js/js.dart';
 
@JS()
library js_dfs_library {
  // 导入JavaScript的DFS函数
  external void depthFirstSearch(Object graph, num startNode, Function visitCallback);
}
 
void main() {
  var graph = js_dfs_library.JSGraph();
  js_dfs_library.depthFirstSearch(graph, 1, allowInterop((node) {
    print(node); // 输出访问的节点
  }));
}
  1. 动态规划算法:0-1背包问题



import 'package:js/js.dart';
 
@JS()
library js_knapsack_library {
  // 导入JavaScript的0-1背包算法函数
  external List knapsack(List weights, List values, num capacity);
}
 
void main() {
  List weights = [1, 3, 4];
  List values = [15, 20, 30];
  int capacity = 4;
  List result = js_knapsack_library.knapsack(weights, values, capacity);
  print(result); // 输出背包装载的最大价值
}
  1. 数学问题:斐波那契数列



import 'package:js/js.dart';
 
@JS()
library js_fibonacci_library {
  // 导入JavaScript的斐波那契数列计算函数
  external int fibonacci(int n);
}
 
void main() {
  int n = 10;
  int result = js_fibonacci_library.fibonacci(n);
  print(result); // 输出斐波那契数列的第n项
}
  1. 字符串匹配算法:KMP算法
2024-08-10

在PHP中,可以使用openssl_encrypt函数来实现3DES算法(ECB模式和PKCS5填充)。以下是一个示例代码:




<?php
function des3_encrypt_ecb_pkcs5($data, $key) {
    $iv = openssl_random_pseudo_bytes(openssl_cipher_iv_length('3DES-ECB'));
    $cipher = openssl_encrypt($data, '3DES-ECB', $key, OPENSSL_RAW_DATA, $iv);
    return base64_encode($cipher);
}
 
$key = 'your-3des-key'; // 3DES密钥,长度需为24字节
$plaintext = 'Your plaintext data here';
 
$encrypted = des3_encrypt_ecb_pkcs5($plaintext, $key);
echo "Encrypted: " . $encrypted . "\n";
 
// 解密(这里仅作为示例,实际情况下不会解密3DES ECB模式,因为它不安全)
$decrypted = openssl_decrypt($encrypted, '3DES-ECB', $key, OPENSSL_RAW_DATA, $iv);
echo "Decrypted: " . $decrypted . "\n";
?>

确保你的密钥长度为24字节(3DES的密钥长度有三种选择:168位,112位或80位,但PHP通常需要64位的长度,即8字节,因此你需要重复输入密钥三次以匹配这个长度)。

注意:ECB模式不提供消息的保密性,因此不推荐用于传输敏感数据。此外,这个示例中展示了如何进行加密和解密,但通常不推荐在实际应用中使用3DES,因为它不安全。

2024-08-10



import requests
from bs4 import BeautifulSoup
import re
import pandas as pd
 
# 示例函数:从指定的新闻网站爬取新闻标题和链接
def crawl_news(url):
    response = requests.get(url)
    soup = BeautifulSoup(response.text, 'html.parser')
    news_items = soup.find_all('div', class_='news-item')
    news_data = []
    for item in news_items:
        title = item.find('a').text
        link = item.find('a')['href']
        news_data.append({'title': title, 'link': link})
    return news_data
 
# 示例函数:使用正则表达式提取新闻内容中的关键词
def extract_keywords(content):
    keywords = re.findall(r'[a-zA-Z]+', content)
    return keywords
 
# 示例函数:将新闻数据转化为DataFrame格式
def prepare_dataframe(news_data):
    df = pd.DataFrame(news_data)
    return df
 
# 示例函数:使用K-means算法对新闻进行聚类
from sklearn.cluster import KMeans
 
def cluster_news(data, k=5):
    kmeans = KMeans(n_clusters=k)
    kmeans.fit(data)
    return kmeans.labels_
 
# 示例函数:根据用户的兴趣喜好,推荐相关新闻
def recommend_news(user_interests, news_data):
    recommended_news = [news for news in news_data if any(interest in news.keywords for interest in user_interests)]
    return recommended_news
 
# 示例函数:将新闻推荐给用户
def present_recommendation(recommended_news):
    for news in recommended_news:
        print(f"新闻标题: {news.title}")
        print(f"新闻链接: {news.link}\n")
 
# 假设的用户兴趣喜好
user_interests = ['科技', '健康']
 
# 假设的新闻网站URL
news_url = 'https://example.com/news'
 
# 爬取新闻
news_items = crawl_news(news_url)
 
# 为新闻数据准备DataFrame
df = prepare_dataframe(news_items)
 
# 为新闻数据提取关键词
df['keywords'] = df['title'].apply(extract_keywords)
 
# 使用K-means算法对新闻进行聚类
cluster_labels = cluster_news(df[['title', 'link']])
df['cluster'] = cluster_labels
 
# 根据用户的兴趣喜好,推荐相关新闻
recommended_news = recommend_news(user_interests, df)
 
# 将新闻推荐给用户
present_recommendation(recommended_news)

这个代码示例展示了如何使用Python爬取新闻网站的新闻标题和链接,如何提取关键词,如何使用K-means算法对新闻进行聚类,以及如何根据用户的兴趣喜好推荐相关新闻。这个过程是一个简化的示例,实际应用中需要更复杂的数据预处理和算法优化。

2024-08-10

由于Instagram不推荐使用API进行数据爬取,可能会违反服务条款,这里提供一个简单的示例来说明如何使用Python爬取Instagram的图片。




import requests
import os
 
# 设置Instagram的用户名
username = 'instagram'
 
# 设置保存图片的路径
save_path = 'instagram_images'
 
# 确保保存路径存在
if not os.path.exists(save_path):
    os.makedirs(save_path)
 
# 设置图片的URL前缀
url_prefix = f'https://www.instagram.com/{username}/'
 
# 发送HTTP GET请求
response = requests.get(url_prefix)
 
# 确保请求成功
if response.status_code == 200:
    # 解析响应内容,寻找图片链接
    # 这里需要使用Instagram的API或者正则表达式等来提取图片链接
    # 示例中省略了具体实现
    # image_urls = parse_response(response.text)
    image_urls = []  # 假设我们已经找到了所有图片的URL
 
    # 下载并保存图片
    for i, image_url in enumerate(image_urls):
        response = requests.get(image_url)
        if response.status_code == 200:
            file_path = os.path.join(save_path, f'{i}.jpg')
            with open(file_path, 'wb') as file:
                file.write(response.content)
            print(f'Image {i} saved successfully.')
        else:
            print(f'Failed to download image {i}.')
else:
    print('Failed to retrieve Instagram page.')

请注意,这个代码示例省略了解析响应内容以找到图片链接的部分,实际应用中你需要使用合适的方法来提取这些信息。此外,由于Instagram的页面结构可能会改变,所以解析逻辑也需要定期更新。

此代码只是一个简单的示例,并不适合用于大规模数据爬取,且在没有遵守Instagram的使用条款的情况下使用其API是非法的,应当确保你有权限和明确的许可来进行这样的操作。

2024-08-10

以下是一个简化的动漫推荐系统的核心函数示例,展示了如何使用机器学习模型进行动漫推荐,并且包括了一个简单的Web接口:




from flask import Flask, request, jsonify
import joblib
import pandas as pd
 
app = Flask(__name__)
 
# 加载协同过滤模型
cf_model = joblib.load('cf_model.pkl')
 
# 加载电视剧数据的特征工程管道
with open('tv_feature_pipeline.pkl', 'rb') as f:
    tv_feature_pipeline = joblib.load(f)
 
@app.route('/recommend', methods=['POST'])
def recommend_tv():
    request_data = request.get_json(force=True)
    tv_id = request_data['tv_id']
 
    # 使用特征工程管道转换输入电视剧的特征
    processed_tv = tv_feature_pipeline.transform([[tv_id]])
 
    # 使用cf_model进行推荐
    recommended_tvs = cf_model.predict(processed_tv)
 
    # 查询电视剧信息(例如,用于生成推荐理由)
    # 假设有一个函数get_tv_info(tv_id)可以获取电视剧信息
    recommended_tv_info = [get_tv_info(tv_id) for tv_id in recommended_tvs[0]]
 
    return jsonify({'recommendations': recommended_tv_info})
 
# 假设的get_tv_info函数,实际应用中需要查询数据库或其他数据源
def get_tv_info(tv_id):
    # 这里只是示例,应该从数据库或其他数据源获取实际的电视剧信息
    return {'tv_id': tv_id, 'title': 'Dummy TV Show', 'genre': 'Drama'}
 
if __name__ == '__main__':
    app.run(debug=True)

这个示例使用了Flask框架来创建一个Web接口,允许用户通过POST请求推荐特定电视剧的相似电视剧。推荐系统的核心部分是加载了一个训练好的协同过滤模型,并使用它来进行推荐。在实际应用中,你需要替换数据查询和模型加载的部分,以及完善get\_tv\_info函数来获取实际的电视剧信息。

2024-08-10

深度优先搜索算法(Depth-First-Search, DFS)是图算法中的一种,其对于所有的节点,都会尽可能深的向下搜索,当无法向下搜索时,才会回溯到上一个节点,并尝试其他的路径。

在二叉树的遍历中,我们通常使用DFS来完成。

以下是一个使用Python实现的DFS算法的例子:




class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
def dfs(root):
    if root is None:
        return
    print(root.data)
    dfs(root.left)
    dfs(root.right)
 
# 创建一个二叉树
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
 
# 执行DFS
dfs(root)

在这个例子中,我们首先定义了一个节点类,然后定义了DFS函数,该函数先打印节点的数据,然后递归的对左右子节点进行DFS。

执行这个程序,我们会得到的输出是:1, 2, 4, 5, 3,这就是DFS的执行结果。

DFS在图的遍历中也有广泛的应用,例如在游戏中寻找最优路径,或者在网络爬虫中寻找新的网页等等。

在DFS算法中,我们通常会使用一个栈(在递归中,系统已经为我们做了这个工作)或者显式的栈来帮助我们回溯到上一个节点。

2024-08-10

一、什么是边缘检测

边缘(Edge)本质上是:

图像灰度值发生剧烈变化的位置

例如:

  • 物体轮廓
  • 字体边界
  • 道路边缘
  • 人脸轮廓
  • 缺陷裂纹

都属于边缘。

从数学角度说:

如果图像表示为二维函数:

[
f(x,y)
]

那么边缘就是:

[
\left|\nabla f(x,y)\right|
]

变化最大的区域。(维基百科)


二、边缘检测核心原理

本质就是求 像素梯度(导数)


1)一阶导数:梯度边缘

梯度定义:

[
G=\sqrt{G_x^2+G_y^2}
]

其中:

  • (G_x):x方向变化
  • (G_y):y方向变化

梯度越大,越可能是边缘。


2)二阶导数:Laplacian

二阶导数更适合检测:

  • 细线
  • 点状目标
  • 高频纹理

公式:

[
\nabla^2 f=\frac{\partial^2 f}{\partial x^2}+\frac{\partial^2 f}{\partial y^2}
]

三、经典边缘检测算法


1)Sobel 算法(最常用入门)

Sobel 使用两个卷积核分别计算水平和垂直梯度。(Muegenai)

X方向卷积核

[
\begin{bmatrix}
-1 & 0 & 1 \
-2 & 0 & 2 \
-1 & 0 & 1
\end{bmatrix}
]

Y方向卷积核

[
\begin{bmatrix}
-1 & -2 & -1 \
0 & 0 & 0 \
1 & 2 & 1
\end{bmatrix}
]

Python 实现(纯 OpenCV)

import cv2
import numpy as np

img = cv2.imread("test.jpg", 0)

sobel_x = cv2.Sobel(img, cv2.CV_64F, 1, 0, ksize=3)
sobel_y = cv2.Sobel(img, cv2.CV_64F, 0, 1, ksize=3)

magnitude = cv2.magnitude(sobel_x, sobel_y)

cv2.imshow("sobel", np.uint8(magnitude))
cv2.waitKey(0)

纯 Python 手写 Sobel(深入理解)

import cv2
import numpy as np

img = cv2.imread("test.jpg", 0)

kernel_x = np.array([
    [-1, 0, 1],
    [-2, 0, 2],
    [-1, 0, 1]
])

kernel_y = np.array([
    [-1, -2, -1],
    [0, 0, 0],
    [1, 2, 1]
])

h, w = img.shape
result = np.zeros((h, w))

for i in range(1, h - 1):
    for j in range(1, w - 1):
        region = img[i-1:i+2, j-1:j+2]

        gx = np.sum(region * kernel_x)
        gy = np.sum(region * kernel_y)

        result[i, j] = np.sqrt(gx**2 + gy**2)

result = np.clip(result, 0, 255).astype(np.uint8)
cv2.imshow("manual sobel", result)
cv2.waitKey(0)

四、Canny 边缘检测(工业级最常用)

Canny 是实际项目里最经典的边缘检测算法。(维基百科)

它包含 5个核心步骤


第一步:高斯滤波去噪

先消除噪声:

blur = cv2.GaussianBlur(img, (5, 5), 1.4)

第二步:计算梯度

底层仍然是 Sobel。

[
G=\sqrt{G_x^2+G_y^2}
]

第三步:非极大值抑制(NMS)

作用:

让边缘从“粗线”变成“细线”

保留局部最大值。


第四步:双阈值检测

两个阈值:

  • 高阈值:强边缘
  • 低阈值:弱边缘

第五步:滞后阈值连接

如果弱边缘连接强边缘,则保留,否则去掉。(Python Geeks)


Python 实现 Canny

import cv2

img = cv2.imread("test.jpg", 0)

edges = cv2.Canny(img, 100, 200)

cv2.imshow("canny", edges)
cv2.waitKey(0)

五、自己手写 Canny(核心流程版)

下面给你一个简化版流程,适合算法学习。

import cv2
import numpy as np

img = cv2.imread("test.jpg", 0)

# 1 高斯滤波
blur = cv2.GaussianBlur(img, (5, 5), 1)

# 2 Sobel梯度
gx = cv2.Sobel(blur, cv2.CV_64F, 1, 0)
gy = cv2.Sobel(blur, cv2.CV_64F, 0, 1)

mag = np.sqrt(gx**2 + gy**2)
angle = np.arctan2(gy, gx)

如果你继续深入,可以再实现:

  • NMS
  • 双阈值
  • hysteresis

就接近完整工业版。


六、Sobel vs Canny 对比

算法优点缺点场景
Sobel快、简单噪声敏感教学、预处理
Laplacian细节强容易误检纹理检测
Canny精度高、边缘细计算复杂工业视觉

(OpenCV)


七、工程实战:视频实时边缘检测

import cv2

cap = cv2.VideoCapture(0)

while True:
    ret, frame = cap.read()
    gray = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)

    edges = cv2.Canny(gray, 80, 150)

    cv2.imshow("edge", edges)

    if cv2.waitKey(1) == 27:
        break

cap.release()
cv2.destroyAllWindows()

适用于:

  • 摄像头轮廓识别
  • 实时车道线检测
  • OCR 预处理
  • 缺陷检测

八、生产级优化思路(非常重要)

你做实际项目时建议这样优化:


1)先做 CLAHE 增强

clahe = cv2.createCLAHE(clipLimit=2.0)
img = clahe.apply(img)

提升低对比度边缘。


2)边缘后做形态学闭运算

kernel = np.ones((3,3), np.uint8)
edges = cv2.morphologyEx(edges, cv2.MORPH_CLOSE, kernel)

连接断裂边缘。


3)结合霍夫变换

用于:

  • 表格线检测
  • 文档边框
  • 车道线检测
lines = cv2.HoughLinesP(edges, 1, np.pi/180, 100)

九、边缘检测在 AI / CV 中的作用

边缘是很多高级算法的第一步:

  • OCR文字识别
  • 图像分割
  • 人脸检测
  • 目标检测
  • 视频跟踪
  • 缺陷检测
  • 医学影像

十、总结(面试高频)

核心记忆:


Sobel

一阶梯度 + 卷积核

Canny

高斯滤波 → 梯度 → NMS → 双阈值 → 边缘连接

最佳实践

如果你做生产系统:

优先 Canny + CLAHE + Morphology

这是工业视觉最稳的一套。


2024-08-10

RIP(Routing Information Protocol)是一种内部网关协议(IGP),用于自动发现、维护网络的路由信息。以下是一个简单的RIP路由算法示例:




import time
 
def rip(network):
    distance_vec = {}  # 距离向量,记录到每个节点的距离
    link_cost = {(neighbor, 1) for neighbor in network.keys()}  # 链路开销
 
    # 初始化距离向量
    for destination in network.keys():
        if destination == 'A':  # 假设起点为A
            distance_vec[destination] = 0
        else:
            distance_vec[destination] = float('inf')
 
    # 循环更新路由信息,直到收敛
    while True:
        changes = set()
        for node in network.keys():
            for neighbor, cost in network[node]:
                new_distance = distance_vec[node] + cost
                if new_distance < distance_vec[neighbor]:
                    distance_vec[neighbor] = new_distance
                    changes.add(neighbor)
        if not changes:
            break  # 如果没有节点的距离发生变化,则停止更新
        time.sleep(1)  # 模拟路由更新延迟
 
    return distance_vec
 
# 示例网络拓扑
network_topology = {
    'A': [('B', 1), ('C', 2)],
    'B': [('A', 1), ('D', 1)],
    'C': [('A', 2), ('E', 3)],
    'D': [('B', 1), ('E', 2)],
    'E': [('C', 3), ('D', 2)]
}
 
# 执行RIP路由算法
distance_vector = rip(network_topology)
print(distance_vector)

OSPF(Open Shortest Path First)是一种链路状态路由协议,用于在单个自治系统(AS)内部工作。以下是一个简单的OSPF路由算法示例:




from collections import defaultdict
 
def ospf(network):
    neighbor_cost = defaultdict(dict)  # 邻居表和开销
    link_state_database = {}  # 链路状态数据库
 
    # 初始化邻居表和链路状态数据库
    for node in network:
        for neighbor, cost in network[node].items():
            neighbor_cost[node][neighbor] = cost
            link_state_database[neighbor] = {node: cost}
 
    # 循环更新链路状态数据库,直到稳定
    while True:
        changes = set()
        for node in neighbor_cost:
            for neighbor in neighbor_cost[node]:
                link_state_database[neighbor].update({node: neighbor_cost[node][neighbor]})
                changes.add(neighbor)
        if not changes:
            break  # 如果没有邻居的链路状态发生变化,则停止更新
 
    return link_state_database
 
# 示例网络拓扑
network_topology = {
    'A': {'B': 1, 'C': 2},
    'B': {'A': 1, 'D': 1},
    'C': {'A': 2, 'E': 3},
    'D': {'B': 1, 'E': 2},
    'E': {'C': 3, 'D': 2}
}
 
# 执行OSPF路由算法
link_state_db = ospf(network_topology)
print(link_state_db)

BGP(Border Gateway Protocol)是一种外部网关协议(EGP),用于自治系统之间的路由信息交换。由于BGP设计复杂且超出简单示例的范围,这里仅提供