备案号 查询 网站,怀化市优化办电话,湖南高端网站制作公,主流建站公司leetcode 150道题 计划花两个月时候刷完之未完成后转#xff0c;今天#xff08;第1天#xff09;完成了4道(101-104)150#xff1a;
101.(215. 数组中的第K个最大元素) 题目描述#xff1a;
给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请…leetcode 150道题 计划花两个月时候刷完之未完成后转今天第1天完成了4道(101-104)150
101.(215. 数组中的第K个最大元素) 题目描述
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。第一版这个题看了好几天。。复习了快排的写法也算有收获最后还是看了解题
class Solution {Random randomnew 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(leftright){return nums[k];}int randomIndexleftrandom.nextInt(right-left1);swap(nums,left,randomIndex);int middleNumnums[left];int leftTempleft1;int rightTempright;while(leftTemprightTemp){while(leftTemprightTempnums[rightTemp]middleNum){rightTemp--;}while(leftTemprightTempnums[leftTemp]middleNum){leftTemp;}if(leftTemprightTemp){break;}swap(nums,leftTemp,rightTemp);leftTemp;rightTemp--;}swap(nums,left,rightTemp);if(krightTemp){return nums[rightTemp];}else if(krightTemp){return quickSort(nums,rightTemp1,right,k);}else{return quickSort(nums,left,rightTemp-1,k);}}public void swap(int[] nums, int left,int right){int tempnums[left];nums[left]nums[right];nums[right]temp;}
}第二版用了java 自带的堆集合大堆根
class Solution {public int findKthLargest(int[] nums, int k) {int lennums.length;PriorityQueueInteger priorityQueuenew PriorityQueueInteger(len,(o1,o2)-o2.compareTo(o1));for(int num:nums){priorityQueue.offer(num);}for(int i0;ik-1;i){priorityQueue.poll();}return priorityQueue.peek();}
}102.373. 查找和最小的 K 对数字题目描述
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)其中第一个元素来自 nums1第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。第一版我一上来就是全部结果拿到然后排序返回前K个然后报超时解题的去重不是很好的理解的。意思就是先将开头的放进去然后下面取下一个要出现的组合时候只需要向右找就行这样就不会重复了
class Solution {public ListListInteger kSmallestPairs(int[] nums1, int[] nums2, int k) {ListListInteger resnew ArrayList();PriorityQueueint[] prioritynew PriorityQueueint[](k,(o1,o2)-{return nums1[o1[0]]nums2[o1[1]]-nums1[o2[0]]-nums2[o2[1]];});int mnums1.length;int nnums2.length;for(int i0;iMath.min(m,k);i){priority.offer(new int[]{i,0});}while(k--0!priority.isEmpty()){int[] temppriority.poll();ListInteger listnew ArrayList();list.add(nums1[temp[0]]);list.add(nums2[temp[1]]);res.add(list);if(temp[1]1n){priority.offer(new int[]{temp[0],temp[1]1});}}return res;}
}103.67. 二进制求和题目描述
给你两个二进制字符串 a 和 b 以二进制字符串的形式返回它们的和。
示例
输入:a 11, b 1
输出100第一版用java自带的api先转为整数相加然后再转为2进制会超长所以只能慢慢算我写的有点啰嗦。。
class Solution {public String addBinary(String a, String b) {StringBuilder sbnew StringBuilder();int lenAa.length();int lenBb.length();int indexAlenA-1;int indexBlenB-1;boolean flagfalse;while(indexA0indexB0){if(flag){if(a.charAt(indexA)1b.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);flagfalse;}}else{if(a.charAt(indexA)1b.charAt(indexB)1){sb.insert(0,0);flagtrue;}else if(a.charAt(indexA)1||b.charAt(indexB)1){sb.insert(0,1);}else{sb.insert(0,0);}}indexA--;indexB--;}while(indexA0){if(flag){if(a.charAt(indexA)1){sb.insert(0,0);}else{sb.insert(0,1);flagfalse;}}else{if(a.charAt(indexA)1){sb.insert(0,1);}else{sb.insert(0,0);}}indexA--;}while(indexB0){if(flag){if(b.charAt(indexB)1){sb.insert(0,0);}else{sb.insert(0,1);flagfalse;}}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 valuepublic int reverseBits(int n) {return Integer.reverse(n);}
}第二版位运算
public class Solution {// you need treat n as an unsigned valuepublic int reverseBits(int n) {int num0;for(int i1;i32;i){num1;//先向左移动一位留出位置//取出 n 的最后一位int p(n1);nump;n1;}return num; }
}年过完了。。亲也相完了。。回归正常!!!
