剑指 Offer II 063. 替换单词
难度中等在英语中，有一个叫做 词根(root) 的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
现在，给定一个由许多词根组成的词典和一个句子，需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
需要输出替换之后的句子。
1 class Solution {
2 public String replaceWords(List<String> dictionary, String sentence) {
3 Set<String> prefix=new HashSet<>();
4 for (String s:dictionary){
5 prefix.add(s);
6 }
7 String[] arr=sentence.split(" ");
8 StringBuilder sb=new StringBuilder();
9 for (int i=0;i<arr.length;i++){
10 boolean f=false;
11 for (int j=0;j<arr[i].length();j++){
12 if (prefix.contains(arr[i].substring(0,j+1))){
13 sb.append(arr[i].substring(0,j+1));
14 f=true;
15 break;
16 }
17 }
18 if (!f) sb.append(arr[i]);
19 if (i!=arr.length-1) sb.append(" ");
20 }
21 return sb.toString();
22 }
23 }
思路：字典树也可以。前缀特殊标记方便判断是否有前缀。
658. 找到 K 个最接近的元素
难度中等给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x|或者|a - x| == |b - x|且a < b
1 class Solution {
2 public List<Integer> findClosestElements(int[] arr, int k, int x) {
3 PriorityQueue<Integer> q=new PriorityQueue<>(
4 (a,b)->{
5 if (Math.abs(a-x)==Math.abs(b-x)){
6 return a-b;
7 }else{
8 return Math.abs(a-x)-Math.abs(b-x);
9 }
10 }
11 );
12 for (int num:arr){
13 q.offer(num);
14 }
15 int[] nums=new int[k];
16 for (int i=0;i<k;i++){
17 nums[i]=q.poll();
18 }
19 Arrays.sort(nums);
20 List<Integer> list=new ArrayList<>();
21 for (int y:nums) list.add(y);
22 return list;
23 }
24 }
思路：可以array直接排序，或者二分查找。
标签：25,arr,String,offer,int,abs,2022,new,词根 From： https://www.cnblogs.com/benbicao/p/16624101.html