emu in blogjava

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks

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 }

2)

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

3)

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

4)

????
{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 阅读(4485) 评论(9)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# re: google中国编程挑战赛入围赛真题 -- HardDuplicateRemover(1000分) 2005-12-21 10:34 Michael Michael
我想知道你这些题是从哪里copy过来的,谢谢  回复  更多评论
  

# re: google中国编程挑战赛入围赛真题 -- HardDuplicateRemover(1000分) 2005-12-21 13:42 emu
参赛就可以copy题目出来了。  回复  更多评论
  

# re: google中国编程挑战赛入围赛真题 -- HardDuplicateRemover(1000分) 2005-12-22 16:38 dotNet程序员
我答案如下:
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 + "}";
}

}  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: