leetcode

发表于 | 分类于

无重复字符的最长子串的长度

用临时StringBuffer存储最长子串，如果遇到重复的字符，将已存储的最长子串中的重复位置前的部分全部删除，并记录此时的长度，时间复杂度是O(n),空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def getuniqsub(s):
    i=0
    j=0
    res = ""
    while j < len(s):
        # print(s[i:j])
        if s[j] not in s[i:j]:
            j += 1
            if j == len(s):
                if j - i > len(res):
                    res = s[i:j]
        else:
            if j - i > len(res):
                res = s[i:j]
            i = i + s[i:j].index(s[j]) + 1
    return res

最长公共前缀

非空个位数链表相加

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
42
43
 public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
           int tag = 0;
        ListNode ret = new ListNode(0);
        ListNode hehe = ret;
        while (l1 != null || l2 != null){
            if (l1 ==null){
                ret.val = (l2.val + tag)%10;
                tag = ( l2.val + tag)/10;
                l2 = l2.next;
            }else if (l2 == null){
                ret.val = (l1.val + tag)%10;
                tag = ( l1.val + tag)/10;
                l1 = l1.next;
            }else{
                ret.val = (l1.val + l2.val + tag)%10;
                tag = (l1.val + l2.val + tag)/10;
                l1 = l1.next;
                l2 = l2.next;
            }
            if (l1 == null && l2 == null ){
                if (tag == 1){
                    ret.next = new ListNode(1);
                    ret = ret.next;
                }else {
                    ret.next = null;
                }

            }else {
                ret.next = new ListNode(0);
                ret = ret.next;
            }

        }


        return hehe;
    }

盛水最多的容器

双指针,设置头指针和为指针，关键思路是找到俩端哪个高度更低，那么就挪动那个端的值，更加有可能找到更大的面积，因为面积取决于低的高度和横坐标之间的长度的乘积。

1
2
3
4
5
6
7
8
9
10
11
12
  public int maxArea(int[] height) {
        int maxarea = 0,l=0,r=height.length-1;
        while(l<r){
            maxarea = Math.max(maxarea,Math.min(height[l],height[r])*(r-l));
            if(height[l] < height[r]){
                l++;
            }else{
                r--;
            }
        }
        return maxarea;
    }

最小覆盖字串

滑动窗口，当窗口右边界不断滑动，从而覆盖了目标子串中的所有元素时，收缩左边界，直到窗口刚刚覆盖目标字串，记录此时的窗口大小，然后将左窗口再收缩一个字符，并且更新是否覆盖字串的标记，继续滑动

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
import  collections
def minWindow( s: str, t: str) -> str:
    need=collections.defaultdict(int)
    for c in t:
        need[c]+=1
    needCnt=len(t)
    i=0
    res=(0,float('inf')) #0和无穷大
    for j,c in enumerate(s):
        if need[c]>0:
            needCnt-=1
        need[c]-=1
        if needCnt==0:       #步骤一：滑动窗口包含了所有T元素
            while True:      #步骤二：增加i，排除多余元素
                c=s[i]
                if need[c]==0: #表示c这个字符属于t
                    break
                need[c]+=1 #表示c这个字符不属于t，继续找下一个字符
                i+=1
            if j-i<res[1]-res[0]:   #记录结果
                res=(i,j)
            need[s[i]]+=1  #步骤三：i增加一个位置，寻找新的满足条件滑动窗口
            needCnt+=1
            i+=1
    return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果

单向链表寻找中间节点

快慢双指针，快指针遍历到末尾的时候，慢指针就是到中间节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Node():

    def __init__(self, val):
        self.val = val
        self.next = None

# 单向链表中间节点
def findmid(node):
    first = node
    second = node
    while first and first.next:
        #print(first.val)
        first = first.next.next
        second = second.next
    return second.val

最多颜色的车辆

滑动窗口，每次移动窗口的时候，只需要比较新加入的元素的个数和之前记录的最多值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def maxColor(color, win):
    count = {
        "0":0,
        "1":0,
        "2":0
    }
    l =0
    r = l + win
    for c in color[l:r]:
        count[c] += 1
    maxV = max(count.values())
    while r < len(color):
        add = color[r]
        remove = color[l]
        l += 1
        r +=1
        count[add]+=1
        count[remove]-=1
        maxV = max(maxV,count[add])
    return maxV

数位DP

电话号码字母组合

