判断两个字符串是否是异构同质
 
在之前刷题看见了一个比较有趣的题目，在这里分享了一下，好好编码，早日上岸。
 
 
 
题目：
 
判断两个字符串是否是异构同质，异构同质的定义如下：一个字符串的字符，重新排列后变成另外一个字符串。
 
要求：
 
输入字符串合法字符集是【a-z，A-Z，0-9】，大小写敏感，不考虑输入异常的情况。
 
例如：
 
输入 ads   asd   输出 TRUE;
 
 
 
看完题目，我想起来的第一个就是自己实现一个字符串的比较过程，这个只是打乱了而已，但是我们这样看一下这个字符串，如果返回时TRUE，证明这两个字符串是异构同质的性质，那么就代表了他们有相同数量的字母而且这些字母个数也是相等的，那整个字符串的ASCII值肯定是一样的，以此我写出了以下的代码。
 
#include <stdio.h>
#include <string.h>
bool judge(const char *str, const char *ptr)
{
	int key=0;
	//if (strlen(str) == strlen(ptr))//  判断是不是一样长，后面还要遍历一次字符串 其实感觉没有什么用
	while (*str != '\0'&&*ptr != '\0')
	{
		key += (*str - *ptr);
		str++;
		ptr++;
	}
	if (*str == '\0'&&*ptr == '\0'&&key == 0)
	{

		return true;
	}
	return false;
}

int main()
{
	char *str = "ab0d";
	char *ptr = "a0bd";
	if (judge(str, ptr))
	{
		printf("TRUE\n");
	}
	else
	{
		printf("FALSE\n");
	}
	return 0;
}
 
时间复杂度是O(N)只遍历一个字符串，空间复杂度O(1)；
 
写完后，看了下大家的评论，发现还有一种方法就是，将两个字符串转化成字符数组，然后用排序的方式，将他们排序，最终比较。
 
方法可行，但是相比我的那种还是复杂一点。

题目：
 
请编码实现一个命令行工具，判定两个指定的字符串是否异构同质；异构同质的定义为：一个字符串的字符重新排列后，能变成另一个字符串。
 
 
 
输入描述:
 
以空格字符分隔的两个字符串；输入字符串的合法字符集为[a-zA-Z0-9 ]，大小写敏感，无需考虑异常输入场景。
 
 
 
输出描述:
 
如果判定两个字符串异构同质，则输出true，否则输出false。
 
 
 
输入例子1:
 
abc acb
 
 
 
输出例子1:
 
true
 
解法1，转为列表，然后排序，再判断是否相等
 
s1, s2 = input().split()
x = list(s1)
x.sort()
x = "".join(x)
y = list(s2)
y.sort()
y = "".join(y)
if x == y:
    print('true')
else:
    print('false')
 
解法2，就是分别将两字符串排序再判断是否相等。或者直接计数每个字符的个数是否相等。 
 
from collections import Counter
s1, s2 = input().split()
c1 = Counter(s1)
c2 = Counter(s2)
if c1 == c2:
    print('true')
else:
    print('false')
 
 
 
 

 function splitstr (str){
     //反过来思考，要随意排序能相等则意味着两者必须长度一样
      let str1 = str.split(" ")[0];
      let str2 = str.split(' ')[1];
      let arr1 = Array.from(str1);
      let arr2 = Array.from(str2);
      let result =true
      if(arr1.length != arr2.length) return false;
      arr1.forEach((item,index) =>{
        let inx = arr2.indexOf(item) //遍历数组，是否能找到相同项，返回的是索引值
        if(inx == -1) result = false;//找不到相同项，一定不满足题意，foreach好像不能终止循环来着
        else{
          arr2[inx] = -1; //输入的字符串为a-zA-Z0-9 ]所以令这一项等于-1，避免重复匹配到相同的项
        }
      })
      if(result) return true
      else return false
  }
 
这个代码在牛客网上提交不成功。。不知道咋回事，自己测了以下没发现问题。。

基于层次结构的动态异构图嵌入
 
摘要：图嵌入已经引起了许多研究兴趣。现有的研究主要集中在静态同质/异构网络或动态同质网络上。然而，动态异构网络在现实中更为普遍，如社会网络、电子商务网络、引文网络等，对动态异构图嵌入的研究还比较缺乏。在本文中，我们提出了一种新的动态异构图嵌入方法，利用层次注意（DyHAN）学习节点嵌入，利用结构异构性和时间演化。我们在三个真实的数据集上评估了我们的方法。结果表明，DyHAN在链路预测任务方面优于各种最新的基线。
 
