首页 > 其他分享 >2023-05-15：对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次， 能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k。 给你两个字母异位词 s1

2023-05-15：对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次， 能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k。 给你两个字母异位词 s1

时间：2023-05-15 22:45:40浏览次数：42  
标签：cur int s2 s1 cost heap 字符串

2023-05-15：对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，

能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k。

给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。

输入：s1 = "abc", s2 = "bca"。

输出：2。

答案2023-05-15：

解题思路：

  • 定义一个小根堆，按照节点的估值函数进行排序。

  • 初始化节点为 s1，将其加入小根堆。同时记录访问过的节点，以避免重复搜索。

  • 从小根堆中弹出代价最小的节点 cur。

  • 如果 cur 与 s2 相等，则返回当前代价 cost。

  • 否则，找到 cur 与 s2 第一个不同的位置 firstDiff，再枚举 firstDiff 之后的位置 i。

  • 如果 cur[i] 与 s2[firstDiff] 相等但不在第 i 个位置，则构造一个新的字符串 newStr，交换 newStr[firstDiff] 和 newStr[i] 的位置。

  • 将 newStr 加入小根堆，代价是 cost+1，where 是 firstDiff+1。

  • 在加入前判断是否已经访问过，如果访问过就跳过该节点。

  • 将 newStr 和 cur 恢复为原始状态（恢复数组）。

  • 重复上述步骤，直到小根堆为空或者找到相同的字符串。

需要注意的点：

  • 估值函数的实现是可以调整的，可以根据实际情况来实现更加合适的估值函数。

  • 在 Go 中没有提供 C 语言中的 strdup 函数。可以使用 string 转换为字节数组 []byte，然后再转换为字符串。

  • 在 Go 中 map 是无序的，如果想要按照访问顺序遍历可以在 Node 中增加一个 visited 字段，每次入队时设置 visited = true，在出队时判断 visited 是否为 true，如果为 true 则跳过。

时间复杂度为O(n^2)，其中n是字符串的长度。

空间复杂度为O(n^2)，存储小根堆和visited哈希表所需的空间。

go完整代码如下：

package main

import "fmt"

type Node struct {
	cost   int
	guess  int
	where_ int
	str_   string
}

func kSimilarity(s1 string, s2 string) int {
	len := len(s1)
	heap := &NodeHeap{}
	visited := make(map[string]struct{})
	heap.Push(&Node{0, 0, 0, s1})
	for heap.Len() > 0 {
		cur := heap.Pop().(*Node)
		if _, ok := visited[cur.str_]; ok {
			continue
		}
		if cur.str_ == s2 {
			return cur.cost
		}
		visited[cur.str_] = struct{}{}
		firstDiff := cur.where_
		for firstDiff < len && cur.str_[firstDiff] == s2[firstDiff] {
			firstDiff++
		}
		curStr := []byte(cur.str_)
		for i := firstDiff + 1; i < len; i++ {
			if curStr[i] == s2[firstDiff] && curStr[i] != s2[i] {
				swap(curStr, firstDiff, i)
				add(string(curStr), s2, cur.cost+1, firstDiff+1, heap, visited)
				swap(curStr, firstDiff, i)
			}
		}
	}
	return -1
}

type NodeHeap []*Node

func (h NodeHeap) Len() int { return len(h) }

func (h NodeHeap) Less(i, j int) bool {
	return h[i].cost+h[i].guess < h[j].cost+h[j].guess
}

func (h NodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *NodeHeap) Push(x interface{}) {
	*h = append(*h, x.(*Node))
}

