算法

快速排序堆排序面试中的算法题

快速排序

快速排序：参考文章

package com.example.demo; import org.junit.jupiter.api.Test; import org.springframework.boot.test.context.SpringBootTest; import java.util.Arrays; @SpringBootTest public class SortTest { /** * 交换位置 * @param arr * @param i * @param j */ public void swap(int[] arr,int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public void sortArr(int[] arr, int left, int right){ if (right<=left){ return; } else { int stopFlag = quickSort(arr, left, right); sortArr(arr,left,stopFlag-1); sortArr(arr,stopFlag+1,right); } } /** * 快速排序的一步 * @param arr * @param left * @param right */ public int quickSort(int[] arr, int left, int right){ int flag = arr[left]; int i = left; int j = right+1; while (true){ while (i < right && arr[++i]<flag){ } while (j > 0 && arr[--j]>flag){ } if (i >= j){ break; }else { swap(arr,i,j); } } //当暂停时，交换flag和暂停的那个元素，注意此步，必须和大的元素arr[j]交换！ swap(arr,left,j); //输出暂停在哪个位置 return j; } @Test public void test() { int[] arr = {8,2,3,1,7,2,3,4,9,11}; sortArr(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } }

堆排序

堆排序：参考文章

package com.example.demo; import org.junit.jupiter.api.Test; import java.util.Arrays; public class HeapSort { /** * 交换位置 * @param arr * @param i * @param j */ public void swap(int[] arr,int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } //构造最大根，通过上升构造树 public void getMaxHeap(int[] arr){ for (int i = 0; i < arr.length; i++) { int currentIndex = i; int fatherIndex = (currentIndex-1)/2; //让当前插入的节点与父节点比较，如果比父节点大，则交换 //结束：直到比父节点小为止 while (arr[currentIndex]>arr[fatherIndex]){ swap(arr,currentIndex,fatherIndex); //让当前节点成为父节点 currentIndex = fatherIndex; //与新的父节点进行判断 fatherIndex = (currentIndex-1)/2; } } } //自顶端下降 public void reGetMaxHeap(int[] arr, int size){ //让每次从根节点下降 int fatherIndex = 0; //左孩子 int left = 2 * fatherIndex + 1; //右孩子 int right = 2 * fatherIndex + 2; while (right<=size){ int largestIndex; //取出左右孩子节点中的最大节点 if (arr[left]<arr[right]){ largestIndex = right; } else { largestIndex = left; } //与父节点比较大小 //如果父节点更大，则不变 if (arr[largestIndex]<=arr[fatherIndex]){ break; } //如果子节点更大，则交换 if (arr[largestIndex]>arr[fatherIndex]){ //让子节点成为父节点 swap(arr,largestIndex,fatherIndex); //并交换索引，让原先的父节点下降 fatherIndex = largestIndex; //重新计算左右孩子 left = 2 * fatherIndex + 1; right = 2 * fatherIndex + 2; } } } @Test void test() { int[] arr = {8,2,3,1,7,2,3,4,9,11}; getMaxHeap(arr); int size = arr.length-1; //将当前最大值放到最后 swap(arr,0,size); while (size>1){ size--; reGetMaxHeap(arr,size); //将重新排序后的大根堆的根节点放在最后 swap(arr,0,size); } System.out.println(Arrays.toString(arr)); } }

面试中的算法题

a为随机数，b为1-9的指定数。 需求：当a为99888772211110，b为1时，由于a中存在4个1，则输出1111

@Test public void test2() { long a = 99888772211110L; int b = 1; int flag = 0; String str = String.valueOf(a); char[] array = str.toCharArray(); char bCh = (char) (b+'0'); System.out.println(bCh); for (char c : array) { if (c==bCh){ flag++; } } System.out.println(flag); int result = 0; for (int i = 0; i < flag; i++) { result+=1*Math.pow(10,i); } System.out.println(result); }