devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

面试常见算法题（一）_无序数组倒数第k个

作者：菜鸟追梦旅行 | 2024-05-31 18:04:53

赞

踩

无序数组倒数第k个

1.两个链表相加

2.判断树是否为镜像二叉树

3.从一个无序数组中找出倒数第k大的数

4.合并两个无序数组为一个有序数组

5.在一个数组中，找到最长子序列

6.爬楼梯问题，打印所有结果

 

1.两个链表相加

3->1->5->null    5->9->2->null       返回8->0->8->null  513+295=808

  1.     public ListNode addList(ListNode l1,ListNode l2){
  2.         ListNode dummy = new ListNode(-1);
  3.         ListNode p1=l1;
  4.         ListNode p2=l2;
  5.         ListNode p =dummy;
  6.         int flag = 0;
  7.         while(p1!=null||p2!=null){
  8.             int temp = flag;
  9.             if(p1!=null){
  10.                 temp+=p1.val;
  11.                 p1=p1.next;
  12.             }
  13.             if(p2!=null){
  14.                 temp+=p2.val;
  15.                 p2=p2.next;
  16.             }
  17.             if(temp>9){
  18.                 temp-=10;
  19.                 flag=1;
  20.             }else{
  21.                 flag=0;
  22.             }
  23.             p.next=new ListNode(temp);
  24.             p=p.next;
  25.         }
  26.         if(flag==1)
  27.             p.next=new ListNode(1);
  28.         return dummy.next;
  29.         
  30.     }

6->1->7 2->9->5  返回9-1-2 617+295=912

  1. public ListNode addList(ListNode l1,ListNode l2){
  2.         ListNode l11 = reverse(l1);
  3.         ListNode l22 = reverse(l2);
  4.         ListNode dummy = new ListNode(-1);
  5.         ListNode p1=l11;
  6.         ListNode p2=l22;
  7.         ListNode p=dummy;
  8.         int flag = 0;
  9.         while(p1!=null||p2!=null){
  10.             int temp=flag;
  11.             if(p1!=null){
  12.                 temp+=p1.val;
  13.                 p1=p1.next;
  14.             }
  15.             if(p2!=null){
  16.                 temp+=p2.val;
  17.                 p2=p2.next;
  18.             }
  19.             if(temp>9){
  20.                 temp-=10;
  21.                 flag=1;
  22.             }else{
  23.                 flag=0;
  24.             }
  25.             p.next=new ListNode(temp);
  26.             p=p.next;
  27.         }
  28.         if(flag==1)
  29.             p.next=new ListNode(1);
  30.         return reverse(dummy.next);
  31.     }
  32.     public ListNode reverse(ListNode haed){
  33.         ListNode cur=head,pre=null;
  34.         while(cur!=null){
  35.             ListNode temp=cur.next;
  36.             cur.next=pre;
  37.             pre=cur;
  38.             cur=temp;
  39.         }
  40.         return pre;
  41.     }

2.判断树是否为镜像二叉树

  1.     public boolean isSymmetric(TreeNode root) {
  2.         return root==null?true:recur(root.left,root.right);
  3.     }
  4.     boolean recur(TreeNode L,TreeNode R){
  5.         if(L==null&&R==null) return true;
  6.         if(L==null||R==null||L.val!=R.val) return false;
  7.         return recur(L.left,R.right)&&recur(L.right,R.left);
  8.     }
  1. public boolean isSymmetric(TreeNode root) {
  2.         //使用队列
  3.         if(root==null) return true;
  4.         Queue<TreeNode> q= new LinkedList<>(){{add(root.left);add(root.right);}};
  5.         while(!q.isEmpty()){
  6.             TreeNode l = q.poll();
  7.             TreeNode r = q.poll();
  8.             if(l==null&&r==null) continue;
  9.             if(l==null||r==null||l.val!=r.val) return false;
  10.             q.offer(l.left);
  11.             q.offer(r.right);
  12.             q.offer(l.right);
  13.             q.offer(r.left);
  14.         }
  15.         return true;
  16.     }

3.从一个无序数组中找出倒数第k大的数

3.1最小的k个数

