精华内容
下载资源
问答
  • leetcode 870 优势洗牌

    2018-08-21 20:42:54
    leetcode 870 优势洗牌 题目描述: 给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。返回 A 的任意排列,使其相对于 B 的优势最大化。 题目分析: 这...

    每天坚持刷题!!!

    leetcode 870 优势洗牌

    题目描述:
    给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。返回 A 的任意排列,使其相对于 B 的优势最大化。

    题目分析:

    1. 这道题乍看起来似乎可以用动态规划,但是细细一想这道题是无法拆分成子问题的。OK,既然动态规划没法用又是求极值的话,首先尝试用贪心法。

    2. 具体分析下,如果给定一个B中的一个数Bx,贪心的来看我们最好在A中找到所有比这个Bx大的数中最小的那个,即min([d for d in A if d > Bx]), 这样可以让A中更大的数去匹配B中可能存在的比Bx大的数

    3. 但是对每个B中的数去找这个备选的list实在太浪费时间,所以一个比较好的方法就是先对A和B进行升序排序,两个指针分别指向A和B开头的数,然后A的指针从头开始移动找到第一个比B的指针指向的数大的数,然后记下A的指针指向的数要移动的位置,即要移动到B的指针指向的数的原来的下标,然后B的指针移动到下一个数,直到A或B的指针指向末尾,没有匹配上的数字随机分配。

    def advantageCount(self, A, B):
            """
            :type A: List[int]
            :type B: List[int]
            :rtype: List[int]
            """
            if not A and not B:
                return
            if len(A) == len(B) == 1:
                return A
            bb = sorted([(i, id) for id, i in enumerate(B)], key=lambda x: x[0])
            A = sorted(A)
            result = [-1 for _ in B]
            temp = []
            start_a = 0
            for data in bb:
                while start_a < len(A) and A[start_a] <= data[0]:
                    temp.append(A[start_a])
                    start_a += 1
                if start_a >= len(A):
                    break
                result[data[1]] = A[start_a]
                start_a += 1
            for i in xrange(len(result)):
                if result[i] == -1:
                    result[i] = temp.pop()
            return result
    展开全文
  • 给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。 返回 A 的任意排列,使其相对于 B 的优势最大化。 示例 1: 输入:A = [2,7,11,15], B = [1,10,4,11] ...

    给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

    返回 A 的任意排列,使其相对于 B 的优势最大化。

    示例 1:

    输入:A = [2,7,11,15], B = [1,10,4,11]
    输出:[2,11,7,15]
    

    示例 2:

    输入:A = [12,24,8,32], B = [13,25,32,11]
    输出:[24,32,8,12]
    

    提示:

    1 <= A.length = B.length <= 10000
    0 <= A[i] <= 10^9
    0 <= B[i] <= 10^9
    

    \color{blue}思路分析:典型的贪心策略题,首先我们使用把vector容器A转换成multiset容器,然后顺序扫描B,对于每一个元素B[i]我们都尽可能在剩余的multiset容器中找到一个比它大的最小元素,如果找到了则直接使用,否则取出multiset中最小的元素。

    class Solution {
    public:
        vector<int> advantageCount(vector<int>& A, vector<int>& B) {
            vector<int> resVec;
            multiset<int> mySet(A.begin(), A.end());//把A转化成set容器
            for (const auto &num : B){//顺序扫描B
                auto it = mySet.upper_bound(num);//(二分法)获取最小的比num大的元素的迭代器
                if (it == mySet.end()){//如果剩余的mySet中没有比num大的元素,则取出最小的元素
                    it = mySet.begin();
                }
                resVec.push_back(*it);
                mySet.erase(it);//将*it从mySet中移除
            }
            return resVec;
        }
    };
    

    在这里插入图片描述

    展开全文
  • leetcode 870优势洗牌

    2020-02-01 14:41:33
    给定两个大小相等的数组A和B,A 相对于 B 的优势可以用满足A[i] > B[i]的索引 i的数目来描述。 返回A的任意排列,使其相对于 B的优势最大化。 示例 1: ...输入:A = [2,7,11,15], B = [1,10,4,11] ...

    给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

    返回 A 的任意排列,使其相对于 B 的优势最大化。

     

    示例 1:

    输入:A = [2,7,11,15], B = [1,10,4,11]
    输出:[2,11,7,15]
    示例 2:

    输入:A = [12,24,8,32], B = [13,25,32,11]
    输出:[24,32,8,12]
     

    提示:

    1 <= A.length = B.length <= 10000
    0 <= A[i] <= 10^9
    0 <= B[i] <= 10^9

    思路:题目的原型是田忌赛马,利用大根堆去处理B数组。

    class Solution {
        public int[] advantageCount(int[] A, int[] B) {
            Arrays.sort(A);
            int[] res = new int[A.length];
            Queue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1,int[] o2) {
                    return o2[0] - o1[0];
                }
            });
            for (int i = 0;i < B.length;i++) {
                queue.add(new int[]{B[i],i});
            }
            int l = 0;
            int r = A.length-1;
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                int index = cur[1];
                int val = cur[0];
                if (A[r] > val) {
                    res[index] = A[r--];
                } else {
                    res[index] = A[l++];
                }
            }
            return res;
        }
    }

     

    展开全文
  • leetcode 840 优势洗牌

    2018-10-13 11:52:27
    思路:很简单,田忌赛马。强对强,弱对弱,如果发现你的强打不过对方的强,就用最弱的对对方的强; 程序实现问题: 1、为了分出强弱,肯定要sort()排序一下, sort(C.rbegin(), C.rend());...

    思路:很简单,田忌赛马。强对强,弱对弱,如果发现你的强打不过对方的强,就用最弱的对对方的强;

    程序实现问题:

    1、为了分出强弱,肯定要sort()排序一下,

    sort(C.rbegin(), C.rend());     降序

    sort(C.begin(), C.end());        升序

    2、排序后索引都变了,怎么存储索引,

    定义  

    vector<pair<int,int>> C; 

     C.push_back({B[i], i});

    pair对存值和索引,注意初始化,这不是双vector

    3、交换vector中的次序,涉及到

    A.insert(A.begin() + i, A[size - 1]);     插入在第i个元素之前
                    A.pop_back();

    代码:

    class Solution {
    public:
        vector<int> advantageCount(vector<int>& A, vector<int>& B) {
            vector<pair<int,int>> C;
            int size = A.size();
            
            vector<int> result(size, -1);
            
            
            for(int i = 0; i < size; i++)
            {
                C.push_back({B[i], i});
            }
            
            sort(C.rbegin(), C.rend());
            sort(A.rbegin(), A.rend());
            
            for(int i = 0; i < size; i++)
            {
                if(A[i] <= C[i].first)
                {
                    A.insert(A.begin() + i, A[size - 1]);
                    A.pop_back();
                    
                }
                
            }
            
            for(int j =0; j< size; j++)
            {
                result[C[j].second] = A[j];
                
            }
            return result;
        }
    };

    展开全文
  • leetcode 870题 优势洗牌

    2020-03-23 23:07:02
    leetcode 870 优势洗牌 贪心算法 田忌赛马 题目:给定两个大小相等的数组 A 和 B A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。 返回 A 的任意排列,使其相对于 B 的优势最大化。 分析: 想...
  • Leetcode 870. 优势洗牌

    2019-03-30 01:03:00
    870.优势洗牌 显示英文描述 我的提交返回竞赛 用户通过次数49 用户尝试次数92 通过次数49 提交次数192 题目难度Medium 给定两个大小相等的数组A和B,A 相对于 B 的优势可以用满足A[i] &...
  • 优势洗牌 JAVA 题解 题目链接:https://leetcode-cn.com/problems/advantage-shuffle/ 思想: 田忌赛马 每次拿A的“当前轮次“的最小值和B的”当前轮次“最小值比较, 若大于,则OK,满足。(1) 若小于,则将A的值...
  • LeetCode 870. 优势洗牌

    2018-07-18 16:13:12
    最近刷LeetCode题目的一些思路,题目信息 给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] &gt; B[i] 的索引 i 的数目来描述。 返回 A 的任意排列,使其相对于 B 的优势最大化。...
  • Leetcode 870:优势洗牌

    2019-04-10 23:02:38
    题目描述 给定两个大小相等的数组A和B,A 相对于 B 的优势可以用满足A[i] > B[i]的索引i的数目来描述。 返回A的任意排列,使其相对于B的优势最大化。 ...输入:A = [12,24,8,32], B = [...
  • 我们可以用手中最弱的来与 b 配对,这样会使 A 中剩余的严格地变大,因此会有更多得分点。 代码 class Solution ( object ) : def advantageCount ( self , A , B ) : """ :type A: List[int] ...
  • leetcode 870.优势洗牌

    2018-11-03 07:52:46
    请输入代码给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。 返回 A 的任意排列,使其相对于 B 的优势最大化。 示例 1: 输入:A = [2,7,11,15], B = [1,10,4,...
  • leetcode 870. 优势洗牌

    2018-09-10 00:58:00
    给定两个大小相等的数组A和B,A 相对于 B 的优势可以用满足A[i] > B[i]的索引i的数目来描述。 返回A的任意排列,使其相对于B的优势最大化。 示例 1: ...输入:A = [2,7,11,15], B = [1,10,4,11] ...
  • LeetCode - 870. 优势洗牌

    2020-04-05 12:12:16
    870. 优势洗牌 给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。 返回 A 的任意排列,使其相对于 B 的优势最大化。 解题思路: 跟田忌赛马情景相似。我们用...
  • 给定两个大小相等的数组 A 和 B,A 相对于 B 的...来源:力扣(LeetCode) 链接: https://leetcode-cn.com/problems/advantage-shuffle 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
  • 优势洗牌(贪心算法) 贪心策略: 田忌赛马 code class Solution: def advantageCount(self, A: list, B: list) -&amp;gt; list: l = len(A) ans = [0 for _ in range(l)] b = sorted(lis...
  • 给定两个大小相等的数组A和B,A 相对于 B 的优势可以用满足A[i] > B[i]的索引i的数目来描述。 返回A的任意排列,使其相对于B的优势最大化。 示例 2: 输入:A = [12,24,8,32], B = [13,25,32,11] ...
  • 给定两个大小相等的数组A和B,A 相对于 B 的优势可以用满足A[i] > B[i]的索引i的数目来描述。 返回A的任意排列,使其相对于B的优势最大化。 示例 1: ...输入:A = [2,7,11,15], B = [1,10,4,11] ...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 134
精华内容 53
关键字:

leetcode洗牌