关于【leetcode算法讲解】，今天乾乾小编给您分享一下，如果对您有所帮助别忘了关注本站哦。
内容导航：1、leetcode算法讲解：10道Leetcode算法题详解，总有一道适合你2、leetcode算法讲解，LeetCode力扣官方题解1、leetcode算法讲解：10道Leetcode算法题详解，总有一道适合你
1、反转链表
反转一个单链表。
输入:1->2->3->4->5
输出:5->4->3->2->1
解法1：迭代，重复某一过程，每一次处理结果作为下一次处理的初始值，这些初始值类似于状态、每 次处理都会改变状态、直至到达最终状态
从前往后遍历链表，将当前节点的next指向上一个节点，因此需要一个变量存储上一个节点prev，当前节点处理完需要寻找下一个节点，因此需要一个变量保存当前节点curr，处理完后要将当前节点赋值给
prev，并将next指针赋值给curr，因此需要一个变量提前保存下一个节点的指针next
1、将下一个节点指针保存到next变量 next = curr.next
2、将下一个节点的指针指向prev，curr.next = prev
3、准备处理下一个节点，将curr赋值给prev
4、将下一个节点赋值为curr，处理一个节点
解法2：递归：以相似的方法重复，类似于树结构，先从根节点找到叶子节点，从叶子节点开始遍历 大的问题(整个链表反转)拆成性质相同的小问题(两个元素反转)curr.next.next = curr
将所有的小问题解决，大问题即解决
只需每个元素都执行curr.next.next = curr，curr.next = null两个步骤即可为了保证链不断，必须从最后一个元素开始
public class ReverseList
{ static class
ListNode{
int val;
ListNode next;
public ListNode(int val, ListNode next) { this.val = val;
this.next = next;
}
}
public static ListNode iterate(ListNode
head){ ListNode prev = null,curr,next;
curr = head;
while(curr != null){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public static ListNode recursion(ListNode head)
{ if (head == null || head.next == null) {
return head;
}
ListNode newHead = recursion(head.next); head.next.next = head;
head.next = null; return newHead;
}
public static void main(String[] args)
{ ListNode node5 = new ListNode(5,null);
ListNode node4 = new ListNode(4,node5);
ListNode node3 = new ListNode(3,node4);
ListNode node2 = new ListNode(2,node3);
ListNode node1 = new ListNode(1,node2);
//ListNode node = iterate(node1);
ListNode node_1 = recursion(node1);
System.out.println(node_1);
}
}
2、统计N以内的素数
素数：只能被1和自身整除的数，0、1除外解法一：暴力算法
直接从2开始遍历，判断是否能被2到自身之间的数整除
public int countPrimes(int n) { int ans = 0;
for (int i = 2; i < n; ++i) { ans += isPrime(i) ? 1 : 0;
}
return ans;
}
//i如果能被x整除，则x/i肯定能被x整除，因此只需判断i和根号x之中较小的即可public boolean isPrime(int x) {
for (int i = 2; i * i <= x; ++i) { if (x % i == 0) {
return false;
}
}
return true;
}
解法2：埃氏筛
利用合数的概念(非素数)，素数*n必然是合数，因此可以从2开始遍历，将所有的合数做上标记
public static int eratosthenes(int n)
{ boolean[] isPrime = new
boolean[n]; int ans = 0;
for (int i = 2; i < n; i++)
{ if (!isPrime[i]) {
ans += 1;
for (int j = i * i; j < n; j += i)
{ isPrime[j] = true;
}
}
}
return ans;
}
将合数标记为true，j = i * i 从 2 * i 优化而来，系数2会随着遍历递增（j += i，相当于递增了系数2）， 每一个合数都会有两个比本身要小的因子(0,1除外)，2 * i 必然会遍历到这两个因子
当2递增到大于根号n时，其实后面的已经无需再判断（或者只需判断后面一段），而2到根号n、实际 上在 i 递增的过程中已经计算过了，i 实际上就相当于根号n
例如：n = 25 会计算以下
2 * 4 = 8
3 * 4 = 12
但实际上8和12已经标记过，在n = 17时已经计算了 3 * 4，2 * 4
寻找数组的中心索引
数组中某一个下标，左右两边的元素之后相等，该下标即为中心索引思路：先统计出整个数组的总和，然后从第一个元素开始叠加
总和递减当前元素，叠加递增当前元素，知道两个值相等
public static int pivotIndex(int[] nums)
{ int sum1 =
Arrays.stream(nums).sum(); int sum2 = 0;
for(int i = 0; i<nums.length; i++){ sum2 += nums[i];
if(sum1 == sum2){ return i;
}
sum1 = sum1 - nums[i];
}
return -1;
}
3、删除排序数组中的重复项
一个有序数组 nums ，原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
双指针算法：
数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要
nums[i]=nums[j]，我们就增加 j 以跳过重复项。
当遇到 nums[j] ！= nums[i]时，跳过重复项的运行已经结束，必须把nums[j]）的值复制到 nums[i +
1]。然后递增 i，接着将再次重复相同的过程，直到 j 到达数组的末尾为止。
public int removeDuplicates(int[] nums)
{ if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++)
{ if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
4、x的平方根
在不使用 sqrt(x) 函数的情况下，得到 x的平方根的整数部分解法一：二分查找
x的平方根肯定在0到x之间，使用二分查找定位该数字，该数字的平方一定是最接近x的，m平方值如果大于x、则往左边找，如果小于等于x则往右边找
找到0和X的最中间的数m，
如果m * m > x，则m取x/2到x的中间数字，直到m * m < x，m则为平方根的整数部分
如果m * m <= x，则取0到x/2的中间值，知道两边的界限重合，找到最大的整数，则为x平方根的整数部分
时间复杂度：O(logN)
public static int binarySearch(int x)
{ int l = 0, r = x, index = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long) mid * mid <= x) {
index = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return index;
}
解法二：牛顿迭代
假设平方根是 i ，则 i 和 x/i 必然都是x的因子，而 x/i 必然等于 i ，推导出 i + x / i = 2 * i，得出 i = (i + x / i) / 2
由此得出解法，i 可以任选一个值，只要上述公式成立，i 必然就是x的平方根，如果不成立， (i + x / i) /
2得出的值进行递归，直至得出正确解
public static int newton(int x)
{ if(x==0) return 0;
return ((int)(sqrts(x,x)));
}
public static double sqrts(double i,int
x){ double res = (i + x / i) / 2;
if (res == i) { return i;
} else {
return sqrts(res,x);
}
}
5、三个数的最大乘积
一个整型数组乘积不会越界nums，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。
如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数 相乘同样也为最大乘积。
如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对 值最大）与最大正数的乘积。
分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答 案。
解法一：排序
public static int sort(int[] nums) { Arrays.sort(nums);
int n = nums.length;
return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
}
解法二：线性扫描
public static int getMaxMin(int[] nums) {
// 最小的和第二小的
int min1 = 0, min2 = 0;
// 最大的、第二大的和第三大的
int max1 = 0, max2 = 0, max3 = 0;
for (int x : nums)
{ if (x < min1) {
min2 = min1;
min1 = x;
} else if (x < min2)
{ min2 = x;
}
if (x > max1)
{ max3 =
max2; max2 =
max1; max1 =
x;
} else if (x > max2)
{ max3 = max2;
max2 = x;
} else if (x > max3)
{ max3 = x;
}
}
return Math.max(min1 * min2 * max1, max1 * max2 * max3);
}
6、斐波那契数列
求取斐波那契数列第N位的值。
斐波那契数列：每一位的值等于他前两位数字之和。前两位固定 0，1,1,2,3,5,8。。。。解法一：暴力递归
public static int calculate(int
num){ if(num == 0 ){
return 0;
}
if(num == 1){
return 1;
}
return calculate(num-1) + calculate(num-2);
}
解法二：去重递归
递归得出具体数值之后、存储到一个集合(下标与数列下标一致)，后面递归之前先到该集合查询一次， 如果查到则无需递归、直接取值。查不到再进行递归计算
public static int calculate2(int num){ int[] arr = new int[num+1];
return recurse(arr,num);
}
private static int recurse(int[] arr, int num) { if(num == 0 ){
return 0;
}
if(num == 1){
return 1;
}
if(arr[num] != 0){ return arr[num];
}
arr[num] = recurse(arr,num-1) + recurse(arr,num-2); return arr[num];
}
解法三：双指针迭代
基于去重递归优化，集合没有必要保存每一个下标值，只需保存前两位即可，向后遍历，得出N的值
public static int iterate(int num){ if(num == 0 ){
return 0;
}
if(num == 1){
return 1;
}
int low = 0,high = 1; for(int i=2; i<= num; i++){
int sum = low + high; low = high;
high = sum;
}
return high;
}
7、环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达该节点，则链表中存在环如果链表中存在环，则返回 true 。 否则，返回 false 。
解法一：哈希表
public static boolean hasCycle(ListNode head)
{ Set<ListNode> seen = new
HashSet<ListNode>(); while (head != null) {
if (!seen.add(head)) { return true;
}
head = head.next;
}
return false;
}
解法二：双指针
public static boolean hasCycle2(ListNode head) {
if (head == null || head.next == null) { return false;
}
ListNode slow = head; ListNode fast = head.next; while (slow != fast) {
if (fast == null || fast.next == null) { return false;
}
slow = slow.next; fast = fast.next.next;
}
return true;
}
8、排列硬币
总共有 n 枚硬币，将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内
解法一：迭代
从第一行开始排列，排完一列、计算剩余硬币数，排第二列，直至剩余硬币数小于或等于行数
public static int arrangeCoins(int n)
{ for(int i=1; i<=n; i++){
n = n-i;
if (n <= i){
return i;
}
}
return 0;
}
解法二：二分查找
假设能排 n 行，计算 n 行需要多少硬币数，如果大于 n，则排 n/2行，再计算硬币数和 n 的大小关系
public static int arrangeCoins2(int n)
{ int low = 0, high = n;
while (low <= high) {
long mid = (high - low) / 2 + low; long cost = ((mid + 1) * mid) / 2;
if (cost == n) { return (int)mid;
} else if (cost > n) { high = (int)mid - 1;
} else {
low = (int)mid + 1;
}
}
return high;
}
解法三：牛顿迭代
使用牛顿迭代求平方根，(x + n/x)/2
假设能排 x 行 则 1 + 2 + 3 + ...+ x = n，即 x(x+1)/2 = n 推导出 x = 2n - x
public static double sqrts(double x,int
n){ double res = (x + (2*n-x) / x) / 2;
if (res == x) { return x;
} else {
return sqrts(res,n);
}
}
9、二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。解法一：深度优先
遍历整颗数，找到每一个叶子节点，从叶子节点往上开始计算，左右子节点都为空则记录深度为1
左右子节点只有一边，深度记录为子节点深度+1
左右两边都有子节点，则记录左右子节点的深度较小值+1
public int minDepth(TreeNode root) { if (root == null) {
return 0;
}
if (root.left == null && root.right == null) { return 1;
}
int min_depth = Integer.MAX_VALUE; if (root.left != null) {
min_depth = Math.min(minDepth(root.left), min_depth);
}
if (root.right != null) {
min_depth = Math.min(minDepth(root.right), min_depth);
}
return min_depth + 1;
}
时间复杂度：O(N)
空间复杂度：O(logN) 取决于树的高度
解法二：广度优先
从上往下，找到一个节点时，标记这个节点的深度。查看该节点是否为叶子节点，如果是直接返回深度 如果不是叶子节点，将其子节点标记深度(在父节点深度的基础上加1)，再判断该节点是否为叶子节点
class QueueNode { TreeNode node; int depth;
public QueueNode(TreeNode node, int depth) { this.node = node;
this.depth = depth;
}
}
public int minDepth(TreeNode root) { if (root == null) {
return 0;
}
Queue<QueueNode> queue = new LinkedList<QueueNode>();
queue.offer(new QueueNode(root, 1));
while (!queue.isEmpty()) {
QueueNode nodeDepth = queue.poll();
TreeNode node = nodeDepth.node; int depth = nodeDepth.depth;
if (node.left == null && node.right == null) { return depth;
}
if (node.left != null) {
queue.offer(new QueueNode(node.left, depth + 1));
}
if (node.right != null) {
queue.offer(new QueueNode(node.right, depth + 1));
}
}
return 0;
}
时间复杂度：O(N) 空间复杂度：O(N)
10、最长连续递增序列
给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。 序列的下标是连续的
贪心算法
从0开始寻找递增序列，并将长度记录，记录递增序列的最后一个下标，然后从该下标继续寻找，记录 长度，取长度最大的即可
public static int findLength(int[] nums)
{ int ans = 0;
int start = 0;
for (int i = 0; i < nums.length; i++)
{ if (i > 0 && nums[i] <= nums[i - 1]) {
start = i;
}
ans = Math.max(ans, i - start + 1);
}
return ans;
}
11、柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。必须给每个顾客正确找零注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
输入：[5,5,5,10,20]
输出：true
输入：[10,10]
输出：false
贪心：
public boolean lemonadeChange(int[] bills) { int five = 0, ten = 0;
for (int bill : bills) { if (bill == 5) {
five++;
} else if (bill == 10) { if (five == 0) {
return false;
}
five--; ten++;
} else {
if (five > 0 && ten > 0) { five--;
ten--;
} else if (five >= 3) { five -= 3;
} else {
return false;
}
}
}
return true;
}
12、香槟塔
我们把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，第二层有2个，依次类推到第100层，每个玻璃杯(250ml)将盛有香槟。
从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向 左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。
（当最底层的玻璃杯满了，香槟会流到地板上）
例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一 半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟
现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（i 和 j都从0
开始）。
public double champagneTower(int poured, int query_row, int query_glass)
{ double[][] A = new double[102][102];
A[0][0] = (double) poured;
for (int r = 0; r <= query_row; ++r) { for (int c = 0; c <= r; ++c) {
double q = (A[r][c] - 1.0) / 2.0; if (q > 0) {
A[r+1][c] += q;
A[r+1][c+1] += q;
}
}
}
return Math.min(1, A[query_row][query_glass]);
}
13、优势洗牌
给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。返回 A 的任意排列，使其相对于 B 的优势最大化。
public static int[] advantageCount(int[] A, int[] B)
{ int[] sortedA = A.clone();
Arrays.sort(sortedA);//找一个代价最小的去匹配B中的，比B大，在A中又是最小的
int[] sortedB = B.clone(); Arrays.sort(sortedB);//避免比较时，A每次都要重头遍历
Map<Integer, Deque<Integer>> assigned = new HashMap();
for (int b: B)
assigned.put(b, new LinkedList());
Deque<Integer> remaining = new LinkedList();
int j = 0;
for (int a: sortedA) {
if (a > sortedB[j]) { assigned.get(sortedB[j++]).add(a);
} else {
remaining.add(a);
}
}
int[] ans = new int[B.length];
for (int i = 0; i < B.length; ++i) { if (assigned.get(B[i]).size() > 0)
ans[i] = assigned.get(B[i]).removeLast();
else
ans[i] = remaining.removeLast();
}
return ans;
}
时间复杂度：O(N log N)，其中 N 是A和B的长度。
空间复杂度：O(N)。
2、leetcode算法讲解，LeetCode力扣官方题解
2044. 统计按位或能得到最大值的子集数目
题目描述
难易度：中等
给你一个整数数组 nums ，请你找出 nums 子集 按位或 可能得到的 最大值 ，并返回按位或能得到最大值的 不同非空子集的数目 。
如果数组 a 可以由数组 b 删除一些元素（或不删除）得到，则认为数组 a 是数组 b 的一个 子集 。如果选中的元素下标位置不一样，则认为两个子集 不同 。
对数组 a 执行 按位或 ，结果等于 a[0] OR a[1] OR ... OR a[a.length - 1]（下标从 0 开始）。
示例 1：
输入：nums = [3,1]输出：2解释：子集按位或能得到的最大值是 3 。有 2 个子集按位或可以得到 3 ：- [3]- [3,1]
示例 2：
输入：nums = [2,2,2]输出：7解释：[2,2,2] 的所有非空子集的按位或都可以得到 2 。总共有 23 - 1 = 7 个子集。
示例 3：
输入：nums = [3,2,1,5]输出：6解释：子集按位或可能的最大值是 7 。有 6 个子集按位或可以得到 7 ：- [3,5]- [3,1,5]- [3,2,5]- [3,2,1,5]- [2,5]- [2,1,5]
提示：
1 <= nums.length <= 161 <= nums[i] <= 105解决方案
方法一：位运算
思路记 n 是数组 nums 的长度，数组中的每个元素都可以选取或者不选取，因此数组的非空子集数目一共有 (2n-1) 个。可以用一个长度为 n 比特的整数来表示不同的子集，在整数的二进制表示中，n 个比特的值代表了对数组不同元素的取舍。第 i 位值为 1 则表示该子集选取对应元素，第 i 位值为 0 则表示该子集不选取对应元素。求出每个子集的按位或的值，并计算取到最大值时的子集个数。
代码
Python3
class Solution: def countMaxOrSubsets(self, nums: List[int]) -> int: maxOr, cnt = 0, 0 for i in range(1, 1 << len(nums)): orVal = reduce(or_, (num for j, num in enumerate(nums) if (i >> j) & 1), 0) if orVal > maxOr: maxOr, cnt = orVal, 1 elif orVal == maxOr: cnt = 1 return cnt
Java
class Solution { public int countMaxOrSubsets(int[] nums) { int maxOr = 0, cnt = 0; for (int i = 0; i < 1 << nums.length; i ) { int orVal = 0; for (int j = 0; j < nums.length; j ) { if (((i >> j) & 1) == 1) { orVal |= nums[j]; } } if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt ; } } return cnt; }}
C#
public class Solution { public int CountMaxOrSubsets(int[] nums) { int maxOr = 0, cnt = 0; for (int i = 0; i < 1 << nums.Length; i ) { int orVal = 0; for (int j = 0; j < nums.Length; j ) { if (((i >> j) & 1) == 1) { orVal |= nums[j]; } } if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt ; } } return cnt; }}
C
class Solution {public: int countMaxOrSubsets(vector<int>& nums) { int n = nums.size(), maxValue = 0, cnt = 0, stateNumber = 1 << n; for (int i = 0; i < stateNumber; i ) { int cur = 0; for (int j = 0; j < n; j ) { if (((i >> j) & 1) == 1) { cur |= nums[j]; } } if (cur == maxValue) { cnt ; } else if (cur > maxValue) { maxValue = cur; cnt = 1; } } return cnt; }};
C
int countMaxOrSubsets(int* nums, int numsSize){ int n = numsSize, maxValue = 0, cnt = 0, stateNumber = 1 << n; for (int i = 0; i < stateNumber; i ) { int cur = 0; for (int j = 0; j < n; j ) { if (((i >> j) & 1) == 1) { cur |= nums[j]; } } if (cur == maxValue) { cnt ; } else if (cur > maxValue) { maxValue = cur; cnt = 1; } } return cnt;}
Golang
func countMaxOrSubsets(nums []int) (ans int) { maxOr := 0 for i := 1; i < 1<<len(nums); i { or := 0 for j, num := range nums { if i>>j&1 == 1 { or |= num } } if or > maxOr { maxOr = or ans = 1 } else if or == maxOr { ans } } return}
JavaScript
var countMaxOrSubsets = function(nums) { let maxOr = 0, cnt = 0; for (let i = 0; i < 1 << nums.length; i ) { let orVal = 0; for (let j = 0; j < nums.length; j ) { if (((i >> j) & 1) === 1) { orVal |= nums[j]; } } if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal === maxOr) { cnt ; } } return cnt;};
复杂度分析
时间复杂度：O(2n×n)，其中 n 是数组 nums 的长度。需要遍历 O(2n) 个状态，遍历每个状态时需要遍历 O(n) 位。空间复杂度：O(1)。仅使用常量空间。方法二：回溯
思路
记 n 是数组 nums 的长度。方法一的缺点是，计算不同状态的按位或的值，都需要消耗 O(n) 的时间。这一步部分可以进行优化。每个长度为 n 比特的状态的按位或的值，都是可以在长度为 n−1 比特的状态的按位或的值上计算出来的，而这个计算只需要消耗常数时间。以此类推，边界情况是长度为 0 比特的状态的按位或的值。我们定义一个搜索函数，参数 pos 表示当前下标，orVal 表示当前下标之前的某个子集按位或值，这样就可以保存子集按位或的值的信息，并根据当前元素选择与否更新 orVal。当搜索到最后位置时，更新最大值和子集个数。
代码
Python3
class Solution: def countMaxOrSubsets(self, nums: List[int]) -> int: maxOr, cnt = 0, 0 def dfs(pos: int, orVal: int) -> None: if pos == len(nums): nonlocal maxOr, cnt if orVal > maxOr: maxOr, cnt = orVal, 1 elif orVal == maxOr: cnt = 1 return dfs(pos 1, orVal | nums[pos]) dfs(pos 1, orVal) dfs(0, 0) return cnt
Java
class Solution { int[] nums; int maxOr, cnt; public int countMaxOrSubsets(int[] nums) { this.nums = nums; this.maxOr = 0; this.cnt = 0; dfs(0, 0); return cnt; } public void dfs(int pos, int orVal) { if (pos == nums.length) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt ; } return; } dfs(pos 1, orVal | nums[pos]); dfs(pos 1, orVal); }}
C#
public class Solution { int[] nums; int maxOr, cnt; public int CountMaxOrSubsets(int[] nums) { this.nums = nums; this.maxOr = 0; this.cnt = 0; DFS(0, 0); return cnt; } public void DFS(int pos, int orVal) { if (pos == nums.Length) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt ; } return; } DFS(pos 1, orVal | nums[pos]); DFS(pos 1, orVal); }}
C
class Solution {public: int countMaxOrSubsets(vector<int>& nums) { this->nums = nums; this->maxOr = 0; this->cnt = 0; dfs(0, 0); return cnt; } void dfs(int pos, int orVal) { if (pos == nums.size()) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal == maxOr) { cnt ; } return; } dfs(pos 1, orVal| nums[pos]); dfs(pos 1, orVal); }private: vector<int> nums; int maxOr, cnt;};
C
void dfs(int pos, int orVal, const int* nums, int numsSize, int* maxOr, int* cnt) { if (pos == numsSize) { if (orVal > *maxOr) { *maxOr = orVal; *cnt = 1; } else if (orVal == *maxOr) { (*cnt) ; } return; } dfs(pos 1, orVal | nums[pos], nums, numsSize, maxOr, cnt); dfs(pos 1, orVal, nums, numsSize, maxOr, cnt);}int countMaxOrSubsets(int* nums, int numsSize) { int cnt = 0; int maxOr = 0; dfs(0, 0, nums, numsSize, &maxOr, &cnt); return cnt;}
Golang
func countMaxOrSubsets(nums []int) (ans int) { maxOr := 0 var dfs func(int, int) dfs = func(pos, or int) { if pos == len(nums) { if or > maxOr { maxOr = or ans = 1 } else if or == maxOr { ans } return } dfs(pos 1, or|nums[pos]) dfs(pos 1, or) } dfs(0, 0) return}
JavaScript
var countMaxOrSubsets = function(nums) { this.nums = nums; this.maxOr = 0; this.cnt = 0; dfs(0, 0); return cnt;};const dfs = (pos, orVal) => { if (pos === nums.length) { if (orVal > maxOr) { maxOr = orVal; cnt = 1; } else if (orVal === maxOr) { cnt ; } return; } dfs(pos 1, orVal | nums[pos]); dfs(pos 1, orVal);}
复杂度分析
时间复杂度：O(2n)，其中 n 是数组 nums 的长度。状态数一共有 O(20 21 ... 2n) = O(2×2n) = O(2n) 种，每次计算只消耗常数时间。空间复杂度：O(n)，其中 n 是数组 nums 的长度。搜索深度最多为 n。BY /
本文作者：力扣
本文关键词：leetcode刷题，leetcode算法常用技巧，leetcode算法题解，leetcodetop，leetcode经典算法题。这就是关于《leetcode算法讲解，10道Leetcode算法题详解》的所有内容，希望对您能有所帮助！更多的知识请继续关注《犇涌向乾》百科知识网站：http://www.029ztxx.com！