Leetcode 2859 计算 K 置位下标对应元素的和
2859.计算 K 置位下标对应元素的和
你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
请你用整数形式返回 nums 中的特定元素之 和 ，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。
整数的二进制表示中的 1 就是这个整数的 置位 。
例如，21 的二进制表示为 10101 ，其中有 3 个置位。
示例 1:
输入: nums = [5,10,1,5,2], k = 1
输出: 13
解释: 下标的二进制表示是：
0 = 0002
1 = 0012
2 = 0102
3 = 0112
4 = 1002
下标 1、2 和 4 在其二进制表示中都存在 k = 1 个置位。
因此，答案为 nums[1] + nums[2] + nums[4] = 13 。
示例 2:
输入: nums = [4,3,2,1], k = 2
输出: 1
解释: 下标的二进制表示是：
0 = 002
1 = 012
2 = 102
3 = 112
只有下标 3 的二进制表示中存在 k = 2 个置位。
因此，答案为 nums[3] = 1 。
提示：
1 <= nums.length <= 10001 <= nums[i] <= 10^50 <= k <= 10
Related Topics
- 位运算
- 数组
题目链接: link
解答
本题的难度是 Easy.
因为数组最大长度为1000, 因此我们可以直接看1000以内的所有数的二进制数各有多少个1, 然后存在表里, 直接打表玩.
代码如下:
class Solution {
public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
if(k == 10) {
return 0;
}
Map<Integer, int[]> map = new HashMap<>();
map.put(0, new int[]{0});
map.put(1, new int[]{1, 2, 4, 8, 16, 32, 64, 128, 256, 512});
map.put(2, new int[]{3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129, 130, 132, 136, 144, 160, 192, 257, 258, 260, 264, 272, 288, 320, 384, 513, 514, 516, 520, 528, 544, 576, 640, 768});
map.put(3, new int[]{7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 131, 133, 134, 137, 138, 140, 145, 146, 148, 152, 161, 162, 164, 168, 176, 193, 194, 196, 200, 208, 224, 259, 261, 262, 265, 266, 268, 273, 274, 276, 280, 289, 290, 292, 296, 304, 321, 322, 324, 328, 336, 352, 385, 386, 388, 392, 400, 416, 448, 515, 517, 518, 521, 522, 524, 529, 530, 532, 536, 545, 546, 548, 552, 560, 577, 578, 580, 584, 592, 608, 641, 642, 644, 648, 656, 672, 704, 769, 770, 772, 776, 784, 800, 832, 896});
map.put(4, new int[]{15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198, 201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240, 263, 267, 269, 270, 275, 277, 278, 281, 282, 284, 291, 293, 294, 297, 298, 300, 305, 306, 308, 312, 323, 325, 326, 329, 330, 332, 337, 338, 340, 344, 353, 354, 356, 360, 368, 387, 389, 390, 393, 394, 396, 401, 402, 404, 408, 417, 418, 420, 424, 432, 449, 450, 452, 456, 464, 480, 519, 523, 525, 526, 531, 533, 534, 537, 538, 540, 547, 549, 550, 553, 554, 556, 561, 562, 564, 568, 579, 581, 582, 585, 586, 588, 593, 594, 596, 600, 609, 610, 612, 616, 624, 643, 645, 646, 649, 650, 652, 657, 658, 660, 664, 673, 674, 676, 680, 688, 705, 706, 708, 712, 720, 736, 771, 773, 774, 777, 778, 780, 785, 786, 788, 792, 801, 802, 804, 808, 816, 833, 834, 836, 840, 848, 864, 897, 898, 900, 904, 912, 928, 960});
map.put(5, new int[]{31, 47, 55, 59, 61, 62, 79, 87, 91, 93, 94, 103, 107, 109, 110, 115, 117, 118, 121, 122, 124, 143, 151, 155, 157, 158, 167, 171, 173, 174, 179, 181, 182, 185, 186, 188, 199, 203, 205, 206, 211, 213, 214, 217, 218, 220, 227, 229, 230, 233, 234, 236, 241, 242, 244, 248, 271, 279, 283, 285, 286, 295, 299, 301, 302, 307, 309, 310, 313, 314, 316, 327, 331, 333, 334, 339, 341, 342, 345, 346, 348, 355, 357, 358, 361, 362, 364, 369, 370, 372, 376, 391, 395, 397, 398, 403, 405, 406, 409, 410, 412, 419, 421, 422, 425, 426, 428, 433, 434, 436, 440, 451, 453, 454, 457, 458, 460, 465, 466, 468, 472, 481, 482, 484, 488, 496, 527, 535, 539, 541, 542, 551, 555, 557, 558, 563, 565, 566, 569, 570, 572, 583, 587, 589, 590, 595, 597, 598, 601, 602, 604, 611, 613, 614, 617, 618, 620, 625, 626, 628, 632, 647, 651, 653, 654, 659, 661, 662, 665, 666, 668, 675, 677, 678, 681, 682, 684, 689, 690, 692, 696, 707, 709, 710, 713, 714, 716, 721, 722, 724, 728, 737, 738, 740, 744, 752, 775, 779, 781, 782, 787, 789, 790, 793, 794, 796, 803, 805, 806, 809, 810, 812, 817, 818, 820, 824, 835, 837, 838, 841, 842, 844, 849, 850, 852, 856, 865, 866, 868, 872, 880, 899, 901, 902, 905, 906, 908, 913, 914, 916, 920, 929, 930, 932, 936, 944, 961, 962, 964, 968, 976, 992});
map.put(6, new int[]{63, 95, 111, 119, 123, 125, 126, 159, 175, 183, 187, 189, 190, 207, 215, 219, 221, 222, 231, 235, 237, 238, 243, 245, 246, 249, 250, 252, 287, 303, 311, 315, 317, 318, 335, 343, 347, 349, 350, 359, 363, 365, 366, 371, 373, 374, 377, 378, 380, 399, 407, 411, 413, 414, 423, 427, 429, 430, 435, 437, 438, 441, 442, 444, 455, 459, 461, 462, 467, 469, 470, 473, 474, 476, 483, 485, 486, 489, 490, 492, 497, 498, 500, 504, 543, 559, 567, 571, 573, 574, 591, 599, 603, 605, 606, 615, 619, 621, 622, 627, 629, 630, 633, 634, 636, 655, 663, 667, 669, 670, 679, 683, 685, 686, 691, 693, 694, 697, 698, 700, 711, 715, 717, 718, 723, 725, 726, 729, 730, 732, 739, 741, 742, 745, 746, 748, 753, 754, 756, 760, 783, 791, 795, 797, 798, 807, 811, 813, 814, 819, 821, 822, 825, 826, 828, 839, 843, 845, 846, 851, 853, 854, 857, 858, 860, 867, 869, 870, 873, 874, 876, 881, 882, 884, 888, 903, 907, 909, 910, 915, 917, 918, 921, 922, 924, 931, 933, 934, 937, 938, 940, 945, 946, 948, 952, 963, 965, 966, 969, 970, 972, 977, 978, 980, 984, 993, 994, 996});
map.put(7, new int[]{127, 191, 223, 239, 247, 251, 253, 254, 319, 351, 367, 375, 379, 381, 382, 415, 431, 439, 443, 445, 446, 463, 471, 475, 477, 478, 487, 491, 493, 494, 499, 501, 502, 505, 506, 508, 575, 607, 623, 631, 635, 637, 638, 671, 687, 695, 699, 701, 702, 719, 727, 731, 733, 734, 743, 747, 749, 750, 755, 757, 758, 761, 762, 764, 799, 815, 823, 827, 829, 830, 847, 855, 859, 861, 862, 871, 875, 877, 878, 883, 885, 886, 889, 890, 892, 911, 919, 923, 925, 926, 935, 939, 941, 942, 947, 949, 950, 953, 954, 956, 967, 971, 973, 974, 979, 981, 982, 985, 986, 988, 995, 997, 998});
map.put(8, new int[]{255, 383, 447, 479, 495, 503, 507, 509, 510, 639, 703, 735, 751, 759, 763, 765, 766, 831, 863, 879, 887, 891, 893, 894, 927, 943, 951, 955, 957, 958, 975, 983, 987, 989, 990, 999});
map.put(9, new int[]{511, 767, 895, 959, 991});
int sum = 0;
for (int i : map.get(k)) {
if (i < nums.size()) {
sum += nums.get(i);
} else {
break;
}
}
return sum;
}
}
狠狠打表, 时间 3ms, 击败 27.24%. 实际上每一次调用, k 都是确定的, 因此我们不需要每次都初始化10种数组, 可以很简单地优化:
class Solution {
public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
if(k == 10) {
return 0;
}
Map<Integer, int[]> map = new HashMap<>();
if (k == 0) {
map.put(0, new int[]{0});
} else if (k == 1) {
map.put(1, new int[]{1, 2, 4, 8, 16, 32, 64, 128, 256, 512});
} else if (k == 2) {
map.put(2, new int[]{3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129, 130, 132, 136, 144, 160, 192, 257, 258, 260, 264, 272, 288, 320, 384, 513, 514, 516, 520, 528, 544, 576, 640, 768});
} else if (k == 3) {
map.put(3, new int[]{7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 131, 133, 134, 137, 138, 140, 145, 146, 148, 152, 161, 162, 164, 168, 176, 193, 194, 196, 200, 208, 224, 259, 261, 262, 265, 266, 268, 273, 274, 276, 280, 289, 290, 292, 296, 304, 321, 322, 324, 328, 336, 352, 385, 386, 388, 392, 400, 416, 448, 515, 517, 518, 521, 522, 524, 529, 530, 532, 536, 545, 546, 548, 552, 560, 577, 578, 580, 584, 592, 608, 641, 642, 644, 648, 656, 672, 704, 769, 770, 772, 776, 784, 800, 832, 896});
} else if (k == 4) {
map.put(4, new int[]{15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198, 201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240, 263, 267, 269, 270, 275, 277, 278, 281, 282, 284, 291, 293, 294, 297, 298, 300, 305, 306, 308, 312, 323, 325, 326, 329, 330, 332, 337, 338, 340, 344, 353, 354, 356, 360, 368, 387, 389, 390, 393, 394, 396, 401, 402, 404, 408, 417, 418, 420, 424, 432, 449, 450, 452, 456, 464, 480, 519, 523, 525, 526, 531, 533, 534, 537, 538, 540, 547, 549, 550, 553, 554, 556, 561, 562, 564, 568, 579, 581, 582, 585, 586, 588, 593, 594, 596, 600, 609, 610, 612, 616, 624, 643, 645, 646, 649, 650, 652, 657, 658, 660, 664, 673, 674, 676, 680, 688, 705, 706, 708, 712, 720, 736, 771, 773, 774, 777, 778, 780, 785, 786, 788, 792, 801, 802, 804, 808, 816, 833, 834, 836, 840, 848, 864, 897, 898, 900, 904, 912, 928, 960});
} else if (k == 5) {
map.put(5, new int[]{31, 47, 55, 59, 61, 62, 79, 87, 91, 93, 94, 103, 107, 109, 110, 115, 117, 118, 121, 122, 124, 143, 151, 155, 157, 158, 167, 171, 173, 174, 179, 181, 182, 185, 186, 188, 199, 203, 205, 206, 211, 213, 214, 217, 218, 220, 227, 229, 230, 233, 234, 236, 241, 242, 244, 248, 271, 279, 283, 285, 286, 295, 299, 301, 302, 307, 309, 310, 313, 314, 316, 327, 331, 333, 334, 339, 341, 342, 345, 346, 348, 355, 357, 358, 361, 362, 364, 369, 370, 372, 376, 391, 395, 397, 398, 403, 405, 406, 409, 410, 412, 419, 421, 422, 425, 426, 428, 433, 434, 436, 440, 451, 453, 454, 457, 458, 460, 465, 466, 468, 472, 481, 482, 484, 488, 496, 527, 535, 539, 541, 542, 551, 555, 557, 558, 563, 565, 566, 569, 570, 572, 583, 587, 589, 590, 595, 597, 598, 601, 602, 604, 611, 613, 614, 617, 618, 620, 625, 626, 628, 632, 647, 651, 653, 654, 659, 661, 662, 665, 666, 668, 675, 677, 678, 681, 682, 684, 689, 690, 692, 696, 707, 709, 710, 713, 714, 716, 721, 722, 724, 728, 737, 738, 740, 744, 752, 775, 779, 781, 782, 787, 789, 790, 793, 794, 796, 803, 805, 806, 809, 810, 812, 817, 818, 820, 824, 835, 837, 838, 841, 842, 844, 849, 850, 852, 856, 865, 866, 868, 872, 880, 899, 901, 902, 905, 906, 908, 913, 914, 916, 920, 929, 930, 932, 936, 944, 961, 962, 964, 968, 976, 992});
} else if (k == 6) {
map.put(6, new int[]{63, 95, 111, 119, 123, 125, 126, 159, 175, 183, 187, 189, 190, 207, 215, 219, 221, 222, 231, 235, 237, 238, 243, 245, 246, 249, 250, 252, 287, 303, 311, 315, 317, 318, 335, 343, 347, 349, 350, 359, 363, 365, 366, 371, 373, 374, 377, 378, 380, 399, 407, 411, 413, 414, 423, 427, 429, 430, 435, 437, 438, 441, 442, 444, 455, 459, 461, 462, 467, 469, 470, 473, 474, 476, 483, 485, 486, 489, 490, 492, 497, 498, 500, 504, 543, 559, 567, 571, 573, 574, 591, 599, 603, 605, 606, 615, 619, 621, 622, 627, 629, 630, 633, 634, 636, 655, 663, 667, 669, 670, 679, 683, 685, 686, 691, 693, 694, 697, 698, 700, 711, 715, 717, 718, 723, 725, 726, 729, 730, 732, 739, 741, 742, 745, 746, 748, 753, 754, 756, 760, 783, 791, 795, 797, 798, 807, 811, 813, 814, 819, 821, 822, 825, 826, 828, 839, 843, 845, 846, 851, 853, 854, 857, 858, 860, 867, 869, 870, 873, 874, 876, 881, 882, 884, 888, 903, 907, 909, 910, 915, 917, 918, 921, 922, 924, 931, 933, 934, 937, 938, 940, 945, 946, 948, 952, 963, 965, 966, 969, 970, 972, 977, 978, 980, 984, 993, 994, 996});
} else if (k == 7) {
map.put(7, new int[]{127, 191, 223, 239, 247, 251, 253, 254, 319, 351, 367, 375, 379, 381, 382, 415, 431, 439, 443, 445, 446, 463, 471, 475, 477, 478, 487, 491, 493, 494, 499, 501, 502, 505, 506, 508, 575, 607, 623, 631, 635, 637, 638, 671, 687, 695, 699, 701, 702, 719, 727, 731, 733, 734, 743, 747, 749, 750, 755, 757, 758, 761, 762, 764, 799, 815, 823, 827, 829, 830, 847, 855, 859, 861, 862, 871, 875, 877, 878, 883, 885, 886, 889, 890, 892, 911, 919, 923, 925, 926, 935, 939, 941, 942, 947, 949, 950, 953, 954, 956, 967, 971, 973, 974, 979, 981, 982, 985, 986, 988, 995, 997, 998});
} else if (k == 8) {
map.put(8, new int[]{255, 383, 447, 479, 495, 503, 507, 509, 510, 639, 703, 735, 751, 759, 763, 765, 766, 831, 863, 879, 887, 891, 893, 894, 927, 943, 951, 955, 957, 958, 975, 983, 987, 989, 990, 999});
} else{
map.put(9, new int[]{511, 767, 895, 959, 991});
}
int sum = 0;
for (int i : map.get(k)) {
if (i < nums.size()) {
sum += nums.get(i);
} else {
break;
}
}
return sum;
}
}
时间 2ms, 45.53%, 然后发现 HashMap 也根本不用创建, 直接用数组就好了. 去掉了 HashMap 初始化和 put 的时间, 再优化:
class Solution {
public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
if(k == 10) {
return 0;
}
int[] table;
if (k == 0) {
table = new int[]{0};
} else if (k == 1) {
table = new int[]{1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
} else if (k == 2) {
table = new int[]{3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 65, 66, 68, 72, 80, 96, 129, 130, 132, 136, 144, 160, 192, 257, 258, 260, 264, 272, 288, 320, 384, 513, 514, 516, 520, 528, 544, 576, 640, 768};
} else if (k == 3) {
table = new int[]{7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 67, 69, 70, 73, 74, 76, 81, 82, 84, 88, 97, 98, 100, 104, 112, 131, 133, 134, 137, 138, 140, 145, 146, 148, 152, 161, 162, 164, 168, 176, 193, 194, 196, 200, 208, 224, 259, 261, 262, 265, 266, 268, 273, 274, 276, 280, 289, 290, 292, 296, 304, 321, 322, 324, 328, 336, 352, 385, 386, 388, 392, 400, 416, 448, 515, 517, 518, 521, 522, 524, 529, 530, 532, 536, 545, 546, 548, 552, 560, 577, 578, 580, 584, 592, 608, 641, 642, 644, 648, 656, 672, 704, 769, 770, 772, 776, 784, 800, 832, 896};
} else if (k == 4) {
table = new int[]{15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 71, 75, 77, 78, 83, 85, 86, 89, 90, 92, 99, 101, 102, 105, 106, 108, 113, 114, 116, 120, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198, 201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240, 263, 267, 269, 270, 275, 277, 278, 281, 282, 284, 291, 293, 294, 297, 298, 300, 305, 306, 308, 312, 323, 325, 326, 329, 330, 332, 337, 338, 340, 344, 353, 354, 356, 360, 368, 387, 389, 390, 393, 394, 396, 401, 402, 404, 408, 417, 418, 420, 424, 432, 449, 450, 452, 456, 464, 480, 519, 523, 525, 526, 531, 533, 534, 537, 538, 540, 547, 549, 550, 553, 554, 556, 561, 562, 564, 568, 579, 581, 582, 585, 586, 588, 593, 594, 596, 600, 609, 610, 612, 616, 624, 643, 645, 646, 649, 650, 652, 657, 658, 660, 664, 673, 674, 676, 680, 688, 705, 706, 708, 712, 720, 736, 771, 773, 774, 777, 778, 780, 785, 786, 788, 792, 801, 802, 804, 808, 816, 833, 834, 836, 840, 848, 864, 897, 898, 900, 904, 912, 928, 960};
} else if (k == 5) {
table = new int[]{31, 47, 55, 59, 61, 62, 79, 87, 91, 93, 94, 103, 107, 109, 110, 115, 117, 118, 121, 122, 124, 143, 151, 155, 157, 158, 167, 171, 173, 174, 179, 181, 182, 185, 186, 188, 199, 203, 205, 206, 211, 213, 214, 217, 218, 220, 227, 229, 230, 233, 234, 236, 241, 242, 244, 248, 271, 279, 283, 285, 286, 295, 299, 301, 302, 307, 309, 310, 313, 314, 316, 327, 331, 333, 334, 339, 341, 342, 345, 346, 348, 355, 357, 358, 361, 362, 364, 369, 370, 372, 376, 391, 395, 397, 398, 403, 405, 406, 409, 410, 412, 419, 421, 422, 425, 426, 428, 433, 434, 436, 440, 451, 453, 454, 457, 458, 460, 465, 466, 468, 472, 481, 482, 484, 488, 496, 527, 535, 539, 541, 542, 551, 555, 557, 558, 563, 565, 566, 569, 570, 572, 583, 587, 589, 590, 595, 597, 598, 601, 602, 604, 611, 613, 614, 617, 618, 620, 625, 626, 628, 632, 647, 651, 653, 654, 659, 661, 662, 665, 666, 668, 675, 677, 678, 681, 682, 684, 689, 690, 692, 696, 707, 709, 710, 713, 714, 716, 721, 722, 724, 728, 737, 738, 740, 744, 752, 775, 779, 781, 782, 787, 789, 790, 793, 794, 796, 803, 805, 806, 809, 810, 812, 817, 818, 820, 824, 835, 837, 838, 841, 842, 844, 849, 850, 852, 856, 865, 866, 868, 872, 880, 899, 901, 902, 905, 906, 908, 913, 914, 916, 920, 929, 930, 932, 936, 944, 961, 962, 964, 968, 976, 992};
} else if (k == 6) {
table = new int[]{63, 95, 111, 119, 123, 125, 126, 159, 175, 183, 187, 189, 190, 207, 215, 219, 221, 222, 231, 235, 237, 238, 243, 245, 246, 249, 250, 252, 287, 303, 311, 315, 317, 318, 335, 343, 347, 349, 350, 359, 363, 365, 366, 371, 373, 374, 377, 378, 380, 399, 407, 411, 413, 414, 423, 427, 429, 430, 435, 437, 438, 441, 442, 444, 455, 459, 461, 462, 467, 469, 470, 473, 474, 476, 483, 485, 486, 489, 490, 492, 497, 498, 500, 504, 543, 559, 567, 571, 573, 574, 591, 599, 603, 605, 606, 615, 619, 621, 622, 627, 629, 630, 633, 634, 636, 655, 663, 667, 669, 670, 679, 683, 685, 686, 691, 693, 694, 697, 698, 700, 711, 715, 717, 718, 723, 725, 726, 729, 730, 732, 739, 741, 742, 745, 746, 748, 753, 754, 756, 760, 783, 791, 795, 797, 798, 807, 811, 813, 814, 819, 821, 822, 825, 826, 828, 839, 843, 845, 846, 851, 853, 854, 857, 858, 860, 867, 869, 870, 873, 874, 876, 881, 882, 884, 888, 903, 907, 909, 910, 915, 917, 918, 921, 922, 924, 931, 933, 934, 937, 938, 940, 945, 946, 948, 952, 963, 965, 966, 969, 970, 972, 977, 978, 980, 984, 993, 994, 996};
} else if (k == 7) {
table = new int[]{127, 191, 223, 239, 247, 251, 253, 254, 319, 351, 367, 375, 379, 381, 382, 415, 431, 439, 443, 445, 446, 463, 471, 475, 477, 478, 487, 491, 493, 494, 499, 501, 502, 505, 506, 508, 575, 607, 623, 631, 635, 637, 638, 671, 687, 695, 699, 701, 702, 719, 727, 731, 733, 734, 743, 747, 749, 750, 755, 757, 758, 761, 762, 764, 799, 815, 823, 827, 829, 830, 847, 855, 859, 861, 862, 871, 875, 877, 878, 883, 885, 886, 889, 890, 892, 911, 919, 923, 925, 926, 935, 939, 941, 942, 947, 949, 950, 953, 954, 956, 967, 971, 973, 974, 979, 981, 982, 985, 986, 988, 995, 997, 998};
} else if (k == 8) {
table = new int[]{255, 383, 447, 479, 495, 503, 507, 509, 510, 639, 703, 735, 751, 759, 763, 765, 766, 831, 863, 879, 887, 891, 893, 894, 927, 943, 951, 955, 957, 958, 975, 983, 987, 989, 990, 999};
} else{
table = new int[]{511, 767, 895, 959, 991};
}
int sum = 0;
int tl = table.length;
int n = nums.size();
for (int i = 0; i < tl; i++) {
if (table[i] < n){
sum += nums.get(table[i]);
}else {
return sum;
}
}
return sum;
}
}
时间效率成功达到 1ms, 击败100%, 试试不打表的方法:
class Solution {
public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
if(k == 10) {
return 0;
}
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
if (Integer.bitCount(i) == k){
sum += nums.get(i);
}
}
return sum;
}
}
不仅代码数量少了, 而且时间效率也达到了 1ms, 击败100%. 因为 Java 自带了计算一个32位整数的二进制位为 1 的数量, Integer.bitCount .
看看自带的 Integer.bitCount 怎么实现的.
public static int bitCount(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
要理解这个可以先理解更简单的版本:
public static int bitCount(int i) {
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF);
n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF);
return n;
}
首先 0x55555555 的二进制表示为 01010101010101010101010101010101
举例：
0x55555555 = 01010101010101010101010101010101
n=0011 1010 1101 1110 0110 1000 1011 0001
n & 0x55555555 即保存奇数位, 两个为1组, 或者说一组种的低位
因此
n : 00 11 10 10 11 01 11 10 01 10 10 00 10 11 00 01
n >> 1 : 00 01 11 01 01 10 11 11 00 11 01 00 01 01 10 00
n & 0x55555555 : 00 01 00 00 01 01 01 00 01 00 00 00 00 01 00 01
(n >> 1) & 0x55555555 : 00 01 01 01 01 00 01 01 00 01 01 00 01 01 00 00
相加就得到的就是每两位的1的数量
n : 00 10 01 01 10 01 10 01 01 01 01 00 01 10 00 01
这里每一组都代表了n在这一组中1的个数, 例如 00 最后相加得到00, 11 最后相加得到 10（代表2）, 就是说2个
0x33333333 = 00110011001100110011001100110011
n : 0010 0101 1001 1001 0101 0100 0110 0001
n & 0x33333333 即4个为一组, 保留后两位
n >> 2 : 0000 1001 0110 0110 0101 0101 0001 1000
(n & 0x33333333) : 0010 0001 0001 0001 0001 0000 0010 0001
(n >> 2) & 0x55555555 : 0000 0001 0010 0010 0001 0001 0001 0000
相加得到4个一组，每组的1的个数
n : 0010 0010 0011 0011 0010 0001 0011 0001
比如第一组有2个1，因此此时n的第一组为0010代表2，第三组有3个1，因此此时n的第三组为0011代表3
依次类推，类似与归并的思想.
而Java源码的方法更快，当然也更复杂，他不考虑前面的，每次只考虑后半部分，这样最后只返回最后6位。
因为是针对32位整数的, 因此最多有 32 个 1, 32 用二进制表示可以表示为 0010 0000, 因此对最后的结果对 0x3f 按位与操作, 取最低6位的结果, 因为 0x3f 的二进制表示为 0011 1111, 因此可以取到最后6位.
类似的题目
汉明距离(Easy)
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4 输出：2 解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
相当于获取两个数中位不同的个数. 要实现得到位不同的为1, 只要求异或即可
class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
}
位1的个数(Easy)
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）
我直接一个 return Integer.bitCount(n);
当然又学到一种 n&(n-1) 的方法
public class Solution {
public int hammingWeight(int n) {
int res = 0;
while (n != 0) {
res++;
n &= n - 1;
}
return res;
}
}
这个是什么意思呢? 就是每一次 n&(n-1) 都是去掉 n 最右边一个1, 怎么实现的呢? 就是通过 n&(n-1), 假设 n 的二进制表示为 10101000:
n : 1 0 1 0 1 0 0 0
n-1: 1 0 1 0 0 1 1 1
-------------------------
n&(n-1): 1 0 1 0 0 0 0 0
会发现这样每次都能很巧妙地去掉最右边一个 1.