algorithm/leetcode/ValidTriangleNumber.java at master · skyczhao/algorithm · 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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
package leetcode;

import java.util.*;

/**
 * ValidTriangleNumber
 * https://leetcode-cn.com/problems/valid-triangle-number/
 * 611. 有效三角形的个数
 * https://leetcode-cn.com/problems/valid-triangle-number/solution/zhi-jie-mei-ju-hui-chao-shi-kao-lu-er-fe-r57t/
 *
 * @author tobin
 * @since 2021-08-04
 */
public class ValidTriangleNumber {
    public static void main(String[] args) {
        ValidTriangleNumber sol = new ValidTriangleNumber();
        System.out.println(sol.triangleNumber(new int[]{0, 0, 0}));
        System.out.println(sol.triangleNumber(new int[]{2, 2, 3, 4}));
        System.out.println(sol.triangleNumber(new int[]{4, 2, 3, 2}));
        System.out.println(sol.triangleNumber(new int[]{
                375, 635, 727, 611, 910, 53, 681, 910, 675, 130, 590, 663, 513, 123, 140, 492, 225, 482, 383, 31, 275, 658,
                948, 710, 275, 733, 27, 143, 322, 921, 939, 669, 48, 664, 134, 706, 125, 18, 229, 980, 632, 102, 310, 698, 954,
                572, 404, 325, 567, 647, 428, 670, 220, 110, 790, 171, 141, 864, 418, 29, 546, 310, 930, 163, 189, 646, 667,
                798, 807, 918, 283, 265, 570, 636, 82, 353, 130, 577, 659, 114, 646, 360, 517, 470, 549, 116, 212, 951, 580,
                968, 276, 597, 646, 856, 774, 619, 853, 782, 718, 861, 601, 710, 879, 804, 507, 941, 657, 127, 957, 543, 105,
                255, 632, 132, 152, 593, 793, 770, 478, 706, 266, 706, 194, 938, 132, 114, 275, 27, 17, 812, 540, 742, 60, 741,
                86, 327, 704, 55, 773, 30, 197, 706, 95, 775, 568, 447, 495, 683, 472, 497, 30, 800, 265, 822, 901, 426, 399,
                503, 350, 500, 162, 149, 31, 297, 643, 233, 443, 363, 277, 699, 545, 588, 222, 947, 227, 279, 946, 365, 934, 479, 732, 729, 232, 643, 244, 58, 695, 873, 573, 372, 201, 381, 498, 4, 80, 506, 830, 98, 177, 667, 453, 254, 8, 229, 902, 92, 713, 53, 269, 122, 222, 38, 831, 19, 834, 648, 766, 270, 713, 398, 563, 494, 480, 338, 334, 493, 293, 736, 884, 100, 345, 946, 551, 951, 886, 749, 584, 18, 699, 764, 868, 440, 731, 260, 377, 869, 135, 464, 634, 805, 996, 328, 529, 924, 374, 736, 139, 783, 155, 4, 626, 355, 671, 912, 521, 430, 387, 471, 845, 982, 454, 246, 721, 420, 595, 890, 146, 879, 245, 292, 112, 874, 302, 941, 758, 538, 530, 141, 763, 972, 133, 844, 101, 397, 219, 428, 396, 683, 190, 551, 974, 848, 336, 279, 815, 344, 520, 81, 134, 660, 951, 856, 771, 311, 353, 251, 53, 810, 600, 840, 598, 549, 95, 87, 127, 132, 240, 354, 678, 384, 942, 736, 85, 242, 631, 79, 304, 831, 460, 584, 489, 585, 38, 421, 945, 901, 506, 421, 72, 214, 345, 707, 348, 138, 298, 681, 432, 199, 265, 96, 123, 771, 204, 608, 215, 129, 904, 823, 656, 773, 302, 617, 445, 546, 477, 355, 607, 4, 297, 368, 356, 470, 823, 767, 18, 444, 41, 384, 197, 369, 468, 470, 555, 95, 907, 159, 140, 503, 628, 975, 801, 453, 688, 799, 644, 689, 7, 561, 367, 665, 302, 746, 223, 275, 977, 274, 917, 352, 961, 733, 191, 341, 551, 929, 13, 432, 304, 270, 127, 138, 203, 821, 618, 714, 239, 77, 661, 585, 821, 585, 179, 981, 287, 507, 933, 401, 845, 113, 836, 193, 495, 580, 711, 547, 70, 963, 892, 4, 328, 672, 123, 609, 93, 84, 529, 626, 404, 102, 700, 304, 911, 524, 499, 533, 523, 362, 952, 987, 36, 137, 471, 202, 786, 657, 846, 143, 992, 564, 156, 375, 589, 820, 38, 804, 453, 111, 23, 218, 188, 354, 553, 677, 574, 725, 712, 999, 16, 634, 857, 258, 446, 607, 819, 370, 319, 813, 90, 98, 644, 805, 80, 146, 599, 680, 755, 312, 382, 714, 886, 931, 47, 666, 273, 933, 258, 541, 530, 8, 375, 893, 950, 251, 412, 52, 88, 108, 477, 230, 483, 247, 980, 389, 292, 844, 170, 48, 357, 484, 681, 127, 189, 181, 560, 693, 928, 530, 899, 822, 59, 744, 724, 255, 764, 431, 459, 895, 450, 768, 547, 443, 378, 684, 791, 582, 497, 251, 894, 469, 144, 967, 600, 46, 782, 665, 144, 978, 542, 982, 397, 414, 425, 814, 900, 416, 988, 25, 10, 537, 628, 106, 32, 992, 569, 169, 118, 385, 997, 97, 678, 56, 763, 709, 669, 951, 664, 198, 407, 379, 13, 243, 976, 951, 887, 239, 894, 448, 870, 194, 780, 757, 615, 783, 424, 267, 705, 382, 89, 913, 212, 246, 843, 12, 899, 771, 496, 687, 71, 828, 189, 157, 43, 115, 533, 974, 631, 146, 122, 611, 615, 124, 381, 953, 487, 416, 862, 979, 502, 32, 679, 890, 431, 325, 312, 887, 543, 537, 824, 644, 191, 324, 530, 726, 954, 58, 728, 50, 313, 95, 15, 468, 157, 57, 573, 560, 7, 921, 732, 809, 918, 132, 800, 366, 356, 27, 744, 553, 885, 586, 624, 869, 262, 115, 332, 617, 719, 369, 534, 348, 954, 546, 303, 427, 366, 953, 394, 294, 403, 129, 666, 322, 728, 744, 138, 714, 49, 282, 155, 944, 577, 46, 266, 131, 26, 785, 310, 208, 363, 322, 915, 751, 701, 142, 178, 916, 648, 137, 482, 39, 351, 252, 50, 362, 29, 853, 895, 118, 321, 381, 578, 970, 888, 311, 335, 935, 234, 680, 867, 123, 727, 151, 91, 993, 68, 852, 831, 864, 451, 119, 695, 795, 271, 459, 846, 50, 437, 398, 276, 893, 281, 346, 808, 227, 450, 397, 251, 866, 66, 943, 587, 70, 486, 885, 475, 606, 886, 285, 26, 398, 835, 21, 497, 375, 195, 200, 284, 675, 946, 442, 465, 507, 188, 389, 830, 490, 365, 766, 683, 635, 963, 861, 967, 317, 315, 370, 485, 659, 203, 565, 715, 354, 649, 931, 388, 33, 635, 946, 18, 961, 474, 251, 746, 309, 136, 86, 705, 945, 416, 574, 568, 867, 834, 757, 961, 386, 999, 718, 546, 219, 227, 81, 505, 177, 70, 495, 571, 490, 325, 298, 79, 605, 253, 699, 803, 722, 709, 212, 692, 929, 180, 542, 649, 595, 168, 505, 997, 476, 688, 21, 610, 844, 343, 22, 362, 268, 168, 798, 775, 912, 867, 204, 561, 237, 129, 782, 948, 731, 613, 755, 83, 23, 139, 724, 72, 978, 271, 171, 732, 469, 490, 421, 941, 981, 632, 515, 394, 203, 38, 545, 898, 105, 235, 781, 552, 543, 662, 162, 603, 337, 301, 397, 735, 457, 581, 828, 40, 645, 90, 683, 301, 999, 999, 869, 734, 257, 535, 306, 488, 912, 500, 963, 474, 817, 381, 505, 135, 66, 197, 907, 454}));
    }

