首页 > 试题广场 > 给定一个非负整数组,给出乘积和小于K的子串数目。
[问答题]

给定一个非负整数组,给出乘积和小于K的子串数目。

Input : [1, 2, 3, 4]
          k = 10
Output :11
The subsequences are {1}, {2}, {3}, {4},
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4},
{1, 2, 3}, {1, 2, 4}
 
Input  : [4, 8, 7, 2]
      k = 50
Output : 9

public class Main {   public static int getNumberOfMultiplySmallerThanK(int[] array, int k, int index, int multiply) {  //递归退出条件  if (index >= array.length) {  return multiply < k ? 1 : 0;  }   //索引为index的数要  return getNumberOfMultiplySmallerThanK(array, k, index + 1, multiply * array[index]) + //索引为index的数不要  getNumberOfMultiplySmallerThanK(array, k, index + 1, multiply);  }   public static void main(String[] args) {  System.out.println(getNumberOfMultiplySmallerThanK(new int[]{1, 2, 3, 4}, 10, 0, 1) - 1);  System.out.println(getNumberOfMultiplySmallerThanK(new int[]{4, 8, 7, 2}, 50, 0, 1) - 1);  } }
发表于 2019-07-24 17:01:55 回复(0)
import itertools
a=input()
b=input()
a=list(a)
count=0 lt=[] for j in range(len(a)):
    l=j+1  for i in itertools.combinations(a,l):
        lt.append(i) for i in lt:
    y = 1   for k in i:
            y=1*y*int(k)  if y<b:
            count=count+1 print count

编辑于 2019-10-09 15:32:29 回复(0)
01背包
//dp[i] 表示积为i的组合有dp[i]个
vector<int> dp(k, 0); dp[1]=1;
bool flag=0;
for (int i = 0; i < n; i++) {
    // 先不考虑1
    if(data[i]==1) {
        flag = 1;
        continue;
    }
    for (int j = k-1; j>0; j--) {
        if (dp[j] > 0 && j * data[i] < k ) {
            dp[j * data[i]] += dp[j];
        }
    }
}   
int res = accumulate(dp.begin()+2, dp.end(), 0); 
if(flag) // 如果有1
    res = 2*res+1;


发表于 2019-08-06 17:27:00 回复(0)
用递归 每次计算乘积值 最后判断 我这里把结果也存了并且输出
#include <iostream>
#include <vector>
#include<string.h>
using namespace std;
void  arraysum(vector<int>&a,vector<int>temp,int c,int k,int len,vector<vector<int> >&res)
{
if(len==a.size())
{
    if(c<k&&!temp.empty())
        res.push_back(temp);
return ;
}

arraysum(a,temp,c,k,len+1,res);
temp.push_back(a[len]);
c=a[len]*c;
arraysum(a,temp,c,k,len+1,res);
}
int main()
{
    vector<int>a;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_back(4);
    int len=0;
    int c=1;int k=10;
    vector<int>temp;
vector<vector<int> > res;
arraysum(a,temp,c,k,0,res);
    for (int j = 0; j < res.size(); j++)     {         cout << endl;         for (int k = 0; k< res[j].size(); k++)         {             cout << res[j][k] << "     ";         }     }
}

发表于 2019-07-27 20:28:16 回复(0)

热门推荐