Software Rendering with JPCT and java2d together

package com.jengine.kevinchwong;
import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Font;
import java.awt.Graphics2D;
import java.awt.GraphicsEnvironment;
import java.awt.RenderingHints;
import java.awt.geom.AffineTransform;
import java.awt.geom.Ellipse2D;
 
import com.threed.jpct.*;
import javax.swing.*;
 
public class SoftwareRenderTest {
 
private World world;
private FrameBuffer buffer;
private Object3D box;
private JFrame frame;
 
public static void main(String[] args) throws Exception {
  new SoftwareRenderTest().loop();
}
 
public SoftwareRenderTest() throws Exception {
 
  frame=new JFrame("Hello world");
  frame.setSize(800, 600);
  frame.setVisible(true);
  frame.setDefaultCloseOperation(JFrame.HIDE_ON_CLOSE);
 
  world = new World();
  world.setAmbientLight(0, 255, 0);
 
  TextureManager.getInstance().addTexture("box", new Texture("res/textures/box.jpg"));
 
  box = Primitives.getBox(13f, 2f);
  box.setTexture("box");
  box.setEnvmapped(Object3D.ENVMAP_ENABLED);
  box.build();
  world.addObject(box);
 
  world.getCamera().setPosition(50, -50, -5);
  world.getCamera().lookAt(box.getTransformedCenter());
}
 
private void loop() throws Exception {
  buffer = new FrameBuffer(800, 600, FrameBuffer.SAMPLINGMODE_NORMAL);
 
  while (frame.isShowing()) {
    box.rotateY(0.01f);
    buffer.clear(java.awt.Color.BLUE);
    world.renderScene(buffer);
    world.draw(buffer);
    buffer.update();
 
//GraphicsEnvironment ge = GraphicsEnvironment.getLocalGraphicsEnvironment();
//    ge.getAllFonts();
 
    RenderingHints rh =
           new RenderingHints(RenderingHints.KEY_ANTIALIASING, 
           RenderingHints.VALUE_ANTIALIAS_ON);
 
       rh.put(RenderingHints.KEY_RENDERING,
              RenderingHints.VALUE_RENDER_QUALITY);
 
    Graphics2D g2d = (Graphics2D) buffer.getGraphics();
   
    g2d.setFont(new Font("Serif", Font.PLAIN, 13));
    //g2d.setFont(new Font("Franklin Gothic Medium", Font.PLAIN, 33));
   
       g2d.drawString("??Most relationships seem so transitory", 20, 130);
       g2d.drawString("They're all good but not the permanent one", 20, 160);
       g2d.drawString("Who doesn't long for someone to hold", 20, 190);
       g2d.drawString("Who knows how to love you without being told", 20, 220);
       g2d.drawString("Somebody tell me why I'm on my own", 20, 250);
       g2d.drawString("If there's a soulmate for everyone", 20, 280);
   
 
       Ellipse2D e = new Ellipse2D.Double(0, 0, 80, 130);
       g2d.setStroke(new BasicStroke(1));
       g2d.setColor(Color.gray);
 
 
       for (double deg = 0; deg < 360; deg += 5) {
           AffineTransform at =
               AffineTransform.getTranslateInstance(400,300);
           at.rotate(Math.toRadians(deg));
           g2d.draw(at.createTransformedShape(e));
       }
       
      buffer.display(frame.getGraphics());
      Thread.sleep(10);
    }
    buffer.disableRenderer(IRenderer.RENDERER_OPENGL);
    buffer.dispose();
    frame.dispose();
    System.exit(0);
  }
}

Test for XML Import and MOXy + EclipseLink

package kcwobjectxmljsontest;
 
import javax.xml.bind.*;
import javax.xml.bind.annotation.*;
import java.io.FileOutputStream;
import java.util.ArrayList;
import java.util.List;
import javax.xml.transform.stream.StreamSource;

/**
 *
 * @author KCW
 */
public class kcwMOXytest {
    
    @XmlRootElement
    @XmlType(propOrder={"street", "city", "zip"})
    @XmlAccessorType(XmlAccessType.FIELD)
    static public class Address {

        String street;
        String city;
        String zip;
    }

    @XmlRootElement
    @XmlType(propOrder={"name","address"})
    @XmlAccessorType(XmlAccessType.FIELD)
    static public class Customer {

        String name;

        @XmlElement
        Address address;

    }
    
