文档章节

【leetcode】885. Boats to Save People

o
 osc_pn11u1x9
发布于 2018/08/06 09:02
字数 494
阅读 0
收藏 0
def

题目如下:

解题思路:本题可以采用贪心算法,因为每条船最多只能坐两人,所以在选定其中一人的情况下,再选择第二个人使得两人的体重最接近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

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

OSChina 周五乱弹 —— 你大妈还是你大妈

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @watergood:是时候分享一波我的这张纯音乐歌单了,过去的五年多时间里,我陆陆续续地把听到的好听的纯音乐添加了进去,目前一共65首,相信总...

小小编辑
今天
19
0
在Objective-C中生成随机数 - Generating random numbers in Objective-C

问题: I'm a Java head mainly, and I want a way to generate a pseudo-random number between 0 and 74. In Java I would use the method: 我主要是Java头,我想要一种生成0到74之间的伪随......

技术盛宴
今天
13
0
ftp-ftps-sftp的关系

Ftp FTP 是File Transfer Protocol(文件传输协议)的英文简称,而中文简称为“文传协议”。用于Internet上的控制文件的双向传输。同时,它也是一个应用程序(Application)。基于不同的操作...

独钓渔
今天
12
0
使Vim将所有空格显示为字符 - Make Vim show ALL white spaces as a character

问题: I can't find a way to make Vim show all white spaces as a character. 我找不到让Vim将所有空白显示为字符的方法。 All I found was about tabs, trailing spaces etc. 我发现的只......

富含淀粉
今天
23
0
RN 接入高德地图遇到的一些问题

react-native-amap-geolocation、react-native-amap3d 1、iOS Geolocation.getCurrentPosition 获取坐标后,没有返回 address 信息? 逆地理编码 Android 默认返回逆地理编码,而 iOS 需要手...

Jack088
今天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部