2024-08-15

A*(A-Star)搜索算法是一种路径规划算法,它能够为网格或任何其他类型的图形中的任务节点找到最低成本的路径到目标节点。它是一种启发式搜索算法,使用了一个估价函数来评估从开始节点到任何给定节点的成本。

A*算法的特征:

  • 启发式搜索:A*算法使用了一种启发式,即它估计了每个节点到目标的距离,并选择了最有可能的节点进行下一步搜索。
  • 最低成本路径:A*算法保证找到最低成本的路径到目标节点。
  • 使用估价函数:A*算法使用了一个估价函数f(n) = g(n) + h(n),其中g(n)是从开始节点到当前节点的实际成本,h(n)是从当前节点到目标节点的估计成本。

A*算法的公式:

f(n) = g(n) + h(n)

  • g(n) 是从开始节点到当前节点的实际移动代价总和。
  • h(n) 是从当前节点到目标节点的估计移动代价总和。
  • f(n) 是从开始节点到当前节点的总估计移动代价。

Python示例代码(带详细注释):




class Node:
    def __init__(self, parent=None, position=None):
        self.parent = parent
        self.position = position
 
    def __repr__(self):
        return f"Node({self.position})"
 
def heuristic(node, end_node):
    # 这是一个简单的例子,通常使用Manhattan距离或欧氏距离
    return abs(node.position[0] - end_node.position[0]) + abs(node.position[1] - end_node.position[1])
 
def search(start_node, end_node):
    closed_set = set()
    open_set = {start_node}
 
    while open_set:
        current = min(open_set, key=lambda o: o.position)  # 选择f值最小的节点
        if current == end_node:
            path = []
            current = current.parent
            while current in closed_set:
                path.append(current.position)
                current = current.parent
            return path[::-1]  # 返回从开始节点到结束节点的路径
 
        open_set.remove(current)
        closed_set.add(current)
 
        for neighbor in current.neighbors:
            if neighbor in closed_set:
                continue
 
            neighbor.g = current.g + 1  # 设置g值为父节点的g值加一
            neighbor.h = heuristic(neighbor, end_node)  # 设置h值
            neighbor.parent = current
 
            if neighbor not in open_set:
                open_set.add(neighbor)
            else:
                if neighbor.g > current.g + 1:  # 更新g值
                    neighbor.g = current.g + 1
                    neighbor.parent = current
    return None
 
# 示例使用
start_node = Node(position=(0, 0))
end_node = Node(position=(4, 4))
# 假设neighbors是节点的邻居列表
start_node.neighbors = [Node(position=(0, 1)), Node(position=(1, 0))]
# ...为其他节点设置neighbors属性
path = search(start_node, end_node)
print(path)

这个Python示例代码定义了一个Node类来表示图中的节点,并提供了一个heuristic函数来估计从当

2024-08-15

CSS 优先级是由四个级别组成:

  1. 内联样式(Inline style)- 优先级最高,为 1000。
  2. ID 选择器(ID selectors)- 优先级为 0100。
  3. 类选择器(Class selectors)、属性选择器(Attribute selectors)和伪类(Pseudo-classes)- 优先级为 0010。
  4. 元素选择器(Type selectors)和伪元素(Pseudo-elements)- 优先级为 0001。

优先级计算时,将这四个级别的数值依次相加,然后比较数值大小。如果两个规则的优先级数值相同,则后定义的规则将会被应用。

例如,考虑以下两个选择器:




#myId .myClass > p { color: red; } /* 优先级 = 0100 + 0010 + 0001 = 1110 */
p#myId > .myClass { color: blue; } /* 优先级 = 0001 + 0100 + 0010 = 1100 */

根据优先级算法,p#myId > .myClass 的规则将会被应用,因为它的优先级更高(1100 > 1110)。

注意:继承的样式不参与优先级计算,并且被认为具有最低的优先级。

2024-08-15

排列组合是数学中的一个基本概念,主要有两种形式:排列和组合。

  1. 排列:排列是指将n个不同的元素,每个元素都有可能出现在每一个位置上。所以,对于n个元素的排列,总共有n!种可能。
  2. 组合:组合是指从n个不同的元素中,选取r个元素进行组合,这里不考虑顺序,所以,对于n个元素的组合,总共有C(n, r) = n! / (r! * (n-r)!)种可能。

以下是使用JavaScript实现排列和组合算法的示例代码:

  1. 排列算法:



function factorial(n) {
    if (n === 0 || n === 1) {
        return 1;
    }
    return n * factorial(n - 1);
}
 
function permutation(n, k) {
    return factorial(n) / factorial(n - k);
}
 
console.log(permutation(5, 3)); // 输出: 60

在上述代码中,factorial函数用于计算一个数的阶乘,permutation函数用于计算排列数。

  1. 组合算法:



function factorial(n) {
    if (n === 0 || n === 1) {
        return 1;
    }
    return n * factorial(n - 1);
}
 
function combination(n, k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}
 
console.log(combination(5, 3)); // 输出: 10

在上述代码中,combination函数用于计算组合数。

以上就是使用JavaScript实现排列和组合算法的简单示例。

2024-08-15

题目描述:

给定一个字符串,请设计一个算法,将字符串中的所有空格替换成 "%20" 。

解决方案:

  1. Java 解法:



public class Solution {
    public String replaceSpaces(StringBuffer str) {
        return str.toString().replace(" ", "%20");
    }
}
  1. JavaScript 解法:



function replaceSpaces(str) {
    return str.replace(/ /g, '%20');
}
  1. Python 解法:



class Solution:
    def replaceSpaces(self , S: str) -> str:
        return S.replace(' ', '%20')
  1. C 解法:



#include <stdio.h>
#include <string.h>
 
void replaceSpaces(char str[]) {
    int i, j, len = strlen(str);
    for (i = j = 0; i < len; i++) {
        if (str[i] == ' ') {
            str[j++] = '%';
            str[j++] = '2';
            str[j++] = '0';
        } else {
            str[j++] = str[i];
        }
    }
    str[j] = '\0'; // 不要忘记添加结束符
}
 
int main() {
    char str[] = "Hello World!";
    replaceSpaces(str);
    printf("%s", str);
    return 0;
}
  1. C++ 解法:



#include <iostream>
#include <string>
#include <algorithm>
 
std::string replaceSpaces(std::string str) {
    std::replace(str.begin(), str.end(), ' ', '%20');
    return str;
}
 
int main() {
    std::string str = "Hello World!";
    std::string replacedStr = replaceSpaces(str);
    std::cout << replacedStr;
    return 0;
}

以上代码提供了不同语言的实现方法,主要使用了字符串替换的方法。对于 Java 和 JavaScript,使用了 String 类的 replace 方法;对于 Python,使用了 str 的 replace 方法;对于 C 和 C++,使用了标准库中的算法 replace。

2024-08-14

滑动窗口算法是一种用于处理字符串或数组中子串问题的高效方法。它通过维护一个窗口,在遍历字符串或数组的过程中,不断更新窗口大小,从而找出满足条件的子串或子序列。

在LeetCode上,滑动窗口算法常见于以下问题类型:

  1. 子串问题:找出字符串中最长/最短的子串满足某种条件。
  2. 字符统计:计算字符串中字符出现的次数。
  3. 字母异位词:判断两个字符串是否由相同的字母构成,可以考虑使用滑动窗口。

以下是一些使用滑动窗口解决的经典问题:

  • 无重复字符的最长子串
  • 滑动窗口最大值
  • 最小滑动窗口范围
  • 滑动窗口中的最大值

解决这些问题通常需要设置两个指针,一个代表窗口的开始,另一个代表窗口的结束,根据需要更新窗口的大小或移动窗口。

以下是无重复字符的最长子串的示例代码:




class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 使用哈希集合记录字符是否出现过
        occ = set()
        n = len(s)
        # 右指针,初始值为-1表示还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断扩大窗口直到出现重复字符
                occ.add(s[rk + 1])
                rk += 1
            # 更新最长无重复子串的长度
            ans = max(ans, rk - i + 1)
        return ans

滑动窗口算法是一种非常实用的技巧,可以解决许多字符串和数组问题。理解和熟练运用该算法对于高效解决编程问题至关重要。

2024-08-14

在Java中使用雪花算法生成全局唯一ID的示例代码如下:




import java.util.concurrent.atomic.AtomicLong;
 
public class SnowflakeIdGenerator {
    // 64位ID的各个部分所占的位数
    private final long twepoch = 1288834974657L; // 起始时间戳 (2010-11-04 09:42:54.657)
    private final long workerIdBits = 5L; // 工作机器ID所占的位数
    private final long datacenterIdBits = 5L; // 数据中心ID所占的位数
    private final long sequenceBits = 12L; // 序列号所占的位数
 
    // 这些位都是直接按位或(|)运算,所以这里需要左移运算符(<<)
    private final long workerIdShift = sequenceBits;
    private final long datacenterIdShift = sequenceBits + workerIdBits;
    private final long timestampShift = sequenceBits + workerIdBits + datacenterIdBits;
 
    private final long sequenceMask = -1L ^ (-1L << sequenceBits); // 生成序列的掩码
 
    private long workerId; // 工作机器ID
    private long datacenterId; // 数据中心ID
    private long sequence = 0L; // 序列号
    private long lastTimestamp = -1L; // 上一次生成ID的时间戳
 
    private AtomicLong id = new AtomicLong(0);
 
    // 构造函数,传入工作机器ID和数据中心ID
    public SnowflakeIdGenerator(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException("workerId can't be greater than %d or less than 0");
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException("datacenterId can't be greater than %d or less than 0");
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }
 
