面试经典150题(101-104)

leetcoindex.php/tags-41973.html" >de 150道题 计划花两个月时候刷完之未完成后转，今天（第1天）完成了4道(101-104)150：

101.(215. 数组中的第K个最大元素) 题目描述：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

第一版（这个题看了好几天。。复习了快排的写法，也算有收获，最后还是看了解题）

class Solution {    Random random=new Random();    public int findKthLargest(int[] nums, int k) {        return quickSort(nums,0,nums.length-1,nums.length-k);    }    public int quickSort(int[] nums, int left,int right,int k){        if(left>=right){            return nums[k];        }        int randomIndex=left+random.nextInt(right-left+1);        swap(nums,left,randomIndex);        int middleNum=nums[left];        int leftTemp=left+1;        int rightTemp=right;        while(leftTemp            while(leftTemp                rightTemp--;            }            while(leftTemp                leftTemp++;            }            if(leftTemp=rightTemp){                break;            }            swap(nums,leftTemp,rightTemp);            leftTemp++;            rightTemp--;        }        swap(nums,left,rightTemp);        if(k==rightTemp){            return nums[rightTemp];        }else if(krightTemp){            return quickSort(nums,rightTemp+1,right,k);        }else{           return quickSort(nums,left,rightTemp-1,k);        }    }    public void swap(int[] nums, int left,int right){        int temp=nums[left];        nums[left]=nums[right];        nums[right]=temp;    }}    public int findKthLargest(int[] nums, int k) {        int len=nums.length;        PriorityQueueo2.compareTo(o1));        for(int num:nums){            priorityQueue.offer(num);        }        for(int i=0;i            priorityQueue.poll();        }        return priorityQueue.peek();    }}    public List        List{            return nums1[o1[0]]+nums2[o1[1]]-nums1[o2[0]]-nums2[o2[1]];        });        int m=nums1.length;        int n=nums2.length;        for(int i=0;i            priority.offer(new int[]{i,0});        }        while(k--0&&!priority.isEmpty()){            int[] temp=priority.poll();            List list=new ArrayList();            list.add(nums1[temp[0]]);            list.add(nums2[temp[1]]);            res.add(list);            if(temp[1]+1                priority.offer(new int[]{temp[0],temp[1]+1});            }        }        return res;    }}    public String addBinary(String a, String b) {        StringBuilder sb=new StringBuilder();        int lenA=a.length();        int lenB=b.length();        int indexA=lenA-1;        int indexB=lenB-1;        boolean flag=false;        while(indexA=0&&indexB>=0){            if(flag){                if(a.charAt(indexA)=='1'&&b.charAt(indexB)=='1'){                    sb.insert(0,'1');                }else if(a.charAt(indexA)=='1'||b.charAt(indexB)=='1'){                    sb.insert(0,'0');                }else{                    sb.insert(0,'1');                    flag=false;                }            }else{                if(a.charAt(indexA)=='1'&&b.charAt(indexB)=='1'){                    sb.insert(0,'0');                    flag=true;                }else if(a.charAt(indexA)=='1'||b.charAt(indexB)=='1'){                    sb.insert(0,'1');                }else{                    sb.insert(0,'0');                }            }            indexA--;            indexB--;        }        while(indexA>=0){            if(flag){                if(a.charAt(indexA)=='1'){                    sb.insert(0,'0');                }else{                    sb.insert(0,'1');                    flag=false;                }            }else{                if(a.charAt(indexA)=='1'){                    sb.insert(0,'1');                }else{                    sb.insert(0,'0');                }            }            indexA--;        }        while(indexB>=0){            if(flag){                if(b.charAt(indexB)=='1'){                    sb.insert(0,'0');                }else{                    sb.insert(0,'1');                    flag=false;                }            }else{                if(b.charAt(indexB)=='1'){                    sb.insert(0,'1');                }else{                    sb.insert(0,'0');                }            }             indexB--;        }        if(flag){            sb.insert(0,'1');        }        return sb.toString();    }}

104.（190. 颠倒二进制位）题目描述：

颠倒给定的 32 位无符号整数的二进制位。

第一版（java 有自带的 api ）

public class Solution {    // you need treat n as an unsigned value    public int reverseBits(int n) {        return Integer.reverse(n);    }}

第二版（位运算）

public class Solution {    // you need treat n as an unsigned value    public int reverseBits(int n) {        int num=0;        for(int i=1;i            num