leetcode-weekly/src/main/java/weekly/wk354.java at master · ZLBer/leetcode-weekly · GitHub

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package weekly;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class wk354 {

    //模拟
    public int sumOfSquares(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums.length % (i + 1) == 0) {
                ans += nums[i] * nums[i];
            }
        }
        return ans;
    }


    //排序+滑窗
    public int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);

        int ans = 0;
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            while (left < i && nums[left] + k < nums[i] - k) {
                left++;
            }

            ans = Math.max(i-left+1, ans);
        }
        return ans;
    }


    //枚举
    public int minimumIndex(List<Integer> nums) {
        Map<Integer, Integer> counter = new HashMap<>();
        for (int i = 0; i < nums.size(); i++) {
            counter.put(nums.get(i), counter.getOrDefault(nums.get(i), 0) + 1);
        }
        int max = 0;
        int count = 0;
        for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
            if (entry.getValue() > count) {
                max = entry.getKey();
                count = entry.getValue();
            }
        }
        if (count * 2 <= nums.size()) {
            return -1;
        }

        int left = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) == max) {
                left++;
            }
            if (left * 2 > (i + 1) && (count - left) * 2 > (nums.size() - i - 1)) {
                return i;
            }
        }
        return -1;
    }


    //暴力 注意数据范围
    public int longestValidSubstring(String word, List<String> forbidden) {
        Map<Integer, Set<String>> map = new HashMap<>();
        for (String s : forbidden) {
            int length = s.length();
            if (!map.containsKey(length)) {
                map.put(length, new HashSet<>());
            }
            map.get(length).add(s);
        }
        int n = word.length();

        int ans = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(word.charAt(i));
            for (int j = sb.length() - 1; j >= 0 && (sb.length() - j <= 10); j--) {
                String sub = sb.substring(j, sb.length());
                if (map.getOrDefault(sub.length(), new HashSet<>()).contains(sub)) {
                    sb = new StringBuilder(sub.substring(1, sub.length()));
                    break;
                }
            }
            ans = Math.max(ans, sb.length());
        }
        return ans;
    }
}