关键词：图嵌入·异构网络·动态图嵌入
 
1简介
 
图形（网络）嵌入引起了人们极大的研究兴趣。它通过编码网络结构或/和节点属性来学习网络中节点到低维空间的投影。该技术已成功应用于多个领域，如推荐[11,18]、节点分类[8]、链路预测[1]和生物学[7]。
 
在现实世界中，图形往往不仅随着时间的推移而发展，而且还包含多种类型的节点和边。例如，电子商务网络有两种类型的节点，用户和项目，以及多种类型的边缘，点击，购买，添加到首选项和添加到购物车。节点和边可能会随时间变化。在社交网络中，用户可以随着时间的推移与他人建立多种类型的联系（跟帖、回复、转发等）。网络的动态性和结构的异质性为编码节点提供了丰富的信息。
 
最近的研究主要集中在静态图嵌入上，静态图具有固定的节点和边集。DeepWalk[9]和node2vec[6]利用了随机游走/有偏随机游走和skip-gram模型。第[12]行保留一阶和二阶近似。GCN[8]在节点的邻域上使用卷积运算。GraphSAGE[7]或PinSAGE[18]提出了一种归纳方法，用节点特征聚合结构信息。进一步的工作考虑异质性。metapath2vec[2]在生成随机游动时考虑元路径。GATNE[1]根据边缘类型将网络划分为不同的视图，从而聚合节点嵌入。HAN[16]使用两级注意来学习邻居节点和元路径的重要性。
 
动态图嵌入是一个新兴领域[17]。DynamicTriad[19]使用三元闭包来改进节点嵌入。DySAT[10]将原来的GAT[15]扩展到了时态图快照。MetaDynaMix[4]提出了一种基于元路径的动态异构信息网络嵌入技术。更多工作可参考[3,5,13]。
 
尽管如此，仍然缺乏同时考虑时间演化和结构异质性的研究。在[16]和[10]的启发下，我们提出了一种新的动态异构图嵌入方法，该方法利用层次注意层（DyHAN），能够捕捉不同层次聚集的重要性。具体地说，对于任意节点，节点级的注意打算学习其邻居对于特定边缘类型的重要性。边缘级别的注意旨在了解每个边缘类型对该节点的重要性。时间层次的注意能够通过计算每个时间步图快照的重要性来融合最终的嵌入。我们对三个真实世界动态异构网络数据集EComm、Twitter和阿里巴巴网站. 结果表明，在链路预测任务中，DyHAN的性能优于几种最先进的基线。
 
2问题定义
 
在本节中，我们将在本文中提供必要的信息。我们将动态异构网络定义为一系列快照，。时间t的快照被定义为，其中是节点类型为的节点集。是边类型为的边集。O和R分别是节点类型集和边类型集，。我们假设每次快照节点和链接都可以更改。
 
动态异构图嵌入的目的是学习一个映射函数，以保持节点之间的结构相似性和在发展链接关系时的时间趋势。
 
3拟定方法
 
在这一节中，我们将介绍我们提出的方法DyHAN，它结合了文献[10,16]中提出的基本思想，利用动态异构图嵌入的分层关注。它主要由节点级注意、边缘级注意和时间级注意三个部分组成。所有这三个组成部分使用不同的注意层聚合不同的信息层。DyHAN的整体架构如图1所示。
 
 
节点级注意。对于每个时间步快照，我们根据边类型将其划分为不同的子图。采用自关注的方法对每个子图进行节点嵌入。对于边类型r和时间步长t，节点对（i，j）的重要性可以表示为：
 
 
其中是一个激活函数，是节点I的输入表示，是一个线性变换矩阵，||表示连接。表示边类型r和时间步长t的节点i的采样邻居节点。与使用所有直接邻居的[15]不同，为了归纳，我们遵循[7]中描述的框架使用采样邻居。是一个权重向量，它参数化了边缘类型r的注意函数，然后得到了边缘类型r的节点i和时间步长t的嵌入，如下所示：
 
 
请注意，参数在不同的时间步快照之间共享。
 