（1）快排

  1. public int[] getLeastNumbers(int[] arr, int k) {
  2.         if (k >= arr.length) return arr;
  3.         quick_sort(arr,0,arr.length-1,k);
  4.         return  Arrays.copyOf(arr, k);
  5.     }
  6.    public static void quick_sort(int[] q,int l,int r,int k){
  7.         //base case 
  8.         if(l>=r){return;}
  9.         int mid=q[l],i=l-1,j=r+1;
  10.         while(i<j){
  11.             do i++;while(q[i]<mid);
  12.             do j--;while(q[j]>mid);
  13.             if(i<j){swap(q,i,j);}
  14.         }
  15.         if(k-1>j){
  16.             quick_sort(q,j+1,r,k);
  17.             quick_sort(q,l,j,k);
  18.         }else{
  19.             quick_sort(q,l,j,k);
  20.         }
  21.     }
  22.     public static void swap(int[] q,int i,int j){
  23.         int temp=q[i];
  24.         q[i]=q[j];
  25.         q[j]=temp;
  26.     }

（2）堆排序

  1. // 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
  2. // 1. 若目前堆的大小小于K，将当前数字放入堆中。
  3. // 2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
  4. //    反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
  5. class Solution {
  6.     public int[] getLeastNumbers(int[] arr, int k) {
  7.         if (k == 0 || arr.length == 0) {
  8.             return new int[0];
  9.         }
  10.         // 默认是小根堆，实现大根堆需要重写一下比较器。
  11.         Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
  12.         for (int num: arr) {
  13.             if (pq.size() < k) {
  14.                 pq.offer(num);
  15.             } else if (num < pq.peek()) {
  16.                 pq.poll();
  17.                 pq.offer(num);
  18.             }
  19.         }
  20.         
  21.         // 返回堆中的元素
  22.         int[] res = new int[pq.size()];
  23.         int idx = 0;
  24.         for(int num: pq) {
  25.             res[idx++] = num;
  26.         }
  27.         return res;
  28.     }
  29. }

手动建堆--大根堆

  1. class Solution {
  2.     public int[] getLeastNumbers(int[] arr, int k) {
  3.         if (k == 0 || arr.length == 0) {
  4.             return new int[0];
  5.         }
  6.         
  7.         int [] res =new int[k];
  8.         System.arraycopy(arr, 0, res, 0, k);
  9.         buildHeap(res);
  10.         for(int i=k;i<arr.length;i++){
  11.             if(arr[i]<res[0])
  12.                 res[0]=arr[i];
  13.                 adjust(res,0);
  14.         }
  15.     
  16.         return res;
  17.     }
  18.  
  19.         public void buildHeap(int[] arr){
  20.         for(int i = arr.length / 2 - 1; i >= 0; i--){
  21.             adjust(arr, i);
  22.         }
  23.     }
  24.     public void adjust(int[] arr, int i){
  25.         int maxIndex = i;
  26.         int len = arr.length;
  27.         if(2*i+1 < len && arr[2*i+1] > arr[maxIndex]) maxIndex = 2*i+1;
  28.         if(2*i+2 < len && arr[2*i+2] > arr[maxIndex]) maxIndex = 2*i+2;
  29.         if(maxIndex != i){
  30.             swap(arr, maxIndex, i);
  31.             adjust(arr, maxIndex);
  32.         }
  33.     }
  34.     public void swap(int[] arr, int i, int j){
  35.         int temp = arr[i];
  36.         arr[i] = arr[j];
  37.         arr[j] = temp;
  38.     }
  39. }

（3）二叉搜索树

  1. class Solution {
  2.     public int[] getLeastNumbers(int[] arr, int k) {
  3.         if (k == 0 || arr.length == 0) {
  4.             return new int[0];
  5.         }
  6.         // TreeMap的key是数字, value是该数字的个数。
  7.         // cnt表示当前map总共存了多少个数字。
  8.         TreeMap<Integer, Integer> map = new TreeMap<>();
  9.         int cnt = 0;
  10.         for (int num: arr) {
  11.             // 1. 遍历数组，若当前map中的数字个数小于k，则map中当前数字对应个数+1
  12.             if (cnt < k) {
  13.                 map.put(num, map.getOrDefault(num, 0) + 1);
  14.                 cnt++;
  15.                 continue;
  16.             } 
  17.             // 2. 否则，取出map中最大的Key（即最大的数字), 判断当前数字与map中最大数字的大小关系：
  18.             //    若当前数字比map中最大的数字还大，就直接忽略；
  19.             //    若当前数字比map中最大的数字小，则将当前数字加入map中，并将map中的最大数字的个数-1。
  20.             Map.Entry<Integer, Integer> entry = map.lastEntry();
  21.             if (entry.getKey() > num) {
  22.                 map.put(num, map.getOrDefault(num, 0) + 1);
  23.                 if (entry.getValue() == 1) {
  24.                     map.pollLastEntry();
  25.                 } else {
  26.                     map.put(entry.getKey(), entry.getValue() - 1);
  27.                 }
  28.             }
  29.             
  30.         }
  31.  
  32.         // 最后返回map中的元素
  33.         int[] res = new int[k];
  34.         int idx = 0;
  35.         for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
  36.             int freq = entry.getValue();
  37.             while (freq-- > 0) {
  38.                 res[idx++] = entry.getKey();
  39.             }
  40.         }
  41.         return res;
  42.     }
  43. }

