【leetcode】885. Boats to Save People

题目如下：

解题思路：本题可以采用贪心算法，因为每条船最多只能坐两人，所以在选定其中一人的情况下，再选择第二个人使得两人的体重最接近limit。考虑到人的总数最大是50000，而每个人的体重最大是30000，因此会有很多人体重一样。这样可以用一个集合set保存体重，再用字典保存每个体重对应的人的数量，可以减少运算量。最后对set进行升序排序，再用双指针的方法，用low指针指向set头部，high指针指向set尾部，分别比较set[low]和set[high]的值，有如下情况：

a. set[low] + set[high] > limit：表示set[high]的体重人只能一人坐一船，得出boats += dic[set[high]], high -= 1;

b. set[low] + set[high] <= high: 表示可以共坐一船，但这里又要考虑 dic[set[high]] 与 dic[set[low]] 的大小：

b1. dic[set[high]] > dic[set[low]] : 得出 boats += dic[set[low]], low += 1;

b2.dic[set[high]] < dic[set[low]] : 得出 boats += dic[set[high]], high -= 1;

b3:dic[set[high]] == dic[set[low]] : 得出 boats += dic[set[high]], high -= 1,low += 1;

最后当low == high的时候，表示只剩下相同体重的人，这时判断这些人能否共坐一船，得出最终boats的总数。

代码如下：

class Solution(object):

    def numRescueBoats(self, people, limit):

        """

        :type people: List[int]

        :type limit: int

        :rtype: int

        """

        dic = {}

        puniq = []

        for i in people:

            if i not in dic:

                dic[i] = 1

                puniq.append(i)

            else:

                dic[i] += 1

        puniq.sort()

        boats = 0

        low = 0

        high = len(puniq) - 1

        while low < high:

            if puniq[low] + puniq[high] > limit:

                boats += dic[puniq[high]]

                dic[puniq[high]] = 0

                high -= 1

            else:

                if dic[puniq[low]] > dic[puniq[high]]:

                    boats += dic[puniq[high]]

                    dic[puniq[low]] -= dic[puniq[high]]

                    dic[puniq[high]] = 0

                    high -= 1

                elif dic[puniq[low]] < dic[puniq[high]]:

                    boats += dic[puniq[low]]

                    dic[puniq[high]] -= dic[puniq[low]]

                    dic[puniq[low]] = 0

                    low += 1

                else:

                    boats += dic[puniq[high]]

                    dic[puniq[high]] = 0

                    dic[puniq[low]] = 0

                    low += 1

                    high -= 1

        if limit >= puniq[high]*2:

            boats += ((dic[puniq[high]]/2) + (dic[puniq[high]]%2))

        else:

            boats += dic[puniq[high]]

        #boats += dic[puniq[low]]

        return boats

巴特西

【leetcode】885. Boats to Save People

最新文章

热门文章