） 编写一个程序，找出第 n 个丑数。...丑数就是只包含质因数 2, 3, 5 的正整数。 Write a program to find the n-th ugly number....全部丑数都找出来 MAX最大的整数 i [1--MAX] i2 j[ i--MAX] j3 k[j--MAX] k*5 方法2 bfs 树的层次遍历 ? 我想到的 ?...Coin Change 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。...i*2+1;kk=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始 if(k+1k]k+1]){//如果左子结点小于右子结点
,find the nth num. 1 1 2 3 5 8... 2 #include 3 using namespace std; 4 5 int fib(int n)...{ 6 if(n==1 || n==2){ 7 return 1; 8 } 9 int prev=1; 10 int result=1; 11 n-=2; 12...while(n--){ 13 result+=prev; 14 prev=result-prev; 15 } 16 return result; 17 } 18 int main...(){ 19 int n; 20 while(cin>>n){ 21 coutn)<<endl; 22 } 23 24 return 0; 25 }
【题目描述】 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。...求按从小到大的顺序的第N个丑数。 【思路】 首先想到的是肯定是暴力法，从1,2,3,…循环一直找到给定的第n个丑数，但是这种做法我记得在LeetCode是TLE的。...那么有没有更elegant的方法呢？以下思路来自《剑指offer》第34题。 既然一个个循环不可行，那么就生成第n个丑数呗。...但是注意4也是一个丑数，它可以由2 x 2得到。所以丑数可以再乘以2,3,5得到下一个丑数，唯一要保证的是应该从小到大得到下一个丑数。...所以要分别保留2,3,5的上一个丑数指针，下一个丑数则是三个指针所指的数值分别乘以对应的因子中的最小值。
https://blog.csdn.net/zy010101/article/details/80079784 #include #include //求第...n个到第m个素数的和 int main() { int n,m; int flag = 0; int sum = 0; int j = 0; int isPrime_1(int n); scanf...("%d %d",&a,&b); for(int i = 2; flag 第m个素数 { j = isPrime_1(i); if (0 ==...j) { continue; } else { flag++; //素数计数器，表示是第几个素数 if(flag >= n) //从第n个素数开始求和...//是素数返回1，否则返回0 { int i = sqrt(n); int a = 1; for(int j = 2; j <= i; j++) { if(0 == n % j)
前言 在C语言中，分别用递归和非递归两种方法实现求第n个斐波那契数 一、思路 首先分析一下关于斐波那契数列的原理： 第一个和第二个数都是1，之后的每个数都是前两个数之和，即： 1，1，2，3，5，8，...…… 1.非递归 用到了循环相关的知识， 当n>2的时候进入循环，将前两个数相加得到第三个数； 当n的时候跳出循环。...2.递归 观察斐波那契数列可以得到一个公式： 根据这个公式就能进行递归。当n>2的时候进行递归，当n = 1或n = 2时返回1。...非递归： 源代码： #include //递归和非递归分别实现求第n个斐波那契数 //非递归 int main() { int i = 1; int j = 1; int temp...，本文简单的介绍了用C语言如何求解第n个斐波那契数的两种思路，还进一步展示了代码的运行结果验证了作者的思路。
1 #include 2 #include 3 using namespace std; 4 5 int nth_prime(int n) { 6...vector primes(n); 7 primes[0] = 2; 8 int CntOfPrime = 1; 9 for (int i = 3; CntOfPrime n; ++i) { 10 bool isPrime = true; 11 for (int j = 0; j < CntOfPrime && primes[j]*primes[j] <...isPrime) { 18 ++CntOfPrime; 19 primes[CntOfPrime - 1] = i; 20 } 21 } 22 return primes[n...- 1]; 23 } 24 25 int main() { 26 int n; 27 while (cin >> n) { 28 cout n) << endl
只包含2、3、5中的1个或多个因子的数称为丑数，要求按从小到大的顺序找到第n个丑数 ''' 2, 3, 5 6: 是丑数 14: 不是丑数，包含7 下一个丑数必定是数组的某一个丑数A * 2、B *...3、C * 5 中最小的值 M2, 之前的丑数*2都小于当前最大的丑数 之后的丑数*2都大于当前最大的丑数 M3、M5 ''' def getUglyNumber(index):
==1){ return 1;} if(n==2){ return 1;} return Fib(n-1)+Fib(n-2); } int main(){ int n; int a; printf...("请输入需要打印的斐波那契数\n"); scanf("%d",&n); a=Fib(n); system("pause"); return 0; } 2.非递归方法实现 #define _CRT_SECURE_NO_WARNINGS...; } //当前项的前一项； int last1=1; //当前项的后一项； int last2=1; int arr=0; for( int i=3;...in; i++ ){ cur=last2+last1; //下一次循环的时候； last2=last1; last1=cur; } return cur...; } int main() { int a; int n; printf("请输入需要打印的斐波那契数"); scanf("%d",&n); a=Fib(n); system("pause")
一道经典的题目。给一堆乱序的数，如果它们从小到大排好，求第 k 个是多少。假设排列的下标从 1 开始，而非 0 开始。 这个问题如此之简单而熟悉，可它却可以是很多现实问题的某一个子问题的抽象。...如果这堆数很多，但是 k 很小，那使用堆为了取第 k 个数，却需要维护一个巨大的堆，多少显得浪费。于是引出了下面这个问题： 能够改进上面堆排序的做法，仅仅维护一个大小为 k 的堆吗？...快排：空间复杂度为 O(1) 我想这个没有问题，但是时间复杂度呢，如果是单纯的快排，目的是让所有元素有序，复杂度是 O(n*log(n))，但是，找到第 k 个，平均的时间复杂度是在 O(n) 的级别，...具体来说，如果拿到若干个数组，从中任意取两个数 x 和 y，要求 x+y 的各种组合里面的第 k 个，或者在全为非负数的情况下引入乘法，比如 x*y+2x 的所有组合里面的第 k 个。...这个方法改变了思考的角度，原本是从一堆数中去找第 k 个数，现在是从中拿出一个数来，去这堆数中找它应该在的位置。 还蛮有趣的。
第K个最大的数 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。...你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。...看看源码 private final static int max= 10^5 +1; //优先队列PQ //给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。...，把减少的部分尽量换成时间复杂度为O(1)的比较操作，这样假设有m次add，那么有（n-m）次比较，综合起来就是O(klogk）+O(n-k） 题目中要求第K个最大的数，数组长度是N，所以定义堆的时候大小为...第K个最大的数，就是第（N-K）个最小的数，因此用（N-K）大小的最大堆，堆顶就是结果。
range(2,int(math.sqrt(num))): if(num%i==0): return False return True sum=0 n=...int(input()) for i in range(2,n+1): if(isPrime(i)): sum+=i print(sum)
,int right) { int i=left,j=right,temp; int p=arr[left]; /* * 是i个相遇的时候就要交换...int value:arr) System.out.print(" "+value); } } 32 68 -98 51 88 1 -98 1 32 51 68 88 寻找一个数组中第...k小的数,比如 [32 68 -98 51 88 1]中，选择第3小的数，就是32，一种想法是把数字排序，在去下标，但是可以利用快排。...,left,right); if(k-1==index) return arr[index]; else if(index>k)...+1,right); } 第3小的数为:32
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 进阶：你能尝试使用一趟扫描实现吗？...示例 1： 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2： 输入：head = [1], n = 1 输出：[] 示例 3： 输入：head...= [1,2], n = 1 输出：[1] 提示： 链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 n <= sz 题解 显然一个指针向前移动...n,步，然后两个在一起前进直到最后一个遇到末尾 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode...{ ListNode *t = head,* p = head; int i = 0; while(i n && t !
在下面的例子中，我们会进一步体会这2个限制条件。 2.递归举例 2.1 举例1 ：求n的阶乘 一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。...举例3：求第n个斐波那契数 我们先来了解一下斐波那契数： 斐波那契数列：1，1，2，3，5，8，13，21，34，55，89…… ， 以递归的方法定义：从第三项开始，每一项都等于前两项之和...就像计算第n个斐波那契数，是不适合使用递归求解的，但是斐波那契数问题的通过是使用递归的形式描述的，如下： 看到这公式，很容易诱导我们将代码写成递归的形式，如下所示： int Fib(int n) {...return 0; } 运行结果： 这里我们看到了，在计算第40个斐波那契数的时候，使用递归方式，第3个斐波那契数就被重复计算了39088169次，这些计算是非常冗余的。...所以斐波那契数的计算，使用递归是非常不明智的，我们就得想迭代的方式解决。 我们知道斐波那契数的前2个数都1，然后前2个数相加就是第3个数，那么我们从前往后，从小到大计算就行了。
题目 题目如下： 讲解算法原理 我们先说一下动态规划题目的整体做题思路： 第一步： 状态表示 什么是状态表示? 做动态规划类题目一般会定义一个dp表。这个dp表一般为一维数组或者二维数组。...然后把这个表给填满，其中的一个值就有可能是我们想要的结果。 状态表示就是dp表中的某一个值所表示的含义 状态表示是怎么来的呢？得到状态表示的途径无非有以下几种：①题目要求。②经验+题目要求。...③分析问题的过程中，发现重复的子问题 本题属于比较简单的题目，根据题目要求即可。题目中说：存在第0个数，那么第N个数就和dp数组中N下标的元素相对应。...所以本题的状态表示为：dp[i]表示第i个泰波那锲数 第二步：状态转移方程 dp[i]等于什么？这就是状态转移方程。 在本题中：dp【i】=dp【i-1】+dp【i-2】+dp【i-3】。...填写n位置时，必须保证n-1，n-2，n-3位置的数据已经获得。所以我们要从左向右进行填表。 -第五步： 返回值 题目要求什么我们就返回什么。一般都是返回dp【n】。
全文图示来源于王争的《数据结构和算法之美》 image.png 归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，讲一个大的问题分解成小的问题来解决，小的问题解决了大的问题也就解决了。...但归并排序并没有像快排那样应用广泛，因为它有一个致命的“弱点”，那就是归并排序不是原地排序算法。原因是合并函数需要借助额外的存储空间，空间复杂度为 O(n)。...快速排序不是一个稳定的排序算法。 归并排序和快速排序的区别 image.png 由上图可以发现，归并排序的处理过程是由下到上的，先处理子问题，然后合并。...快排思想求第K大元素 利用快排思想可以实现O(n)时间复杂度内求无序数组中的第 K 大元素，LeetCode题目215....数组中的第K个最大元素，具体实现如下： class Solution { public: int findKthLargest(vector& A, int k) {
泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n，请返回第 n 个泰波那契数... Tn 的值。...第一反应 斐波那契是 T(n) = T(n-1) + T(n-2) 泰波那契是 T(n) = T(n-1) + T(n-2) + T(n-3) 那求和也简单鸭，第一个数是 0，第二个数是 1，第三个数是...+ tribonacci(n-2) + tribonacci(n-3) return res }; 运行时间超出内存，递归时间复杂度 O(3n) 小结： 本题关键在于认识下泰波那契数，有概念即可...~~ 是不是对于斐波那契、爬楼梯这样的题目得心应手了呢？
第 N 个泰波那契数 泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n，请返回第...n 个泰波那契数 Tn 的值。...示例 1： 输入：n = 4 输出：4 解释： T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 示例 2： 输入：n = 25 输出：1389537 提示： 0 n...<= 37 答案保证是一个 32 位整数，即 answer 的代码： class Solution { // 其实就是斐波拉契数列的升级版 public: int tribonacci(int n) { if (n == 0)
另一个就是本题（两个题都出现了）： ? 01 PART 第K个排列 ? 题目比较绕，耐心点还是可以看懂的~加油！ 题目：给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。...按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： "123" "132" "213" "231" "312" "321" 给定 n 和 k，返回第 k 个排列。...说明： 给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 给出两个示例： 示例 1: 输入: n = 3, k = 3 输出: "213" ?...示例 2: 输入: n = 4, k = 9 输出: "2314" 02 PART 题解分析 ? 这道题目的标签标的数学和回溯算法，所以我们分别用数学和回溯的方法来解题。 ?...换句话说，就是给我们了 X 的值，让我们求 ? 。 对于 逆康托展开，我还是给一个例子。比如 nums 还是 1234，我们要找第 15 位。
public class a { //杨辉三角m层的第n个元素 public static int f(int m,int n){ if(n==0) return 1;...if(m==n) return 1; return f(m-1,n)+f(m-1,n-1); } /* public static void
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
腾讯会议
对象存储
云直播
