您当前的位置:首页 > 时尚 > 内容

leetcode算法讲解,10道Leetcode算法题详解

关于【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

leetcode算法讲解,10道Leetcode算法题详解

1、将下一个节点指针保存到next变量 next = curr.next

2、将下一个节点的指针指向prev,curr.next = prev

3、准备处理下一个节点,将curr赋值给prev

4、将下一个节点赋值为curr,处理一个节点

解法2:递归:以相似的方法重复,类似于树结构,先从根节点找到叶子节点,从叶子节点开始遍历 大的问题(整个链表反转)拆成性质相同的小问题(两个元素反转)curr.next.next = curr

leetcode算法讲解,10道Leetcode算法题详解

将所有的小问题解决,大问题即解决

只需每个元素都执行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。。。。解法一:暴力递归

leetcode算法讲解,10道Leetcode算法题详解

public static int calculate(int

num){ if(num == 0 ){

return 0;

}

if(num == 1){

return 1;

}

return calculate(num-1) + calculate(num-2);

}

解法二:去重递归

递归得出具体数值之后、存储到一个集合(下标与数列下标一致),后面递归之前先到该集合查询一次, 如果查到则无需递归、直接取值。查不到再进行递归计算

leetcode算法讲解,10道Leetcode算法题详解

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的值

leetcode算法讲解,10道Leetcode算法题详解

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 的优势最大化。

leetcode算法讲解,10道Leetcode算法题详解

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!


声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,谢谢。

上一篇: 喜羊羊美羊羊主题儿歌原版(美羊羊喜羊儿歌主题歌)

下一篇: 淘宝是谁创立的(淘宝是谁的创始人是谁)



猜你感兴趣

推荐阅读

网站内容来自网络,如有侵权请联系我们,立即删除! | 软文发布 | 粤ICP备2021106084号