HOT 100【LeetCode】

HOT 100【LeetCode】

前言

写作于
2022-11-07 20:59:56

发布于
2022-11-20 16:05:50

1. 两数之和

简单
15.7K
相关企业
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map=new HashMap<>();
     
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        

        return new int[0];

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

三数之和
四数之和
两数之和 II - 输入有序数组

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：


输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

我的解法：一位加法器

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode res=new ListNode(-1);
        ListNode cur=res;
        ListNode cur1=l1;
        ListNode cur2=l2;
        int[] r={0,0};
        while(cur1!=null&&cur2!=null){
            r=add(cur1.val, cur2.val, r[0]);
            cur.next=new ListNode(r[1]);
            cur1=cur1.next;
            cur2=cur2.next;
            cur=cur.next;
        }

        while (cur1!=null){
            r= add(cur1.val, 0, r[0]);
            cur.next=new ListNode(r[1]);
            cur1=cur1.next;
            cur=cur.next;

        }
        while (cur2!=null){
            r= add(0, cur2.val, r[0]);
            cur.next=new ListNode(r[1]);
            cur2=cur2.next;
            cur=cur.next;
        }
        if(r[0]!=0){
            cur.next=new ListNode(r[0]);
        }
        return res.next;

    }
     public int[] add(int a,int b,int jin){
        int c=(a+b+jin)%10;
        jin=(a+b+jin)/10;
        return new int[]{jin,c};
    }
}
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

我之前的解法

递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1==null){
            return l2;
        }
        if (l2==null){
            return l1;
        }
        l2.val= l1.val+ l2.val;
        if(l2.val>=10){
            l2.val= l2.val%10;
            if (l2.next!=null){
                l2.next.val+=1;
                if (l2.next.val==10){
                    l2.next = addTwoNumbers(new ListNode(0, null), l2.next);
                }
            }
            else {
                l2.next = new ListNode(1, null);
            }
        }

        l2.next = addTwoNumbers(l1.next, l2.next);

        return l2;

    }
}
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 ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}


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

3. 无重复字符的最长子串

中等
8.4K
相关企业
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5. 最长回文子串

中等
5.9K
相关企业
给你一个字符串 s，找到 s 中最长的回文子串。

 

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
1
2
3
4
5
6
7
8
9
10
11

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

方法一：动态规划

对于一个子串而言，如果它是回文串，并且长度大于 222，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是“a”。

P(i,j)=P(i+1,j−1)∧(S i ==S j )

class Solution {
    public String longestPalindrome(String s) {
        //长度为1，本身就是回文的
        int len=s.length();
        if(len<2){
            return s;
        }

        //记录最长回文子串长度
        int maxLen=1;
        //记录回文子串的开始
        int begin=0;

       
         // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean [][] dp=new boolean[len][len];
         //所有长度为1的子串都是回文的
        for(int i=0;i<len;i++){
            dp[i][i]=true;
        }

        char[] charArray = s.toCharArray();
        // 递推开始

        //枚举子串长度
        for(int L=2;L<=len;L++){
            //枚举左边界
            for(int l=0;l<len;l++){
                int r=L+l-1;
                if(r>=len){
                    break;
                }
                //s[i,j] 本身不是一个回文串；
                if(charArray[l]!=charArray[r]){
                    dp[l][r]=false;
                }else{
                    if(r-l<3){
                        dp[l][r]=true; 
                    }else{
                        dp[l][r]=dp[l+1][r-1];
                    }
                }
                 // 只要 dp[l][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                   if (dp[l][r] && r - l + 1 > maxLen) {
                    maxLen = r - l + 1;
                    begin = l;
                }


            }

        }
        return s.substring(begin, begin + maxLen);

    }
}
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

方法二：中心扩展算法

每一个长度为1的子串都是回文子串，向外扩展即可

我们仔细观察一下方法一中的状态转移方程：

​

P(i,i)=true
P(i,i+1)=(S i ==S i+1 )
P(i,j)=P(i+1,j−1)∧(S i ==S j )
​

找出其中的状态转移链：

P(i,j)←P(i+1,j−1)←P(i+2,j−2)←⋯←某一边界情况

可以发现，所有的状态在转移的时候的可能性都是唯一的。也就是说，我们可以从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。

边界情况即为子串长度为 1 或 2 的情况。我们枚举每一种边界情况，并从对应的子串开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展，例如从P(i+1,j−1) 扩展到 P(i,j)；如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了。

聪明的读者此时应该可以发现，「边界情况」对应的子串实际上就是我们「扩展」出的回文串的「回文中心」。方法二的本质即为：我们枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案。

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }

        int start=0;
        int end=0;
        //对于每一个回文中心
        for(int i=0;i<s.length();i++){
            //长度为1的回文中心
            int len1=expand(s,i,i);
            //长度为2的回文中心
            int len2=expand(s,i,i+1);
            int len=Math.max(len1,len2);
            //更新最长
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }


        }

        return s.substring(start, end + 1);

    

    }

    //扩展
    public int expand(String s,int left,int right){
        while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        return right-left-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
36
37
38
39
40

15. 三数之和

中等
5.4K
相关企业
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

排序+双指针

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
          List<List<Integer>> ans=new ArrayList<>();
        int n=nums.length;
        Arrays.sort(nums);

        //枚举a
        for (int first = 0; first <n; first++){
            //去重上次
            if(first>0&&nums[first]==nums[first-1]){
                continue;
            }

            //枚举c
            int third=n-1;
            int target=-nums[first];

            //枚举b
            for (int second = first+1; second <n ; second++) {
                //去重上次
                if(second > first+1&&nums[second]==nums[second-1]){
                    continue;
                }
                //需要保证c在b的右侧
                while (second<third&&nums[second]+nums[third]>target){
                    third--;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }





            }



        }


        return ans;


    }
}
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

