定义一个单词的“兄弟单词”为:交换该单词字母顺序(注:可以交换任意次),而不添加、删除、修改原有的字母就能生成的单词。
兄弟单词要求和原来的单词不同。例如: ab 和 ba 是兄弟单词。 ab 和 ab 则不是兄弟单词。
现在给定你 n 个单词,另外再给你一个单词 x ,让你寻找 x 的兄弟单词里,按字典序排列后的第 k 个单词是什么?
注意:字典中可能有重复单词。
数据范围:,输入的字符串长度满足 ,
输入只有一行。 先输入字典中单词的个数n,再输入n个单词作为字典单词。 然后输入一个单词x 最后后输入一个整数k
第一行输出查找到x的兄弟单词的个数m 第二行输出查找到的按照字典顺序排序后的第k个兄弟单词,没有符合第k个的话则不用输出。
3 abc bca cab abc 1
2 bca
6 cab ad abcd cba abc bca abc 1
3 bca
abc的兄弟单词有cab cba bca,所以输出3 经字典序排列后,变为bca cab cba,所以第1个字典序兄弟单词为bca
while True: try: ls = list(input().split()) # 将所有输入存储在列表ls中 n = int(ls[0]) # 获取输入单词的个数n ls.pop(0) # 从原列表中删除n k = int(ls.pop()) # 获取列表ls最后的值,即待查找的位置k(即删除最后的元素,存入k) # !!!这里注意k需要转换为整数类型!!! # 上面两步经过pop()方法的操作,得到更新后的列表ls。 # print(ls) x = ls[-1] # 获取更新后的列表ls中的最后一个值x # print(x) # 判断输入的n个单词是否是x的兄弟单词并存入列表lsn中 lsn = [] for i in range(n): if ls[i] != x and sorted(ls[i]) == sorted(x): lsn.append(ls[i]) # 接下来对lsn按字典顺序进行排序 lsn.sort() # print(lsn) # 最后输出结果 length = len(lsn) print(length) if k <= length: print(lsn[k-1]) except:break虽然分类的困难,但其实题目读懂,真的写起来并不难,就是一个一个判断,就是代码有点多。
#这题够坑,后面输出判定,调试了很久。。。。 while True: try: ls=list(raw_input().split()) s=ls[-2] lm=ls[1:-2] ll=[] count=0 for i in lm: if s!=i: m=list(s) m.sort() n=list(i) n.sort() if "".join(m)=="".join(n): count+=1 ll.append(i) ll.sort() if count!=0 and int(ls[-1])<=len(ll) and ll: print(count) print(ll[int(ls[-1])-1]) elif count!=0 and int(ls[-1])>len(ll): print(count) elif count==0: print(count) except: break
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String[] array = in.nextLine().split(" "); List<String> bro = new ArrayList<>(); String pattern = array[array.length - 2]; char[] temp = pattern.toCharArray(); int count = 0; Arrays.sort(temp); String sortedPattern = String.valueOf(temp); for(int i = 1; i < array.length - 2; i++){ //相同的单词 if(array[i].equals(pattern)) continue; //不同的单词 //先排序,再比对 char[] cur = array[i].toCharArray(); Arrays.sort(cur); String sortedCur = String.valueOf(cur); if(sortedCur.equals(sortedPattern)){ bro.add(array[i]); count++; } } Collections.sort(bro); int index = Integer.valueOf(array[array.length - 1]); System.out.println(count); if( index <= count){ System.out.println(bro.get(index - 1)); } } }我笔试能遇到这么无聊的困难题,我就把牛客的题库打出来全吃了。
//朋友们,这道题有2个坑,不怪大家不AC,就是出题人没说清楚(插会腰,可把自己牛逼坏了) //1.输出分为2行,第一行为兄弟个数,第二行输出指定第几个兄弟,要是没有就不输出。 //2.找出的兄弟要以字典序排列 #include<iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int const maxNum = 1000 + 1; bool equSring(string a,string b); //b是不是就是a bool isBrother(string a,string b); //b是不是a的兄弟 bool cmp(string a ,string b){ //字典序排列 return a<b; } int main(){ int n; while(cin>>n){ string inp1[maxNum]; for(int i=0;i<n;i++) cin>>inp1[i]; string lookAns; int posAns; cin>>lookAns>>posAns; vector<string> aa; for(int i=0;i<n;i++){ if(isBrother(lookAns,inp1[i])){ aa.push_back(inp1[i]); } } sort(aa.begin(),aa.end(),cmp); if(posAns<=aa.size()){ cout<<aa.size()<<endl; cout<<aa[posAns-1]<<endl; }else cout<<aa.size()<<endl; } return 0; } bool equSring(string a,string b){ return a.compare(b); } bool isBrother(string a,string b){ //b是不是a的兄弟 if((a.length() ==b.length())&&(equSring(a,b))){ int len = b.length(); char* p = new char[len]; for(int i=0;i<len;i++) p[i]=b[i]; sort(p,p+len); char* pp = new char[len]; for(int i=0;i<len;i++) pp[i]=a[i]; sort(pp,pp+len); for(int i=0;i<len;i++){ if(p[i]!=pp[i]){ delete p; delete pp; return false; } } delete p; delete pp; return true; }else return false; }
def is_brother(str1, str2): if str1 == str2: return False str1 = "".join(sorted(str1)) str2 = "".join(sorted(str2)) if str1 == str2: return True return False while True: try: input_list = input().split() word_list, word, k = input_list[1:-2], input_list[-2], int(input_list[-1]) brother_list = [] for sub in word_list: if is_brother(word, sub): brother_list.append(sub) brother_list = sorted(brother_list) print(len(brother_list)) print(brother_list[k-1]) except: break
const n = arr[0]; const x = arr[arr.length - 2]; const k = arr[arr.length - 1]; const newArr = [...arr] const res = [] newArr.shift() newArr.pop() newArr.pop() newArr.forEach(item=>{ if(item.length === x.length && item.split('').sort().join('') === x.split('').sort().join('') && item !== x){ res.push(item) } }) console.log(res.length) if(k-1<res.length){ console.log(res.sort()[k-1]) }
while True: try: data = input().split() bro_len = int(data[0]) k = int(data[-1]) temp = data[-2] words = data[1:-2] assert len(words) == bro_len, print('the length must be the same') bros = [] for word in words: if sorted(word.lower()) == sorted(temp.lower()) and (not word==temp): bros.append(word) sorted_bros = sorted(bros, ) print(len(bros)) print(sorted_bros[k-1]) except: break
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; class Solution { public: void FindBrotherWord(const vector<string>& strs,const int& strs_size,const string& tar_str,const int& tar_index) { vector<string> brother_word;//存放所有兄弟单词的数组 for(int i = 0; i < strs_size;i++) { //如果字符串个数相等,但是直接比较不等的情况 if( (strs[i].size() == tar_str.size() ) && (strs[i] != tar_str)) { string tar_tmp = tar_str;//暂时存放目标字符串 string init_tmp = strs[i];//存放原字符串的字符 sort(tar_tmp.begin(), tar_tmp.end());//两种分别排序后再判断是否相等 sort(init_tmp.begin(), init_tmp.end()); if(tar_tmp == init_tmp)//如果相等,保存到兄弟单词数组中 { brother_word.push_back(strs[i]); } } } sort(brother_word.begin(),brother_word.end()); //查找索引 if(tar_index > brother_word.size())//比兄弟个数要多 cout << brother_word.size() << endl; else { cout << brother_word.size() << endl; cout << brother_word[tar_index-1] << endl; } } }; int main() { int i = 0; vector<string> strs; int strs_num = 0;//字典序中单词的个数 string tar_str;//目标单词 int tar_index; //要查找的兄弟单词在兄弟单词集的索引位置 string str; while(cin >> str) { if(i == 0) strs_num = stoi(str); else if( i > 0 && i <= strs_num) strs.push_back(str); else if( i == (strs_num + 1)) tar_str = str; else tar_index = stoi(str); i++; } Solution s; s.FindBrotherWord(strs,strs_num,tar_str, tar_index); //测试输入 /* cout << strs_num << endl; for(auto p : strs) { cout << p << endl; } cout << tar_str << endl; cout << strs_index << endl;*/ return 0; }
def test(s: str): num, *lis, x, k = s.split(' ') k = int(k) result = sorted([i for i in lis if x != i and sorted(x) == sorted(i)]) print(len(result)) if len(result) >= k: print(result[k - 1]) if __name__ == '__main__': try: test(input()) except EOFError: pass
// 题目细节容易忽略,其他还好 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); List<String> list = new ArrayList<>(); while (n > 0) { list.add(sc.next()); n--; } String target = sc.next(); int k = sc.nextInt(); List<String> brother = new ArrayList<>(); int count = 0; for (String s : list) { if (!s.equals(target) && isBrotherWord(s, target)) { brother.add(s); } } Collections.sort(brother); System.out.println(brother.size()); if (brother.size() >= k) { System.out.println(brother.get(k - 1)); } } public static boolean isBrotherWord(String s1, String s2) { char[] chs1 = s1.toCharArray(); char[] chs2 = s2.toCharArray(); Arrays.sort(chs1); Arrays.sort(chs2); return String.valueOf(chs1).equals(String.valueOf(chs2)); } }
while True: try: list_a = list(input().split(sep=' ')) word = list_a[-2] num = int(list_a.pop()) new_list = [] for i in list_a: if sorted(i) == sorted(word) and i != word: new_list.append(i) res = sorted(new_list) print(len(res)) print(res[num-1]) except: break
当务之急是对输入的各个字符串,分辨出其中哪些字符串是给定字符串的兄弟单词。由题意可知,当两个字符串长度不等时,或两个字符串内容一摸一样时,它俩必然不是兄弟关系;当两个字符串长度相等,同时各索引位置对应的字符不全相等,但是构成各字符串的字符种类及其频次相等时,这两个字符串互为兄弟。
先从原始输入顺序的字符串序列中筛选出兄弟单词,并存入数组或数组链表等容器中,对容器中的字符串进行排序。如果对于容器存储元素的个数length,目标次序k有效,即k<=length,即可找到目标元素。理论上该方法可行,但对于本题提供的测试用例以及时间要求,运行结果表明该方法超出时间限制。分析一下,不难得知,因为这个处理过程不仅需要重新存储兄弟单词,还要对其进行排序,这两个任务不能同时进行。当输入的字符串数量很大时,当然要花费较多的时间,消耗较大的内存空间。但是,题目要求寻找有序的兄弟单词序列中的第k个兄弟单词,所以对兄弟单词序列进行排序是必需的。如果从原本就有序的字符串序列中依次筛查当前字符串是否为给定单词的兄弟单词,且同时计数,就可以在一次遍历过程结束时获悉目标结果。当计数值与k相等时,当前的字符串就是有序的第k个兄弟单词;如果直到遍历结束,计数值还小于k值,那么说明k值无效,没有找到有序的第k个兄弟单词。代码如下所示。
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int length = in.nextInt(); String[] strArr = new String[length]; for (int i = 0; i < length; i++) { strArr[i] = in.next(); } String pattern = in.next(); int k = in.nextInt(); in.nextLine(); getKthBroStr(pattern, strArr, k); } in.close(); } private static void getKthBroStr(String pattern, String[] strArr, int k) { //查找strArr中pattern的兄弟单词顺序序列中的第k个 Arrays.sort(strArr); //记录兄弟单词的个数 int broCount = 0; //存储第k个兄弟单词 String candidate = null; for (int i = 0; i < strArr.length; i++) { if (isBroStr(pattern, strArr[i])) { //如果数组中当前单词为兄弟单词,则broCount加一 broCount++; //如果broCount值与k相等,即为目标 if (k == broCount) candidate = strArr[i]; } } System.out.println(broCount); if (candidate != null) { //如果找到了第k个兄弟单词,打印其,否则不打印 System.out.println(candidate); } } private static boolean isBroStr(String pattern, String str) { //判断str是否为pattern的兄弟单词 //如果两个字符串的长度不等,则不是兄弟 if (pattern.length() != str.length()) return false; //如果两个字符串内容一摸一样,则不是兄弟,而是影子 if (pattern.equals(str)) return false; char[] patternChars = pattern.toCharArray(); char[] strChars = str.toCharArray(); //对两个字符串对应的字符串组进行自然排序 //如果排序后的两个数组各索引位置上对应的值相等,那这两个字符串互为兄弟,否则不是 Arrays.sort(patternChars); Arrays.sort(strChars); return Arrays.equals(patternChars, strChars); } }
#include<iostream> #include<set> #include<string> #include<vector> #include<unordered_map> std::pair<int, std::string> findBrother(std::vector<std::string>& arr,const std::string& findStr, int &k) { size_t len = findStr.size(); std::multiset<std::string> m; std::unordered_map<char, int> hash; for(auto &ch : findStr) { hash [ch]++; } std::unordered_map<char, int> temp; for(auto & s: arr) { for(auto &ch : s) { temp [ch]++; } bool flag = (temp == hash) ? true : false; if(s != findStr && flag) { m.insert(s); } temp.clear(); } int pos = static_cast<int>(m.size()); std::string str; for(auto &s : m) { if(--k == 0) { str = s; break; } } return std::make_pair(pos, str); } int main() { int n; std::cin >>n; std::string str; std::vector<std::string> array(n); for(auto &s : array) { std::cin >>s; } std::string findStr; std::cin >>findStr; int k =0; std::cin >> k; std::pair<int, std::string> ret = findBrother(array, findStr, k); std::cout << ret.first << std::endl; std::cout << ret.second << std::endl; return 0; }
while True: try: s=input().split() m=int(s[0]) t=list(s[len(s)-2]) k=int(s[len(s)-1]) s.pop(0) s.pop(len(s)-1) s.pop(len(s)-1) bro=[] for x,i in enumerate(s): i=list(i) if i!=t: if sorted(i)==sorted(t): bro.append(s[x]) print(len(bro)) bro.sort() if k<=len(bro): print(bro[k-1]) except: break
import java.util.*; public class HJ27 { private static String target; private static List<String> brothers = new ArrayList<>(); private static boolean flag = false; public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String str = sc.nextLine(); String[] strArr = str.split(" "); int n = Integer.valueOf(strArr[0]); int k = Integer.valueOf(strArr[strArr.length-1]); target = strArr[strArr.length -2]; for (int i =1; i<= n; i++) { String item = strArr[i]; if (item.length() != target.length() || item.equals(target)) { continue; } isBrother(item, 0); if(flag) { brothers.add(item); } flag = false; } System.out.println(brothers.size()); if (brothers.size() >= k) { brothers.sort((s1,s2) -> { return s1.compareTo(s2); }); System.out.println(brothers.get(k-1)); } brothers.clear(); } } private static void isBrother(String item, int m) { if (m == item.length() - 1) { if (item.equals(target)) { flag = true; } } // 对target的字母进行全排列 for (int i=m; i < item.length();i++) { item = swap(item.toCharArray(), i, m); isBrother(item, m + 1); item = swap(item.toCharArray(), i, m); } } private static String swap(char[] arr, int m , int n) { char temp = arr[m]; arr[m] = arr[n]; arr[n] = temp; return String.valueOf(arr); } }
def broword(myword): res=[] def backtrack(word,temp): if not word: res.append(temp) return for i in range(len(word)): temp+=word[i] backtrack(word[:i]+word[i+1:],temp) temp=temp[:-1] backtrack(myword,"") j = res.index(myword) return res[:j]+res[j+1:] while True: try: get=list(input().split()) n=int(get[0]) k=int(get[-1]) myword=get[-2] words=get[1:-2] dic=broword(myword) res=[] for i in words: if i in dic: res.append(i) rlen=len(res) print(rlen) res=sorted(res) if k <= rlen: print(res[k-1]) except: break帮看一下怎么 结果不对