LeetCode每日一题

2023-11-05 LeetCode187: 重复的DNA序列

字符串＋去重＋滑动窗口 因为s.substring的时间复杂度为O(n),频繁调用会影响效率，所以采用hashmap

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
public List<String> findRepeatedDnaSequences(String s) {
        HashMap<String, Integer> hp = new HashMap<>();
        List<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        if (s.length() < 10) return result;
        //初始化
        for (int i = 0; i < 9; i++) {
            sb.append(s.charAt(i));
        }
        for (int i = 9; i < s.length(); i++) {
            sb.append(s.charAt(i));
            if (hp.containsKey(sb.toString())) {
                hp.put(sb.toString(), 2);
            } else {
                hp.put(sb.toString(), 1);
            }
            sb.deleteCharAt(0);
        }
        for (Map.Entry<String, Integer> stringIntegerEntry : hp.entrySet()) {
            if (stringIntegerEntry.getValue() == 2){
                result.add(stringIntegerEntry.getKey().toString());
            }
        }
        return result;
    }

2023-11-06 LeetCode318: 最大单词长度乘积

第一次接触位运算。 对于本题目来说，O(n^2)的基础时间复杂度是少不了的，所以最好是可以把单词是否含有公共字母的判断降到O(1)的时间复杂度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxProduct(String[] words) {
        int[] nums = new int[words.length];
        int max = 0;
        for (int k = 0; k < words.length; k++) {
            String word = words[k];
            int bitnum = 0;
            for (int i = 0; i < word.length(); i++) {
                bitnum |= 1 << (word.charAt(i) - 'a');
            }
            nums[k] = bitnum;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int  j = 0; j < i; j++) {
                if ((nums[j] & nums[i]) == 0) max = Math.max(max, words[i].length() * words[j].length());
            }
        }
        return max;
    }

2023-11-07 LeetCode2586: 统计范围内的元音字符串数

一道很直白的简单题: 

1
2
3
4
5
6
7
8
9
10
11
12
13
public int vowelStrings(String[] words, int left, int right) {
       int result = 0;
       for (int i = left; i <= right; i++) {
           String str = words[i];
           if (isVowel(str)) result++;
       }
       return result;
   }
   private boolean isVowel(String str) {
       char start = str.charAt(0), end = str.charAt(str.length() - 1);
       if ((start == 'a' || start == 'e' || start == 'i' || start == 'o' || start == 'u') && (end == 'a' || end == 'e' || end == 'i' || end == 'o' || end == 'u' ))     return true;
        return false;
   }

2023-11-08 LeetCode2609: 最长平衡子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int findTheLongestBalancedSubstring(String s) {
        int[] nums = new int[2];//nums[0]表示连续零的数量 nums[1]表示连续1的数量
        int max  = 0,  i = 0;;
        while (i < s.length() && s.charAt(i) != '0') i++;//去掉前导1
        while (i < s.length()) {
            if(s.charAt(i) != '1') {
                if (i >= 1 && s.charAt(i - 1) == '1') {
                    nums[0] = 0;
                    nums[1] = 0;
                }
                nums[0]++;
               
            }
            if (s.charAt(i) != '0') {
                if (nums[1] < nums[0]) nums[1]++;
                max = Math.max(max, nums[1]);
                
            }
            i++;
        }
        return max * 2;
    }

2023-11-09 LeetCode2258: 逃离火灾