3.2 数组中第k个最大元素

  1. class Solution {
  2.     public int findKthLargest(int[] nums, int k) {
  3.         if (k > nums.length) return -1;
  4.         quick_sort(nums,0,nums.length-1,nums.length-k+1);
  5.         return  nums[nums.length-k];
  6.     }
  7.  
  8.     public static void quick_sort(int[] q,int l,int r,int k){
  9.         //base case 
  10.         if(l>=r){return;}
  11.         int mid=q[l],i=l-1,j=r+1;
  12.         while(i<j){
  13.             do i++;while(q[i]<mid);
  14.             do j--;while(q[j]>mid);
  15.             if(i<j){swap(q,i,j);}
  16.         }
  17.         if(k-1>j){
  18.             quick_sort(q,j+1,r,k);
  19.             quick_sort(q,l,j,k);
  20.         }else{
  21.             quick_sort(q,l,j,k);
  22.         }
  23.     }
  24.     public static void swap(int[] q,int i,int j){
  25.         int temp=q[i];
  26.         q[i]=q[j];
  27.         q[j]=temp;
  28.     }
  29. }

3.3 堆

建堆----大根堆

  1.     public void buildHeap(int[] arr){
  2.         for(int i = arr.length / 2 - 1; i >= 0; i--){
  3.             adjust(arr, i);
  4.         }
  5.     }
  6.     public void adjust(int[] arr, int i){
  7.         int maxIndex = i;
  8.         int len = arr.length;
  9.         if(2*i+1 < len && arr[2*i+1] > arr[maxIndex]) maxIndex = 2*i+1;
  10.         if(2*i+2 < len && arr[2*i+2] > arr[maxIndex]) maxIndex = 2*i+2;
  11.         if(maxIndex != i){
  12.             swap(arr, maxIndex, i);
  13.             adjust(arr, maxIndex);
  14.         }
  15.     }
  16.     public void swap(int[] arr, int i, int j){
  17.         int temp = arr[i];
  18.         arr[i] = arr[j];
  19.         arr[j] = temp;
  20.     }

小根堆

  1.     public void buildHeap(int[] arr){
  2.         for(int i = arr.length / 2 - 1; i >= 0; i--){
  3.             adjust(arr, i);
  4.         }
  5.     }
  6.     public void adjust(int[] arr, int i){
  7.         int minIndex = i;
  8.         int len = arr.length;
  9.         if(2*i+1 < len && arr[2*i+1] < arr[minIndex]) maxIndex = 2*i+1;
  10.         if(2*i+2 < len && arr[2*i+2] < arr[minIndex]) maxIndex = 2*i+2;
  11.         if(maxIndex != i){
  12.             swap(arr, maxIndex, i);
  13.             adjust(arr, maxIndex);
  14.         }
  15.     }
  16.     public void swap(int[] arr, int i, int j){
  17.         int temp = arr[i];
  18.         arr[i] = arr[j];
  19.         arr[j] = temp;
  20.     }

4.合并两个无序数组为一个有序数组

合并两个数组，然后快排或者堆排序，香不

5.在一个数组中，找到最长子序列

再等等

6.爬楼梯问题，打印所有结果

  1. class Solution {
  2.     public static List<List<Integer>> res = new LinkedList<>();
  3.     public int numWays(int n) {
  4.         if(n==0) return 1;
  5.         LinkedList<Integer> track = new LinkedList<Integer>();
  6.         int[] nums = new int[]{1, 2};
  7.         backtrack(nums, n, track);
  8.         System.out.println(res);
  9.         return res.size();
  10.     }
  11.  
  12.     private static void backtrack(int[] nums, int n, LinkedList<Integer> track) {
  13.         if(n<0)
  14.             return;
  15.         if(n==0) {
  16.             res.add(new LinkedList(track));
  17.             System.out.println(track);
  18.             return;
  19.         }
  20.  
  21.         for(int i=0; i<nums.length; i++) {
  22.  
  23.             track.add(nums[i]);
  24.  
  25.             backtrack(nums, n-nums[i], track);
  26.  
  27.             track.removeLast();
  28.         }
  29.     }
  30. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/653670
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号