J****a
发帖数: 15 | 1 Based on ibread's method, I think this is easy to understand, welcome any
comments.
Example: [-2, 2, -1, 3, -6] and k=3
For step 2
1) 还是计算sum[i]。O(n) sum_origianl=(-2,0,-1,2,-4)
2)排序，排的时候以sum[i]为key，同时带上下标i。O(nlgn)
sum=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)]
3)给排好序的 arrary, every i , sum[i]-k; O(n)
(in order to在排序好的sum数组中找 sum[j] 正好 <= sum[i]-k, so I create a
sumnew)
Sumnew=[(-7,4),(-5,0),(-4,2),(-3,1),(-1,3)], next step is 在sum中找 最小下
标。
4)找min-index[i]. O(n)
a=0, b=0;
Temp=n+1; (p... 阅读全帖 |
|
b*m
发帖数: 34 | 2 似乎现在的解法都不太完美。
ihasleetcode 的算法有点诡异。
Using binary search, we found the smallest j that satisfies the condition
sorted_cum[i]+k >= sorted_cum[j]
这里 为什么用这个不等式sorted_cum[i]+k >= sorted_cum[j]
使你打错了造成了我们的误解吗？
假设i〉j s[i]-s[j]>=k 才是我们要的， 还是 这里有什么深意呢？求解释？
然后你是要找刚好满足条件的，这个binary search 似乎不能保证找的的是刚好满足条
件的临界位置，只能保证满足条件，所以这里要找到刚好满足条件的那个按你的算法似
乎还是要n*n。
然后
你这里的
min_index[] = {1, 1, 1, 1, 1, 1, 1, 6, 6, 10, 10}
max_index[] = {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10}
的实际物理意义是当前sorted cum array 当前对应的坐标后的元素中... 阅读全帖 |
|
w********p
发帖数: 948 | 3 终于有人和我想的差不多
第二题O（n) time 和O(n) spance 就可以了
不过要注意K>0和K<0算法有些不一样。
case 1: K>=0
/*working on array of sum(i)
/* sum(i) defintion: sum of all element from 0 to i. ex: sum(2) = sum(1)
+ number[2] = number[0]+ number[1]+ number [2] */
1. get new array sum[n]: from sum(0) to sum(n) O(n) time and O(n) space
2. find the max sum which index is j O(n) time
3. check from left side of sum(j), find the min of sum array which index is
k
4 .If the min >= 0, all number array [0-j] are the sub array
... 阅读全帖 |
|
S**I
发帖数: 15689 | 4 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 5 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
s******n
发帖数: 3946 | 6 这个题目能用DP的关键是每个数都大于等于0：
总和为sum
A(i,Y) 表示前i项选任意个之和小于Y且与Y最接近的差。
所以我们要求：A(N, sum/2)
递推:
A(i, Y) = min(A(i-1, Y), A(i-1, Y-a[i]))
代码
============================================
dp[N][SUM/2];
for (int i=1; i
for (int j=0; j
dp[i][j]=MAX_INT;
for (int i=0; i
int calculate(int i, int sum)
{
if (dp[i,sum]!=MAX_INT) return dp[i,sum];
assert(i>0);
int solution1 = calculate(i-1, sum);
int solution2 = MAX_INT;
if (Y>a[i]) solution2 = calculate(i... 阅读全帖 |
|
s***c
发帖数: 1926 | 7 public class Solution {
public int findMaxLengthSubArrayEqY(int[] A, int y) {
if(A == null || A.length == 0) return 0;
int sum = 0;
int maxLen = 0;
// key=sum(0:i)+y; value=i
Map map = new HashMap();
map.put(y, -1);
for(int i = 0; i < A.length; i++) {
sum += A[i];
if(map.containsKey(sum)) {
int len = i - map.get(sum);
... 阅读全帖 |
|
g****g
发帖数: 1828 | 8 In probability theory, the normal (or Gaussian) distribution, is a
continuous probability distribution that is often used as a first
approximation to describe real-valued random variables that tend to cluster
around a single mean value. The graph of the associated probability density
function is “bell”-shaped, and is known as the Gaussian function or bell
curve:[nb 1]
f(x) = \tfrac{1}{\sqrt{2\pi\sigma^2}}\; e^{ -\frac{(x-\mu)^2}{2\sigma^2}
},
where parameter μ is the mean (location of the pe... 阅读全帖 |
|
R*********r
发帖数: 1855 | 9 应该有个前提：a，A>0
x>0且充分小时有e^(-x-x^2)<1-x
因此m，n（m
B(m-1)exp(-A\sum[1/i^a,{i,m,n]-A^2\sum[1/i^(2a),{i,m,n]
sum[1/i^a,{i,m,n])
地球人都知道a>1时 无穷乘积B(n)收敛。
a<1时B(n)
积分判别法知\sum exp(-A/(1-a)*n^(1-a))收敛，因此\sum B(n)收敛。
a=1时B(n)必定发散到零。 A<=1时，B(n)收敛是错的。
由\sum B(n)~\sum const*e^{-A\sum 1/i)~const*\sum n^(-A)即得\sum B(n)敛散性。
细节自己补充。 |
|
g***s
发帖数: 3811 | 10 sum(i)表示到第i个元素的和。O(n)可以做。
用二分对i来找到一个位置p，使得sum(p)可以满足题意，但sum(p-1)不能。 O(nlogn)
例如 2，2，2，2，2，5，5，5，1，1，1，1，1 k=3
那么这个p=5 sum(5)=10,sum(4）=8不行
然后对 sum（p-1) -> sum(p)进行二分。可以知道，sum(p)-sum(p-1)的值就是a[p]，
小于等
于max(a[])
所以，负责度是O(nlogn + n log max(a[])
对于DP，因为
dp[k-1][n] 对于n是一个单调递增的函数。我们用二分来找那个max就可以了。
所以是 O(NKLogN)
另外，空间复杂度可以用O(n)因为任何dp函数，k都只和dp[k-1]相关。所以，用两个长
度为n
的array就可以了。（另外还要一个sum（i）的数组，那么空间是3×n） |
|
e***s
发帖数: 799 | 11 来自主题: JobHunting版 - 问个编程题 #include
#include
#include
#include
#include
using namespace std;
vector FindSet(unsigned int sum, vector &coinset)
{
vector rtn;
int *Min = new int[sum + 1];
vector *Combination = new vector[sum + 1];
Min[0] = 0;
unsigned int i;
unsigned int j;
for(i = 1; i <= sum; i++)
{
Min[i] = INT_MAX;
}
for(i = 1; i <= sum; i++)
{
for(j = 0; j < co... 阅读全帖 |
|
H***e
发帖数: 476 | 12 编了下method 1(swanswan说的 ) and method 2(我说的）,
没太狂调。
/*
* Given an array of integers, find out number of ways in which you can
* select increasing subsequences of length K(K<=n).e.g.array is 1 4 6 2
5 &
* K=3 then the answer is : 1 4 5, 1 2 5,1 4 6, so total is 3
*/
// define M[i,k] is the # of k-length sequences that ends at i, i.e.
that sunseq ends at i.
public int numOfIncreasingSubSeq(int[] data, int K) {
// boundary
if (data == null || data.length... 阅读全帖 |
|
f*******t
发帖数: 7549 | 13 写了很长的代码，感觉不太对，如果一个数组里面有重复的数，应该会输出重复的组合
，但程序实际运行结果貌似是没有，不知道为什么。
#include
#include
#include
#include
#include
#define N 5
using namespace std;
struct combination {
int indices[N];
int sum;
combination();
bool operator<(const combination& c) const;
void operator=(const combination& c);
bool operator() (const combination& c) const;
bool operator== (const combination& c) const;
};
combination::combination()
{
sum = 0;
f... 阅读全帖 |
|
f*********m
发帖数: 726 | 14 题目：
在网上搜了一个code,如下，做了一些小修改，可是总过不了online judge.大家能发一
个能通过judge的(n^2) code吗？谢谢。
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = num.size();
vector > result;
map > sums;
for (int i = 0; i < n; ++i) {
// 'sums' hastable holds all possible sums a[k] + a[l]
// where k and l are both less than i
for (int j = i + 1;... 阅读全帖 |
|
f*********m
发帖数: 726 | 15 题目：
在网上搜了一个code,如下，做了一些小修改，可是总过不了online judge.大家能发一
个能通过judge的(n^2) code吗？谢谢。
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = num.size();
vector > result;
map > sums;
for (int i = 0; i < n; ++i) {
// 'sums' hastable holds all possible sums a[k] + a[l]
// where k and l are both less than i
for (int j = i + 1;... 阅读全帖 |
|
b******7
发帖数: 92 | 16 在[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 | 17 在[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********t
发帖数: 147 | 18 写了下google第二题
bool IsSumEqualTarget(int target, int i, vector &nums, vector
int>> &sum) {
if (!target && i == nums.size()) return true;
for (int j = i; j < nums.size(); ++j) {
if(IsSumEqualTarget(target-sum[i][j], j+1, nums, sum)) return true;
}
return false;
}
bool IsSumEqualTarget(int target, vector &nums) {
if (nums.empty()) return false;
vector> sum(nums.size(), vector(nums.size(), 0));
sum[0][0] = nums[0];
for (int i ... 阅读全帖 |
|
l*3
发帖数: 2279 | 19 我的c++过了。之前也是超时，改进方法就是要把每一步临时算出来的结果保存，不要
在最后的时候重复算。不过说实话我觉得这个影响不大，理论上讲无非就是把一个最坏
是 O(n * 4^n) 的东西降到了 O(4^n)，少了一个factor而已，不过确实是过例子很快
。。只要44ms（我不知道超时一般判定是多少，不过之前有的题跑了600ms也算过了，
不过也不知道是不是所有题的超时判定都一样?我估计是1000ms，如果这么说的话其实
实际上改进还挺大）
贴一段我的代码，最tricky的地方就是楼上说的，你需要知道这些：
乘法运算的优先级比加减法高，所以你要保存一个 “连乘串” 的结果。直到你某一步
走到了某个你想插入加减法的地方，你才把连乘串的结果去添加到临时的sum结果中，
否则就要一直保留。
另外什么是加法和减法呢？其实就相当于你update你临时的sum，并且把新的乘积起始
点赋值成 1 （对应加法） 或者 -1 （对应减法）
code 如下：
class Solution {
public:
//主函数，没有干什么大事，就是预处理一下字符串，把两个位置之间的字符转换的整
数结果都保存下... 阅读全帖 |
|
发帖数: 1 | 20 534 Design TinyURL 0.0% Medium
283 Move Zeroes 50.7% Easy
301 Remove Invalid Parentheses 35.5% Hard
273 Integer to English Words 22.4% Hard
621 Task Scheduler 42.4% Medium
67 Add Binary 33.2% Easy
325 Maximum Size Subarray Sum Equals k 43.1% Medium
689 Maximum Sum of 3 Non-Overlapping Subarrays 41.2% Hard
253 Meeting Rooms II 39.3% Medium
17 Letter Combinations of a Phone Number 35... 阅读全帖 |
|
发帖数: 1 | 21 问题：输入一个整数N，请问有多少种不同的方法把若干个连续的整数相加使得它们的
和为N？例如输入N=9，由于9 = 9、9 = 4 + 5、9 = 2 + 3 + 4，因此正确的输出是3。
分析：这是LeetCode第829题。
解法一：时间复杂度O(n)
我们可以想象有一个整数数组，数组里的第一个数字是1，第二个数字是2，以后的数字
以此类推。再假设有两个指针，第一个指针初始化指向数组的第一个数字，第二个指针
初始化指向数组的第二个数字。这两个指针就定位了一个子数组，该子数组由两个指针
之间的所有数字（包括两个指针指向的数字）组成。由于数组里的数字是连续递增的，
那么两个指针之间的任意子数组的数字也是连续递增的。
如果两个指针之间的子数组的所有数字之和小于输入的整数N，我们希望这个子数组包
含更多的数字，于是把第二个指针向右移动。每把第二个指针向右移动一位，相当于往
子数组的最右边添加一个新的数字，子数组的数字之和也会相应变大。如果此时子数组
的和仍然小于N，我们继续向右移动第二个指针。
如果子数组的和等于N，我们就找到了一个符合条件的子数组。接下来可以继续向右移
动第二个指针去寻找其... 阅读全帖 |
|
|
j****u
发帖数: 1413 | 23 新闻请见：http://www.ustcif.org/default.php/content/1772/
9月16日，斯坦福-中国科大-麻省理工教授论坛[Stanford-USTC-MIT 2013，简称
SUM2013]将在中国科大启幕。SUM2013将成为中国科大结盟海外名校的又一动作？
SUM2013在中国科大尚未有公开报道，但新创基金会发现网站（sum.ustc.edu.cn）已有
不少信息。SUM网站称，SUM2013主题为“大学与创新”，来自Stanford、MIT 物理、化
学与材料科学、地球与空间科学等三领域数十位教授将齐聚合肥，进行学术交流。中国
科大还将邀请中国常青藤联盟（C9）高校80位大学生参加论坛。SUM2013组织委员会主
席系“新创讲席教授”潘建伟院士；执行主席为“千人计划”入选者张捷（817，MIT博
士）。信息学院院长李卫平（776，Stanford博士）亦名列组织委员会。
SUM网站显示，至少12位Stanford教授将出席论坛，包括科大校友崔便晓（9314）、崔
屹（9312）、王善祥（812）
2012年，斯坦福-中国科大-麻省理工曾联合举办SU... 阅读全帖 |
|
B*****g
发帖数: 34098 | 24 SELECT SUM(IIf(Q1=1, 1, 0))/COUNT(*) AS A1,
SUM(IIf(Q1=2, 1, 0))/COUNT(*) AS A2,
SUM(IIf(Q1=3, 1, 0))/COUNT(*) AS A3,
SUM(IIf(Q1=4, 1, 0))/COUNT(*) AS A4,
SUM(IIf(Q1=5, 1, 0))/COUNT(*) AS A5
FROM QA
UNION ALL
SELECT SUM(IIf(Q2=1, 1, 0))/COUNT(*) AS A1,
SUM(IIf(Q2=2, 1, 0))/COUNT(*) AS A2,
SUM(IIf(Q2=3, 1, 0))/COUNT(*) AS A3,
SUM(IIf(Q2=4, 1, 0))/COUNT(*) AS A4,
SUM(IIf(Q2=5, 1, 0))/COUNT(*) AS A5
FROM QA
.... |
|
i*****e
发帖数: 68 | 25 喜欢这个证明.能用简单工具解决问题最好.
如果把条件sum h_i =sum r_i =1 去掉,你这个办法实际上证明了
2sum r_i -sum h_i <= sum(r_i^2/h_i).
前面几位用C-S证明的是
(sum r_i)^2 /(sum h_i)<= sum(r_i^2/h_i).
由于2sum r_i -sum h_i <=(sum r_i)^2 /(sum h_i),所以C-S 实际上证明了一个更强
的不等式.总之,个有长处吧. |
|
t********e
发帖数: 25 | 26 Is it greedy? Or is it DP?
since sum(x1<->xn) = 0.
think the array as + - + - + - + - ....
say sum(x1<->xk) is the maximum
For the maximum sum segment, there will be no sum(x1<->xi') < 0 , i' <
k,
otherwise, the maximum sum segment is sum(xi'+ 1<->xk).
OK. So there is no problem travelling in the maximum segment.
Also after the maximum sum segment, there will be no segment is smaller
than
-sum(x1<->xk). if there is one, say sum(xk+1<->xk'), k' >= k+1 and
could
be
any. Then from the end of such s |
|
g**t
发帖数: 3 | 27 硬想出来的，没什么值得总结的思路，应该work，也满足条件。大家测测吧
public class Longest10Substring {
public static void main(String[] args) {
calc(new int[] { 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0 });
calc(new int[] { 0 });
}
public static void calc(int[] a) {
int n = a.length;
int minority = 0, cnt = 0;
for (int i = 0; i < n; i++) {
if (a[i] == 1) {
cnt++;
}
}
if (cnt == 0 || cnt == n) {
print(a, 0, 0... 阅读全帖 |
|
j*******a
发帖数: 61 | 28 Thanks for all posts. Just want to confirm I understand right, let me repeat
your ideas.
Assume input: 4, -1, 5, 2, 0, -2.
looks for the closest sub array for 3
0 1 2 3 4 5 get sums sort BS for 3
------------------------------------
0 | 4 3 8 10 10 8 n nlgn lgn
1 | -1 4 6 6 4 lgn lgn
2 | 5 7 7 5 lgn lgn
3 | 2 2 0 lgn lgn
4 | 0 -2... 阅读全帖 |
|
S****z
发帖数: 666 | 29
i]
排了序之后，对sum[i+1,...j]来说,j在i后面应该是sum[j]比sum[i]大啊
比如说sum[i]处刚好是0，sum[i+1,...j]刚好是K，那么sum[j]就是K
那么怎么可能找到你说的 K = sum[j] <= sum[i]-K = 0-K = -K?
那岂不是sum[i+1,...j]这个被miss了？
以了 |
|
f**********w
发帖数: 93 | 30
...
1. get new array sum[n]: from sum(0) to sum(n) O(n) time and O(n) space
2. find the max sum which index is j O(n) time
~~~~~~~~This search need to be from right to left, in case
there are equal maximum sum(j)
3. check from left side of sum(j), find the min of sum array which index is
k
~~~~~~~~~Here need to check condition sum[j] - sum[k] >= K,
right?
4 .If the min >= 0, all number array [0-j] are the sub array
if the min < 0 , number array[k+1 -... 阅读全帖 |
|
g***s
发帖数: 3811 | 31 Your idea is correct. and gloomyturkey gave the detail based on your
idea.
for 1, now, it is correct. Another mehtod gloomyturkey gave is: after we
get sum(i) using O(N), we can also use binary search to find the i and
j. (find the max x, let sum(x) - sum(x+3,n)<0). return x+2.
for 2, i cannot understand how to using DP to get in O(n)
for 3, 2 pipe has only one split point, so, the choice is O(n). but for
pipe is 3, with two split points, is difficult to be solved in O(n).
for 4, f(x) = sum(x) -... 阅读全帖 |
|
w**********o
发帖数: 140 | 32 小弟抛块砖，希望大牛们点评下。
首先sort， 从大到小排列。
L: 100, 98, 97, 76, 50, 30, ...., 10, 9, 2,1
分3组, a, b, c. 挨个拿。
First time
a: 100
b: 98
c: 97
sum(a) = 100
sum(b) = 98
sum(c) = 97 最小, 把L里面最大的分给他
Second time
a: 100,
b: 98,
c: 97, 76
sum(a) =100
sum(b) = 98 最小, 把L里面最大的分给他
sum(c) =173
3rd
a: 100,
b: 98, 50,
c: 97, 76,
sum(a) =100 最小, 把L里面最大的分给他
sum(b) = 148
sum(c) = 173
3rd
a: 100, 30
b: 98, 50,
c: 97, 76,
以此类推， 全部分完。
这样3组的difference比较小，size基本一样的情况下。
算法：个人理解就和国内分蛋糕一样。
每人都拿一块， c拿最小的要说话了， 再给我一份。
c变最大， b说他也要，一次不行... 阅读全帖 |
|
p*****2
发帖数: 21240 | 33 真有意思。scala做上边的题非常简洁。
比如这道
The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural
numbers and the square of the sum is 3025 385 = 2640.
Find the difference between the sum of the squares of the first one hundred
natural numbers and the square of the sum.
scala：
val nums=1 to 100
println(nums... 阅读全帖 |
|
s*****r
发帖数: 108 | 34 今天做了 Gas station，然后来看讨论发现市面上的解法已经很经典，通过计算所有和
检测是否有解，通过计算部分和找到 index。
本题本质是找到一个序列使所有前缀和非负。所以是这样想的，假设 index 0 （用
beg 表示）就是解，如果假设成立，那么从这开始的前缀和（假设已经走到了 end）都
是非负的，一直累加。然而一旦发现不成立，那么就退一步把 beg 设为 beg - 1 作为
候选。直到 beg == end。这样只要一个累加和就好了。
初始时把 beg = 0, end = (beg + 1) % n ，更新时是 beg = (beg - 1 + n) % n，
end = (end + 1) % n，但这样并不美观。所以技巧是把 beg 初值设为 n - 1，end 设
为 0，两数更新就都是单调的了。
class Solution {
public:
int canCompleteCircuit(vector &gas, vector &cost) {
int beg = gas.size() - 1, end = ... 阅读全帖 |
|
s*****r
发帖数: 108 | 35 今天做了 Gas station，然后来看讨论发现市面上的解法已经很经典，通过计算所有和
检测是否有解，通过计算部分和找到 index。
本题本质是找到一个序列使所有前缀和非负。所以是这样想的，假设 index 0 （用
beg 表示）就是解，如果假设成立，那么从这开始的前缀和（假设已经走到了 end）都
是非负的，一直累加。然而一旦发现不成立，那么就退一步把 beg 设为 beg - 1 作为
候选。直到 beg == end。这样只要一个累加和就好了。
初始时把 beg = 0, end = (beg + 1) % n ，更新时是 beg = (beg - 1 + n) % n，
end = (end + 1) % n，但这样并不美观。所以技巧是把 beg 初值设为 n - 1，end 设
为 0，两数更新就都是单调的了。
class Solution {
public:
int canCompleteCircuit(vector &gas, vector &cost) {
int beg = gas.size() - 1, end = ... 阅读全帖 |
|
x*********1
发帖数: 23 | 36 我写了一个，大家帮看看， 谢谢啦， 请问楼主在哪找到的第二题的code，很想学习
一下
public long stringToLong(String str) {
if (str==null||str.length()==0){
return 0;
}
int sign=1;
Long sum=(long) 0;
int i=0;
while(i
i++;
}
if (i==str.length()){
return 0;
}
if (str.charAt(i)=='+'){
... 阅读全帖 |
|
g********n
发帖数: 447 | 37 我写了一下，可是结果总是不对
public boolean consum(int[] a, int target){
int[] sum = new int[a.length+1];
sum[0] = 0;
for(int i=1; i
sum[i] = a[i-1]+sum[i-1];
}
HashMap hm = new HashMap();
for(int i=0; i
if(hm.containsKey(sum[i]+target)){
int j = hm.get(sum[i]+target);
if(j
... 阅读全帖 |
|
g********n
发帖数: 447 | 38 我写了一下，可是结果总是不对
public boolean consum(int[] a, int target){
int[] sum = new int[a.length+1];
sum[0] = 0;
for(int i=1; i
sum[i] = a[i-1]+sum[i-1];
}
HashMap hm = new HashMap();
for(int i=0; i
if(hm.containsKey(sum[i]+target)){
int j = hm.get(sum[i]+target);
if(j
... 阅读全帖 |
|
b*********e
发帖数: 26 | 39 第二题这个方法有可能吗？
先求sum，w/o loss of generality, assume sum>0
然后从两端加逼，如果两端有>0的数，去掉一个使得|sum|最小，然后继续
如果两端都小于0，就一起往里扫算subarray sum，直到碰到subarray sum>0的时候停
止，去掉subarray sum可以mininize |sum|的那个subarray
sum<0的情况同理
过程中记录|sum|最小的时候的subarray |
|
P**********n
发帖数: 6311 | 40 题目：编写程序输出1+2+3..+100的值。
喜：
Int sum = 0;
For(int i = 1;I <=100; sum + = i, i++);
Out(sum);
怒：
Int sum = 0;for(int i = 1;i<=100;i++)for(int j=0; j
哀：
Int
Sum=1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+2
0+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+
38+39+40+41+42+43+44+45+46+47+48+49+50+51+52+53+54+55
+56+57+58+59+60+61+62+63+64+65+66+67+68+69+70+71+72+7
3+74+75+76+77+78+79+80+81+82+83+84+85+86+87+88+89+90+
91+92+93+94+95+96+97+98+99+100;
Out(sum);
乐：
Int sum=5050；
Out(s... 阅读全帖 |
|
X******2
发帖数: 5859 | 41 http://blogs.ethz.ch/kowalski/2013/05/21/bounded-gaps-between-p
And so it came to pass, that an almost millenial quest found a safe resting
place…
Like all analytic number theorists, I’ve been amazed to learn that Yitang
Zhang has proved that there exist infinitely many pairs of prime numbers ell
So, how did he do it?
Well, since the paper just became available, I don’t have anything
intelligent to say yet on the new ideas that he introduced (but ... 阅读全帖 |
|
H*X
发帖数: 281 | 42 programming pearls上有讨论，好像CLRS也有
就是记录2个sum: current sum, current max sum,
把数组扫描一遍，如果current sum < 0，就从0开始重新计算，如果current sum >
current max sum, 那么current max sum = current sum, |
|
g***s
发帖数: 3811 | 43 Since the DP stores all the values, we don't need to handle (log v_N) times.
So, it is same time complexity of Knapsack problem.
new_V < 2*V
Knapsack can be handle in O(N*V), so this question can be handled in O(N*2*V
) = O(N*V). N is the type of coins.
the O(N*V) codes for knapsack are hard to read. following is sample codes,
time = O(V * sigma log s_i) .
public static int getMinStampNum(Coin[] coins, int V) {
ArrayList p = new ArrayList();
for (Coin coin ... 阅读全帖 |
|
g**********y
发帖数: 14569 | 44 来自主题: JobHunting版 - 问个编程题 带输出的，不用分配那么多空间，只要记住parent index就行。
public int solve2(int[] a, int sum) {
ArrayList numbers = new ArrayList();
for (int i : a) if (i!=1) numbers.add(i);
int[][] m = new int[sum+1][2];
m[0] = new int[]{0, -1};
m[1] = new int[]{1, 0};
for (int i=2; i<=sum; i++) {
m[i] = new int[]{sum+1, -1};
for (int j : numbers) {
if (j<=i && m[i][0] > 1+m[i-j][0]) {
m[i][0] = 1+m[i... 阅读全帖 |
|
m******d
发帖数: 25 | 45 我贡献一个只扫描一遍的算法把。首先用最左和最右计算一个最大可能的雨量。如果左
边比右边低，那么从左边前进一个。如果左边第二个比第一个要低，那么从总水量里减
去左边第二个的高度；否则，用左边第二个和最右边的计算一个新的最大可能的水量。
右边同理。
public class Solution {
public int trap(int[] A) {
// Start typing your Java solution below
// DO NOT write main() function
if (A.length < 3){
return 0;
}
int l=0;
int r=A.length-1;
int left=A[l], right=A[r];
int sum = (A[l] < A[r] ? A[l] : A[r]) * (A.length - 2);
while(l
... 阅读全帖 |
|
w**z
发帖数: 8232 | 46 http://www.forbes.com/sites/jacquelynsmith/2012/03/21/10-things
If you’re unemployed and worried that employers will turn you down for
taking on unimpressive work during the recession or for the large employment
gaps on your résumé—you needn’t panic. A new survey just released by
the careers website CareerBuilder.com reveals that the vast majority of
employers are sympathetic to such circumstances.
The nationwide survey was conducted online by Harris Interactive, on behalf
of CareerBuilder, amo... 阅读全帖 |
|
i*********7
发帖数: 348 | 47 int* findmaxsumarray(int *array, int length, int maxsum){
int *sum = new int[length + 1];
sum[0] = 0;
for(int i = 1; i <= length; i++)
sum[i] = sum[i - 1] + array[i - 1];
int *max = new int[length + 1];
int *min = new int[length + 1];
for(int i = 0;i<=length;i++)
cout<
cout<
max[0] = 0;
for(int i = 1; i < length + 1;i++)
{
max[i] = std::max(max[i - 1], sum[i]);
}
min[length] = sum[length];
for(int i = ... 阅读全帖 |
|
h**********9
发帖数: 3252 | 48 来自主题: JobHunting版 - 请问G一题
客气点好吗？我又不是全职解题的，拖家带口的有点时间不容易.
还有一些地方没想通，就当这个是 heuristic greedy 解，不一定能算出最优解，先给
个 O((Max(x) - Min(x))*N^2） 的 code, 谁能帮忙验证一下？ 如果可行我再解析O((
Max(x) - Min(x))*N*LG(N))。
import java.util.Arrays;
public class Partition {
public static int getMinDifference(int input[]) {
assert (input.length % 2 == 0) : "Input must have even number of
items.";
Arrays.sort(input);
int x[] = new int[input.length / 2];
int y[] = new int[input.length / 2];
for(int i = 0; i < x.... 阅读全帖 |
|
h**********9
发帖数: 3252 | 49 来自主题: JobHunting版 - 请问G一题
客气点好吗？我又不是全职解题的，拖家带口的有点时间不容易.
还有一些地方没想通，就当这个是 heuristic greedy 解，不一定能算出最优解，先给
个 O((Max(x) - Min(x))*N^2） 的 code, 谁能帮忙验证一下？ 如果可行我再解析O((
Max(x) - Min(x))*N*LG(N))。
import java.util.Arrays;
public class Partition {
public static int getMinDifference(int input[]) {
assert (input.length % 2 == 0) : "Input must have even number of
items.";
Arrays.sort(input);
int x[] = new int[input.length / 2];
int y[] = new int[input.length / 2];
for(int i = 0; i < x.... 阅读全帖 |
|
b*****n
发帖数: 482 | 50 应该是对的. 写了个code过了OJ
int threeSumClosest(vector &num, int target) {
sort(num.begin(), num.end());
int bestSum;
int diff = INT_MAX;
for(int i=0;i
int l=i+1, r=num.size()-1;
while(l
int sum = num.at(i) + num.at(l) + num.at(r);
// found perfect sum, return immediately
if(sum == target)
return sum;
// update diff and bestSum
if(abs(sum-target) < diff) {
... 阅读全帖 |
|
