HOT 100【LeetCode】_leetcode hot100
赞
踩
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<c 的 c 了，可以退出循环 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
