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));
    }