    @XmlRootElement
    static public class Customers {
        @XmlElement(name="customer")
        List<Customer> customers;
    }
    
    
    public static void main(String[] args) throws Exception {
        JAXBContext jc = JAXBContext.newInstance(Customers.class);
 
        System.out.println("---------------------");
        System.out.println("Convert XML to Object");
        System.out.println("---------------------");

        Unmarshaller unmarshaller = jc.createUnmarshaller();
        StreamSource xml = new StreamSource("data/customers.xml");
//        Customers customers = (Customers) unmarshaller.unmarshal(xml);
        Customers doc= (Customers) unmarshaller.unmarshal(xml);
        
//        System.out.println("customers.test="+customers.test);
        System.out.println("customerlist.customers.="+doc.customers.size());
        int i=0;
        for(Customer s : doc.customers) {
            System.out.println("doc.customers.get("+i+").name="+s.name);
            System.out.println("doc.customers.get("+i+").address.city="+s.address.city);
            System.out.println("doc.customers.get("+i+").address.street="+s.address.street);
            System.out.println("doc.customers.get("+i+").address.zip="+s.address.zip);
            System.out.println("---------------------");
            i++;
        }        


        System.out.println("");
        System.out.println("");
        System.out.println("---------------------");
        System.out.println("Convert Object to XML");
        System.out.println("---------------------");

        Marshaller marshaller = jc.createMarshaller();
        marshaller.setProperty(Marshaller.JAXB_FORMATTED_OUTPUT, true);
        marshaller.marshal(doc, System.out);
        
        FileOutputStream fos= new FileOutputStream("data/test-list.xml");
        marshaller.marshal(doc, fos);
    }
}


//================================================
// Customers.xml

<?xml version="1.0" encoding="UTF-8"?>

<customers>

    <customer>

        <name>Jane Doe</name>

        <address>

            <zip>19873</zip>

            <street>1 A Street</street>

            <city>Any Town</city>

        </address>

    </customer>

    <customer>

        <name>Jane Doe 2</name>

        <address>

            <zip>19872</zip>

            <street>2 A Street</street>

            <city>Any Town Area</city>

        </address>

    </customer>

</customers>

Test for XML and perst.jar

package kcwxmltest;

import org.garret.perst.*;
import java.io.*;

public class TestXML { 
    static class Record extends Persistent { 
        String strKey;
        long   intKey;
        double realKey;
    };
    
    static class Indices extends Persistent {
        Index      strIndex;
        FieldIndex intIndex;
        FieldIndex compoundIndex;
    }

    final static int nRecords = 100000;
    final static int pagePoolSize = 32*1024*1024;

    static public void main(String[] args) throws Exception {   
        Storage db = StorageFactory.getInstance().createStorage();

        for (int i = 0; i < args.length; i++) { 
            if ("altbtree".equals(args[i])) { 
                db.setProperty("perst.alternative.btree", Boolean.TRUE);
            }
        }
        db.open("data/test1.dbs", pagePoolSize);
        Indices root = (Indices)db.getRoot();
        if (root == null) { 
            root = new Indices();
            root.strIndex = db.createIndex(String.class, true);
            root.intIndex = db.createFieldIndex(Record.class, "intKey", true);
            root.compoundIndex = db.createFieldIndex(Record.class, new String[]{"strKey", "intKey"}, true);
            db.setRoot(root);
        }
        FieldIndex intIndex = root.intIndex;
        FieldIndex compoundIndex = root.compoundIndex;
        Index strIndex = root.strIndex;
        long start = System.currentTimeMillis();
        long key = 1999;
        int i;
        for (i = 0; i < nRecords; i++) { 
            Record rec = new Record();
            key = (3141592621L*key + 2718281829L) % 1000000007L;
            rec.intKey = key;
            rec.strKey = Long.toString(key);
            rec.realKey = (double)key;
            intIndex.put(rec);                
            strIndex.put(new Key(rec.strKey), rec);                
            compoundIndex.put(rec);                
        }
        db.commit();
        System.out.println("Elapsed time for inserting " + nRecords + " records: " 
                           + (System.currentTimeMillis() - start) + " milliseconds");

        start = System.currentTimeMillis();
        Writer writer = new BufferedWriter(new FileWriter("data/test.xml"));
        db.exportXML(writer);
        writer.close();
        System.out.println("Elapsed time for XML export " + (System.currentTimeMillis() - start) + " milliseconds");
        db.close();
        db.open("data/test2.dbs", pagePoolSize);

        start = System.currentTimeMillis();
        Reader reader = new BufferedReader(new FileReader("data/test.xml"));
        db.importXML(reader);
        reader.close();
        System.out.println("Elapsed time for XML import " + (System.currentTimeMillis() - start) + " milliseconds");
        root = (Indices)db.getRoot();
        intIndex = root.intIndex;
        strIndex = root.strIndex;
        compoundIndex = root.compoundIndex;
        
        start = System.currentTimeMillis();
        key = 1999;
        for (i = 0; i < nRecords; i++) { 
            key = (3141592621L*key + 2718281829L) % 1000000007L;
            String strKey = Long.toString(key);
            Record rec1 = (Record)intIndex.get(new Key(key));
            Record rec2 = (Record)strIndex.get(new Key(strKey));
            Record rec3 = (Record)compoundIndex.get(new Key(strKey, new Long(key)));
            Assert.that(rec1 != null);
            Assert.that(rec1 == rec2);
            Assert.that(rec1 == rec3);
            Assert.that(rec1.intKey == key);
            Assert.that(rec1.realKey == (double)key);
            Assert.that(strKey.equals(rec1.strKey));
        }
        System.out.println("Elapsed time for performing " + nRecords*2 + " index searches: " 
                           + (System.currentTimeMillis() - start) + " milliseconds");
        db.close();
    }
}