17. 电话号码的字母组合

中等
2.2K
相关企业
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]
1
2
3
4
5
6
7
8
9
10
11
12

提示：

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

笛卡尔积

1

20. 有效的括号

简单
3.6K
相关企业
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
 
1
2
3
4
5
6
7
8
9
10
11
12
13

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

栈

class Solution {
    public boolean isValid(String s) {
        int n=s.length();
        if(n%2!=0){
            return false;
        }
        Stack<Character> stack=new Stack();
        HashMap<Character,Character> map=new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');

        for(int i=0;i<n;i++){
            Character c= s.charAt(i); 
            if(map.containsKey(c)){
                if(stack.isEmpty()||stack.peek()!=map.get(c)){
                    return false;
                }
                 stack.pop();
            }else{
                stack.push(c);
            }

        }
        return stack.isEmpty();
    }
}
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

括号生成
最长有效括号
删除无效的括号

121. 买卖股票的最佳时机

简单
2.6K
相关企业
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
 
1
2
3
4
5
6
7
8
9
10
11
12

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 104

class Solution {
    public int maxProfit(int[] prices) {
        int minP=Integer.MAX_VALUE;
        int maxP=0;
        for(int i=0;i<prices.length;i++){
            if(prices[i]<minP){
                minP=prices[i];
            }
            if(maxP<prices[i]-minP){
                maxP=prices[i]-minP;
            }
        }
        return maxP;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode low=head;
        ListNode fast=head;

        while(fast!=null&&fast.next!=null){
            low=low.next;
            fast=fast.next.next;
            if(low==fast){
                return true;
            }
        }
        return false;
    }
}
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

环形链表 II

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode low=head;
        ListNode fast=head;

        while(fast!=null&&fast.next!=null){
            low=low.next;
            fast=fast.next.next;
            if(low==fast){
                ListNode node=head;
                
                while(node!=low){
                    node=node.next;
                    low=low.next;
                   
                }
                return node;
            }
        }
        return null;
    }
}
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

快乐数

160. 相交链表

简单
1.9K
相关企业
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

hash表

双指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;


    }
}
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

169. 多数元素

简单
1.6K
相关企业
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3
示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2
 
1
2
3
4
5
6
7
8
9

提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

HashMap计数

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                int count=map.get(nums[i]);
                map.put(nums[i],count+1);
            }else{
                map.put(nums[i],1);
            }
        }
        for(Integer i:map.keySet()){
            if(map.get(i)>nums.length/2){
                return i;
            }
        }
        return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

排序返回[n/2]

同归于尽法

https://leetcode.cn/problems/majority-element/solution/javashi-pin-jiang-jie-xi-lie-majority-element-by-s/
“同归于尽消杀法” ：

由于多数超过50%, 比如100个数，那么多数至少51个，剩下少数是49个。

遍历数组

第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，此时领主 winner 就是这个阵营的人，现存兵力 count = 1。

如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，领主不变，winner 依然是当前这个士兵所属阵营，现存兵力 count 加一；

如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽。 此时前方阵营兵力-1, 即使双方都死光，这块高地的旗帜 winner 不变，没有可以去换上自己的新旗帜。

当下一个士兵到来，发现前方阵营已经没有兵力，新士兵就成了领主，winner 变成这个士兵所属阵营的旗帜，现存兵力 count ++。

就这样各路军阀一直厮杀以一敌一同归于尽的方式下去，直到少数阵营都死光，剩下几个必然属于多数阵营的，winner 是多数阵营。

（多数阵营 51个，少数阵营只有49个，死剩下的2个就是多数阵营的人）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public int majorityElement(int[] nums) {
    int winner = nums[0];
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (winner == nums[i]) {
            count++;
        } else if (count == 0) {
            winner = nums[i];
            count++;
        } else {
            count--;
        }
    }
    return winner;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

338. 比特位计数

简单
1.1K
相关企业
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

示例 1：

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10
示例 2：

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

提示：

0 <= n <= 105

进阶：

很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

调用函数

class Solution {
    public int[] countBits(int n) {
        int[] count=new int[n+1];
        for(int i=0;i<=n;i++){
            count[i]=Integer.bitCount(i);
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9

实现bitCount

class Solution {
    public int[] countBits(int n) {
        int[] count=new int[n+1];
        for(int i=0;i<=n;i++){
            count[i]=bitCount(i);
        }
        return count;
    }
    int bitCount(int i){
        int count=0;
        while(i!=0){
            if(i%2==1){
                count++;
            }
            i/=2;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//Brian Kernighan 算法的原理是：对于任意整数 xxx，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」
    public int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }


1
2
3
4
5
6
7
8
9
10
11

448. 找到所有数组中消失的数字

简单
1.1K
相关企业
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]
示例 2：

输入：nums = [1,1]
输出：[2]

提示：

n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

原地哈希

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
    	 int n = nums.length;
        for (int num : nums) {
            int x = (num - 1) % n;//num会改变，但它取模的值不回变 0~n-1
            nums[x] += n;//num会改变为num+n
        }
        System.out.println(Arrays.toString(nums));

        List<Integer> ret = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                ret.add(i + 1);
            }
        }
        return ret;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

461. 汉明距离

简单
650
相关企业
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
示例 2：

输入：x = 3, y = 1
输出：1

提示：

0 <= x, y <= 231 - 1

异或+bitcount

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x^y);
    }
}
1
2
3
4
5

146. LRU 缓存

中等
2.5K
相关企业
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put