双BFS，考虑到位置问题 所有火灾同时参与BFS: 

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
    private int[][] fire;
    private int[][] people;
    private int[][] move = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    public int maximumMinutes(int[][] grid) {
        fire = new int[grid.length][grid[0].length];
        people = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    fire[i][j] = -1;
                    people[i][j] = -1;
                } else {
                    people[i][j] = Integer.MAX_VALUE;
                }
                if (grid[i][j] == 0) fire[i][j] = Integer.MAX_VALUE;
            }
        }
        people[0][0] = 0;
        bfs(people, List.of(new int[]{0, 0}));
        int  manTime =  people[grid.length - 1][grid[0].length - 1];
        if (manTime == Integer.MAX_VALUE) return -1;
        List<int[]> firePos = new ArrayList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    firePos.add(new int[]{i, j});
                }
            }
        }
        bfs(fire, firePos);
        int  fireTime = fire[grid.length - 1][grid[0].length - 1]; 
        if (fireTime == Integer.MAX_VALUE) return 1000000000;
        int d = fireTime - manTime;
        int  m1 = people[grid.length - 2][grid[0].length - 1], f1 = fire[grid.length - 2][grid[0].length - 1];
        int m2 = people[grid.length - 1][grid[0].length - 2], f2 = fire[grid.length - 1][grid[0].length - 2];
        if (d < 0) return -1;
        if (m1 != Integer.MAX_VALUE && m1 + d < f1 || m2 != Integer.MAX_VALUE && m2 + d < f2) return d;
        return d -1;
    }
    private void bfs(int[][] tmp,List<int[]> q) {
        boolean[][] used = new boolean[tmp.length][tmp[0].length];
        int m = tmp.length, n = tmp[0].length;
        int count = 0;
        Queue<int[]> queue = new LinkedList<>();
        for (int [] num : q) {
            queue.offer(new int[]{num[0], num[1]});
            tmp[num[0]][num[1]] = count; 
            used[num[0]][num[1]] = true;
        }
        count++;
        while(!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                int[] cur = queue.poll();
                size--;
                for (int i = 0; i < 4; i++) {
                int nexty = cur[0] + move[i][0];
                int nextx = cur[1] + move[i][1];
                if (nexty < 0 || nexty >= tmp.length || nextx < 0 || nextx >= tmp[0].length || used[nexty][nextx] || tmp[nexty][nextx] == -1) continue;
                queue.offer(new int[]{nexty, nextx});
                used[nexty][nextx] = true;
                tmp[nexty][nextx] = Math.min(tmp[nexty][nextx], count);
                }
            }
            count++;    
        }
    }
}

2023-11-10 LeetCode2300: 咒语和药水的 成功对数

O(nlogn)的时间复杂度: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] successfulPairs(int[] spells, int[] potions, long success) {
    int[] result = new int[spells.length];
    Arrays.sort(potions);
    for (int i = 0; i < spells.length; i++) {
        long tmp = spells[i];
        int left = 0, right = potions.length - 1;
        int mid; 
        while (left < right) {
            mid = (left + right) / 2;
            if (tmp * potions[mid] >= success) right = mid - 1;
            else if (tmp * potions[mid] < success) left = mid + 1;
        }
        if (tmp * potions[left] >= success) result[i] = potions.length - left;
        else result[i] = potions.length - left - 1;
    }
    return result;
}

2023-11-13 LeetCode307: 区域和检索，数组可修改

首先，对于本题目来说，直接做也能过，但是时间复杂度较高:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int[] num;
   public NumArray(int[] nums) {
       num = new int[nums.length];
       for (int i = 0; i < nums.length; i++) {
           num[i] = nums[i];
       }
   }
   
   public void update(int index, int val) {
       num[index] = val;
   }
   
   public int sumRange(int left, int right) {
       int sum = 0;
       for (int i = left; i <= right; i++) {
           sum += num[i];
       }
       return sum;
   }

