LeetCode 每日一题 2022/9/12-2022/9/18

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

---

9/12 1608. 特殊数组的特征值

nums有n个数
从大到小排序后
找到x使得 nums[x]=x

def specialArray(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    n = len(nums)
    nums.sort(reverse=True)
    for i in range(1,n):
        if nums[i]<i and nums[i-1]>=i:
            return i
    if n<=nums[-1]:
        return n
    return -1


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

9/13 670. 最大交换

分解 排序
找到最先不同的位置

def maximumSwap(num):
    """
    :type num: int
    :rtype: int
    """
    l = []
    ori = num
    while num>0:
        l.append(num%10)
        num//=10
    n = len(l)
    tmp = [v for v in l]
    tmp.sort()
    print(l,tmp)
    loc = -1
    for i in range(n-1,-1,-1):
        if tmp[i]!=l[i]:
            loc = i
            break
    if loc==-1:
        return ori
    for i in range(n):
        if tmp[loc]==l[i]:
            l[loc],l[i] = l[i],l[loc]
            break
    ans = 0
    for v in l[::-1]:
        ans = ans*10+v
    return ans


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

9/14 1619. 删除某些元素后的数组均值

排序后统计中间部分均值

def trimMean(arr):
    """
    :type arr: List[int]
    :rtype: float
    """
    arr.sort()
    n = len(arr)
    v = n//20
    total = sum(arr[v:n-v])
    return total/(n-2*v)
1
2
3
4
5
6
7
8
9
10

---

9/15 672. 灯泡开关 Ⅱ

对于每个开关 先后顺序不影响结果
对于单个开关 按两次则相当于没有按 只需要考虑每个开关是奇数次还是偶数次
找规律 第一个开关影响全部
偶数 2 4 6
奇数 1 3 5
3k+1 1 4
可以发现
6k+1 被 1,3,4影响
6k+2,6k+6 被1,2影响
6k+3,6k+5 被1,3影响
6k+4 被 1,2,4影响
只需考虑前四盏灯状态即可
假设开关次数a,b,c,d
1.6k+1 = (a+c+d)%2
2.6k+2 = (a+b)%2
3.6k+3 = (a+c)%2
4.6k+4 = (a+b+d)%2
再考虑如果1,3盏灯状态相同 则d为偶数 2,4相同
否则d为奇数 2,4不同
所以4的状态可以根据1,2,3得出
最后只需考虑三盏灯的状态
三盏灯开始状态为111
按一次 000,101,010,011
按两次 有7种
三次及以上 8种可能
特殊考虑 只有1盏或2盏灯

def flipLights(n, presses):
    """
    :type n: int
    :type presses: int
    :rtype: int
    """
    if presses==0:
        return 1
    if n==1:
        return 2
    elif n==2:
        if presses==1:
            return 3
        else:
            return 4
    else:
        if presses==1:
            return 4
        elif presses==2:
            return 7
        else:
            return 8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

9/16 850. 矩形面积 II

扫描线法
用一条垂直的线从左到右扫描
直线上被覆盖的部分累加则为矩形面积
该直线上被覆盖的线段 即为矩形上下边界的范围
将所有上下边界去重排序bound 将直线分割成m个区间 seg[i] = bound[i+1]-bound[i]
将左右边界排序lr 左边界意味着线段+1 右边界意味着线段-1
直线扫描时 将横坐标相同的左右边界一同处理
统计所有区间seg 将被覆盖的相加

def rectangleArea(rectangles):
    """
    :type rectangles: List[List[int]]
    :rtype: int
    """
    MOD = 10**9+7
    bound = set()
    lr = []
    for i,rect in enumerate(rectangles):
        bound.add(rect[1])
        bound.add(rect[3])
        lr.append((rect[0],i,1))
        lr.append((rect[2],i,-1))
    bound = sorted(bound)
    m = len(bound)
    seg = [0]*(m-1)
    lr.sort()
    ans = 0
    i = 0
    while i<len(lr):
        j = i
        while j+1<len(lr) and lr[i][0]==lr[j+1][0]:
            j+=1
        if j+1==len(lr):
            break
        
        for k in range(i,j+1):
            _,idx,diff = lr[k]
            bt,up = rectangles[idx][1],rectangles[idx][3]
            for x in range(m-1):
                if bt<=bound[x] and up>=bound[x+1]:
                    seg[x]+=diff
        cover = 0
        for x in range(m-1):
            if seg[x]>0:
                cover += bound[x+1]-bound[x]
        ans += cover *(lr[j+1][0]-lr[j][0])
        i = j+1
    return ans %MOD


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

---

9/17 1624. 两个相同字符之间的最长子字符串

hash记录每个字符第一次出现的位置

def maxLengthBetweenEqualCharacters(s):
    """
    :type s: str
    :rtype: int
    """
    loc = {}
    ans = 0
    for idx,c in enumerate(s):
        if c in loc:
            ans = max(ans,idx-1-loc[c])
        else:
            loc[c] = idx
    return ans


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

9/18 827. 最大人工岛

dfs获取当前每个岛 并给每个岛内的陆地打上相同标签curtag
area保存每个curtag岛屿面积
遍历每一个当前为0的区域 寻找其上下左右是否存在岛屿
将其相连的岛屿相加得到面积 取最大值

def largestIsland(grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    from collections import defaultdict
    n = len(grid)
    tag = [[0]*n for _ in range(n) ]
    curtag = 0
    area = defaultdict(int)
    area[0]=0
    def dfs(i,j):
        tag[i][j] = curtag
        area[curtag] +=1
        for x,y in (i-1,j),(i+1,j),(i,j-1),(i,j+1):
            if 0<=x<n and 0<=y<n and tag[x][y]==0 and grid[x][y]==1:
                dfs(x,y)
    for i in range(n):
        for j in range(n):
            if grid[i][j]==1 and tag[i][j]==0:
                curtag+=1
                dfs(i,j)
    
    ans = max(area.values())
    for i in range(n):
        for j in range(n):
            if grid[i][j]==0:
                curv = 1
                s =set()
                for x,y in (i-1,j),(i+1,j),(i,j-1),(i,j+1):
                    if 0<=x<n and 0<=y<n and tag[x][y]>0:
                        s.add(tag[x][y])
                for t in s:
                    curv+=area[t]
                ans = max(ans,curv)
    return ans


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---