NC刷题笔记14-其他算法
-
- 1 KMP
- 2 替换空格
- 3 最长公共前缀
- 4 回文串
-
- 4.1 最长回文串
- 4.2 验证回文串
- 4.3 最长回文子串
- 4.4 最长回文子序列
- 5 括号匹配
- 6 把字符串转换成整数
- 7 随机算法Knuth
- 8 堆排序
- 9 快速排序
- 10 归并排序
- 11 堆Java实现
1 KMP
思路：字符串A和字符串B匹配的过程中不需要从头开始，如果已经匹配过的字符字串有前后缀相同的部分，就从公共前后缀后面的位置开始匹配
public class KMP { public static int[] getNextArray(char[] t) { int[] next = new int[t.length]; next[0] = -1; next[1] = 0; int k; for (int j = 2; j < t.length; j++) { k=next[j-1]; while (k!=-1) { if (t[j - 1] == t[k]) { next[j] = k + 1; break; }else { k = next[k]; } next[j] = 0; } } return next; } public static int kmpMatch(String s, String t){ char[] s_arr = s.toCharArray(); char[] t_arr = t.toCharArray(); int[] next = getNextArray(t_arr); int i = 0, j = 0; while (i<s_arr.length && j<t_arr.length){ if(j == -1 || s_arr[i]==t_arr[j]){ i++; j++; }else j = next[j]; } if(j == t_arr.length) return i-j; else return -1; } public static void main(String[] args) { System.out.println(kmpMatch("abcabaabaabcacb", "abaabcac")); }}
2 替换空格
public class Main { public String Replacespace0(String str){ if(str==null||str.length()==0) return str; StringBuilder sb=new StringBuilder(); for(int i=0;i<str.length();i++){ if(String.valueOf(str.charAt(i)).equals(" ")){ sb.append("%20"); }else{ sb.append(str.charAt(i)); } } return sb.toString(); } public String Replacespace1(String str){ return str.replaceAll(" ","%20"); }}
3 最长公共前缀
思路：1 先判空2 排序3 比较最短和最长的两个字符串公共前缀
public class Main1 { public static String LongestPrifix(String[] strings){ if(strings==null||strings.length==0||judgeEmpty(strings)) return ""; Arrays.sort(strings); int n=Math.min(strings[0].length(),strings[strings.length-1].length()); StringBuilder sb=new StringBuilder(); for(int i=0;i<n;i++){ if(strings[0]==strings[strings.length-1]) sb.append(strings[0].charAt(i)); else break; } return sb.toString(); } public static boolean judgeEmpty(String[] strings){ for(String s:strings){ if(s==null||s.equals("")||s.length()==0) return false; } return true; }}
4 回文串
4.1 最长回文串
题目给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写输入: "abccccdd"输出: 7解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7
思路：1 偶数个字符结果+22 存在奇数个字符结果+13 返回结果
public static int HuiWenString(String str){ if(str==null||str.equals("")) return 0; HashSet<Character> set=new HashSet<>(); int result=0; for(int i=0;i<str.length();i++){ char c=str.charAt(i); if(set.contains(c)){ set.remove(c); result+=2; }else{ set.add(c); } } return set.size()==0?result:result+1; }
4.2 验证回文串
LeetCode: 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。输入: "A man, a plan, a canal: Panama"输出: true
public class Main3 { public static boolean HuiWenString(String str){ str=str.toLowerCase(); int i=0,j=str.length()-1; while(i<j){ while(!Character.isLetterOrDigit(str.charAt(i))) i++; while(!Character.isLetterOrDigit(str.charAt(j))) j--; if(str.charAt(i)!=str.charAt(j)) return false; i++; j--; } return true; } public static void main(String[] args) { System.out.println(HuiWenString("A man, a plan, a canal: Panama")); }}
4.3 最长回文子串
思路：中心扩散法，奇数和偶数
public class LongestHuiWenString { private int index, len; public String longestPalindrome(String s) { if (s.length() < 2) return s; for (int i = 0; i < s.length() - 1; i++) { PalindromeHelper(s, i, i); PalindromeHelper(s, i, i + 1); } return s.substring(index, index + len); } public void PalindromeHelper(String s, int l, int r) { while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; } if (len < r - l - 1) { index = l + 1; len = r - l - 1; } } }
4.4 最长回文子序列
思路：动态规划dp[i][i]=dp[i+1][j-1]+2;dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
class Solution { public int longestPalindromeSubseq(String s) { int len = s.length(); int [][] dp = new int[len][len]; for(int i = len - 1; i>=0; i--){ dp[i][i] = 1; for(int j = i+1; j < len; j++){ if(s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2; else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); } } return dp[0][len-1]; }}
5 括号匹配
爱奇艺 2018 秋招 Java：一个合法的括号匹配序列有以下定义: 1 空串""是一个合法的括号匹配序列 2 如果"X"和"Y"都是合法的括号匹配序列,"XY"也是一个合法的括号匹配序列 3 如果"X"是一个合法的括号匹配序列,那么"(X)"也是一个合法的括号匹配序列 4 每个合法的括号序列都可以由以上规则生成。 例如: "","()","()()","((()))"都是合法的括号序列对于一个合法的括号序列我们又有以下定义它的深度: 1 空串""的深度是0 2 如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为max(x,y) 3 如果"X"的深度是x,那么字符串"(X)"的深度是x+1 例如: "()()()"的深度是1,"((()))"的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度
public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); int cnt = 0, max = 0, i; for (i = 0; i < s.length(); ++i) { if (s.charAt(i) == '(') cnt++; else cnt--; max = Math.max(max, cnt); } sc.close(); System.out.println(max); }}
6 把字符串转换成整数
public static int StrToInt(String str) { if (str.length() == 0) return 0; char[] chars = str.toCharArray(); int flag = 0; if (chars[0] == '+') flag = 1; else if (chars[0] == '-') flag = 2; int start = flag > 0 ? 1 : 0; int res = 0; for (int i = start; i < chars.length; i++) { if (Character.isDigit(chars[i])) { int temp = chars[i] - '0'; res = res * 10 + temp; } else { return 0; } } return flag != 2 ? res : -res; }
7 随机算法Knuth
思路：倒序遍历数组，随机获取前面的元素与当前元素进行交换时间复杂度：O(n)空间复杂度：O(1)
public static void RandomArray(int[] array){ Random random = new Random(); for(int i=array.length-1; i>=0; i--){ int index=random.nextInt(array.length)%(i+1); int temp=array[i]; array[i]=array[index]; array[index]=temp; }
8 堆排序
public class HeapSort { public static void main(String[] args) { int[] nums=new int[]{1,8,5,3,7,2,0,1}; HeapSort h=new HeapSort(); h.buildMaxHeap(nums,nums.length); for(int i:nums) System.out.println(i); } public void buildMaxHeap(int[] a, int heapSize) { for (int i = heapSize / 2; i >= 0; --i) { maxHeapify(a, i, heapSize); } for (int j = a.length - 1; j >= 0; j--) { swap(a, 0, j); maxHeapify(a, 0, j); } } public void maxHeapify(int[] a, int i, int heapSize) { int l = i * 2 + 1, r = i * 2 + 2, largest = i; if (l < heapSize && a[l] > a[largest]) largest = l; if (r < heapSize && a[r] > a[largest]) largest = r; if (largest != i) { swap(a, i, largest); maxHeapify(a, largest, heapSize); } } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; }}
9 快速排序
public void quicksort(int[] a,int left,int right){ int l=left,r=right,povit=a[(l+r)/2]; while(l<r){ while(a[l]>povit) l++; while(a[r]<povit) r--; if (l >= r) break; int temp=a[l]; a[l]=a[r]; a[r]=temp; if(a[l]==povit) r--; if(a[r]==povit) l++; } if(l==r){ l++; r--; } if(l<right) quicksort(a,l,right); if(r>left) quicksort(a,left,r); }
10 归并排序
public class Solution { public void sort(int [] array) { mergeSort(array,0,array.length-1); } public void mergeSort(int[] array,int begin,int last){ if(begin>=last) return; int mid=begin+(last-begin)/2; mergeSort(array,begin,mid); mergeSort(array,mid+1,last); merge(array,begin,mid,last); } public void merge(int[] array,int begin,int mid,int last){ int[] tempArray=new int[last-begin+1]; int i=begin,j=mid+1,k=0; while(i<=mid&&j<=last){ if(array[i]<=array[j]){ tempArray[k++]=array[i++]; }else{ tempArray[k++]=array[j++]; res=(res+mid-i+1)%1000000007; } } while(j<=last){ tempArray[k++]=array[j++]; } while(i<=mid){ tempArray[k++]=array[i++]; } for(int k1=0;k1<tempArray.length;k1++){ array[begin+k1]=tempArray[k1]; } }}
11 堆Java实现
package BP;import java.util.Arrays;public class BinaryTree { public static void main(String[] args) { int[] num=new int[]{1,8,7,6,5,4,2,3,9}; BinaryTree heap=new BinaryTree(num); System.out.println(heap.toString()); System.out.println("移除元素"); while(heap.size()!=0){ System.out.println(heap.poll()); } System.out.println(heap.toString()); System.out.println("添加元素"); int index=10; while(index<20){ heap.offer(index++); System.out.println(heap.peek()); } System.out.println(heap.toString()); } int[] headNum; public BinaryTree(int[] nums){ this.headNum = nums; headSort(nums,0,nums.length-1); } public int poll(){ if(headNum.length==0) return -1; int res=headNum[0]; headNum=getRemoveFirstArray(); adjustRemove(0); return res; } public void adjustRemove(int i){ int l=2*i+1,r=2*i+2,largest=i; if(l<headNum.length && headNum[l]>headNum[largest]) largest=l; if(r<headNum.length && headNum[r]>headNum[largest]) largest=r; if(largest!=i){ swap(headNum,i,largest); adjustRemove(largest); } } public int[] getRemoveFirstArray(){ swap(headNum,0,headNum.length-1); int[] num=new int[headNum.length-1]; for(int i=0;i<num.length;i++){ num[i]=headNum[i]; } headNum=num; return headNum; } public void offer(int num){ addSize(num); adjustInsert(headNum.length-1); } public void addSize(int num){ int[] nums=new int[headNum.length+1]; for(int i=0;i<headNum.length;i++){ nums[i]=headNum[i]; } nums[nums.length-1]=num; this.headNum=nums; } public void adjustInsert(int i){ int parent=getParent(i),largest=i; if(parent==-1) return; if(headNum[parent]<headNum[i]){ largest=parent; } if(largest!=i){ swap(headNum,i,largest); adjustInsert(largest); } } public int getParent(int i){ if(i==0) return -1; if(i==1||i==2) return 0; int left=i-1; int right=i-2; return left%2==0?left/2:right/2; } public void headSort(int[] nums,int l,int r){ int length=r-l+1; for(int i=nums.length/2;i>=0;i--){ heapFy(nums,i,length); } for(int j=nums.length-1;j>=0;j--){ swap(nums,0,j); heapFy(nums,0,j); } } public void heapFy(int[] nums,int i,int heapSize){ int l=2*i+1,r=2*i+2,largest=i; if(l<heapSize && nums[l]<nums[largest]) largest=l; if(r<heapSize && nums[r]<nums[largest]) largest=r; if(largest!=i){ swap(nums,i,largest); heapFy(nums,largest,heapSize); } } public void swap(int[] nums,int a,int b){ int temp=nums[a]; nums[a]=nums[b]; nums[b]=temp; } public int size(){ return headNum.length; } public int peek(){ if(headNum.length==0) return -1; return headNum[0]; } @Override public String toString(){ return Arrays.toString(headNum); }}
4万个成语大全