    public int triangleNumber(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        Collections.sort(list);

        int size = 0;
        for (int i = 0; i < nums.length; i++) {
            int edge = 0;
            for (int j = i + 1; j < nums.length; j++) {
                int tmp = list.get(i) + list.get(j);

                if (edge <= j) {
                    edge = j + 1;
                    if (edge >= nums.length || tmp <= list.get(edge)) {
                        continue;
                    }
                }
                // edge的位置可以随着j逐步递进
                while (edge + 1 < nums.length) {
                    if (tmp > list.get(edge + 1)) {
                        edge++;
                    } else {
                        break;
                    }
                }

                size += (edge - j);
            }
        }
        return size;
    }

    public int triangleNumber3(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            if (num == 0) { // bug
                continue;
            }
            int c = 1;
            if (counts.containsKey(num)) {
                c = counts.get(num) + 1;
            }
            counts.put(num, c);
        }

        List<Integer> uniques = new ArrayList<>();
        uniques.addAll(counts.keySet());
        Collections.sort(uniques);
        int length = uniques.size();

        int total = 0;
        // 1 v 1 v 1
        for (int i = 0; i < length; i++) {
            int v_i = uniques.get(i);
            for (int j = i + 1; j < length; j++) {
                int v_j = uniques.get(j);
                int tmp = v_i + v_j;
                for (int k = j + 1; k < length; k++) {
                    int v_k = uniques.get(k);
                    if (tmp > v_k) {
                        total += (counts.get(v_i) * counts.get(v_j) * counts.get(v_k));
                    } else {
                        break;
                    }
                }
            }
        }
        // 2 v 1
        for (int i = 0; i < length; i++) {
            int v_i = uniques.get(i);
            int c_i = counts.get(v_i);
            if (c_i > 1) {
                int tmp = v_i + v_i;
                for (int j = 0; j < length; j++) {
                    if (i == j) { // bug
                        continue;
                    }
                    int v_j = uniques.get(j);
                    if (tmp > v_j) {
                        total += (c_i * (c_i - 1) / 2 * counts.get(v_j));
                    } else {
                        break;
                    }
                }
            }
        }
        // 3
        for (int i = 0; i < length; i++) {
            int v_i = uniques.get(i);
            int c_i = counts.get(v_i);
            if (v_i == 0) { // bug
                continue;
            }

            if (c_i > 2) {
                total += (c_i * (c_i - 1) * (c_i - 2) / 6);
            }
        }

        return total;
    }

    public int triangleNumber2(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        Collections.sort(list);

        int size = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int tmp = list.get(i) + list.get(j);
                for (int k = j + 1; k < nums.length; k++) {
                    if (tmp > list.get(k)) {
                        size++;
                    } else {
                        break;
                    }
                }
            }
        }
        return size;
    }
}