做歌手的网站/有做网站的吗

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

56-Merge-Intervals 合并区间

解题思路：Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

class Interval:def __init__(self, s=0, e=0):self.start = sself.end = edef merge(intervals):""":type intervals: List[Interval]:rtype: List[Interval]"""ret = []if len(intervals) == 0:return retintervals.sort(key=lambda x:x.start)now = intervals[0]for v in intervals[1:]:if v.start <= now.end:now.end = max(now.end,v.end)else:ret.append(now)now = vret.append(now)return ret

75. Sort Colors 颜色分类

解题思路：设定三个坐标i,j,k
i用来记录可与0调换的位置 j用来记录可与2调换的位置 k用来扫描整个list
当k扫描到2时 将这个2与j上的调换 将2放到后面 j往前移 (此时不知道被调过来的数 需要重新扫描 所以k不需要往后移)
当k扫描到0时 将这个0与i上的调换 将0放到后面 i,k往后移 (此时调过来的数是在前面已经扫描过的 所以k往后移)
当k扫描到1时 不做处理 k往后移

def sortColors(nums):""":type nums: List[int]:rtype: void Do not return anything, modify nums in-place instead."""i = 0k = 0j = len(nums)-1while k<=j:if nums[k]==2:nums[k],nums[j] = nums[j],nums[k]j-=1elif nums[k]==0:nums[i],nums[k] = nums[k],nums[i]k+=1i+=1else:k+=1

147. Insertion Sort List 对链表进行插入排序

解题思路：建立top头节点
每次处理head这个点 暂存下一个点在nt中 head.next
tpos,tv备份top从头开始遍历 找到某点值大于head值 (tpos 是 tv 之前的点 tpos->tv)
tv的值比head要大 所以要将head插入其中 tpos->head->tv
交换好后 head继续处理下一个点 (之前存储在nt)

class ListNode(object):def __init__(self, x):self.val = xself.next = Nonedef insertionSortList(head):""":type head: ListNode:rtype: ListNode"""top = ListNode(0)while head:nt = head.nexttpos = toptv = top.nextwhile tv and head.val>tv.val:tv = tv.nexttpos = tpos.nexttpos.next = headhead.next = tvhead = ntreturn top.next

179. Largest Number 最大数

解题思路：自定义排序

import functools
def largestNumber(nums):""":type nums: List[int]:rtype: str"""nums = list(map(str,nums))nums.sort(key=functools.cmp_to_key(lambda a,b: 1 if a+b<b+a else -1))s = (''.join(nums))return '0' if s[0]=='0' else s

274. H-Index H指数

解题思路：排除list为空 以及 全部未被引用的情况
将list从大到小排序 比较次数与位置大小 记录引用次数大的位置

def hIndex(citations):""":type citations: List[int]:rtype: int"""citations.sort(reverse=True)if len(citations)==0 or max(citations)==0:return 0ans = 0for i in range(1,len(citations)+1):if i<=citations[i-1]:ans = ielse:breakreturn ans