网站收录一键提交,wordpress注册没有界面,网站开发需要多钱,郑州网站推广优化公司题目
https://www.lintcode.com/problem/552/description
描述
给出两个长度分别是m和n的数组来表示两个大整数#xff0c;数组的每个元素都是数字0-9。从这两个数组当中选出k个数字来创建一个最大数#xff0c;其中k满足k m n。选出来的数字在创建的最大数里面的位置…题目
https://www.lintcode.com/problem/552/description
描述
给出两个长度分别是m和n的数组来表示两个大整数数组的每个元素都是数字0-9。从这两个数组当中选出k个数字来创建一个最大数其中k满足k m n。选出来的数字在创建的最大数里面的位置必须和在原数组内的相对位置一致。返回k个数的数组。你应该尽可能的去优化算法的时间复杂度和空间复杂度。样例
样例 1:输入nums1 [3, 4, 6, 5] nums2 [9, 1, 2, 5, 8, 3]k 5
输出[9, 8, 6, 5, 3]
解释
从第一个数组选择[6, 5]从第二个数组选择[9, 8, 3]
样例 2:输入nums1 [6, 7] nums2 [6, 0, 4]k 5
输出[6, 7, 6, 0, 4]
解释
从第一个数组选择[6, 7]从第二个数组选择[6, 0, 4]
样例 3:输入nums1 [3, 9] nums2 [8, 9]k 3
输出[9, 8, 9]
解释
从第一个数组选择[9]从第二个数组选择[8, 9]//思路 左边选i个右边选k - i个merge出最大的/*参考C答案地址https://blog.csdn.net/qq_31552435/article/details/52216546比较双端队列【具有队列栈的特性】 大小的逻辑https://blog.csdn.net/Olivia_CFS/article/details/121596084和C答案这篇博客不同的是java判断两个LinkedList的大小需要自己写而C 的vector本身就是可比较的答案
public class Solution {/*** param nums1: an integer array of length m with digits 0-9* param nums2: an integer array of length n with digits 0-9* param k: an integer and k m n* return: an integer array*/public int[] maxNumber(int[] nums1, int[] nums2, int k) {//思路 左边选i个右边选k - i个merge出最大的/*参考C答案地址https://blog.csdn.net/qq_31552435/article/details/52216546比较双端队列【具有队列栈的特性】 大小的逻辑https://blog.csdn.net/Olivia_CFS/article/details/121596084和C答案这篇博客不同的是java判断两个LinkedList的大小需要自己写而C 的vector本身就是可比较的*/int len1 nums1.length, len2 nums2.length;int start Math.max(k - len2, 0);int end Math.min(k, len1);LinkedListInteger path null;for (int k1 start; k1 end; k1) {LinkedListInteger path1 f(nums1, k1);LinkedListInteger path2 f(nums2, k - k1);// System.out.println(path1: path1);//System.out.println(path2: path2);LinkedListInteger cmp connect(path1, path2);// System.out.println(cmp: cmp);//System.out.println(path: path);if (path ! null) {for (int i 0; i cmp.size(); i) {if (path.get(i) ! cmp.get(i)) {if (cmp.get(i) path.get(i)) {path cmp;}break;}}} else {path cmp;}}if(path.size()0 path.get(path.size()-1) null){path.removeLast();}int[] ans new int[path.size()];for (int i 0; i path.size(); i) {ans[i] path.get(i);}return ans;}/*·输入数据[1,6,5,4,7,3,9,5,3,7,8,4,1,1,4][4,3,1,3,5,9]21输出数据[4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,1,4,1,3,5,9]期望答案[4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,3,5,9,1,1,4]*/public static LinkedListInteger connect(LinkedListInteger ll1, LinkedListInteger ll2) {//https://blog.csdn.net/Olivia_CFS/article/details/121596084,比较逻辑参考C代码LinkedListInteger ll new LinkedList();while (ll1.size() ll2.size() 0) {//参考https://blog.csdn.net/Olivia_CFS/article/details/121596084//检查ll1,ll2谁更大while (ll1.isEmpty() !ll2.isEmpty())ll.add(ll2.pollFirst());while (!ll1.isEmpty() ll2.isEmpty())ll.add(ll1.pollFirst());int max 1;int i1 0,i2 0;boolean findMax false;int n1 ll1.size(),n2 ll2.size();while (i1n1 i2 n2){if(ll2.get(i2) ll1.get(i1)){max 2;findMax true;break;}else if(ll2.get(i2) ll1.get(i1)){max 1;findMax true;break;}else{i1;i2;}}//对于有的测试用例这里很关键if(findMax){ //如果找到最大的了比如 ll1 1 2 3 4 和 ll21 2 4 ll2更大if(max 1)ll.add(ll1.pollFirst());if(max 2)ll.add(ll2.pollFirst());}else{//没有找到更大的比如 ll1 1 2 3 ll2 1 2 3 4 那么ll2 更大if(n1n2)ll.add(ll1.pollFirst());else ll.add(ll2.pollFirst());}}return ll;}public static LinkedListInteger f(int[] nums, int k) {int drop nums.length - k;LinkedListInteger ll new LinkedList();for (int num : nums) {while (drop 0 ll.size() 0 ll.peekLast() num) {ll.removeLast();drop--;}ll.add(num);}while (ll.size() k) {ll.removeLast();}return ll;}}本地测试代码
public class LC552 {public static int[] maxNumber(int[] nums1, int[] nums2, int k) {//思路 左边选i个右边选k - i个merge出最大的/*参考C答案地址https://blog.csdn.net/qq_31552435/article/details/52216546比较双端队列【具有队列栈的特性】 大小的逻辑https://blog.csdn.net/Olivia_CFS/article/details/121596084和C答案这篇博客不同的是java判断两个LinkedList的大小需要自己写而C 的vector本身就是可比较的*/int len1 nums1.length, len2 nums2.length;int start Math.max(k - len2, 0);int end Math.min(k, len1);LinkedListInteger path null;for (int k1 start; k1 end; k1) {LinkedListInteger path1 f(nums1, k1);LinkedListInteger path2 f(nums2, k - k1);// System.out.println(path1: path1);//System.out.println(path2: path2);LinkedListInteger cmp connect(path1, path2);// System.out.println(cmp: cmp);//System.out.println(path: path);if (path ! null) {for (int i 0; i cmp.size(); i) {if (path.get(i) ! cmp.get(i)) {if (cmp.get(i) path.get(i)) {path cmp;}break;}}} else {path cmp;}}if(path.size()0 path.get(path.size()-1) null){path.removeLast();}int[] ans new int[path.size()];for (int i 0; i path.size(); i) {ans[i] path.get(i);}return ans;}/*·输入数据[1,6,5,4,7,3,9,5,3,7,8,4,1,1,4][4,3,1,3,5,9]21输出数据[4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,1,4,1,3,5,9]期望答案[4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,3,5,9,1,1,4]*/public static LinkedListInteger connect(LinkedListInteger ll1, LinkedListInteger ll2) {//https://blog.csdn.net/Olivia_CFS/article/details/121596084,比较逻辑参考C代码LinkedListInteger ll new LinkedList();while (ll1.size() ll2.size() 0) {//参考https://blog.csdn.net/Olivia_CFS/article/details/121596084//检查ll1,ll2谁更大while (ll1.isEmpty() !ll2.isEmpty())ll.add(ll2.pollFirst());while (!ll1.isEmpty() ll2.isEmpty())ll.add(ll1.pollFirst());int max 1;int i1 0,i2 0;boolean findMax false;int n1 ll1.size(),n2 ll2.size();while (i1n1 i2 n2){if(ll2.get(i2) ll1.get(i1)){max 2;findMax true;break;}else if(ll2.get(i2) ll1.get(i1)){max 1;findMax true;break;}else{i1;i2;}}//对于有的测试用例这里很关键if(findMax){ //如果找到最大的了比如 ll1 1 2 3 4 和 ll21 2 4 ll2更大if(max 1)ll.add(ll1.pollFirst());if(max 2)ll.add(ll2.pollFirst());}else{//没有找到更大的比如 ll1 1 2 3 ll2 1 2 3 4 那么ll2 更大if(n1n2)ll.add(ll1.pollFirst());else ll.add(ll2.pollFirst());}}return ll;}public static LinkedListInteger f(int[] nums, int k) {int drop nums.length - k;LinkedListInteger ll new LinkedList();for (int num : nums) {while (drop 0 ll.size() 0 ll.peekLast() num) {ll.removeLast();drop--;}ll.add(num);}while (ll.size() k) {ll.removeLast();}return ll;}public static void main(String[] args) {test99();//test99ok();// test1();//test2();// test3();//test4();}public static void test99() {int[] nums1 arr99, nums2 arr100;int k1 k99;int[] data1 maxNumber(nums1, nums2, k1);for (int i : data1) {System.out.print(i ,);}System.out.println();int[] nums11 arr99, nums21 arr100;int k11 k99;int[] data11 new Solution().maxNumber(nums11, nums21, k11);for (int i : data11) {System.out.print(i ,);}int n data1.length;int incr 0;for (int i 0; i n; i) {if (data1[i] ! data11[i]) {System.out.println(i 正确 data11[i] 当前 data1[i]);if (incr 3)break;}}}public static void test99ok() {int[] nums1 arr99, nums2 arr100;int k1 k99;int[] data1 new Solution().maxNumber(nums1, nums2, k1);for (int i : data1) {System.out.print(i ,);}System.out.println();}public static void test1() {int[] nums1 {3, 4, 6, 5}, nums2 {9, 1, 2, 5, 8, 3};int k1 5;int[] data1 maxNumber(nums1, nums2, k1);for (int i : data1) {System.out.print(i );}System.out.println();}public static void test2() {int[] nums1 {6, 7}, nums2 {6, 0, 4};int k1 5;int[] data1 maxNumber(nums1, nums2, k1);for (int i : data1) {System.out.print(i );}System.out.println();}public static void test3() {int[] nums1 {3, 9}, nums2 {8, 9};int k1 3;int[] data1 maxNumber(nums1, nums2, k1);for (int i : data1) {System.out.print(i );}System.out.println();}public static void test4() {int[] nums1 {1, 6, 5, 4, 7, 3, 9, 5, 3, 7, 8, 4, 1, 1, 4}, nums2 {4, 3, 1, 3, 5, 9};int k1 21;int[] data1 maxNumber(nums1, nums2, k1);for (int i : data1) {System.out.print(i );}System.out.println();}static int[] arr99 {2,0,2,1,2,2,2,2,0,1,0,0,2,0,2,0,2,1,0,1,1,0,1,0,1,2,1,1,1,0,1,2,2,1,0,0,1,2,1,2,2,1,1,0,1,2,0,2,0,1,2,0,2,1,1,1,2,0,0,1,0,2,1,2,0,1,0,0,0,1,2,1,0,1,1,2,0,2,2,0,0,1,1,2,2,1,1,2,2,1,0,1,2,0,1,2,2,0,0,0,2,0,2,0,2,2,0,1,1,1,1,2,2,2,2,0,0,2,2,2,2,0,2,0,1,0,0,2,1,0,0,2,0,2,1,1,1,1,0,1,2,0,2,1,0,1,1,1,0,0,2,2,2,0,2,1,1,1,2,2,0,0,2,2,2,2,2,0,2,0,2,0,2,0,0,1,0,1,1,0,0,2,1,1,2,2,2,1,2,2,0,0,2,1,0,2,1,2,1,1,1,0,2,0,1,1,2,1,1,0,0,1,0,1,2,2,2,0,2,2,1,0,1,2,1,2,0,2,2,0,1,2,2,1,2,2,1,1,2,2,2,2,2,1,2,0,1,1,1,2,2,2,0,2,0,2,0,2,1,1,0,2,2,2,1,0,2,1,2,2,2,0,1,1,1,1,1,1,0,0,0,2,2,0,1,2,1,0,0,2,2,2,2,1,0,2,0,1,2,0},arr100{1,1,1,0,0,1,1,0,2,1,0,1,2,1,0,2,2,1,0,2,0,1,1,0,0,2,2,0,1,0,2,0,2,2,2,2,1,1,1,1,0,0,0,0,2,1,0,2,1,1,2,1,2,2,0,2,1,0,2,0,0,2,0,2,2,1,0,1,0,0,2,1,1,1,2,2,0,0,0,1,1,2,0,2,2,0,1,0,2,1,0,2,1,1,1,0,1,1,2,0,2,0,1,1,2,0,2,0,1,2,1,0,2,0,1,0,0,0,1,2,1,2,0,1,2,2,1,1,0,1,2,1,0,0,1,0,2,2,1,2,2,0,0,0,2,0,0,0,1,0,2,0,2,1,0,0,1,2,0,1,1,0,1,0,2,2,2,1,1,0,1,1,2,1,0,2,2,2,1,2,2,2,2,0,1,1,0,1,2,1,2,2,0,0,0,0,0,1,1,1,2,1,2,1,1,0,1,2,0,1,2,1,2,2,2,2,0,0,0,0,2,0,1,2,0,1,1,1,1,0,1,2,2,1,0,1,2,2,1,2,2,2,0,2,0,1,1,2,0,0,2,2,0,1,0,2,1,0,0,1,1,1,1,0,0,2,2,2,2,0,0,1,2,1,1,2,0,1,2,1,0,2,0,0,2,1,1,0,2,1,1,2,2,0,1,0,2,0,1,0};static int k99 600;static class Solution {/*** param nums1 an integer array of length m with digits 0-9* param nums2 an integer array of length n with digits 0-9* param k an integer and k m n* return an integer array*/public int[] maxNumber(int[] nums1, int[] nums2, int k) {// Write your code hereif (k 0)return new int[0];int m nums1.length, n nums2.length;if (m n k) return null;if (m n k) {int[] results merge(nums1, nums2, k);return results;} else {int max m k ? k : m;int min n k ? 0 : k - n;int[] results new int[k];for (int i 0; i k; i)results[i] -0x7ffffff;for (int i min; i max; i) {int[] temp merge(getMax(nums1, i), getMax(nums2, k - i), k);results isGreater(results, 0, temp, 0) ? results : temp;}return results;}}private int[] merge(int[] nums1, int[] nums2, int k) {int[] results new int[k];if (k 0) return results;int i 0, j 0;for (int l 0; l k; l) {results[l] isGreater(nums1, i, nums2, j) ? nums1[i] : nums2[j];}return results;}private boolean isGreater(int[] nums1, int i, int[] nums2, int j) {for (; i nums1.length j nums2.length; i, j) {if (nums1[i] nums2[j])return true;if (nums1[i] nums2[j])return false;}return i ! nums1.length;}private int[] getMax(int[] nums, int k) {if (k 0)return new int[0];int[] results new int[k];int i 0;for (int j 0; j nums.length; j) {while (nums.length - j i k i 0 results[i - 1] nums[j])i--;if (i k)results[i] nums[j];}return results;}}}
/*
366 ms
时间消耗
·
21.32 MB
空间消耗
·
输入数据
[1,6,5,4,7,3,9,5,3,7,8,4,1,1,4]
[4,3,1,3,5,9]
21
输出数据
[4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,1,4,1,3,5,9]
期望答案
[4,3,1,6,5,4,7,3,9,5,3,7,8,4,1,3,5,9,1,1,4]*/