// ==============================================
// Sample data not provided.

Test for the access to DB2

package kcwdb2test;

import com.ibm.as400.access.AS400JDBCConnectionPoolDataSource;
import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.sql.Statement;

public class KcwDB2TestDev {
   
    public static void main(String[] args) {

            Connection dbConnection = null;
            String cipher="AES";
            String cipherdomain="INTRANET";
            String host="1.2.3.4";
            String dblibrary="WWWDLIB";

            String login="not-encoded";
            String user="kcw";
            String password="12345678";
            
     try {
      AS400JDBCConnectionPoolDataSource datasource = new AS400JDBCConnectionPoolDataSource(host, user, password);
      datasource.setLibraries(dblibrary);
         dbConnection = datasource.getConnection();
                
                // Sample 1
                String query = "SELECT DMNDMCDEC,USRFINAMC,USRLANAMC,USREMPIDN,USRUSIDNN FROM ASWDLIB.WWUSR10 where DMNDMCDEC='INTRANET'";
                Statement statement = dbConnection.createStatement();
                ResultSet resultSet = statement.executeQuery(query);
                
                while(resultSet.next()) {
                    System.out.println(
                        resultSet.getString(1) + " " +
                        resultSet.getString(2) + " " +
                        resultSet.getString(3) + " " +
                        resultSet.getInt(4) + " " +
                        resultSet.getInt(5));
                }
                statement.close();

                // Sample 2
                PreparedStatement statement2 = dbConnection.prepareStatement(
                        "SELECT DMNDMCDEC,USRFINAMC,USRLANAMC,USREMPIDN,USRUSIDNN FROM ASWDLIB.WWUSR10 where DMNDMCDEC=?"
                        );
                statement2.setString(1, "INTRANET");
                ResultSet resultSet2 = statement2.executeQuery();
                while(resultSet2.next()) {
                    System.out.println(
                        resultSet2.getString(1) + " " +
                        resultSet2.getString(2) + " " +
                        resultSet2.getString(3) + " " +
                        resultSet2.getInt(4) + " " +
                        resultSet2.getInt(5));
                }
                statement2.close();

                
                dbConnection.close();

     } catch (SQLException sqle) {
                sqle.printStackTrace();
     }
            
    }
}

Leetcode: triangle

public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int n1=triangle.size();
        int n2=triangle.get(n1-1).size();
        int[] sum=new int[n1+1];



// Bottom Up

        for(int i=n1;i>0;i--)
        {
            int[] newsum=new int[n1+1];
            for(int j=0;j<i;j++)
            {
                int ans1=sum[j];
                int ans2=sum[j+1];
                int ans=(ans1<ans2)?ans1:ans2;
                newsum[j]=triangle.get(i-1).get(j)+ans;
            }
            sum=newsum;
        }
        return sum[0];