所以，对于今天的每日一题，自然有了新的解法。

  • (1)线段树。 线段树 segmentTree是一个二叉树，每个结点保存数组 nums在区间 [s,e]的最小值、最大值或者总和等信息。线段树可以用树也可以用数组（堆式存储）来实现。对于数组实现，假设根结点的下标为 0，如果一个结点在数组的下标为 node，那么它的左子结点下标为 node×2+1，右子结点下标为 node×2+2。

    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
    52
    private int[] segmentTree;
      int n;
      public NumArray(int[] nums) {
          n = nums.length;
          segmentTree = new int[n * 4];
          build(0, 0, n - 1, nums);
      }
      
      public void update(int index, int val) {
           change(index, val, 0, 0, n - 1);
      }
      
      public int sumRange(int left, int right) {
          return range(left, right, 0, 0, n - 1);
      }
      //自底向上开始建树 node节点保存nums[s]到nums[e]的总和
      private void build (int node, int s, int e, int[] nums) {
          if (s == e) {
              segmentTree[node] = nums[s];
              return;
          }
          int m = (s + e) / 2;
          build(node * 2  + 1, s, m, nums);
          build(node * 2 + 2, m + 1, e, nums);
          segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
      }
      private void change(int index, int val, int node, int s, int e) {
          if (s == e) {
              segmentTree[node] = val;
              return;
          }
          int m = (s + e) / 2;
          if (index <= m) {
              change(index, val, node * 2 + 1, s, m);
          } else {
              change(index, val, node * 2 + 2, m + 1, e);
          }
          segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
      }
      private int range(int left, int right, int node, int s, int e) {
          if (left == s && right == e) {
              return segmentTree[node];
          }
          int m = (s + e) / 2;
          if (right <= m) {
              return range(left, right, node * 2 + 1, s, m);
          } else if (left > m) {
              return range(left, right, node * 2 + 2, m + 1, e);
          } else{
              return range(left, m, node * 2 + 1, s, m) + range(m + 1, right, node * 2 + 2, m + 1, e);
          }
      }

  • (2) 树状数组。树状数组是一种可以动态维护序列前缀和的数据结构（序列下标从1开始），它的功能是：
    (1)单点修改 add(index, val) 把序列第index个数增加val (2) 区间查询 prefixSum(index)：查询前 index 个元素的前缀和

    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
    private int[] tree;
     private int[] nums;

     public NumArray(int[] nums) {
         tree = new int[nums.length + 1];
         this.nums = nums;
         for (int i = 0; i < nums.length; i++) {
             add(i + 1, nums[i]);
         }
     }
     
     public void update(int index, int val) {
         add(index + 1, val - nums[index]);
         nums[index] = val;
     }
     
     public int sumRange(int left, int right) {
         return prefixSum(right + 1) - prefixSum(left);
     }
     private int lowBit(int x) {
         return x & -x;
     }
     private void add(int index, int val) {
         while (index < tree.length) {
             tree[index] += val;
             index += lowBit(index);
         }
     }
     private int prefixSum(int index) {
         int sum = 0;
         while (index > 0) {
             sum += tree[index];
             index -= lowBit(index);
         }
         return sum;
     }

2023-11-14 LeetCode1334: 阈值距离内邻居最少的城市

图上的动态规划，做了两个多小时: 

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
class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] distance = new int[n][n];//表征从i到j的最短距离
        int[] result = new int[n];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                distance[i][j] = Integer.MAX_VALUE;//表征不可到达
            }
        }
        //初始化
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];
            int tmpDistance = edges[i][2];
            distance[from][to] = tmpDistance;
            distance[to][from] = distance[from][to];
        }
        for (int i = n - 2; i >= 0; i--) {
           for (int j = 0; j < n; j++) {
               for (int k = 0; k < n; k++) {
                   if (distance[i][k] != Integer.MAX_VALUE && distance[k][j] != Integer.MAX_VALUE)distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
                   distance[j][i] = distance[i][j];
               }
           } 
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (distance[i][j] <= distanceThreshold) result[i]++;
            }
            if (result[i] < min) min = result[i];
        }
        for (int i = n - 1; i >= 0; i--) {
            if (result[i] == min) return i;
        }
        return 1;
    }
}

2023-11-15 LeetCode2656: K个最大元素的和

1
2
3
4
5
6
7
8
9
10
11
12
ublic int maximizeSum(int[] nums, int k) {
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) max = nums[i];
        }
        int result = max;
        while (k > 1) {
            result += ++max;
            k--;
        }
        return result;
    }

2023-11-15 LeetCode2760: 最长奇偶子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int longestAlternatingSubarray(int[] nums, int threshold) {
       int res = 0, dp = 0;
       for (int l = nums.length - 1; l >= 0; l--) {
           if (nums[l] > threshold) {
               dp = 0;
           } else if (l == nums.length - 1 || nums[l] % 2 != nums[l + 1] % 2) {
               dp++;
           } else {
               dp = 1;
           }
           if (nums[l] % 2 == 0) {
               res = Math.max(res, dp);
           }
       }
       return res;
   }
Leetcode
#代码练习日记
LeetCode每日一题
http://example.com/2023/11/05/LeetCode每日一题/
作者
John Doe
发布于
2023年11月5日
许可协议