g*********e
发帖数: 14401 | 1 void closestSum(int arr[], int n, int t){
int prev=0;
int post=0;
int curSum=arr[0];
int resPrev, resPost;
int closeSum=arr[0];
while(1){
if(curSum==t){
resPrev=prev;
resPost=post;
break;
}
else if(curSum
if(prev==n-1)
break;
else{
prev++;
curSum+=arr[prev];
}
}
else{
curSum-=arr[post+... 阅读全帖 |
|
f****4
发帖数: 1359 | 2 int findMaximumSeq(int *arr, int size, int &start, int & end){
int curSum = 0, maxiSum = 0;
start = 0; end =0;
for(int i = 0, j = 0; j < size; j++)
{
curSum += arr[j];
if (curSum > maxiSum){
maxiSum = curSum;
start = i;
end = j;
}else if (curSum < 0){
i = j + 1;
curSum = 0;
}
}
return maxiSum;
}
void testFindMaximumSeq(){
int arr[] = {1, -2, -3, 4, 5, 7, -6};
int |
|
B*******1
发帖数: 2454 | 3 How about this:
void printlist(vector &result)
{
for (int i = 0; i < result.size(); i++)
cout << result[i]->element << " ";
cout << " " << endl;
}
void FindPaths_sum(Node_t* root,int curSum, int target, vector &v)
{
if(root==NULL) return;
curSum += root->element;
if (curSum == target)
printlist(v);
v.push_back(root->left);
FindPaths_sum(root->left,curSum ,target, v);
v.pop_back();
v.push_back(root->right);
FindPaths_sum(ro... 阅读全帖 |
|
r**h
发帖数: 1288 | 4 题目不要求subarray是连续的吧
DFS，就是根据每个节点（取或者不取）两种情况向后搜索并记录当前的解。由于题目
里面提到数组中所有元素都是正数，因此如果当前的和已经大于sum那么就可以直接剪枝
void findSubSetSum(int *pArr, int *pSub, int nSize, int nIndex, int curSum,
int nSum){
//剪枝
if(curSum+pArr[nIndex] > nSum)
return;
//找到解
if(curSum+pArr[nIndex] == nSum){
pSub[nIndex] = 1;
printResult(pArr, pSub, nIndex);
pSub[nIndex] = 0;
return;
}
//继续向后搜索，分两种情况
if(nIndex < nSize-1){
pSub[nIndex] = 1;
findSubSetSum(pArr, pSub, nSize, nIndex+1, curSum+pArr[nIndex... 阅读全帖 |
|
g**********y
发帖数: 14569 | 5 public class SplitNumber {
private int count;
public int countWays(int sum, int[] numbers) {
int N = sum/numbers[0] + 1;
int[] a = new int[N];
count = 0;
for (int i=0; i
a[0] = numbers[i];
split(sum, numbers, a, i, 1, a[0]);
}
return count;
}
private void split(int sum, int[] numbers, int[] a, int low, int len,
int curSum) {
if (curSum == sum) {
count++;
... 阅读全帖 |
|
b******7
发帖数: 92 | 6 在[0,n-1]间查找，再减去多余的部分
int adjust(int A[],int n, int b)
{
if(n <= 0 || b < 0) return -1;
sort(A,A+n);
int index = -1;
int cursum = -1;
int low = 0, high = n-1;
while(low <= high)
{
int mid = low + (high - low)/2;
int sum = 0;
for(int i = 0; i < n; i++)
{
sum += min(A[i],A[mid]);
}
if(sum == b) return A[mid];
else if(sum > b)
{
index = mid;
cursum = sum;
high =... 阅读全帖 |
|
b******7
发帖数: 92 | 7 在[0,n-1]间查找，再减去多余的部分
int adjust(int A[],int n, int b)
{
if(n <= 0 || b < 0) return -1;
sort(A,A+n);
int index = -1;
int cursum = -1;
int low = 0, high = n-1;
while(low <= high)
{
int mid = low + (high - low)/2;
int sum = 0;
for(int i = 0; i < n; i++)
{
sum += min(A[i],A[mid]);
}
if(sum == b) return A[mid];
else if(sum > b)
{
index = mid;
cursum = sum;
high =... 阅读全帖 |
|
d*****1
发帖数: 263 | 8 问题虽然解决了。但是，还是没有彻底明白。
问题是：Sum Root to Leaf Numbers (见链接)
http://oj.leetcode.com/problems/sum-root-to-leaf-numbers/
下面的3个方案，都是用了递归.
方案1： 利用了一个static 变量存储结果。
public class Solution{
public static int totalSum = 0;
public int sumNumbers(TreeNode root) {
if (root != null) {
getSum(root, 0);
}
return totalSum;
}
private void getSum(TreeNode node, int upperSum) {
if (node.left == null && node.right == null) {// find leaf
totalSum +... 阅读全帖 |
|
l******s
发帖数: 3045 | 9 C#回溯法，未测试。
public IList> MNCombination(int m, int n)
{
IList> result = new List> result();
combination(result, new List(), 0, m, n);
return result;
}
private void combination(IList> result, IList curLst, int
curSum, int m, int n) //m objects, n buckets
{
if(n == 0 && curSum == m) result.Add(new List(curLst));
else if (n > 0)
{
for(int i = curLst.Count == 0 ? 0 : curLst[curLst.Count - 1]; i +
curSum <= m; i... 阅读全帖 |
|
i*********7
发帖数: 348 | 10 抛砖引玉一下
这是我做的大数乘法
void bigmultiply(string num1, string num2){
vector result(num1.size()+num2.size(), 0);
int carry = 0;
for(int i = num2.size() - 1; i >= 0; i--){
carry = 0;
for(int j = num1.size() - 1; j >= 0; j--){
int i1 = num1[j] - '0';
int i2 = num2[i] - '0';
int curdig = (i1 * i2) % 10;
int nextbit = i1 * i2 / 10;
int cursum = curdig + carry + result[i + j + 1];
carry = cursum/10 + nextb... 阅读全帖 |
|
S****G
发帖数: 3 | 11 关于输赢那个题目，根据版上大牛们的讨论，写了code大家可以一看，主要用了zemel
定理（也可以不用但code会比较messy）。此外，博弈树怎么做这个题，谁有相关资料
可以发来看看。
http://feisyr.blogspot.com/2015/04/zermelos-theorem-game-theory
bool canW(int val1, std::vector &available, int curSum, int & desT){
if (val1 + curSum >= desT) return true;
else{
bool theOtherWin = false;
for (int val2 = 1; val2 < available.size(); ++val2){
if (!available[val2]) continue;
available[val2] = false;
theOtherWin = the... 阅读全帖 |
|
c*****m
发帖数: 271 | 12 这种情况的话，在curSum < target时，不能把curSum重置０吧？比如target = 10,
array=[-1, 100]，最大长度是２，而不是１ |
|
c*****m
发帖数: 271 | 13 curSum < target的时候怎么操作呢？ |
|