// Top down
/*      
        for(int i=0;i<n1;i++)
        {
            int[] newsum=new int[n2];
            for(int j=0;j<=i;j++)
            {
                int x=triangle.get(i).get(j);
                int ans1=sum[j]+x;
                int ans2=Integer.MAX_VALUE;

                if(j>0)ans2=sum[j-1]+x;
               
                if(j==0)newsum[j]=ans1;
                else if(j==i)newsum[j]=ans2;
                else newsum[j]=(ans1<ans2)?ans1:ans2;
            }
            sum=newsum;
        }

        int m=Integer.MAX_VALUE;
        for(int i=0;i<n2;i++)
            if(sum[i]<m)m=sum[i];
           
        return m;
 */

    }
}

LeetCode : Search insert position

It is easy to do by O(N)...

But this solution is by O(logN)

public class Solution {
    public int searchInsert(int[] A, int target) {

        int f=0;
        int l=A.length;
        int m;
        
        while(true)
        {
            m=(f+l)/2;
            if(m>0&&m<A.length)
            {    if(target>A[m-1]&&target<=A[m]) return m;}
            else if(m==0)
            {
                if(target<=A[m]) return m;
            }
            else
            {    if(target>A[m-1]) return m;}

            
            if(target>A[m])
                f=m+1;
            else if(target<A[m])
                l=m;
        }
    }
}

Leet Code: search in rotated sorted array with duplicate...

Search in Rotated Sorted Array II

 

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

This one is not difficult to find the trick, 
but if you think in a wrong way, you will use a lot of effort to ignore duplicate items..

* If you just think on the index, you don't need recursive...
* In each loop, change l and f in order to find a right region to go on searching...

public class Solution {
    
    public boolean search(int[] A, int target) {
        
        int f=0;
        int l=A.length-1;
        
        while(l>=f)
        {
            int m=(f+l)/2;
            if(A[m]==target)
                return true;

            if(A[f]<A[m])
            {
                if(target>=A[f]&&target<=A[m])
                    l=m-1;
                else
                    f=m;
            }
            else if(A[f]>A[m])
            {
                if(target>=A[m]&&target<=A[l])
                    f=m+1;
                else
                    l=m;
            }
            else            
                f++;              // Trick: A[f]==A[m])
        }
        return false;

    }
}

LeetCode : Combination

public class Solution {
   
    public void reorg(int [] p, int x, int k)
    {
        int c=p[x]+1;
        for(int i=x+1;i<k;i++,c++)
           p[i]=c;
        return;
    }
   
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
       int p[]=new int[k];
       p[0]=1;
       reorg(p,0,k);
       int bound=n-k+2;
     
       ArrayList<ArrayList<Integer>> all=new ArrayList<ArrayList<Integer>>();
     
       int kk=k-1;
       while(p[0]<bound&&kk>=0)
       {
           ArrayList<Integer> al=new ArrayList<Integer>();
           for(int i=0;i<k;i++)
             al.add(i,p[i]);
           all.add(al);
         
           kk=k-1;
           boolean reorgflag=false;
           while(kk>=0)
           {
               p[kk]++;

               if(reorgflag){
                   reorg(p,kk,k);
                   reorgflag=false;
               }
                       
               if(p[kk]>n-k+1+kk)
               {
                   kk--;
                   reorgflag=true;
               }
               else break;
           }
       }

        return all;
    }
}

LeetCode : Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

**通常找max的題目, 元素中有負值的話，計算cost時，千萬不要把負值的部份也加進去。因為答案是可以選擇性不包括負值部份。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int calcmaxbranch(TreeNode root,HashMap<TreeNode,Integer> maxbranch)
    {
        if(root==null)return 0;
        int llen=calcmaxbranch(root.left,maxbranch);
        int rlen=calcmaxbranch(root.right,maxbranch);
        int ext=(llen>rlen)?llen:rlen;
        int mylen=root.val+(ext>0)?ext:0;
        maxbranch.put(root,mylen);
        return mylen;
    }
    public int findMaxPathSum(TreeNode root,HashMap<TreeNode,Integer> maxbranch)
    {
        if(root==null)return 0;
        int sum2=Integer.MIN_VALUE;
        int sum3=Integer.MIN_VALUE;
        int sum11=0;
        if(root.left!=null)
        {
            sum11=maxbranch.get(root.left);
            sum2=findMaxPathSum(root.left,maxbranch);
        }
        int sum12=0;
        if(root.right!=null)
        {
            sum12=maxbranch.get(root.right);
            sum3=findMaxPathSum(root.right,maxbranch);
        }
        int sum1=root.val;
        if(sum11>0)sum1+=sum11;
        if(sum12>0)sum1+=sum12;
        int max=sum1;
        if(sum2>max)max=sum2;
        if(sum3>max)max=sum3;
        return max;
    }
   
    public int maxPathSum(TreeNode root) {
        HashMap<TreeNode,Integer> maxbranch=new HashMap<TreeNode,Integer>();
        calcmaxbranch(root,maxbranch);
        int res=findMaxPathSum(root,maxbranch);
        return res;
    }
}

