FB店面

您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

Thanks for sharing and wish you can get the offer asap.

I implemented the first question with a sortedDictionary:

        private static IList<int> ReduceModule(int[] A, int[] B, int limit)
        {
            int sum = 0;
            SortedDictionary<int, List<int>> dict = new SortedDictionary<int, List<int>>(new DescendingComparer<int>());
            for (int i = 0; i < A.Length; i++)
            {
                sum += A[i];
                A[i] -= B[i];
                if(!dict.ContainsKey(A[i])) dict.Add(A[i], new List<int>());
                dict[A[i]].Add(i);
            }
            sum -= limit;

            IList<int> res = new List<int>();
            while (dict.Count > 0 && sum > 0)
            {
                KeyValuePair<int, List<int>> kvp = dict.First();
                sum -= kvp.Key;
                res.Add(kvp.Value.First());
                kvp.Value.RemoveAt(0);
                if (kvp.Value.Count == 0) dict.Remove(kvp.Key);
            }

            return res;
        }

zhou.yuh 发表于 2018-10-17 10:34
求排序解法 🙏

就逐个求差值，然后把差值从大排到小，你把原大小和要压缩的大小的差值作为target，什么时候差值的和达到了target就可以输出了

xiebw 发表于 2018-10-17 00:55
第一题可以算出差值，建立一个差值数组然后sliding window吗

来自一亩三分地官方APP

没说要求连续吧，所以是不是求差排序然后从最大开始取就可以了？

第一题可以算出差值，建立一个差值数组然后sliding window吗

来自一亩三分地官方APP

xiebw 发表于 2018/10/17 00:55:47
第一题可以算出差值，建立一个差值数组然后sliding window吗

来自一亩三分地官方APP

说错了……是差值然后背包吗……

来自一亩三分地官方APP

iversonhw 发表于 2018/10/17 00:59:49


没说要求连续吧，所以是不是求差排序然后从最大开始取就可以了？

对对，我一开始看错了，我是觉得也可以背包来整，不过似乎排序解简单粗暴

来自一亩三分地官方APP

xiebw 发表于 2018-10-17 01:07
对对，我一开始看错了，我是觉得也可以背包来整，不过似乎排序解简单粗暴

来自一亩三分地官方APP

嗯，直接排序就行了

楼主知道结果了吗？

xiebw 发表于 2018-10-17 01:07
对对，我一开始看错了，我是觉得也可以背包来整，不过似乎排序解简单粗暴

来自一亩三分地官方APP

求排序解法 🙏