首页 > 专题系列 > Java解POJ > POJ 2591 Set Definition [解题报告] Java
2013
11-11

POJ 2591 Set Definition [解题报告] Java

Set Definition

问题描述 :

Set S is defined as follows:

(1) 1 is in S;

(2) If x is in S, then 2x + 1 and 3x + 1 are also in S;

(3) No other element belongs to S.

Find the N-th element of set S, if we sort the elements in S by increasing order.

输入:

Input will contain several test cases; each contains a single positive integer N (1 <= N <= 10000000), which has been described above.

输出:

For each test case, output the corresponding element in S.

样例输入:

100
254

样例输出:

418
1461

解题代码:

//* @author: [email protected]
import java.util.*;
public class Main
{
 public static void main(String[] args)
 {
   TreeSet< Long> t=new TreeSet< Long>();
   Scanner in=new Scanner(System.in);
   int[] arr=new int[10000001];
   arr[0]=1;
   int k1=0,k2=0;
   for(int i=1;i< 10000001;i++)
    {
	int y1=arr[k1]*2+1;
	int y2=arr[k2]*3+1;
	arr[i]=Math.min(y1, y2);
	if(arr[i]==y1) k1++;
	if(arr[i]==y2) k2++;
     }
    while(in.hasNext())
    {
	int a=in.nextInt();
	System.out.println(arr[a-1]);
    }
  }
}

  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。