1460. 通过翻转子数组使两个数组相等
难度简单给你两个长度相同的整数数组 target
和 arr
。每一步中,你可以选择 arr
的任意 非空子数组 并将它翻转。你可以执行此过程任意次。
如果你能让 arr
变得与 target
相同,返回 True;否则,返回 False 。
1 class Solution { 2 public boolean canBeEqual(int[] target, int[] arr) { 3 int i=0,j=0; 4 while (j<arr.length){ 5 int index=-1; 6 for (int k=j;k<arr.length;k++){ 7 if (arr[k]==target[i]){ 8 index=k; 9 break; 10 } 11 } 12 if (index==-1) return false; 13 rev(arr,j,index); 14 j++; 15 i++; 16 } 17 return true; 18 } 19 20 public void rev(int[] arr,int l,int r){ 21 while (l<r){ 22 int t=arr[l]; 23 arr[l]=arr[r]; 24 arr[r]=t; 25 l++; 26 r--; 27 } 28 } 29 }
思路:每次找到与目标数组一样的数字,反转到正确的位置。重复直到完全一样。
剑指 Offer II 062. 实现前缀树
难度中等Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类:
Trie()
初始化前缀树对象。void insert(String word)
向前缀树中插入字符串word
。boolean search(String word)
如果字符串word
在前缀树中,返回true
(即,在检索之前已经插入);否则,返回false
。boolean startsWith(String prefix)
如果之前已经插入的字符串word
的前缀之一为prefix
,返回true
;否则,返回false
。
1 class Trie { 2 Node root; 3 /** Initialize your data structure here. */ 4 public Trie() { 5 root=new Node(); 6 } 7 8 /** Inserts a word into the trie. */ 9 public void insert(String word) { 10 Node head=root; 11 for (int i=0;i<word.length();i++){ 12 char c=word.charAt(i); 13 if (head.children[c-'a']==null){ 14 head.children[c-'a']=new Node(); 15 } 16 head=head.children[c-'a']; 17 } 18 head.isWord=true; 19 } 20 21 /** Returns if the word is in the trie. */ 22 public boolean search(String word) { 23 Node head=root; 24 for (int i=0;i<word.length();i++){ 25 char c=word.charAt(i); 26 if (head.children[c-'a']==null){ 27 return false; 28 } 29 head=head.children[c-'a']; 30 } 31 return head.isWord; 32 } 33 34 /** Returns if there is any word in the trie that starts with the given prefix. */ 35 public boolean startsWith(String prefix) { 36 Node head=root; 37 for (int i=0;i<prefix.length();i++){ 38 char c=prefix.charAt(i); 39 if (head.children[c-'a']==null){ 40 return false; 41 } 42 head=head.children[c-'a']; 43 } 44 return true; 45 } 46 } 47 class Node{ 48 boolean isWord; 49 Node[] children; 50 Node(){ 51 isWord=false; 52 children=new Node[26]; 53 } 54 Node(char c){ 55 isWord=false; 56 children=new Node[26]; 57 } 58 } 59 /** 60 * Your Trie object will be instantiated and called as such: 61 * Trie obj = new Trie(); 62 * obj.insert(word); 63 * boolean param_2 = obj.search(word); 64 * boolean param_3 = obj.startsWith(prefix); 65 */
思路:可以不用Node实现,可以直接用trie实现。
标签:24,Node,arr,word,前缀,offer,Trie,2022,String From: https://www.cnblogs.com/benbicao/p/16619480.html