【面试题51：数组中重复的数字】
【面试题32：求从1到n的整数中1出现的次数】
【面试题33：把数组排成最小的数】
【面试题40：数组中只出现一次的数字】
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次，请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
思路：首先考虑仅有一个数字出现了一次，其他出现了两次的情况。利用数字异或自身为0的特点，从头到尾依次异或每个数字，结果即为只出现一次的数字。
考虑有两个数字的情况，将数组分成两组，分别利用上面的异或策略即可找出。依然从头到尾异或，其结果是两个目标数字的异或，我们选用该结果的第一个1的位置为标准进行分组（异或是指只有不同才为1）。
【面试题03：二维数组中的查找】Search a 2D Matrix II
查找二维数组中是否存在给定整数：行递增，列递增二维数组。
思路：1）选取右上角或左下角元素为判断起点，2）循环找到第一个小的列，3）根据2）的列，循环找到第一个小的行，4）判断是否为给定整数，循环2）3），5）直到边界溢出，返回false。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty())
return false;
int row = matrix.size();
int col = matrix[0].size();
int i = 0, j = col-1;
while(i<row && j>=0){
if(matrix[i][j] == target)
return true;
while(j>=0 && matrix[i][j]>target)
j--;
while(i<row && matrix[i][j]<target)
i++;
}
return false;
}
};
【面试题08：旋转数组的最小数字】Find Minimum in Rotated Sorted Array II
题目： 把一个数组最开始的若干个元素搬到数组的末尾， 我们称之数组的旋转。输入一个递增排序的数组的一个旋转， 输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2 ｝为｛ 1,2,3,4,5}的一个旋转，该数组的最小值为1
思路： 数组分两部分，前部分大于后部分，且最小值位于后部分的第一个元素。采用二分查找的方式，若中点大于起点，则中点位于前部分，更新起点为此时的中点，反之位于后部分，更新终点为此时的中点，最后终点起点相差1时，取终点位置即为最小值。
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.empty()) return -1;
int begin = 0;
int end = nums.size()-1;
if(nums[begin]<nums[end]) return nums[begin];//特殊情况：旋转数组本身为排序数组
while(begin <= end){
if(begin == end || (begin+1 == end)) return nums[end];
int middle = (begin+end)/2;
if(nums[middle]==nums[begin] && nums[middle]==nums[end])
//特定情况，只能采用顺序查找了。如[10111]
return sequenceFindMin(nums,begin,end);
if(nums[middle]>=nums[begin])
begin = middle;
if(nums[middle]<=nums[end])
end = middle;
}
}
int sequenceFindMin(vector<int>& nums,int begin,int end){
int min = nums[begin];
for(int i = begin+1;i <= end;i++){
if(min>nums[i]) min = nums[i];
}
return min;
}
};
【面试题11：数值的整数次方】 Pow(x, n)
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路：递归思想。
class Solution {
public:
double myPow(double x, int n) {
if(x == 0.0) return 0.0;
if(n == 0) return 1.0;
if(n == 1) return x;
unsigned int absn = n<0? -n: n;
double result = myPow(x,absn>>1);
result *= result;
if(n%2) result *= x;
return n<0? 1.0/result:result;
}
};
【面试题12：打印1 到最大的n 位数】
题目：输入数字n，按顺序打印出1到最大的n位十进制数。比如输入3，则打印1,、2、3、一直到最大的3位数999。
思路：n位所有十进制数是0到9的全排列。打印时排在前面的0不打印。递归思想，每一位都有九种可能，然后设置下一位，设置到最后一位数，递归结束打印即可从小到大打印出所有十进制数。
void printtomax2(int n)
{
if (n <= 0) return;
char *number = new char[n + 1];
number[n] = '\0';
printnumber(number, n, -1);//调用递归方法
}
void printnumber(char *number, int n, int index)
{//判断最后一位数字是否已经赋值，是则打印
if (index == n - 1){
Print(number);
return;
}
//否则递归赋值，直到到达最后一位
//从下一位开始，0-9依次赋值
for (int i = 0; i<10; i++){
number[index + 1] = '0' + i;
printnumber(number, n, index + 1);
}
}
//打印number中存的数字
void Print(char * number)
{
int length = strlen(number);
int i = 0;
while (i < length && number[i] != '0')
i++;
while (i++ < length)
cout << number[i];
cout << " ";
}
【面试题14：调整数组顺序使奇数位于偶数前面】
题目:输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位予数组的后半部分
思路：快排思想，时间复杂度O(n).
void ReOrderOddEven_2(int *pdata,unsigned int length){
if(pdata==NULL || length<=0)
return;
int *pBegin=pdata;
int *pEnd=pdata+length-1;
while(pBegin<pEnd){
while(pBegin<pEnd && (*pBegin&0x1)!=0)
pBegin++;
while(pBegin<pEnd && (*pEnd&0x1)==0)
pEnd--;
if(pBegin<pEnd){
int tmp=*pBegin;
*pBegin=*pEnd;
*pEnd=tmp;
}
}
}
【面试题20：顺时针打印矩阵】Spiral Matrix
题目：输入一个矩阵，按照从外向里以顺时针的顺序依次扫印出每一个数字.
思路：分析清楚各情形的条件。1)从左往右，必备，2）从上往下，行数大于2；3）从右往左，至少两行两列；4）从下往上，至少三行两列。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix){
vector<int>printVector;
if(matrix.empty()) return printVector;
int rows = matrix.size();
int cols = matrix[0].size();
int start = 0;
while(cols>start*2 && rows > start*2){
int endX = cols - 1 - start;
int endY = rows - 1 - start;
for(int i = start;i<=endX ;i++){
printVector.push_back(matrix[start][i]);
}//from right to left
if(endY>start){
for(int i = start+1; i<= endY ;i++)
printVector.push_back(matrix[i][endX]);
}//from up to down
if(endX>start && start< endY){
for(int i = endX-1; i>= start; i--)
printVector.push_back(matrix[endY][i]);
}//from left to right:
if(endX>start && endY>start+1){
for(int i = endY-1; i> start; i--)
printVector.push_back(matrix[i][start]);
}//from down to up
start++;
}
return printVector;
}
};
【面试题29：数组中出现次数超过一半的数字】Majority Element
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
思路：超过长度一半，则中位数一定是该数字。快排思想,时间复杂度O(n)。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int index = Partition(nums,0,nums.size()-1);
int middle = nums.size()/2;
while(index != middle)
index = index>middle? Partition(nums,0,index-1):Partition(nums,index+1,nums.size()-1);
return nums[middle];
}
int Partition(vector<int> &number,int begin, int end){
int random = number[begin];
while(begin<end){
while(begin<end && number[end]>=random)
end--;
number[begin] = number[end];
while(begin<end && number[begin]<=random)
begin++;
number[end] = number[begin];
}
number[begin] = random;
return begin;
}
//利用map统计元素个数
/*int majorityElement(vector<int>& nums) {
map<int,int>mapping;
int len = nums.size();
for(int i = 0; i < len; i++){
if(++mapping[nums[i]]>(len/2)) return nums[i];
}
}*/
};
【面试题30：最小的k个数】
题目： 输入n个整数，找出其中最小的k个数。
思路：基于快排分治思想，时间复杂度O(n),输入数组会被改变。
void GetLeastKNum(int *input,int n,int *output,int k)
{
if(input==NULL || n<=0 || k<=0) return;
int start=0;
int end=n-1;
int index=Partition(input,start,end);
while(index!=k-1)
index=index<k-1 ? Partition(input,index+1,end) : Partition(input,start,index-1);
for(int i=0;i<k;i++)
output[i]=input[i];
//其中，output[k-1]就是第k小的数
}
【面试题64：数据流中的中位数】
题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
思路：采用堆，均匀将数据流分成两个堆，左边为最大堆，右边是最小堆。中位数去中间值。
注意：需要分析清楚如何交替insert数据到堆中，以一种情况为例，数据流中的偶数个数据插入最小堆，奇数个数据插入最大堆。最后，数据流若为偶，则中位数为(min[0]+max[0])/2;若为奇，则为min[0] (最小堆中多一个数据，例如012,02在min中，1在max中)。ps：insert数据时可能会产生不合适的情况。
头文件是#include <algorithm>
一般用到这四个：make_heap()、pop_heap()、push_heap()、sort_heap();
（1）make_heap()构造堆
void make_heap(first_pointer,end_pointer,compare_function);
默认比较函数是(<)，即最大堆。
函数的作用是将[begin,end)内的元素处理成堆的结构
（2）push_heap()添加元素到堆
void push_heap(first_pointer,end_pointer,compare_function);
新添加一个元素在末尾，然后重新调整堆序。该算法必须是在一个已经满足堆序的条件下。
先在vector的末尾添加元素，再调用push_heap
（3）pop_heap()从堆中移出元素
void pop_heap(first_pointer,end_pointer,compare_function);
把堆顶元素取出来，放到了数组或者是vector的末尾。
要取走，则可以使用底部容器（vector）提供的pop_back()函数。
先调用pop_heap再从vector中pop_back元素
（4）sort_heap()对整个堆排序
排序之后的元素就不再是一个合法的堆了。
class Solution {
public:
void Insert(int num){
if(((max.size()+min.size())%2) == 0){
if(max.size()&& num<max[0]){
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());// 调整最大堆
num = max[0];
pop_heap(max.begin(),max.end(),less<int>());
max.pop_back();//在容器中删除
}
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
}
else{
if(min.size()>0 && num>min[0]){
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
num = min[0];
pop_heap(min.begin(),min.end(),greater<int>());
min.pop_back();
}
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());
}
}
double GetMedian()
{
if(((max.size()+min.size())&1) == 0)
return (max[0]+min[0])/2.0;
else
return min[0];
}
private:
vector<int>min;
vector<int>max;
};
【面试题31：连续子数组的最大和】
题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
思路：遍历一遍，两点考虑：1）累加的更新；2）最大和的更新。
累加思想：当前一个和是负数了，接下来累加就比当前值更小了，这时抛弃前面的累加，从当前数值开始往下遍历，即累加和更新为当前值。
#include<limits.h>//INT_MAX与INT_MIN的头文件
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.size() == 0) return 0;
int sum = 0;
int max = INT_MIN;//0x80000000;
//给int类型赋值的话，0X7FFFFFFF代表最大值，0X80000000代表最小值
//NT_MAX 代表最大值， INT_MIN 代表最小值
for(int i = 0;i<array.size();i++){
if(sum<=0) sum = array[i];
else sum += array[i];
if(sum>max) max = sum;
}
return max;
}
//动态规划思想，sum[i] = sum[i-1]<=0 ? array[i]:sum[i-1]+array[i];
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.size() == 0) return 0;
int max = INT_MIN;
int sum[array.size()];
sum[0] = array[0];
for(int i = 1;i<array.size();i++){
if(sum[i-1]<=0) sum[i] = array[i];
else sum[i] = sum[i-1]+array[i];
if(sum[i]>max) max = sum[i];
}
return max;
}
};
【面试题44：数字序列中某一位的数字】
题目：Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
思路：三个定位：1）首先定位n在哪个区间，并更新n；2）定位这个区间的哪个整数；3）最后定位这个整数的哪个数字。ps:注意第几个与数组角标的问题。
class Solution {
public:
int findNthDigit(int n) {
if(n <= 0) return 0;
if(n>std::pow(2,31)) return 0;
int bit = 1;
while(n>bit*9*std::pow(10,bit-1)){
n -= bit*9*std::pow(10,bit-1);
bit++;
}//第一个定位，并更新n
int existnumber = std::pow(10,bit-1)+ (n-1)/bit;//第二个定位
return to_string(existnumber)[(n-1)%bit]-'0'; //第三个定位
}
}
【面试题47：礼物的最大价值】Minimum Path Sum
题目：Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
思路：典型的动态规划问题，f(i,j) = f(i-1,j)+f(i,j-1),只能通过两种途径到达(i,j)。ps: 主要i=0和j=0时的比较。
#include<limits.h>
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.size() == 0) return 0;
int minSum[grid.size()][grid[0].size()];
/*申请动态数组：
int** minSum = new int* [grid.size()];
for (int i=0; i<grid.size(); i++)
minSum[i]= new int[grid[0].size()];
//释放内存：
for (int i=0; i<grid.size(); i++)
delete[] minSum[i];
delete[] minSum;*/
for (int i=0; i<grid.size(); i++){
for(int j = 0;j<grid[0].size();j++){
if(i== 0&&j == 0) minSum[0][0] = grid[0][0];
else{
int right = i>0 ?minSum[i-1][j]:INT_MAX;
int down = j>0 ? minSum[i][j-1]:INT_MAX;
minSum[i][j] = std::min(right,down)+grid[i][j];
}
}
}
return minSum[grid.size()-1][grid[0].size()-1];
}
};
【面试题34：丑数】
题目：我们把只包含因子2、3 和5 的数称作丑数（Ugly Number）。求从小到大的顺序的第1500个丑数。
思路：用空间换取时间，定义一个排序的丑数数组。需要解决如何排序，首先需要找到三个指针，分别指向当前数组中x2，x3，x5后大于当前值的第一个丑数。然后取x2，x3，x5后的最小值作为排序数组中下一个丑数。
class Solution {
public:
int GetUglyNumber_Solution(int index) {
if(index<=0) return 0;
int UglyNumber[index];
UglyNumber[0] = 1;
int *pMultiply2 = UglyNumber;
int *pMultiply3 = UglyNumber;
int *pMultiply5 = UglyNumber;
int curIndex = 1;
while(curIndex<index){
UglyNumber[curIndex] = Min(*pMultiply2*2,*pMultiply3*3,*pMultiply5*5);
while(*pMultiply2*2 <= UglyNumber[curIndex])
pMultiply2++;
while(*pMultiply3*3 <= UglyNumber[curIndex])
pMultiply3++;
while(*pMultiply5*5 <= UglyNumber[curIndex])
pMultiply5++;
curIndex++;
}
return UglyNumber[index-1];
}
int Min(int num1,int num2,int num3) {
int min = std::min(num1,num2);
return std::min(min,num3);
}
};
【面试题36：数组中的逆序对】
【面试题38：在排序数组中查找数字-数字在排序数组中出现的次数】Find First and Last Position of Element in Sorted Array
题目：数字在排序数组中出现的次数。Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
思路：主要问题是在排序数组中找到目标值的首次出现的位置和最后出现的位置。采用二分查找，实现O(logn)时间复杂度。次数即为两个位置间的元素个数。
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int>position;
if(nums.size() != 0){
int firstPos = SearchFirstValue(nums,target,0,nums.size()-1);
int lastPos = SearchLastValue(nums,target,0,nums.size()-1);
position.push_back(firstPos);
position.push_back(lastPos);
}
else{
position.push_back(-1);
position.push_back(-1);
}
return position;
}
int SearchFirstValue(vector<int>& nums, int target, int begin, int end) {
if(begin> end) return -1;
int middle = (begin+end)/2;
if(nums[middle] == target){
if((middle>=1 && nums[middle-1] != target) || middle == 0 )
return middle;
end = middle-1;
}
else if(nums[middle] > target)
end = middle-1;
else
begin = middle+1;
return SearchFirstValue(nums,target,begin,end);
}
int SearchLastValue(vector<int>& nums, int target, int begin, int end) {
if(begin> end) return -1;
int middle = (begin+end)/2;
if(nums[middle] == target){
if((middle<nums.size()-1 && nums[middle+1] != target) || middle == nums.size()-1)
return middle;
begin = middle+1;
}
else if(nums[middle] < target)
begin = middle+1;
else
end = middle-1;
return SearchLastValue(nums,target,begin,end);
}
};
【面试题57：和为s的数字】
题目：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思路：利用递增特点，首尾两个指针遍历数组，时间复杂度O(n)。
拓展：和为s的连续正数序列。相同的思路：两个指针逐步增加。
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
int ahead = 0;
int behind = array.size()-1;
while(ahead<behind){
int temp = array[ahead] + array[behind];
if( temp == sum)
return {array[ahead], array[behind]};
else if(temp < sum)
ahead++;
else
behind--;
}
return {};
}
vector<vector<int> > FindContinuousSequence(int sum) {
if(sum<3) return {};
int small = 1;
int big = 2;
vector<vector<int>>Result;
while(big <= (sum+1)/2){//big+(big-1)<=sum,至少有两个数
int temp = (small+big)*(big-small+1)/2;
if(temp == sum){
vector<int>result;
for(int i=small; i<=big; i++)
result.push_back(i);
Result.push_back(result);
big++;
}
else if(temp < sum)
big++;
else
small++;
}
return Result;
}
};
【面试题63：股票的最大利润】Best Time to Buy and Sell Stock
题目：已知一个数组的第 i 个元素是给定股票在第 i 天的价格。设计一个算法来找到买卖该股票一次最大的利润。
拓展：Best Time to Buy and Sell Stock II 多次买卖股票的最大利润。不能同时参与多个交易（必须在再次购买前出售股票）。
思路：交易一次：每次找到第i天之前i-1天的最小值，差值最大即为最大利润。多次交易：低买高卖一次不漏，即累加相隔两天的增量。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) return 0;
int min = prices[0];
int maxProfit = 0;
for(int i=1; i<prices.size(); i++){
if(prices[i]<min)
min = prices[i];
int profitDiff = prices[i] - min;
if(profitDiff>maxProfit)
maxProfit = profitDiff;
}
return maxProfit;
}
//多次交易的最大利润。
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
for(int i=1; i<prices.size();i++)
maxProfit += std::max(0, prices[i]-prices[i-1]);
return maxProfit;
}
};
网易-个人所得税
问题：1）根据工资计算税费；2）根据税费计算工资
思路：1）采用二位数组，循环累加；2）采用二分查找。
int sal2tax(int salary) {
salary -= 2000;//计算应扣税部分
double tax = 0;
double sal[][2] = {
{0, 0.05},
{500, 0.1},
{2000, 0.15},
{5000, 0.2},
{20000, 0.25},
{40000, 0.3},
{60000, 0.35},
{80000, 0.4},
{100000, 0.45}
};
for(int i = 0; i < 8; ++i) {
if(salary < sal[i][0]) break;
tax += (salary> sal[i + 1][0]) ? (sal[i + 1][0] - sal[i][0]) : (salary - sal[i][0])) * sal[i][1];
}
return int(tax+0.5);
}
int tax2sal(int tax){
int sal_h = 80000;
int sal_l = 0;
while(sal_h>sal_l){
int mid = (sal_h + sal_l)/2;
if(sal2tax(mid) == tax)
return mid;
if(sal2tax(mid)>tax)
sal_h = mid-1;
else
sal_l = mid+1;
}
return -1；
}
好未来-求和
题目：输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来
输入描述:
每个测试输入包含2个整数,n和m
输出描述:
按每个组合的字典序排列输出,每行输出一种组合
思路：涉及到递归遍历问题，将1到n的排列组合全部遍历，然后设置条件打印。具体地，vector压入i，m将更新为m-i，然后在i+1之后找寻m-i。
又类似于寻找路径，遍历排列组合实际形成了一棵树，然后需要找到路径和为m的路径。而且，结点i的子结点是i+1之后的所有结点。
//递归遍历框架：打印所有1到n的排列组合。
void resursive(vector<int>&combine,int num) {
//设置遍历过程的操作，可以是全部打印，可以是特定条件下的打印
for (int j = 0; j < combine.size(); j++)
cout << combine[j];
cout << endl;
//以树为例
for (int i = num; i < 4; i++) {
combine.push_back(i); // 保存父结点
resursive(combine,i+1); //遍历该父节点的的子树。
combine.pop_back();//弹出结点，遍历该父节点的其他兄弟树。
}
}
int main() {
vector<int>combine;
resursive(combine,1);
输入
5 5
输出
1 4
2 3
5
#include<iostream>
#include<vector>
using namespace std;
void traverse(vector<int>&combine,int num, int n,int m){
if(m == 0){
for(int j=0; j<combine.size();j++)
j==0 ? cout<<combine[j] : cout<<' '<<combine[j];
cout<<endl;
}
for(int i=num; i<=n && i<=m; i++){
combine.push_back(i);
traverse(combine,i+1,n,m-i);
combine.pop_back();
}
}
int main(){
int n,m;
vector<int>combine;
while(cin>>n>>m){
traverse(combine,1,n,m);
}
return 0;
}
好未来-n个数里最小的k个
找出n个数里最小的k个
输入描述:
每个测试输入包含空格分割的n+1个整数，最后一个整数为k值,n
不超过100。
输出描述:
输出n个整数里最小的k个数。升序输出
注意: 题目要求排序打印。1）直接sort排序输出，2）分治找出k个数，然后排序输出
输入
3 9 6 8 -10 7 -11 19 30 12 23 5
输出
-11 -10 3 6 7
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
int Partition(vector<int> &number,int begin, int end){
int random = number[begin];
while(begin<end){
while(begin<end && number[end]>=random){
end--;
}
number[begin] = number[end];
while(begin<end && number[begin]<=random){
begin++;
}
number[end] = number[begin];
}
number[begin] = random;
return begin;
}
int main(){
int input;
vector<int>number;//获取符号，不会忽略换位符\n，空格之类
while(cin>>input){
number.push_back(input);
}//这样输入，题目也能运行
int k = number.back();
number.pop_back();
int index = Partition(number,0, number.size()-1);
while(index != k-1){
index = index > k-1 ? Partition(number,0,index-1)
:Partition(number,index+1,number.size()-1);
}
//直接用algorithm中的sort
sort(number.begin(),number.begin()+k);
for(int i=0; i<k; i++){
i<k-1 ? cout<<number[i]<<' ': cout<<number[i]<<endl;
}
}
补充sort函数：
时间复杂度为n*log2(n)
#include <algorithm>
bool great)(int a,int b)
return a>b;
bool les(node a, node b)
return a.val > b.val;
sort(vec.begin(),vec.end(),great); //升序，默认
sort(vec.begin(), vec.end(),les); //降序
美团-拼凑钱币
题目：给你六种面额 1、5、10、20、50、100 元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数。
思路：动态规划。二维数组dp[i][sum]表示用前i种纸币拼凑钱币sum。
公式
#include<iostream>
using namespace std;
int main() {
int coins[6] = {1,5,10,20,50,100};
int n;
while (cin >> n) {
long dp[6][n+1];
for(int i=0; i<6; i++){
for(int j=0;j<=n; j++)
dp[i][j] = 0;
} //初始化dp
for(int j=0;j<=n;j++)
dp[0][j]=1;//只使用第一个钱币1时，组合数都是1.
for(int i=1;i<6;i++){
for(int j=1;j<=n;j++){
for(int k=0; k<=j/coins[i]; k++)
dp[i][j] += dp[i-1][j - k*coins[i]];
}
}
cout << dp[5][n] << endl;
}
return 0;
}
网友评论