G面经prepare: Sort String Based On Another
On string Sort based 面经 another prepare
2023-09-11 14:14:07 时间
Given a sorting order string, sort the input string based on the given sorting order string. Ex sorting order string -> dfbcae Input string -> abcdeeabc output -> dbbccaaee
法一:Comparable
sample Input:
String order = "dfbcae";
String str = "akbcdeeabc";
Sample Output: dbbccaaeekk
要注意13行,indexOf()没有matched到是return -1, 要把它设为最大
1 package SortStringBasedOnAnother; 2 import java.util.*; 3 4 public class Solution { 5 public class Sortable implements Comparable<Sortable> { 6 7 private Character content; 8 private int order; 9 10 public Sortable(char str, String sortingOrder) { 11 this.content = str; 12 this.order = sortingOrder.indexOf(str); 13 if (this.order == -1) this.order = Integer.MAX_VALUE; 14 } 15 16 public int compareTo(Sortable another) { 17 if (this.order > another.order) { 18 return 1; 19 } else if (this.order == another.order) { 20 return 0; 21 } else { 22 return -1; 23 } 24 } 25 26 public String toString() { 27 return String.valueOf(content); 28 } 29 30 } 31 32 public void sort(String order, String str) { 33 Sortable[] array = new Sortable[str.length()]; 34 for (int i = 0; i < str.length(); i++) { 35 array[i] = new Sortable(str.charAt(i), order); 36 } 37 Collections.sort(Arrays.asList(array)); //Arrays.sort(array); 38 for (int i = 0; i < array.length; i++) { 39 System.out.print(array[i]); 40 } 41 42 } 43 44 public static void main(String[] args) { 45 Solution sol = new Solution(); 46 String order = "dfbcae"; 47 String str = "abcdkkeeabc"; 48 sol.sort(order, str); 49 } 50 }
方法二:(Better)counting sort
If taking extra mem in allowed. Take an int array with size same as "sorting order string" that will maintain a count. now iterate the input string & keep on incrementing the corresponding char count in this new array.
记得要用一个queue记录没有在order里面的str的元素
1 package SortStringBasedOnAnother; 2 import java.util.*; 3 4 public class Solution2 { 5 public void sort(String order, String str) { 6 int[] count = new int[order.length()]; 7 Queue<Character> notInOrder = new LinkedList<Character>(); 8 StringBuffer sb = new StringBuffer(); 9 for (int i=0; i<str.length(); i++) { 10 boolean matched = false; 11 char cur = str.charAt(i); 12 for (int j=0; j<order.length(); j++) { 13 if (cur == order.charAt(j)) { 14 count[j]++; 15 matched = true; 16 break; 17 } 18 } 19 if (!matched) notInOrder.offer(cur); 20 } 21 for (int i=0; i<count.length; i++) { 22 while (count[i] > 0) { 23 sb.append(order.charAt(i)); 24 count[i]--; 25 } 26 } 27 while (!notInOrder.isEmpty()) { 28 sb.append(notInOrder.poll()); 29 } 30 System.out.println(sb.toString()); 31 } 32 33 34 /** 35 * @param args 36 */ 37 public static void main(String[] args) { 38 // TODO Auto-generated method stub 39 Solution2 sol = new Solution2(); 40 String order = "dfbcae"; 41 String str = "akbcdeeabc"; 42 sol.sort(order, str); 43 44 } 45 46 }
12-19行可以用IndexOf替代
1 char cur = str.charAt(i); 2 int index = order.indexOf(cur); 3 if (index == -1) notInOrder.offer(cur); 4 else count[index]++;
相关文章
- Spark On YARN内存分配
- 1,字符是否为空,2,比较两个字符大小。String.Compare(String, String)。string.IsNullOrEmpty(string)
- [SAA + SAP] 06. Containers on AWS: ECS, Fargate, ECR & EKS
- 【RF库测试】Encode String To Bytes&Decode Bytes To String& should be string&should be unicode string &should not be string
- String copy on write 引发的线程不安全
- [AWS] Kubernetes on AWS
- check user valid on JQuery
- Spark on k8s提交测试任务失败报错解决办法:User “system:serviceaccount:default:default“ cannot get resource “pods
- spark on yarn相关脚本整理20210524
- 【2017 ACM-ICPC 亚洲区(乌鲁木齐赛区)网络赛 G】Query on a string
- 成功解决pandascoreframe.py:2754: SettingWithCopyWarning: A value is trying to be set on a copy of a s
- TypeScript里string和String,真不是仅仅是大小写的区别
- pandas 报错:【sys:1: DtypeWarning: Columns (15) have mixed types. Specify dtype option on import or set low_memory=False.】
- kali linux on android 更新源
- Windows 11 on ARM Insider Preview 下载
- 【云原生】zookeeper + kafka on k8s 环境部署
- 【ML on Kubernetes】第 1 章:机器学习的挑战
- LInux fork的写时复制(copy on write)