D****6
发帖数: 278 | 1 Core Java. 具体官方要求如下. 其实刚毕业的也行. 没有金融背景也行. 英语不能太
差. 前段面了个口音重的没要. 最好有身份能马上(一两周)开始的. OPT也行, sponsor
H1B, 但是transfer h1b等太久经理不太愿意. 站内发简历, 我大概会挑一下然后
forward给经理.
大家互相帮助. 有问题我会尽量回答.
RESPONSIBILITIES
Key responsibilities will include the following:
General
* Enhance and support our valuation service and risk system for over-the-
counter products, making it available to multiple applications within the
firm (CDS, Interest Rate Swaps, FX Forwards, FX Options, Volatility Swaps
etc.)
* Manage and support ven... 阅读全帖 |
|
d**e
发帖数: 6098 | 2 O(n)时间, O(n)空间的简单，不用说了。
如果O(1)空间的，我只能想到O(n^2)时间.
把它分上下两行看比较清楚。
b1, b2, b3, ...., bn
a1, a2, a3, ...., an
方法就是斜线交换
swap(a2, b1), swap(a3, b2)... swap(an, b_{n-1})
这样就处理好b1和an
a2, a3, .... an, bn
a1, b1, b2...... b_{n-1}
然后再隔一个交换，swap(b2, a2), swap(b3, a3) ...
处理好了a2和b_{n-1}
再斜线隔两个交换，如此类推.... |
|
k****n
发帖数: 369 | 3
no
2> The first thing I can think of is to still use siftdown method, the only
benifit is we don't need to do comparison, just use the right child. This
has been O(N), can it be faster? Let's see what is happening in the
heapifying process:
In a BST:
X
X4 | X
X X1 | X X
X X X2 X3 | X X
At first, X3 will swap with X1, then for X4, it will swap with X3 and then
X1.
So because of the feature of BST, an element is always swapped at the right
hand side, and gurantees to be swapped to the bottom. So ... 阅读全帖 |
|
s*****y
发帖数: 897 | 4 No.2 刚写了一个,似乎是对的,只是测试了2个例子:
{9, 4, 14, 2, 8, 10, 16, 1, 3, 7};
//in place swap without using addition variable
void swap(Tree *a, Tree *b)
{
a->element = a->element ^ b->element;
b->element = a->element ^ b->element;
a->element = a->element ^ b->element;
}
void BstToHeap1( Tree *root)
{
if (!root)
return;
BstToHeap1(root->left);
BstToHeap1(root->right);
if (root->right)
swap(root, root->right);
}
void Heapify(Tree *root)
{
if (!root) return;
... 阅读全帖 |
|
r*******g
发帖数: 1335 | 5 我比较了你和doubleplay的算法，然后自己用二分法写了个，二分法的效率是O(nlogn)
我现在还没看懂doubleplay的算法，你的算法更容易理解，每次判断是否是loop的开头
，doubleplay那个至今理解不了。
但是我发觉你们的结果都没有二分法快啊，我用的N=10000000，你能不能测试下，不知
道结果是不是和我类似，难道是c++的问题？
感觉你们这个也不是O(N)，shyx那个是O(N)，但是很难想到什么基于素数的算法。
void Swap(int * array,int begin,int end){
for (int i=0;i<(end-begin+1)/2;i++){
int tmp=array[begin+i];
array[begin+i]=array[end-i];
array[end-i]=tmp;
}
}
void Convert(int * array,int begin,int total){
int N=total/2;
if(N==1)
... 阅读全帖 |
|
w****o
发帖数: 2260 | 6 我也自己写了一个。其实就是拿到一个值后，根据值得大小，判断应该把者个值放在哪
里，把真正的操作用代码给直接的描述出来。
具体用法：比如有个数组a[]，有4种颜色，数组大小为n,可以调用 DNF_K(a, 4, 0, n-
1)
// this is the code for k colors.
// the element values can be 0, 1, 2, ..., k-1
// partition[i] records the starting index for value i
// partition[0] does not matter, and should be always 0
// partition[k-1] denotes the lower index of unknown section
// h denotes the upper index of unknown section
// sections are :
// 0 1 2 3 ... unknown k-1
// complexity: O(n*k)
//
void DNF_K(in... 阅读全帖 |
|
p*i
发帖数: 411 | 7 #include
#include
#include
#include
using namespace std;
inline void swap(int &a, int &b) {
int t = a; a = b; b = t;
}
int partition(vector& work, vector& indices, int p, int q) {
// use work[q] to partition the array
const int x = work[q];
int i = p-1;
for (int j = p; j < q; j++) {
if (work[j] < x) {
i++;
swap(work[i], work[j]);
swap(indices[i], indices[j]);
}
}
i++;... 阅读全帖 |
|
j*****n
发帖数: 1545 | 8 可以这样， 先把中间的1对, 然后swap的2对，然后3对..
a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 -- swap (a5,b1)
a1 a2 a3 a4 b1 a5 b2 b3 b4 b5 -- swap (a4,b1) (a5,b2)
a1 a2 a3 b1 a4 b2 a5 b3 b4 b5 -- swap (a3,b1) (a4,b2) (a5,b3)
a1 a2 b1 a3 b2 a4 b3 a5 b4 b5 -- swap (a2,b1) (a3,b2) (a4,b3) (a5,b4)
a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 -- done |
|
e****e
发帖数: 418 | 9 Agree.
public void convert(char[] a) {
swap(a, 1, 2);
swap(a, 5, 6);
swap(a, 2, 4);
swap(a, 3, 5);
}
private void swap( char[] a, int i, int j ) {
char tmp = a[i]; a[i] = a[j]; a[j] = tmp;
} |
|
f*******t
发帖数: 7549 | 10 我觉得swap不如位运算。
位运算是把N+1个数全读一遍。
swap概率上平均要读(N+1)/4个数，但对每个数，需要做swap操作的概率是N/(N+1)。也
就是说，要进行N/4次swap。swap的cost不止是位运算的4倍吧。 |
|
D****6
发帖数: 278 | 11 Core Java. 具体官方要求如下. 其实刚毕业的也行. 没有金融背景也行. 英语不能太
差. 前段面了个口音重的没要. 最好有身份能马上(一两周)开始的. OPT也行, sponsor
H1B, 但是transfer h1b等太久经理不太愿意. 站内发简历, 我大概会挑一下然后
forward给经理.
大家互相帮助. 有问题我会尽量回答.
RESPONSIBILITIES
Key responsibilities will include the following:
General
* Enhance and support our valuation service and risk system for over-the-
counter products, making it available to multiple applications within the
firm (CDS, Interest Rate Swaps, FX Forwards, FX Options, Volatility Swaps
etc.)
* Manage and support ven... 阅读全帖 |
|
f******h
发帖数: 45 | 12 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
a**********0
发帖数: 422 | 13 如果有duplicates 用下面这个算法
import java.util.*;
public class PermutationsII {
public ArrayList> permuteUnique(int[] num) {
Arrays.sort(num);
ArrayList> myResult = new ArrayList
Integer>>();
ArrayList temp1 = new ArrayList();
for(int i = 0; i<= num.length-1; i++)
temp1.add(num[i]);
myResult.add(temp1);
while(nextPermutation(num)){
... 阅读全帖 |
|
a**********0
发帖数: 422 | 14 java代码
import java.util.*;
public class PermutationsII {
public ArrayList> permuteUnique(int[] num) {
Arrays.sort(num);
ArrayList> myResult = new ArrayList
Integer>>();
ArrayList temp1 = new ArrayList();
for(int i = 0; i<= num.length-1; i++)
temp1.add(num[i]);
myResult.add(temp1);
while(nextPermutation(num)){
ArrayList<... 阅读全帖 |
|
M**********7
发帖数: 378 | 15 这个思路挺好的，的确很像15-puzzle，不过这个可能比那个简单，有点像那种中心有
一个空位可供交换的例如8-puzzle。
分析的部分有点不懂：
：每次swap组合成的情侣可能值为0,1,2. 最优情况下每次swap至少应该组合一对情侣。
这里说的“优情况下每次swap至少应该组合一对情侣”是指组合成的情侣总数加一，还
是只是有一个新的组合产生，而不管是否破坏的情况？
如果是指组合成的情侣总数加一，下面这种情况就不满足：
A BB CC DD EE A ->
A AB CC DD EE B ->
A AB BC DD EE C ->
A AB BC CD EE D ->
A AB BC CD DE E
4次移动只加了一对。
：不可能比两次swap，每次组合成一对更优
ABAB ->
AABB
一次交换可以凑2对。
：我们可以依次序尝试组合成两对的，组合成一
如下这种情况，把两个A和X Y对调，单次swap就不产生任何组合，或者是看2步？
A BB CC DD EE A FF GG HH II JJ KK X Y
我这里很可能断章取义了，因为看不太懂，不好意思哈。 |
|
y********g
发帖数: 6 | 16 写了个O(n)的，有更优的解法么？
public void swap(int[] A, int i, int j, int[] map) {
map[A[i]] = j;
map[A[j]] = i;
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
public void move(int[] begin, int[] end) {
int n = end.length;
int[] map = new int[n]; // value->position in begin array
for(int i=0; i
map[begin[i]] = i;
}
for(int i=0; i
if(begin[i] == end[i]) continue;
swa... 阅读全帖 |
|
D*****a
发帖数: 810 | 17 Buy (3) Pedigree Dentastix dog treats 9 ct - $1
Use (1) $3/3 PEDIGREE Treats For Dogs Printable
Final Price: FREE
Buy (2) Dr. Pepper Ten 2-Liters – $0.88
Use $1/2 Dr Pepper 2-liter bottles/12-pack cans printable
And use 40% off Ten Soda Target Cartwheel Offer
Final price: $0.03 each
Bounty Basic Paper Towels Single Roll - $0.97 (Regular Price)
Use 10% Off Bounty basic paper towels Target Carthweel
And use $0.50/1 Bounty Towels printable
Final price $0.38
Play Doh Classic 4-pack - $2... 阅读全帖 |
|
l**g
发帖数: 1914 | 18 自己回复一下：
The device can not be active with Sprint. You need a spare Sprint device to
activate with R+, then port your number to that device and then do an ESN
swap. Or...... open a support ticket to get them to help with a number
transfer and ESN swap. They most likely will use a dummy ESN to port your
number to and then likewise do a ESN swap.
Port in is $8 and ESN swap $1.
是不是说必须是没有在sprint active 的手机才可以注册R＋？那ESN SWAP后这个spare
sprint device 还能不能
用在别的carrier上？还是就废了？或者我用dummy phone换掉在sprint上注册的acti... 阅读全帖 |
|
s*******e
发帖数: 432 | 19 1. strategy one: do not the swap, you win when the first card is a joker, so
the probability is 1/3.
2. strategy two: do the swap, you win when the first card is not a joker(
since the dealer will point out which one is not joker and you get the joker
if the first card is not a joker). So the probability is 1-1/3=2/3
You swap. Basically, if you do not swap you are not using the information
given by the dealer while you do swap you use this information. |
|
d**********o
发帖数: 1321 | 20 第一个项目report
这时偶刚到CSAC工作不久，与小A同学还不熟，我用的还是latex。随着贴的作业越来越
多，应该是用有共同爱好的小伙伴更亲密些。这次贴latex，下次才再org-mode。
\documentclass[b5paper,11pt, abstraction, titlepage]{scrartcl}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{CJKutf8}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{listings}
\usepackage{geometry}
\geometry{b5paper}
\usepackage{graphicx,floatrow}
\usepackage{graphicx,subfigure}
\newsavebox{\abstractbox}
\renewenvironment{abstract}
{\begin{lrbox}{0}\begin{minipage}{\t... 阅读全帖 |
|
d**********o
发帖数: 1321 | 21 第一个项目report
这时偶刚到CSAC工作不久，与小A同学还不熟，我用的还是latex。随着贴的作业越来越
多，应该是用有共同爱好的小伙伴更亲密些。这次贴latex，下次才再org-mode。
\documentclass[b5paper,11pt, abstraction, titlepage]{scrartcl}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{CJKutf8}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{listings}
\usepackage{geometry}
\geometry{b5paper}
\usepackage{graphicx,floatrow}
\usepackage{graphicx,subfigure}
\newsavebox{\abstractbox}
\renewenvironment{abstract}
{\begin{lrbox}{0}\begin{minipage}{\t... 阅读全帖 |
|
r****t
发帖数: 10904 | 22 你是不是用 swap 分区了？然后 server 又比较忙，经常写 swap? disable swap 可能好
点？至少用 swap file，不用 swap 分区
in the |
|
N**********d
发帖数: 9292 | 23 fdisk /dev/sdb
然后n，p，2, 分区大小默认，然后t改成swap
不过现在分区表里面有sdb2了，还是不让我开swap。。。真是郁闷嘞
~$ sudo fdisk -l
Disk /dev/sda: 160.0 GB, 160041885696 bytes
255 heads, 63 sectors/track, 19457 cylinders
Units = cylinders of 16065 * 512 = 8225280 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0xb1935407
Device Boot Start End Blocks Id System
/dev/sda2 * 2 19457 156280320 5 Extended
/dev/sda5... 阅读全帖 |
|
k***g
发帖数: 7244 | 24 这个只能算钻 accounting 的漏洞，把借债包装成 cross-currency swap （虽然这个
已经不是通常意义上的 currency swap ），而 currency swap 是不出现在一个国家的
负债表上的；
这个和企业利用 derivatives （譬如 interest rate swap，或者 dividend-related
stock
swap） 避税差不多,都是钻 accounting 的空；
这种做法也不是希腊首创的，意大利90年代就用过。所以不存在希腊是不是受骗的问题
，希腊知道这样做的后果，而希腊之所以这么做，也有它的如意算盘，交易都是
Pareto-optimal 的。
这个 deal 当时也不算秘密，很多地方都报道了。
其实南欧这些问题也是南欧自己搞出来的，意大利在 Euro 还是 ERM 的时候就被迫暂
时退出过 ERM，把所有的欧洲国家都和德国绑在一起未必是好事。
反正现在欧元区就是一盘浆糊啊，事事都靠德国了。 |
|
z***e
发帖数: 5600 | 25 1. Replication of variance swap by strip of options is fine at least for SPX
index options. Note that size of a certain option is fixed (proportional
to 1/K^2). In fact, market maker do trade replication strips to close their
VIX positions during the special quote window of the expiring Wednesday.
3. There is also a special case when extrapolation instead of interpolation
is required to calculate VIX index when next monthly SPX option expiration
is five weeks away. Has CBOE started using week... 阅读全帖 |
|
x***u
发帖数: 297 | 26 Swap回去的时候死活不接受ICCID。最后只好不填。voice可以的，但是没有data (因为
没加SIM的ICCID）
有人有一样的问题吗？
: swap device, 马上在swap回来就好了，其实是要reset account, swap能
trigger
: reset. 我昨天发了个ticket, 没人理，回家自己swap就好了，网上google来的
|
|
y******i
发帖数: 2584 | 27 2018-10-13 00:17:02 来源：参考消息网 责任编辑：郭庆娜
核心提示：英国皇家思瓦普协会（Royal Swap Society)宣布刘强东章泽天正式成
为该协会首位中国国籍夫妻，将在今年12月再次访问英国。
参考消息网8月22日报道
据英国媒体报道，当地时间10月12日，备受英国女王疼爱的孙女尤金妮公主(Princess
Eugenie)在著名的温莎城堡大婚，刘强东携妻子章泽天盛装出席，还有网友在伦敦街头
偶遇二人。
从视频看，刘强东身着一件黑色西装，配粉色领带，章泽天则是一身粉色短裙礼服，颜
值气质绝佳，而且笑逐颜开，心情很好。
有趣的是，刘强东夫妇出现在直播视频中之后，一位不认识奶茶妹妹的英国网友在评论
里问：“她是日本公主吗？”
而据当地著名媒体《英国邮报》爆料，具有两百多年历史的英国皇家思瓦普协会（
Royal Swap Society)，也通过这次皇家婚礼，正式接纳刘强东和章泽天成为正式会员。
皇家思瓦普协会（Royal Swap Society)的现任主席凯瑟琳·克里斯说道，她是在婚礼
的后半段有机会和章泽天接触，在章泽天提到自己是个亿万富翁的妻子后... 阅读全帖 |
|
W*****B
发帖数: 4796 | 28 其家庭曾参与一档换妻游戏电视节目
Wife Swap Killings: Son Charged with Killing Mom, Brother Before Shooting
Himself in Head
Chris Harris
Having recently recovered from a self-inflicted gunshot wound to the head,
an Ohio bluegrass musician whose family appeared on an episode of the ABC
show Wife Swap is now facing murder charges in the 2017 deaths of his mother
and brother.
Jacob Timothy Stockdale, 26, turned himself in after learning grand jurors
had indicted him on murder charges stemming from the fatal shootin... 阅读全帖 |
|
S*********n
发帖数: 4050 | 29 Son, you brain is too limited to understand what is bigger -
Big Risk: $1.2 Quadrillion Derivatives Market Dwarfs World GDP
By Peter Cohan Posted 10:45AM 06/09/10 Economy, Investing, Investing Basics
Comments Text Size A A A
213413100
One of the biggest risks to the world's financial health is the $1.2
quadrillion derivatives market. It's complex, it's unregulated, and it ought
to be of concern to world leaders that its notional value is 20 times the
size of the world economy. But traders rule t... 阅读全帖 |
|
s*********g
发帖数: 153 | 30 这个例子这么解：
第一个区：
1，-2，3，-4，||5，-6||
swap 结果
1，-2，3，-4，-6，5
第二个区：
1，-2，||3，-4，-6||,5
swap 结果
1，-2，-4，-6，3，5
第三个区：
||1,-2,-4,-6||,3,5
结果
-2，-4，-6，1，3，5
分了三个区，但时间复杂度不是O（n*n）
首先，不是遍历三回，得到的三个区，而是遍历一遍的过程中得到三个区，因为每次产
生一个区，swap结束后，下一个区的end就已经确定了，只需要往前找下个区的start。
另外，每个区的swap时间复杂度为o（k）， o(k1+k2+k3) = o(n); |
|
g*********s
发帖数: 1782 | 31 2. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。
时间复杂度，如何优化。
recursion?
is_equal(root1, root1) ::= root1->dat == root2->dat &&
(is_equal(root1->left, root2.left) && is_equal(root1->right, root1-
>right || ... //swap case).
each node can at most trigger 2 swap ops. so worst case 2n? not sure if
a swap on one parent and a swap on its kid would cancel each other.
complexity exponential?
optimization: traverse the tree to calculate the size of each sub-tree.
check the sub-tree size before recursive call.
3.... 阅读全帖 |
|
c********t
发帖数: 5706 | 32 好像是不可能。要么要存比较过哪些数，要么要存原始的index位置(swap)。我想了想
，没想通，抛砖引玉,说说我的想法吧。
O(1) space. 就是可以有variable. 如果只用swap，就可以做到要求。
比如ihasleetcode的方法，如果能不用空间保存和最大数比较过的数就可以实现。我延
伸一下，两两比较如果swap大的数到前面。那么得出最大数(第一个数）的同时，如果
知道了它原始的index。从这个index应该有方法知道，都比较过哪些数，比如 第2个数
最大，那么最后就应该和 2，3，5，9，17... 2^i+1... 比较过。第11个数最大，最后
就应该和9，11，12，17，...2^i+1比较过。这些比较过数里的最大的就是second max.
所以是lg(n)-1
可是我的难题是第一，没有储存原始index。第二，虽然有规律，但还不知道如何算哪
些index比较过。
用quick sort + swap 也类似，好像知道最大数比较过的patition最左边数再比较就可
以知道second。 |
|
l*****y
发帖数: 56 | 33 像楼主说的，每次把最小的往上移。
用了三个指针，分别指向三个数组，中间会交换指针，min, mid, max，他们分别指向
三个从小到到大排列的数， 距离就是 *max -*min.
最后return the minimal distance, the vector d records the three elements
with minimal distance.
请指正， 谢谢了！
void swap(vector::iterator &a, vector::iterator &b){
vector::iterator temp;
temp=a;
a=b;
b=temp;
}
int min_dist(vector &a, vector &b, vector &c, vector &d){
vector::iterator min=a.begin(), mid=b.begin(), max=c.begin();
int dist=100... 阅读全帖 |
|
l*****y
发帖数: 56 | 34 像楼主说的，每次把最小的往上移。
用了三个指针，分别指向三个数组，中间会交换指针，min, mid, max，他们分别指向
三个从小到到大排列的数， 距离就是 *max -*min.
最后return the minimal distance, the vector d records the three elements
with minimal distance.
请指正， 谢谢了！
void swap(vector::iterator &a, vector::iterator &b){
vector::iterator temp;
temp=a;
a=b;
b=temp;
}
int min_dist(vector &a, vector &b, vector &c, vector &d){
vector::iterator min=a.begin(), mid=b.begin(), max=c.begin();
int dist=100... 阅读全帖 |
|
j*******e
发帖数: 1058 | 35 我的解法，是一个普遍的k解法。在main里面把k改为2或者是面试官喜欢的k的值就ok。
希望大家指正。
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// Start typing your Java solution below
// DO NO... 阅读全帖 |
|
j*******e
发帖数: 1058 | 36 我的解法，是一个普遍的k解法。在main里面把k改为2或者是面试官喜欢的k的值就ok。
希望大家指正。
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// Start typing your Java solution below
// DO NO... 阅读全帖 |
|
w*******s
发帖数: 96 | 37 Two implementation. one use sort and one use hash.
//pre: str is sorted.
void PermutationWithDuplicate(char *str, int position)
{
if (position == strlen(str)) {
printf("%s", str);
return;
}
char lastChar = '\0';
for (int i = position; i
{
//skip those character which is duplicated. Since the string is
sorted, it's easy.
if (lastChar == str[i] ) continue;
lastChar = str[i];
swap(str[po... 阅读全帖 |
|
m********g
发帖数: 272 | 38 O(n) 的解法：
array = {1, 2, 4, 5, 6, 7, 9, 12}, k = 3，length = 8
1. 先reverse 前面 5个数 {1，2， 4，5，6} －－>｛6, 5,4,2,1｝(length - k)/2
2. 再reverse 后面3个数｛7，9，12｝－－> {12, 9, 7} k/2
现在的array ＝ ｛6， 5， 4，2，1， 12， 9，7｝
3. 现在把整个array reverse ＝ ｛7 9 12 1 2 4 5 6 ｝length/2
所以total runtime ＝ （length -k ）/2 + k/2 + length/2 = length
code:
==========
private static void rotate(int[] array, int k)
{
int length = array.length;
k = (k % length + length) % length;
for(int ... 阅读全帖 |
|
c******5
发帖数: 84 | 39 恩 我的思路是这样的：
不断的swap 碰到零或者负数就跳过，把正数A[i]swap到A[i]-1的位置，但要注意数组
的越界，所以有A[i] - 1 < A.length这个条件,由于swap后得到的新数可能也需要新的
swap，所以有i--
最后从位置0开始找第一个A[i-1]!=i的数,return i
比如0.4,1,2
0,4,1,2->1,4,0,2->1,2,0,4 |
|
c******5
发帖数: 84 | 40 恩 我的思路是这样的：
不断的swap 碰到零或者负数就跳过，把正数A[i]swap到A[i]-1的位置，但要注意数组
的越界，所以有A[i] - 1 < A.length这个条件,由于swap后得到的新数可能也需要新的
swap，所以有i--
最后从位置0开始找第一个A[i-1]!=i的数,return i
比如0.4,1,2
0,4,1,2->1,4,0,2->1,2,0,4 |
|
t**i
发帖数: 314 | 41 编译过了，运行出错，帮忙看看哪儿出了问题，多谢。
import java.util.*;
public class Solution {
public ArrayList> threeSum(int[] num) {
assert(num.length >= 3);
ArrayList> triplet = new
ArrayList>();
for(int i = 0; i < num.length - 2; i++) {
for(int j = i + 2; j < num.length; j++) {
for(int k = i + 1; k < j; k++) {
if((num[i] + num[j] + num[k]) == 0) {
int[] th... 阅读全帖 |
|
h*****3
发帖数: 1391 | 42 我来说说吧，看说的对不对。
rule:a[i]=i+1
a(0)=10,swap a(9),a(0),a(9)=10,a(0)=5
swap a(4),a(0),a(4)=5,a(0)=8
swap a(7),a(0)...until a(0) is 1
check if a( 1) is 2,... 前面swap过的，基本上只是判断而已,因为已经满足了条件。 |
|
w****x
发帖数: 2483 | 43 partition解法, 一点都没觉得简单:
int _inner_min_set(int a[], int n, int k)
{
if (n <= 0) return 0;
if (n == 1) return a[0] >= k ? 1 : 0;
swap(a[0], a[n/2]);
int i = 1;
int j = n-1;
while (i <= j)
{
if (a[i] < a[0])
i++;
else if (a[j] >= a[0])
j--;
else swap(a[i], a[j]);
}
swap(a[0], a[j]);
int nSum = 0;
int nLft = 0;
if (j == n-1)
{
nSum = a[j];
nLft = n-1;
}
else
{
for (... 阅读全帖 |
|
c********s
发帖数: 817 | 44 This is my implementation for these two functions, and a driver to run them.
cat string_reverse.c
#include
#include
#include
void swap(char* c1, char* c2);
// -----------------
void string_reverse1(char* string) {
if (string == NULL)
return;
char* head = string;
char* tail = head;
// find the tail
while (*tail) ++tail;
--tail;
// while loop to do the swap
while (head < tail)
swap(head++, tail--);
}
// -----------------
// the caller of this function is res... 阅读全帖 |
|
n****r
发帖数: 120 | 45 【 以下文字转载自 Topcoders 俱乐部 】
发信人: nibber (nibber), 信区: Topcoders
标 题: 讨论一道老题：分离数组中的正负数
关键字: 算法 数组 O(n) 时间复杂度分析
发信站: BBS 未名空间站 (Thu Nov 8 10:45:04 2012, 美东)
负数在前，正数在后，需要保持负数之间和正数之间的顺序不变！时间复杂度要求O(n)
,空间复杂度O(1)
下面是我的代码，空间复杂度O(1)没问题，时间复杂度分析如下，
设数组中共有负数X个，分散在K个分离的连续负数的子数组段，每个子数组段的长度为
Li，1<=Li
下面算法中K个分离的负数子数组段移到最后位置需要最多进行K次swap操作，而swap的
时间复杂度是O(n)，（这里n是子数段的长度），因此
一共的需要的时间是O(L1)+O(L2)+...+O(Lk) = O(X).因此整体的时间复杂度就是O(n)
这个分析妥不妥？请大牛们给指点一下，还有其他的时间O(n),空间O(1)解法没有？
public static void split(int[] ... 阅读全帖 |
|
l***i
发帖数: 1309 | 46 assume all nodes are distinct
1. recursively find maxL and minR, which are max element in root->left
subtree and min element in root->right subtree
2. if maxL > minR, then these two are swapped elements
3. if maxL > root value, then maxL is swapped with root
4. if root value > minR, then minR is swapped with root
5. the only case remain is maxL < root < minR, in this case recurse on both
root->left and root->right because the two swapped nodes must be in the same
subtree now. |
|
