输入:表示电影时长的双数组,例如
。您最多可以观看 每天 3 时长的电影。durations[] ={1.01, 2.4, 1.01, 1.01, 1.4}
求看完所有电影所需的最少天数。
约束:1.01 <= duration[i] <= 3.00.
(可以选择当天观看任意电影,不会重复 看电影)示例测试用例:
输入:持续时间[] = {1.01, 2.4, 1.01, 1.01, 1.4}输出:3
输入:duration[] = {1.01, 2.4, 1.4, 1.6, 2.6, 1.7} 输出:4
输入:持续时间[] = {1.01, 2.4, 1.5, 1.6, 2.6, 1.7} 输出:5
我在放置编码测试中得到了这个,但无法按时完成 但后来使用递归做到了。它适用于我的几个测试用例 定制的,但我不确定它是否适用于所有可能的情况 测试用例。我也觉得它可以增强以获得更好的时间 复杂。请帮忙。
我的见解:你每天最多可以看 2 部电影 时长始终 >= 1.01,因此观看任意 3 部电影都会 持续时间超过 3.00。
这是我的代码:
import java.util.ArrayList;
public class MoviesBetterSolution {
public static void main(String[] args) {
double arr[] = {2.0,1.01,1.4,2.4,1.71}; //test case
System.out.println( f( 0, 0.00 , 1, 3.00, new ArrayList<Integer>(), arr , 0) );
//days passed a 1 as we start from day 1
//initial wtn (watched till now for a particular day) passes is 0.00
} static int minDays = Integer.MAX_VALUE;
//wtn -> watched till now (keeps track of duration of movies watched on the current day
//taken keeps track of number of movies watched on current day
// picked : watched movies on the day till now private static int f(int i, double wtn, int days, double limit, ArrayList<Integer>
picked, double[] arr, int taken) {
//updating minDays after reaching a point where all movies have been watched
if(picked.size()==arr.length) {
if( days<minDays ) minDays = days;
return minDays;
}
if(i == arr.length) { //finished traversing array
if(taken != 0) { //restart traversing to watch unwatched movies only if atleast 1
//movie was watched on the day, setting taken for the new traversal to be 0
i = 0;
taken = 0; }else { // otherwise just return if nothing was watched on the day, otherwise it
//will stackoverflow for all non watch choice recursion branch
return minDays;` } }
if((wtn + arr[i] <= limit) && !(picked.contains(i)) ) { //only movies that havent been watched can be watched
ArrayList<Integer> temp = new ArrayList<Integer>();
temp = (ArrayList<Integer>) picked.clone();
temp.add(i);
if(taken<2) { //as u can watch only 2 movies a day
f(i+1, wtn + arr[i] , days, limit, temp, arr, taken+1); //watch & move to next movie but on same day }
f(0, 0 , days +1 , limit, temp, arr, taken+1); // watch & move to next movie but on next day , wtn and index(i) set to 0 as u
starting new day }
f(i+1, wtn, days, limit, picked, arr, taken); //not watch & move to next movie on same day
return minDays; } }
假设所有电影的运行时间都在 1.01 到 3.00 之间,解决这个问题需要 O(n log n)
1. sort your list
2. set days = 0
3. set two pointers to the two ends of your list.
4. repeatedly do the following until all elements have been processed:
4.1 increment days
4.2 if the sum of the movies referred to is <= 3.0 then move both pointers towards the center, otherwise just decrement the larger one.
就在结束之前,两个指针有可能引用同一个元素。这需要一天时间。
我在面试时也遇到过同样的问题,但当时无法解决.. 我通过迭代方法的解决方案是......找到最大和对的电影以获得最短的天数。 1.用for循环初始化两个指针(i,j),最多我们可以选择2部电影。 2.通过填充 -1 .. 来获取两部电影和小于 3 个条件的最大和并块输入数组索引,以便我们可以跳过已经选择的该元素。 3.如果没有形成对,则仅阻止 1 部带有 -1 的电影,即第 i 个索引。 4.在第二个for循环结束时增加天数计数器并返回循环结束时的天数。
如果此方法有任何问题,请告诉我,非常感谢任何更好的解决方案。
我在面试中得到了这个问题,这就是我解决它的方法。
//Move list to an array, sort the array (baseline O(nlogn))
//set two int index pointers, left to the first element right to the last, and an index solution counter
//while left != right
//if arr[left] + arr[right] <= 3.00
//increment solution counter
//push left ptr right and right left
//else
//increment solution counter
//push right ptr left
//check if left == right, inc counter if so
//return counter
在 O(nlogn) 时间内简单解决。
您可以在movieswatchinhd平台观看电影
高清电影观看是提供宝莱坞、好莱坞和其他电影行业高清电影和网络系列的终极目的地,还允许您下载高清电影,我们在高清电影观看,为您带来所有最新的宝莱坞电影、好莱坞以及更多行业和网络系列。通过有史以来最值得信赖的高清电影下载器网站,一睹令人兴奋的电影和网络连续剧世界。
通过来自世界各地的文章,我们为您提供宝莱坞、好莱坞和其他电影行业的高清电影和网络系列等的最早片段。我们正在努力提供即将上映的高清电影。我们也将确保将来提供知情内容。