LeetCode: Single Number 2

Given an array of integers, every element appears three times except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

public class Solution {
    public int singleNumber(int[] A) {
        int N=64;
        int countbit[]=new int[N];
        int countbitN[]=new int[N];
        int res=0;
        int resN=0;
        for(int i=0;i<A.length;i++)
        {
            int n=A[i];
            if(n>=0)
                for(int j=0;j<N;j++)
                    countbit[j]+=((n&(1<<j))>0)?1:0;
            else
                for(int j=0;j<N;j++)
                    countbitN[j]+=((-(1+n)&(1<<j))>0)?1:0;
           
        }
        for(int j=0;j<64;j++)
        {
            if(countbit[j]%3>0)res|=(1<<j);
            if(countbitN[j]%3>0)resN|=(1<<j);
        }
       
        return (resN>0)?-(resN+1):res;
    }
}

LeetCode : anagrams

public class Solution {
    
    public String hashcoding(String s){
        int count[]=new int[26];
        StringBuffer sb=new StringBuffer("H");
        for(int i=0;i<s.length();i++)
            count[s.charAt(i)-'a']++;
        for(int i=0;i<26;i++)
            if(count[i]>0)sb.append(""+(i+(int)'a')+count[i]);
        return sb.toString();
    }
    public ArrayList<String> anagrams(String[] strs) {
        HashMap<String,ArrayList<String>> hm= new HashMap<String,ArrayList<String>>();
        ArrayList<String> rl=new ArrayList<String>();
        int ecount=0;
        for(int i=0;i<strs.length;i++)
        {
            String hc=hashcoding(strs[i]);
            ArrayList<String> al=hm.get(hc);
            if(al==null)al=new ArrayList<String>();
            al.add(new String(strs[i]));
            if(hm.get(hc)==null)hm.put(hc,al);
        }
        
        for(ArrayList<String> al:hm.values())
        {
            if(al.size()>1)rl.addAll(al);
        }
        
        return rl;
    }
}

LeetCode:palindrome

Determine whether an integer is a palindrome. Do this without extra space.

public class Solution {
    public boolean isPalindrome(int x) {
        if(x<0) return false;
        if(x<10) return true;
        int l=(int)Math.log10(x)+1;
        for(int i=l/2;i>=1;i--)
        {
           int r100=(int)Math.pow(10,i);
           int l100=(int)Math.pow(10,l-i);
           int rc=x%r100;
           int lc=x/l100;
           int rcl=(int)Math.log10(rc)+1;
           int lcl=(int)Math.log10(lc)+1;
           if(lcl>1)
           {
                if((rc<10)&&(lc%((int)Math.pow(10,lcl))==0))
                if(rc%10==lc/(int)Math.pow(10,lcl))
                {
                    if(l-rc-lc==0)
                        return true;
                    else
                        return isPalindrome((x/r100)%10);
                }
           }
           else if(lcl==1&&rc==lc)
                if(l-rc-lc==0)
                    return true;
                else
                    return isPalindrome((x/r100)%10);
        }
return false;
    }
}

LeetCode : regular expression

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

