视频一区三区,亚洲综合影视,国产精品久久看

google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分)

Problem Statement
????
We have a sequence of integers, and we would like to remove all duplicate elements from this sequence. There may be multiple ways to perform this task. For example, given the sequence { 1, 2, 1, 3 }, we could end up with either { 1, 2, 3 } or { 2, 1, 3 } as the remaining sequence, depending on which duplicate 1 we remove from the original sequence. For this problem, we want to return the lexicographically first of of all possible remaining sequences. A sequence S1 comes before sequence S2 lexicographically if and only if S1 has a smaller value than S2 at the lowest index at which the two sequences differ (so, for example, { 1, 2, 3 } comes before { 2, 3, 1 }).
You will be given a int[] sequence. Return a int[] containing the sequence after all the duplicates are removed. See the examples for further clarification.
Definition
????
Class:
HardDuplicateRemover
Method:
process
Parameters:
int[]
Returns:
int[]
Method signature:
int[] process(int[] sequence)
(be sure your method is public)
????

Constraints
-
sequence will have between 1 and 50 elements, inclusive.
-
Each element of sequence will be between 1 and 1000, inclusive.
Examples
0)

????
{5, 6, 5, 1, 6, 5}
Returns: {1, 6, 5 }
There are six different ways to remove duplicates (remaining numbers are marked by '*'):
{ *5, *6, 5, *1, 6, 5},
{ *5, 6, 5, *1, *6, 5},
{ 5, *6, *5, *1, 6, 5},
{ 5, 6, *5, *1, *6, 5},
{ 5, *6, 5, *1, 6, *5},
{ 5, 6, 5, *1, *6, *5}.

The last variant is the lexicographically first.
1)

????
{3, 2, 4, 2, 4, 4}
Returns: {3, 2, 4 }

????
{6, 6, 6, 6, 6, 6}
Returns: {6 }

????
{1, 3, 2, 4, 2, 3}
Returns: {1, 2, 4, 3 }