    // 生成下一个ID
    public synchronized long nextId() {
        long timestamp = timeGen();
 
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
 
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0;
        }
 
        lastTimestamp = timestamp;
 
        id.set((timestamp - twepoch) << timestampShift | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence);
        return id.get();
    }
 
    // 获取当前时间戳
    protected long timeGen() {
        return System.currentTimeMillis();
    }
 
    // 等待下一个毫秒的到来,用于解决时钟回拨问题
    protected long tilNextMil
2024-08-14

在Linux中配置SSH连接的加密算法,你需要编辑SSH服务器的配置文件sshd_config,通常位于/etc/ssh/sshd_config

以下是配置SSH使用特定加密算法的步骤:

  1. 打开sshd_config文件:

    
    
    
    sudo nano /etc/ssh/sshd_config
  2. 找到或添加以下配置行,并设置所需的加密算法。例如,仅使用Curve25519加密:

    
    
    
    KexAlgorithms curve25519@libssh.org
    Ciphers aes256-ctr
    MACs hmac-sha2-256
  3. 保存并关闭文件。
  4. 重启SSH服务以应用更改:

    
    
    
    sudo systemctl restart sshd

请注意,更改加密算法可能会影响客户端和服务器之间的兼容性。确保你的客户端也支持你所配置的算法。

这里是一个配置示例,仅使用Curve25519加密算法:




# 编辑sshd_config
sudo nano /etc/ssh/sshd_config
 
# 添加或修改以下行
KexAlgorithms curve25519@libssh.org
Ciphers aes256-ctr
MACs hmac-sha2-256
 
# 保存退出并重启SSH服务
sudo systemctl restart sshd

确保在进行任何更改之前备份sshd_config文件,并在对生产环境进行更改之前在测试环境中验证配置。

2024-08-14

Go语言的sort包提供了各种用于切片排序的函数。以下是一些使用sort包进行排序的示例代码:




package main
 
import (
    "fmt"
    "sort"
)
 
func main() {
    // 对整数切片进行排序
    ints := []int{7, 2, 4, 1, 5, 9}
    sort.Ints(ints)
    fmt.Println(ints) // 输出:[1 2 4 5 7 9]
 
    // 对字符串切片进行排序
    strings := []string{"banana", "apple", "cherry"}
    sort.Strings(strings)
    fmt.Println(strings) // 输出:[apple banana cherry]
 
    // 对自定义类型切片进行排序
    type Person struct {
        Name string
        Age  int
    }
    people := []Person{
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35},
    }
    // 按年龄排序
    sort.Slice(people, func(i, j int) bool {
        return people[i].Age < people[j].Age
    })
    fmt.Println(people) // 输出:[{Bob 25} {Alice 30} {Charlie 35}]
}

在这个例子中,我们展示了如何使用sort包中的IntsStringsSlice函数来对整数、字符串和自定义类型的切片进行排序。对于自定义类型的排序,我们提供了一个排序函数作为Slice函数的参数。这个函数定义了切片元素的排序逻辑。

2024-08-14



function dijkstra(graph, start, finish) {
    const distances = {};
    const previous = {};
    const visited = new Set();
    const nodes = Object.keys(graph);
 
    // 初始化距离和前驱节点
    for (let node of nodes) {
        distances[node] = Infinity;
        previous[node] = null;
    }
    distances[start] = 0;
 
    // 循环直到找到最短路径
    while (nodes.length) {
        let currentNode = findClosestNode(nodes, distances, visited);
        if (currentNode === finish) break; // 找到最短路径
        visited.add(currentNode);
 
        // 更新当前节点的邻居节点的距离
        for (let neighbor in graph[currentNode]) {
            if (visited.has(neighbor)) continue;
            let newDistance = distances[currentNode] + graph[currentNode][neighbor];
            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance;
                previous[neighbor] = currentNode;
            }
        }
    }
 
    // 构建最短路径
    const buildPath = (prev, node) => {
        if (prev[node] && prev[node] !== start) {
            return buildPath(prev, prev[node]) + '->' + node;
        } else {
            return node;
        }
    };
 
    return {
        distances: distances,
        path: buildPath(previous, finish)
    };
}
 
// 测试用例
const graph = {
    'start': {'a': 6, 'b': 2},
    'a': {'finish': 1},
    'b': {'a': 3, 'finish': 5},
    'finish': {}
};
 
const shortestPath = dijkstra(graph, 'start', 'finish');
console.log(shortestPath.distances);
console.log('Shortest Path:', shortestPath.path);

这段代码实现了Dijkstra算法,用于找到加权图中两个节点之间的最短路径。它首先初始化距离和前驱节点,然后通过循环找到最短路径,并构建最短路径的路径字符串。