func (h *NodeHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func add(add string, s2 string, cost int, index int, heap *NodeHeap, visited map[string]struct{}) {
	if _, ok := visited[add]; !ok {
		heap.Push(&Node{cost, evaluate(add, s2, index), index, add})
	}
}

func swap(s []byte, i int, j int) {
	tmp := s[i]
	s[i] = s[j]
	s[j] = tmp
}

func evaluate(s1 string, s2 string, index int) int {
	diff := 0
	for i := index; i < len(s1); i++ {
		if s1[i] != s2[i] {
			diff++
		}
	}
	return (diff + 1) / 2
}

func main() {
	s1 := "abc"
	s2 := "bca"
	fmt.Println(kSimilarity(s1, s2))
	s1 = "ab"
	s2 = "ba"
	fmt.Println(kSimilarity(s1, s2))
}

在这里插入图片描述

rust完整代码如下：

#[derive(Eq, PartialEq)]
struct Node {
    cost: i32,
    guess: i32,
    where_: usize,
    str_: String,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        (self.cost + self.guess).cmp(&(other.cost + other.guess))
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn k_similarity(s1: String, s2: String) -> i32 {
    let len = s1.len();
    let mut heap = std::collections::BinaryHeap::new();
    let mut visited = std::collections::HashSet::<String>::new();
    heap.push(Node {
        cost: 0,
        guess: 0,
        where_: 0,
        str_: s1,
    });
    while let Some(cur) = heap.pop() {
        if visited.contains(&cur.str_) {
            continue;
        }
        if cur.str_ == s2 {
            return cur.cost;
        }
        visited.insert(cur.str_.clone());
        let mut first_diff = cur.where_;
        while cur.str_.chars().nth(first_diff).unwrap() == s2.chars().nth(first_diff).unwrap() {
            first_diff += 1;
        }
        let cur_str = cur.str_.as_bytes();
        for i in first_diff + 1..len {
            if cur_str.get(i).unwrap() == &s2.as_bytes()[first_diff]
                && cur_str.get(i).unwrap() != &s2.as_bytes()[i]
            {
                let mut new_str = String::from_utf8_lossy(cur_str).to_string();
                swap(&mut new_str, first_diff, i);
                add(
                    new_str,
                    s2.clone(),
                    cur.cost + 1,
                    first_diff + 1,
                    &mut heap,
                    &visited,
                );
            }
        }
    }
    -1
}

fn swap(s: &mut String, i: usize, j: usize) {
    unsafe {
        let s_mut = s.as_mut_vec();
        let tmp = std::ptr::read(s_mut.get_unchecked(i));
        std::ptr::copy_nonoverlapping(s_mut.get_unchecked(j), s_mut.get_unchecked_mut(i), 1);
        std::ptr::write(s_mut.get_unchecked_mut(j), tmp);
    }
}

fn add(
    add: String,
    s2: String,
    cost: i32,
    index: usize,
    heap: &mut std::collections::BinaryHeap<Node>,
    visited: &std::collections::HashSet<String>,
) {
    if !visited.contains(&add) {
        heap.push(Node {
            cost,
            guess: evaluate(&add, &s2, index),
            where_: index,
            str_: add,
        });
    }
}

// 估值函数
// 看每周有营养的大厂算法面试题，2022年1月第3周
// 估值函数的估计值要绝对 <= 真实距离
// 但又要确保估计值足够大足够接近真实距离，这样效果最好
fn evaluate(s1: &str, s2: &str, index: usize) -> i32 {
    let mut diff = 0;
    for i in index..s1.len() {
        if s1.chars().nth(i).unwrap() != s2.chars().nth(i).unwrap() {
            diff += 1;
        }
    }
    (diff + 1) as i32 / 2
}

fn main() {
    let s1 = String::from("abc");
    let s2 = String::from("bca");
    println!("{}", k_similarity(s1, s2));
    let s1 = String::from("ab");
    let s2 = String::from("ba");
    println!("{}", k_similarity(s1, s2));
}

在这里插入图片描述

c完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node {
    int cost; // 代价，已经换了几回了！
    int guess;// 猜测还要换几回，能变对！
    int where;// 有必须去比对的下标，左边不再换了！
    char* str; // 当前的字符
} Node;

int CompareNode(const void* a, const void* b) {
    Node* pa = (Node*)a;
    Node* pb = (Node*)b;
    return (pa->cost + pa->guess) - (pb->cost + pb->guess);
}

void swap(char* a, char* b) {
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

int evaluate(char* s1, char* s2, int index, int len) {
    int diff = 0;
    for (int i = index; i < len; i++) {
        if (s1[i] != s2[i]) {
            diff++;
        }
    }
    return (diff + 1) / 2;
}

void add(char* add, char* s2, int cost, int index, Node* heap, int heapSize,
    char** visited, int* visitedSize) {
    for (int i = 0; i < *visitedSize; i++) { // 判断是否已经访问过
        if (strcmp(add, visited[i]) == 0) {
            return;
        }
    }
    Node next;
    next.cost = cost;
    next.guess = evaluate(add, s2, index, strlen(add));
    next.where = index;
    next.str = _strdup(add);
    heap[heapSize] = next;
    qsort(heap, heapSize + 1, sizeof(Node), CompareNode); // 排序小根堆
    visited[*visitedSize] = _strdup(add);
    (*visitedSize)++;
}

int kSimilarity(char* s1, char* s2) {
    int len = strlen(s1);
    Node* heap = (Node*)malloc(sizeof(Node) * len * len); // 分配空间
    int heapSize = 0;
    char** visited = (char**)malloc(sizeof(char*) * len * len); // 分配空间
    int visitedSize = 0;
    add(s1, s2, 0, 0, heap, heapSize++, visited, &visitedSize);

    while (heapSize > 0) {
        Node cur = heap[0];
        Node tmp = heap[--heapSize]; // 最后一个节点移到根节点，并下移
        heap[0] = tmp;
        int index = 0;
        while (index * 2 + 1 < heapSize) {
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            int min = left;
            if (right < heapSize && (heap[right].cost + heap[right].guess) < (heap[left].cost + heap[left].guess)) {
                min = right;
            }
            if ((heap[index].cost + heap[index].guess) > (heap[min].cost + heap[min].guess)) {
                tmp = heap[index];
                heap[index] = heap[min];
                heap[min] = tmp;
                index = min;
            }
            else {
                break;
            }
        }
        if (strcmp(cur.str, s2) == 0) {
            int cost = cur.cost;
            free(cur.str);
            for (int i = 0; i < heapSize; i++) {
                free(heap[i].str);
            }
            free(heap); // 释放内存
            for (int i = 0; i < visitedSize; i++) {
                free(visited[i]);
            }
            free(visited);
            return cost;
        }
        int firstDiff = cur.where;
        while (cur.str[firstDiff] == s2[firstDiff]) {
            firstDiff++;
        }
        for (int i = firstDiff + 1; i < len; i++) {
            if (cur.str[i] == s2[firstDiff] && cur.str[i] != s2[i]) {
                char* newStr = _strdup(cur.str); // 复制字符串
                swap(&newStr[firstDiff], &newStr[i]); // 交换字符
                add(newStr, s2, cur.cost + 1, firstDiff + 1, heap, heapSize++, visited, &visitedSize); // 加入新节点
                swap(&newStr[firstDiff], &newStr[i]); // 恢复字符串
            }
        }
        free(cur.str);
    }

    for (int i = 0; i < heapSize; i++) {
        free(heap[i].str);
    }
    free(heap); // 释放内存
    for (int i = 0; i < visitedSize; i++) {
        free(visited[i]);
    }
    free(visited);

    return -1;
}

int main() {
    char s1[] = "abc";
    char s2[] = "bca";
    printf("%d\n", kSimilarity(s1, s2));
    char s3[] = "ab";
    char s4[] = "ba";
    printf("%d\n", kSimilarity(s3, s4));
    return 0;
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>

using namespace std;

struct Node {
    int cost; // 代价，已经换了几回了！
    int guess;// 猜测还要换几回，能变对！
    int where;// 有必须去比对的下标，左边不再换了！
    string str; // 当前的字符

    Node(int r, int g, int i, string s) : cost(r), guess(g), where(i), str(s) {}
};

struct CompareNode {
    bool operator()(const Node& a, const Node& b) {
        return (a.cost + a.guess) > (b.cost + b.guess); // 小根堆
    }
};

void swap(char& a, char& b) {
    char tmp = a;
    a = b;
    b = tmp;
}

int evaluate(string s1, string s2, int index) {
    int diff = 0;
    for (int i = index; i < s1.size(); i++) {
        if (s1[i] != s2[i]) {
            diff++;
        }
    }
    return (diff + 1) / 2;
}

void add(string add, string s2, int cost, int index, priority_queue<Node, vector<Node>, CompareNode>& heap,
    unordered_set<string>& visited) {
    if (!visited.count(add)) {
        heap.push(Node(cost, evaluate(add, s2, index), index, add));
    }
}

int kSimilarity(string s1, string s2) {
    int len = s1.size();
    priority_queue<Node, vector<Node>, CompareNode> heap;
    unordered_set<string> visited;
    heap.push(Node(0, 0, 0, s1));
    while (!heap.empty()) {
        Node cur = heap.top();
        heap.pop();
        if (visited.count(cur.str)) {
            continue;
        }
        if (cur.str == s2) {
            return cur.cost;
        }
        visited.insert(cur.str);
        int firstDiff = cur.where;
        while (cur.str[firstDiff] == s2[firstDiff]) {
            firstDiff++;
        }
        string curStr = cur.str;
        for (int i = firstDiff + 1; i < len; i++) {
            if (curStr[i] == s2[firstDiff] && curStr[i] != s2[i]) {
                swap(curStr[firstDiff], curStr[i]);
                add(curStr, s2, cur.cost + 1, firstDiff + 1, heap, visited);
                swap(curStr[firstDiff], curStr[i]);
            }
        }
    }
    return -1;
}



int main() {
    string s1 = "abc";
    string s2 = "bca";
    cout << kSimilarity(s1, s2) << endl;
    s1 = "ab";
    s2 = "ba";
    cout << kSimilarity(s1, s2) << endl;
}

在这里插入图片描述

标签：cur,int,s2,s1,cost,heap,字符串
From： https://www.cnblogs.com/moonfdd/p/17403368.html

相关文章

  • C基础笔记(字符串)
    字符串strlen计算字符串长度:strlen(s1);返回字符串s1的长度。strcat字符串相连: strcat(s1,s2);  连接字符串s2到字符串s1的末尾。strcmp字符串比较    strcmp(s1,s2);如果s1和s2是相同的，则返回1；如果s1<s2则返回小于0；如......
  • Lua 字符串
    Lua字符串字符串或串(String)是由数字、字母、下划线组成的一串字符。Lua语言中字符串可以使用以下三种方式来表示：单引号间的一串字符。双引号间的一串字符。[[与]]间的一串字符。以上三种方式的字符串实例如下：实例str1="Lua"print("双引号字符串：",str1)str2......
  • 给定一个字符串，用java代码找出其中不含有重复字符的最长子串的长度
    publicintlengthOfLongestSubstring(Strings){intn=s.length(),ans=0;Map<Character,Integer>map=newHashMap<>();for(inti=0,j=0;j<n;j++){if(map.containsKey(s.charAt(j))){i=Math.ma......
  • 字符串
    String直接赋值会复用字符串常量池中的new出来的不会复用,会开辟一个新的空间用for循环遍历数组,通过charc=str.charAt(i)来索引值.再定义一个数组,对应......
  • 剑指 Offer 20. 表示数值的字符串
    题目描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。   classSolution{publicbooleanisNumber(Strings){if(s==null||s.length()==0)returnfalse;//s为空对象或s长度为0(空字符串)时,不能表示数值charstr[]=s.trim()......
  • Windows10升企业版
    VK7JG-NPHTM-C97JM-9MPGT-3V66TW269N-WFGWX-YVC9B-4J6C9-T83GXNYW94-47Q7H-7X9TT-W7TXD-JTYPMNJ4MX-VQQ7Q-FP3DB-VDGHX-7XM87MH37W-N47XK-V7XM9-C7227-GCQG9 win10怎么升级到专业版密钥(win10系统如何升级到专业版)-装机吧(zhuangjiba.com)......
  • 直播软件开发，JS生成随机字符串的方法
    直播软件开发，JS生成随机字符串的方法functionrandomString(randomLen,min,max){  varstr="",    range=min,    arr=['0','1','2','3','4','5','6','7','8�......
  • VB.NET 截取字符串
    在VB.NET中，您可以使用Substring方法或Split方法来截取字符串。Substring方法允许您从字符串中提取一个子字符串，该子字符串从指定的起始索引开始，并继续到字符串的末尾或指定的长度。以下是使用Substring方法截取字符串的示例：DimstrAsString="HelloWorld!"DimsubStr1As......
  • 三菱PlC程序大型项目QCPU+QD77MS16 项目说明如下： 1.宝贝包含一套完
    三菱PlC程序大型项目QCPU+QD77MS16项目说明如下：1.宝贝包含一套完整的电气开发系统资料（包含plc程序，触摸屏程序，伺服模块设置程序，程序开发地址规划表）2.这套开发程序是用一套完美的程序结构进行设计，掌握这套程序结构后就可以开发各种自动化设备控制程序3.提供的这套三菱plc程序开发地......
  • Windows 11、Windows 10使用VS2022安装 .NET 4.0、.NET 4.5等低版本环境
    由于新版windows10、windows11自带.NETFramework4.8，而一些旧的代码，又需要.NET4.0、.NET4.5等低版本的运行环境。最新携带运行环境版本如下：.NETFramework系统要求-.NETFramework|MicrosoftLearn安装低版本运行环境方法：无需安装VS2019，在VisualStudio2022中编......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99