public class Solution {
    public boolean isMatch(String s, String p) {
        
        // p=.*  s=c  ==> recursive
        
        // p=.   s=c  ==> p++, s++
        
        // p=x*  s=c  => p+=2
        //       s=x  => s++
        
        // p=x   s=c  => not
        //       s=x  => p++, s++
        
        int sl=s.length();
        int pl=p.length();
        char p1,p2;
        char s1;
        
        if(sl==0)
        {
            if(pl==0)return true;                                           // "":""    => T
            
            if(pl>1)                
            {
                p1=p.charAt(0);
                p2=p.charAt(1);                                             // "":"a*"  => T
                if(pl==2)                                                   // "":".*"  => T
                {
                     return (p2=='*'&&(p1=='.'||(p1>='a'&&p1<='z')||(p1>='A'&&p1<='Z')));
                }
                else if((p1>='a'&&p1<='z')||(p1>='A'&&p1<='Z')||p1=='.')   
                {
                    if(p2=='*') 
                            return isMatch(s,new String(p.substring(2)));   // "":"a*??" => recursive
                    else
                            return false;                                   // "":"a" => F
                }
            }
            return false;
        }
        
        if(sl>0&&pl==0) return false;                                       // "a...":""  => F
        
        p1=p.charAt(0);
        s1=s.charAt(0);
        if(pl==1)
        {
            if(p1=='.'||((p1==s1)&&((p1>='a'&&p1<='z')||(p1>='A'&&p1<='Z'))))
                return isMatch(new String(s.substring(1)),"");                  //"abc...":"?" => recursive
            else
                return false;
        }
        
        p2=p.charAt(1);
        if((p1>='a'&&p1<='z')||(p1>='A'&&p1<='Z'))                             
        {
            if(p2=='*')                                           // "abc...":"b*abc..." => test many cases
            {
                if(isMatch(s,new String(p.substring(2))))
                    return true;
                else
                    for(int i=0;(i<sl)&&s.charAt(i)==p1;i++)
                        if(isMatch(new String(s.substring(i+1)),new String(p.substring(2))))
                            return true;;
                return false;                                                   // "abc...":"a*cd.." =>F 
            }
            else
            {
                if(p1==s1)                                                      // "a...":"a..." =>recursive
                    return isMatch(new String(s.substring(1)),new String(p.substring(1)));
                else
                    return false;                                               // "a...":"b..." =>F
            }
        }
        else if(p1=='.')   
        {
            if(p2=='*')
            {
                if(pl==2)
                    return true;                                             // "????":".*"     => T
                else if(isMatch(s,new String(p.substring(2))))               // "a???":".*a???" => recursive
                    return true;
                else
                    for(int i=0;i<sl;i++)                             // "aaab??":".*b" =>test many cases
                        if(isMatch(new String(s.substring(i+1)),new String(p.substring(2))))
                            return true;
                return false;
            }
            else
            {                                                             // "ab???":".b???" => recursive
                    return isMatch(new String(s.substring(1)),new String(p.substring(1)));
            }
        }

        return false;
    }
}

LeetCode : Subset I

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

Input:[4,1,0]
Expected:[[],[0],[1],[4],[0,1],[0,4],[1,4],[0,1,4]]


public class Solution {
    
    // we do it recursively
    public void pickSS(ArrayList<ArrayList<Integer>> list, int[] remain)
    {
        if(remain==null)return;
        int rl=remain.length;
        if(rl==0) return;
        
        // seperate the list f + remain2
        int f=remain[0];
        int[] remain2=new int[rl-1];
        for(int i=0;i<rl-1;i++){
            remain2[i]=remain[i+1];
        }
        
        ArrayList<ArrayList<Integer>> templist = new ArrayList<ArrayList<Integer>>();

        // templist is addition list
        for(ArrayList<Integer> al:list)
        {
            ArrayList<Integer> nl=new ArrayList<Integer>(); //new list
            int all=al.size();
            if(all==0)
            {
                nl.add(0,f);
                templist.add(nl);  // empty list + one element f
            }
            else
            {
                for(int i=0;i<all;i++)
                    nl.add(i,(Integer)al.get(i));
                nl.add(all,f);
                templist.add(nl);   // joining a list + one element f.
            }
        }

        // result list = original list + temp list
        for(ArrayList<Integer> al:templist)
        {
            list.add(al);
        }
        
        // call next level
        pickSS(list,remain2);
    }

    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        res.add(new ArrayList<Integer>());
        
        //sort S
        for(int i=0;i<S.length;i++)
        {
            for(int j=i+1;j<S.length;j++)
            {
                if(S[j]<S[i])
                {
                    int t=S[i];
                    S[i]=S[j];
                    S[j]=t;
                }
            }
        }
        pickSS(res, S);
        return res;
    }
}