????
{5, 4, 1, 5}
Returns: {4, 1, 5 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted on 2005-12-20 10:29 emu 閱讀(4811) 評論(9) 編輯收藏所屬分類: google編程大賽模擬題及入圍賽真題

我答案如下：
public class HardDuplicateRemover
{

public static void Main()
{
HardDuplicateRemover total = new HardDuplicateRemover();
int[] ary=total.process(new int[]{5, 6, 5, 1, 6, 5});
for (int i=0;i<ary.Length;i++)
System.Console.Write("{0} ",ary[i]);
System.Console.ReadLine();
}

public int[] process(int[] sequence)
{
System.Collections.Queue[] map=new System.Collections.Queue[10];//分別表示0-9隊列
for(int i=0;i<sequence.Length;i++)
{
int number=sequence[i];
if (map[number]==null) map[number]=new System.Collections.Queue();
map[number].Enqueue(i);
}
//減除重復的
System.Collections.ArrayList lst=new System.Collections.ArrayList();
int curMinPos=-1; //當前最小數的最小位置
for(int i=0;i<10;i++)
{
if (map[i]!=null)
{
int pos=0;//位置
while(map[i].Count>0)
{
pos=(int)map[i].Dequeue();
if (curMinPos==-1) curMinPos=pos;
if (pos>=curMinPos)
{
lst.Add(new Position(i,pos));
break;
}
}
}
}
//排序
mySort(lst);
int[] result=new int[lst.Count];
for(int i=0;i<lst.Count;i++)
result[i]=(lst[i] as Position).number;
return result;
}
private void mySort(System.Collections.ArrayList list)
{
for(int i=0;i<list.Count;i++)
{
for(int j=i+1;j<list.Count;j++)
{
if ((list[i] as Position)>(list[j] as Position))
{
Position p=list[i] as Position;
list[i]=list[j];
list[j]=p;
}
}
}
}
private class Position
{
public int number;
public int pos;
public Position(int n,int p)
{
number=n;
pos=p;
}
public static bool operator >(Position p1,Position p2)
{
return p1.pos>p2.pos;
}
public static bool operator <(Position p1,Position p2)
{
return p1.pos<p2.pos;
}
}
} 回復更多評論

# re: google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) 2005-12-22 18:38 emu

又是自己做排序啊? 回復更多評論

# 我的答案,程序有點長 2006-03-08 16:14 xjingg

import java.util.*;

public class HardDuplicateRemover {
public static void main(String[] args) {
HardDuplicateRemover h = new HardDuplicateRemover();
h.process(new int[]{5, 6, 5, 1, 6, 5});
h.process(new int[]{3, 2, 4, 2, 4, 4});
h.process(new int[]{6, 6, 6, 6, 6, 6});
h.process(new int[]{1, 3, 2, 4, 2, 3});
h.process(new int[]{5, 4, 1, 5});
h.process(new int[]{5, 16, 25, 1, 16, 5, 6 , 6, 25, 5});
}
public int[] process(int[] sequence){
List repeat=new ArrayList();
int num=sequence.length;
for (int i=0;i<sequence.length;i++){
for (int j=0 ;j<repeat.size();j++){
int[] re=(int[]) repeat.get(j);
if (re[0]==sequence[i]){
re[1]=re[1]+1;
num--;
break;
}
if (j==repeat.size()-1){
repeat.add(new int[] {sequence[i], 1});
j++;
}
}
if (i==0){
repeat.add(new int[] {sequence[i],1});
}
}
int [] result=new int[num];
for (int j=0 ;j<repeat.size();j++){
int[] re=(int[]) repeat.get(j);
if (re[1]==1){
repeat.remove(j);
}
}
List sequence_s=new ArrayList();
sequence_s.add(sequence);
for (int i = 0; i < repeat.size(); i++) {
int[] re = (int[]) repeat.get(i);
for (int k = 0; k < sequence_s.size(); k++) {
int[] s = (int[]) sequence_s.get(k);
sequence_s.remove(k);
for (int j = 0; j < re[1]; j++) {
int[] s_o=s.clone();
int order = 0;
for (int l = 0; l < s.length; l++) {
if (s[l] == re[0]) {
if (order == j) {
}else{
s_o[l] = 0;
}
order++;
}
}
sequence_s.add(k, s_o);
k++;
}
k--;
}
}
List sequence_f=new ArrayList();
for (int i=0;i<sequence_s.size();i++){
int[] s = (int[]) sequence_s.get(i);
int n=0;
int[] d=new int[num];
for (int j=0;j<s.length;j++){
if (s[j]!=0){
d[n]=s[j];
n++;
}
if (j==s.length-1){
sequence_f.add(d);
}
}
}
int min=0;
for (int i=0;i<sequence_f.size();i++){
int[] s = (int[]) sequence_f.get(i);
int sum=0;
for(int j=0;j<s.length;j++){
int t=1;
int sum2=sum;
while (sum2>0){
sum2 = sum2 / 10;
t=t*10;
}
sum=sum+s[s.length-j-1]*t;
}
if (i==0){
min=sum;
result=s;
}
if (sum<min){
min=sum;
result=s;
}
}
return result;
}
} 回復更多評論

# re: google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) 2006-08-23 14:29 yichao.zhang

再提交一份

package org.chao.test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Vector;

public class HardDuplicateRemover {
int[] process(int[] sequence) {
Map<Integer, Vector<Integer>> map = new HashMap<Integer, Vector<Integer>>();
for (int i = 0; i < sequence.length; i++) {
if (null == map.get(sequence[i])) {
Vector<Integer> v = new Vector<Integer>();
v.add(1);
v.add(i);
map.put(sequence[i], v);
} else {
Vector<Integer> v = map.get(sequence[i]);
int value = v.get(0);
v.set(0, value + 1);
v.add(i);
map.put(sequence[i], v);
}
}

List<Integer> keys = new ArrayList<Integer>();
for (Iterator<Integer> i = map.keySet().iterator(); i.hasNext();) {
keys.add(i.next());
}
Collections.sort(keys);

for (Iterator<Integer> i = keys.iterator(); i.hasNext();) {
int key = i.next();
process(key, map, sequence);
}

int size = keys.size();
int[] ret = new int[size];
int j = 0;
for (int i = 0; i < sequence.length; i++) {
if (sequence[i] != 0) {
ret[j++] = sequence[i];
}
}
return ret;
}

private void process(int key, Map<Integer, Vector<Integer>> map, int[] sequence) {
Vector<Integer> v = map.get(key);
int num = v.get(0);
if (num > 1) {
for (int i = 2; i < v.size(); i++) {
int p = v.get(i);
sequence[p] = 0;
}
int pp = v.get(1);
v.removeAllElements();
v.add(1);
v.add(pp);

}

int start = v.get(1);
if(start > 0 ){
for (int i = 0; i < start; i++) {
int value = sequence[i];
if(value != 0){
Vector<Integer> v2 = map.get(value);
//如果start后面還有值就為0
if (v2.get(v2.size() - 1) > start) {
sequence[i] = 0;
int size = v2.get(0);
v2.remove(0);
v2.remove(i);
v2.add(0, size - 1);
}
}
}
}
}

private void print(int[] is) {
for (int i = 0; i < is.length; i++) {
System.out.print(is[i]+",");
}
System.out.println();
}

public static void main(String[] args) {
HardDuplicateRemover hdr = new HardDuplicateRemover();
hdr.print(hdr.process(new int[]{5, 4, 1, 5}));
}
}
回復更多評論

# re: google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) 2007-01-16 15:36 zhangjiji

//-----------------------------
#include <map>
#include <vector>

//for output
#include <algorithm>
#include <iterator>
#include <iostream>

std::vector<int> foo(const std::vector<int>& iv)
{
std::vector<int> result;

if(iv.size()==0)
return result;

std::map<int,int> table;

for(std::vector<int>::const_iterator it=iv.begin();it!=iv.end();++it)
{
++table[*it];
}

std::vector<int>::const_iterator itpre=iv.begin();
std::vector<int>::const_iterator itend=iv.end();

std::vector<int>::const_iterator it=itpre;
++it;

for(;it!=itend;++it,++itpre)
{
if(*it<*itpre)
{
if(--table[*itpre]==0)
{
result.push_back(*itpre);
--table[*itpre];
}
}
else
{
if(table[*itpre]!=-1)
{
result.push_back(*itpre);
table[*itpre]=-1;
}
}
}
//handle the last one
if(table[*itpre]!=-1)
{
result.push_back(*itpre);
}

return result;
}

int main()
{

int ia[]={3,2,4,1,1,3,2,4,5,4};
std::vector<int> iv(ia,ia+10);
std::vector<int> result=foo(iv);
std::copy(result.begin(),result.end(),std::ostream_iterator<int>(std::cout," "));
std::cout<<"\n";

int ia2[]={1,1,1,1,1,1,1,1,1,1};
std::vector<int> iv2(ia2,ia2+10);
std::vector<int> result2=foo(iv2);
std::copy(result2.begin(),result2.end(),std::ostream_iterator<int>(std::cout," "));
std::cout<<"\n";

int ia3[]={5,4,3,2,1,5,4,3,2,1};
std::vector<int> iv3(ia3,ia3+10);
std::vector<int> result3=foo(iv3);
std::copy(result3.begin(),result3.end(),std::ostream_iterator<int>(std::cout," "));
std::cout<<"\n";

}
回復更多評論

# re: google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) 2007-01-16 22:07 zhangjiji

#include <vector>
#include <map>

#include <iostream>
#include <algorithm>
#include <iterator>

std::vector<int> foo(const std::vector<int>& iv)
{
std::vector<int> result;

if(iv.size()==0)
return result;

std::vector<int>::const_iterator itcur=iv.begin();
std::vector<int>::const_iterator itend=iv.end();

std::map<int,int> table;

for(std::vector<int>::const_iterator it=itcur;it!=itend;++it)
{
++table[*it];
}

for(;itcur!=itend;++itcur)
{
if(table[*itcur]==1) //no duplicate
result.push_back(*itcur);
else if(table[*itcur]==0) //already handle
continue;
else
{
std::vector<int>::const_iterator temp=itcur+1;
while(1)
{
if(table[*temp]!=0)
{
if(*itcur>*temp)
{
--table[*itcur];
break;
}
else
{
if(table[*temp]==1)
{
result.push_back(*itcur);
table[*itcur]=0;
break;
}
}
++temp;
}
else if(temp==itend)
{//all the same
result.push_back(*itcur);
table[*itcur]=0;
break;
}
}
}
}

return result;
}

int main()
{
int ia[]={3,2,4,1,1,3,2,4,5,4};
std::vector<int> iv(ia,ia+10);
std::vector<int> result=foo(iv);
std::copy(result.begin(),result.end(),std::ostream_iterator<int>(std::cout," "));
std::cout<<"\n";

int ia2[]={1,1,1,1,1,1,1,1,1,1};
std::vector<int> iv2(ia2,ia2+10);
std::vector<int> result2=foo(iv2);
std::copy(result2.begin(),result2.end(),std::ostream_iterator<int>(std::cout," "));
std::cout<<"\n";

int ia3[]={5,4,3,2,1,5,4,3,2,1};
std::vector<int> iv3(ia3,ia3+10);
std::vector<int> result3=foo(iv3);
std::copy(result3.begin(),result3.end(),std::ostream_iterator<int>(std::cout," "));
std::cout<<"\n";
}
回復更多評論

# re: google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) 2007-10-27 00:57 Tomato

我的答案：

public class HardDuplicateRemover {

public static void main(String[] args) {
HardDuplicateRemover h = new HardDuplicateRemover();
System.out.println("{5,6,5,1,6,5} returns: " + h.printIntArray(h.process(new int[] { 5, 6, 5, 1, 6, 5 })));
System.out.println("{3, 2, 4, 2, 4, 4} returns: " + h.printIntArray(h.process(new int[] {3, 2, 4, 2, 4, 4})));
System.out.println("{6, 6, 6, 6, 6, 6} returns: " + h.printIntArray(h.process(new int[] {6, 6, 6, 6, 6, 6})));
System.out.println("{1, 3, 2, 4, 2, 3} returns: " + h.printIntArray(h.process(new int[] {1, 3, 2, 4, 2, 3})));
System.out.println("{5, 4, 1, 5} returns: " + h.printIntArray(h.process(new int[] {5, 4, 1, 5})));
}

public int[] process(int[] sequence) {
String result = "";

for (int i = 0; i < sequence.length; i++) {
int s = sequence[i];
if (result.indexOf(s+"") < 0) {
// not contain
result += s;
} else {
String newResult = result.replaceAll(s + "", "") + s;
int smallLen = Math.min(result.length(), newResult.length());
for (int j = 0; j < smallLen; j++) {
int resultDigit = Integer.valueOf(
result.substring(j, j + 1)).intValue();
int newResultDigit = Integer.valueOf(
newResult.substring(j, j + 1)).intValue();
if (resultDigit > newResultDigit) {
result = newResult;
break;
}
else if(resultDigit < newResultDigit)
break;
}
}

}

int[] output = new int[result.length()];
for (int i = 0; i < result.length(); i++) {
output[i] = Integer.valueOf(result.substring(i, i + 1)).intValue();
}

return output;
}

private String printIntArray(int[] ints) {
String result = "{";
for (int i = 0; i < ints.length; i++) {
if (i > 0)
result += "," + ints[i];
else {
result += ints[i];
}
}
return result + "}";
}

} 回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 沒忍住手癢做了一道題，結果還沒作對。差點被燕潘考倒了 1000分模擬題CraneWork 500分模擬題 MaximalPalindromeSubstrings 250分模擬題 SalesRouting SecretSum (code jam china round2 500分真題) FactorialSystem (code jam china round2 300分真題) RecurringNumbers (code jam china 1000分真題) google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) google中國編程挑戰賽入圍賽真題 -- BlockStructure(500分)

emu in blogjava

公告

常用鏈接

留言簿(92)

隨筆分類(20)

隨筆檔案(171)

文章分類(89)

文章檔案(103)

相冊

收藏夾(46)

友情連接

收藏

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

評論