使用回溯算法，套公式即可

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
def letterCombinations(digits):
    n_dict ={
        "2":["a","b","c"],
        "3":["d","e","f"],
        "4":["g","h","i"],
        "5":["j","k","l"],
        "6":["m","n","o"],
        "7":["p","q","r","s"],
        "8":["t","u","v"],
        "9":["w","x","y","z"]
    }
    if not digits:
        return []
    tmp = []
    result = []
    def backtrack(i):
        if i >= len(digits):
            result.append("".join(tmp))
            return
        for item in n_dict[digits[i]]:
            tmp.append(item)
            backtrack(i+1)
            tmp.pop()
    backtrack(0)
    return result

最大平分数组

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
42
43
44
45
46
47
48
49
50
51
def getR(input_list: list):
    input_list.sort(reverse=True)
    sumV = sum(input_list)
    n = len(input_list)
    while n>= 1:
        if split(input_list,n):
            return n
        n -= 1


def split(input_list,n):
    # 判断列表能不能被均分成n个小组

    # 如果列表和不能均分成n份，那么一定是false
    if sum(input_list) % n != 0:
        return False

    subSum = sum(input_list) / n

    # 如果均分值小于最大值，那么一定是false，这里默认列表里面不能有负值
    if subSum < max(input_list):
        return False

    # 列表已经倒序排序了，如果是单个元素就等于均分值，那么这个元素就直接剔除
    while len(input_list) > 0 and input_list[0] == subSum:
        input_list.pop(0)
        n -= 1

    buckets = [0]* n

    def backtrack(input, index, buckets,subSum):
        # 如果将所有元素都放到桶里面了，那么就说明可以成功均分
        if index == len(input):
            return True

        select = input[index]

        for i in range(len(buckets)):
            # 原因：如果元素和相等，那么 nums[index] 选择上一个桶和选择当前桶可以得到的结果是一致的
            if i > 0 and buckets[i] == buckets[i-1]:
                continue

            # 将当前球放入桶中
            if select + buckets[i] <= subSum:
                buckets[i] += select
                if backtrack(input,index+1,buckets,subSum):
                    return True
                buckets[i] -= select
        return False

    return backtrack(input_list,0,buckets,subSum)

计算网络信号强度

广度优先遍历，核心是找出广度迭代方式，即遍历上下左右的坐标，以及每次将新赋值的坐标作为下一次遍历的列表

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
def getSignal(arr,target_i,target_j):
    m = len(arr)
    n = len(arr[0])
    # 需要遍历上下左右
    offsets = [(0,1),(0,-1),(-1,0),(0,1)]
    queue = []
    for i  in range(m):
        for j in range(n):
            if arr[i][j] > 0:
                queue.append((i,j))

    while len(queue)>0:
        newQueue = []
        for i,j in queue:
            val = arr[i][j] - 1
            if val == 0:
                break
            for offsetX,offsetY in offsets:
                x = i+offsetX
                y = j+offsetY
                if x>=0 and x< m and y >=0 and y<n:
                    # print(x,y)
                    if arr[x][y] == 0:
                        arr[x][y] = val
                        # 将新赋值的坐标，作为下一次遍历的列表
                        newQueue.append((x,y))
        queue = newQueue
    return arr[target_i][target_j]

最优高铁城市修建方案

最小生成树，在无向联通图中，权重和最小的让所有节点都链接的树就是最小生成树，n个节点，n-1条边，没有环

Prim算法：基于顶点寻找，类似贪心算法，从一个顶点出发，不断寻找对外权重最小的边，如果权重最小的边有多个，那么就任意选择一个，

Kruskal算法：将所有边按照权重排序，从小到大，依次添加，当添加一条边的时候，如果形成了环，那么就抛弃这条边，选下一个，直到选了n-1条边

并查集：

士兵过河

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
def getMinTime(times,t):

    def getMax(t1,t2):
        if t1*10 >= t2:
            return t2
        else:
            return t1*10

    # 总人数
    n = len(times)

    # 排序下
    times.sort()

    # 动态规划数组初始化
    dp = [0] * n
    # 第一个人渡河时间
    dp[0] = times[0]

    # 如果最短的渡河时间的人都大于时间限制，那么没有人可以渡河
    if dp[0] > t:
        return "0 0"

    dp[1] = getMax(times[0],times[1])
    # 如果俩个人一起渡河的时间超过限制时间，那么只能一个人渡河了
    if dp[1] > t:
        return f"1 {dp[0]}"

    for i in range(2,n):
        dp[i] = min(dp[i-1] + times[0]+getMax(times[0],times[i]),
                    dp[i-2]+ times[0]+getMax(times[i-1],times[i]) + times[1]+ getMax(times[0],times[1]))
        if dp[i] > t:
            return f"{i} {dp[i-1]}"

    return f"{n} {dp[n-1]}"