LeetCode : Sort a linked list with insertion sort.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    
    public ListNode insert(ListNode head,ListNode x)
    {
        ListNode pp=null;
        if(head==null)return x;

        for(ListNode p=head;p!=null;p=p.next)
        {
            if(x.val<p.val)
            {
                if(pp!=null)
                {
                    pp.next=x;
                    x.next=p;
                    return head;
                }
                else
                {
                    x.next=head;
                    return x;
                }
            }
            pp=p;
        }
        pp.next=x;           // dont 
        x.next=null;
        return head;
    }
    
    public ListNode insertionSortList(ListNode head) {
        
        ListNode ph,qh,qq;
        
        if(head==null)return head;
        if(head.next==null)return head;

        ph=head;
        qh=head.next;
        head.next=null;

        while(qh!=null)
        {
            qq=qh.next;      // we must use qq to save qh.next
                             // in case qh will change their structure 
                             // after insert()
            ph=insert(ph,qh);
            qh=qq;
        }
        return ph;
        
    }
}

LeetCode : Sort a linked list

Sort a linked list in O(n log n) time using constant space complexity.

    public ListNode merge(ListNode sA,ListNode sB)
    {
        if(sA==null)return sB;
        if(sB==null)return sA;
        ListNode hA=sA;
        ListNode hB=sB;
        ListNode x=null;
        ListNode hR=null;
        ListNode lR=null;
        while(!(hA==null&&hB==null))
        {
            if(hB==null)
            {
                x=hA;
                hA=hA.next;
            }
            else if(hA==null)
            {
                x=hB;
                hB=hB.next;
            }
            else if(hA.val<hB.val)  // Beware hA or hB is null
            {
                x=hA;
                hA=hA.next;
            }
            else
            {
                x=hB;
                hB=hB.next;
            }
         
            x.next=null;
            if(lR==null)
                hR=x;
            else
                lR.next=x;
            lR=x;
        }
        return hR;
    }
 
    public ListNode sortList(ListNode head) {
        if(head==null)return null;
        if(head.next==null)return head;
        ListNode q1=head,p1=head,p2=head;

// Seperate the link list in O(n);
        while(true)
        {
            if(p2.next==null)break;
            p2=p2.next;
            q1=p1;
            p1=p1.next;
            if(p2.next==null)break;
            p2=p2.next;
        }
        q1.next=null;
        if(p1==head)p1=null;

        return merge(sortList(head),sortList(p1));
    }

Building a data store API with PHP (2)

Next plan,

1. To reduce the speed of the query, we will add Family concept.

Each query just works on all objects of same Family.

2. We will add the User, Session, Role and Security concept.

Building a data store API with PHP (1)

What I want to do is try to use PHP to build a web application so that you can create JSON objects and stored in a PHP server.

The design is try to make it simple and generic.

These are some of the API functions.

1. New(json) --> You can create a completely new Object and store it into the server. A new Id supposed to be returned.

2. Wash(id, json) --> Empty fields, attributes and relations in an object.

3. Add(id, json) --> Just add new attributes and relations without delete the existing old data.

4. Mine(id, json) --> Just replace all attributes and relations with my data.

5. Your(id, json) --> Just add new attributes and relations if it does not exists.

6. Kill(id) --> Completed remove an object.

7. Query(json) --> Get a list of ids with given condition. 

8. Obtain(id[]) --> get a array of records based on the list of ids.

SRM 156 DIV 2 250

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class DiskSpace
{
public int minDrives(int[] used, int[] total)
{
int n= used.length;
int t=0;

ArrayList<Integer> l=new ArrayList();
for(int i=0;i<n;i++)
l.add(total[i]);
Collections.sort(l);

for(int i=0;i<n;i++)
{
t+=used[i];
}
int c=0;

 System.out.println(t);

for(int i=0;i<n;i++)
 System.out.println("-"+l.get(n-i-1));
for(int i=n-1;i>=0;i--,c++)
{
t-=l.get(i);
if(t<=0)break;
}
return c+1;
}

<%:testing-code%>
}
//Powered by [KawigiEdit] 2.0!

SRM 154 DIV-2 450

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class SuperRot
{
    public String cd="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 ";
    public String dc="NOPQRSTUVWXYZABCDEFGHIJKLMnopqrstuvwxyzabcdefghijklm5678901234 ";
public String decoder(String message)
{
String r="";
for(int i=0;i<message.length();i++)
{
r+=dc.charAt(cd.indexOf(message.charAt(i)));
}
return r;

}

<%:testing-code%>
}
//Powered by [KawigiEdit] 2.0!