边缘级注意。我们假设特定于边缘的节点嵌入表示异构图中一种语义类型的信息。为了更有效、更稳健地聚集这些信息，我们采用注意层来自动学习不同边缘类型的重要性。每种边类型的重要性由一层MLP计算。
 
 
其中σ是一个激活函数，是边缘层次的注意向量。和是单层MLP的参数。所有参数在不同的时间步和不同的边类型中共享。节点i的融合嵌入是，
 
 
时间层面的注意。一旦获得每个时间步快照的节点嵌入，下一步就是跨一系列时间快照聚合这些节点嵌入。为了计算最终的节点嵌入，我们使用来处理它的所有历史时间表示，。标度点积注意力[14]是通过假设它能够捕捉时间演化特征来使用的。我们将节点i在时间上的表示形式包装为，然后将转化为查询，键和值，其中，，。时间注意力的定义是，
 
 
其中是一个掩模矩阵，因此只随时间步长≤T衰减。
 
 
我们将使用作为最终的节点嵌入。注意，多头注意可以应用于节点级和时间级注意。
 
优化。为了训练同时捕获结构和时间信息的模型，我们鼓励在最后一个时间步附近的节点具有相似的表示。采用交叉熵损失，
 
 
其中σ是sigmoid函数，<，>表示内积。v是在最后一个时间步中，在固定长度随机行走上，在u附近发生的节点。是一个负采样分布，在最后一个时间步中我们使用节点的度。Q定义负样本数。
 
4实验
 
数据集。我们使用三个真实世界的数据集进行评估。它们的统计数据汇总在表1中。
 
 
EComm数据集取自CIKM 2019 EComm AI竞赛的数据集，来自一个类别。有两种类型的节点，用户和项目。它有四种类型的边缘，包括点击，收集，添加到购物车和购买。
 
twitter2数据集是从Twitter的用户行为日志中抽取的，关于2012年7月1日至7日期间发现的难以捉摸的希格斯玻色子。有三种类型的边缘：转发，回复和提及。请注意，只有一种类型的节点。
 
阿里巴巴数据集是从alibaba.com电子商务平台。对2019年7月11日至7月21日期间的客户电子类网络进行了抽样调查。它由用户和项目之间的交互组成。有三种类型的互动，点击，查询和联系。
 
实验装置。我们学习了基于图快照的节点嵌入，然后在最后一个图快照上进行了链路预测实验
 
链路预测任务的目的是预测任意两个节点之间是否存在链路。我们遵循[10,19]中所述的链路预测评估框架。我们建立了一个动态链路预测的Logistic回归分类器。我们从上一个时间步快照中抽取20%的边作为超参数优化的保留验证集。最后一个时间步快照的其余边用于链路预测任务。具体来说，我们随机选取25%的链接和剩下的75%的链接分别作为训练集和测试集。对于每个训练集和测试集，分别使用相等数量的随机抽样的无连接节点对作为负样本。我们使用节点对的节点嵌入的内积作为链路的表示特征。然后使用ROC曲线下面积（AUC）[9]得分和准确度来报告表现。
 
基线。考虑到代码的可用性和重新实现的工作量，我们将我们提出的DyHAN与以下最先进的静态/动态和同构/异构图嵌入算法进行了比较。DeepWalk[9]，我们使用[7]提供的实现。Metapath2Vec[2]，作者提供的原始实现专用于特定的数据集。因此，直接推广到其它数据集是不方便的。我们用python重新实现了它。GAT[15]，作者提供的原始实现是为节点分类而设计的。我们在GraphSAGE框架中重新实现了它。注意，要被关注的节点是从直接邻居中采样的。GraphSAGE[7]，我们使用作者提供的实现并使用默认设置。测试了四种不同节点聚合技术的变体，即平均值、平均池、最大池和LSTM。DynamicTriads[19]和DySAT[10]，我们使用作者提供的实现。采用忽略结构非均质性的DyGAT方法对非均质性进行了比较。对于基于随机游动的方法，我们将每个节点的游动次数设置为50，每个游动的长度设置为5。所有训练历元设置为1。所有节点嵌入维度都设置为32。
 
结果。实验结果如表2所示。迪汉在竞争对手中取得了最高的AUC得分和准确率。更具体地说，DyHAN在AUC上获得2.8%-4.9%的收益，在比较最佳基线（不包括DyGAT）的准确性上获得0.7%-7.8%的收益。与GAT相比，DyGAT的增益显示了结合时间信息的有效性。此外，DyHAN对DyGAT的增益表明了考虑异质性的有效性。
 
 
5结论
 
本文提出了一种新的层次注意神经网络DyHAN来学习动态异构图中的节点嵌入。DyHAN能够有效地捕捉结构异质性和时间演化。在三个真实数据集上的实验结果表明，DyHAN优于几种最先进的技术。一个有趣的未来方向是探索更多的时间聚合技术。