LeetCode-Number of 1 Bits

发表于 2014-07-14

LeetCode地址：https://leetcode.com/problems/number-of-1-bits/

Problem:
Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

思路

使用移位操作，每次将最后的最低位累加
我想说一模一样的代码，Java和C++的执行效率真的相差挺大

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int i=0;
        int sum=0;
        for(;i<32;i++)
        {
            
            sum+=n&0x1;
            n=n>>1;
        }
        
        return sum;
    }
};

the Runetime is 10ms

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int i=0;
        int sum=0;
        for(;i<32;i++)
        {
            
            sum+=n&0x1;
            n=n>>1;
        }
        
        return sum;
    }
}

the Runtime is 239ms

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-Single Number II

By Kubi Code

发表于 2014-07-12

LeetCode地址：https://leetcode.com/problems/single-number-ii/

Problem:
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?

思路

将数组A中每个整形的二进制分散到一个32位数组A上求和，出现3次的在该位上的和肯定是3的倍数

public class Solution {
    public int singleNumber(int[] A) {
        int ret=0,index=0;
        int[] binarySum=new int[32];
        if(A==null || A.length==0)
            return ret;
        
        for(int i=0;i<A.length;i++)
        {
            index=0;
            do
            {
                binarySum[index++]+=A[i]%2;
                A[i]/=2;
            }while(A[i]!=0);
        }
        
        
        for(int i=0;i<binarySum.length;i++)
        {
            index=binarySum[i]%3;
            if(Math.abs(index)>1)
            {
                index=(index+3)%3;
            }
            ret+=Math.pow(2, i)*(index);
        }
        
        return ret;
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-Linked List Cycle II

By Kubi Code

发表于 2014-07-10

LeetCode地址：https://leetcode.com/problems/linked-list-cycle-ii/

Problem:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode cycleStart=null,
                singleStepNode=null,
                doubleStepNode=null;
        boolean isCycle=false;
        
        if(head==null)
            return cycleStart;
        
        singleStepNode =head;
        doubleStepNode=head;
        
        while(singleStepNode!=null && doubleStepNode!=null && doubleStepNode.next!=null)
        {
            singleStepNode=singleStepNode.next;

            doubleStepNode=doubleStepNode.next.next;
            
            if(singleStepNode==doubleStepNode)
            {
                isCycle=true;
                break;
            }
        }
        
        if(isCycle)
        {
            singleStepNode=head;
            while(singleStepNode != doubleStepNode)
            {
                singleStepNode=singleStepNode.next;
                doubleStepNode=doubleStepNode.next;
            }
            
            cycleStart=singleStepNode;
        }
        
        return cycleStart;
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-Single Number

By Kubi Code

发表于 2014-07-10

LeetCode地址：https://leetcode.com/problems/single-number/

Problem:
Given an array of integers, every element appears twice except for one. Find that single one.

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

思路：

两个相同数据进行异或操作之后为0
一个数字与0进行异或操作之后还是自己

public class Solution {
    public int singleNumber(int[] A) {
        int ret=0;
        if(A==null || A.length==0)
            return ret;
        
        ret=A[0];
        for(int i=1;i<A.length;i++)
        {
            ret=ret^A[i];
        }
        
        return ret;
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-Evaluate Reverse Polish Notation

By Kubi Code

发表于 2014-07-08

LeetCode地址：https://leetcode.com/problems/evaluate-reverse-polish-notation/

Problem:
Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> numStack=new Stack<Integer>();
        Integer ret=Integer.MAX_VALUE;
        for(String str:tokens)
        {
            if(str.matches("-?\\d+"))
            {
                numStack.push(Integer.parseInt(str));
                
                
            }else{
                
                ret=numStack.pop();
                switch(str)
                {
                    case "+":ret=numStack.pop()+ret;break;
                    case "-":ret=numStack.pop()-ret;break;
                    case "*":ret=numStack.pop()*ret;break;
                    case "/":ret=numStack.pop()/ret;break;
                }
                numStack.push(ret);
                
            }
        }
        
        
        return numStack.pop();
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-Clone Graph

By Kubi Code

发表于 2014-07-08

LeetCode地址：https://leetcode.com/problems/clone-graph/

Problem:
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node==null)
            return null;
        
        HashMap<Integer,UndirectedGraphNode> graphMap=new HashMap<Integer,UndirectedGraphNode>();
        Queue<UndirectedGraphNode> visit=new LinkedList<UndirectedGraphNode>();
        UndirectedGraphNode temp;
        
        visit.add(node);
        
        while(!visit.isEmpty())
        {
            temp=visit.poll();
            
            if(!graphMap.containsKey(temp.label))
            {
                UndirectedGraphNode graphNode=new UndirectedGraphNode(temp.label);
                graphMap.put(temp.label, graphNode);
                
                visit.addAll(temp.neighbors);
            }
        }
        
        visit.add(node);
        while(!visit.isEmpty())
        {
            temp=visit.poll();
            UndirectedGraphNode graphNode=graphMap.get(temp.label);
            if(graphNode.neighbors.size()==0 && temp.neighbors.size()!=0)
            {
                for(UndirectedGraphNode neighbor:temp.neighbors)
                {
                    graphNode.neighbors.add(graphMap.get(neighbor.label));
                    visit.add(neighbor);
                }
            }
        }
        
        return graphMap.get(node.label);
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-Candy

By Kubi Code

发表于 2014-07-07

LeetCode地址：https://leetcode.com/problems/candy/

Problem:
There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

public class Solution {
    public int candy(int[] ratings) {
        int n=ratings.length;
        if(n<2) return n;

        int[] maxseq=new int[n];
        for(int i=n-2; i>=0; --i)
            if(ratings[i]>ratings[i+1]) maxseq[i]=1+maxseq[i+1];

        int[] candies=new int[n];
        
        int sum=0;
        for(int i=0; i<n; ++i){
            candies[i]=1;
            
            if(i!=0 && ratings[i]>ratings[i-1])
            {
                candies[i]=1+Math.max(candies[i-1], maxseq[i]);
            }else{
                candies[i]+=maxseq[i];
            }
            
            sum+=candies[i];
        }
        return sum;
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-Reorder List

By Kubi Code

发表于 2014-07-06

LeetCode地址：https://leetcode.com/problems/reorder-list/

Problem:
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head==null || head.next==null)
            return ;
        
        Stack<ListNode> stack=new Stack<ListNode>();
        
        ListNode temp=head;
        while(temp!=null)
        {
            stack.push(temp);
            temp=temp.next;
        }
        
        int length=stack.size();
        temp=head;
        for(int i=0;i<Math.floor((length+1)/2)-1;i++)
        {
            ListNode node=stack.pop();
            node.next=temp.next;
            temp.next=node;
            
            temp=node.next;
        }
        stack.pop().next=null;
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-Best Time to Buy and Sell Stock III

By Kubi Code

发表于 2014-07-05

LeetCode地址：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

Problem:
Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

public class Solution {
    public int maxProfit(int[] prices) {
        int ret=0,
            buy=0,
            sale=0,
            length=prices.length;
        
        if(length<2)
            return ret;
        
        int[] historyProfit=new int[length];
        
        buy=prices[0];
        for(int i=1;i<length;i++)
        {
            historyProfit[i]=getMax(historyProfit[i-1], prices[i]-buy);
            buy=getMin(buy, prices[i]);
        }
        
        sale=prices[length-1];
        ret=historyProfit[length-1];
        for(int i=length-1;i>0;i--)
        {
            ret=getMax(ret, historyProfit[i-1]+sale-prices[i]);
            sale=getMax(sale, prices[i]);
        }
        
        return ret;
    }
    
    public int getMax(int a,int b)
    {
        return a>b?a:b;
    }
    
    public int getMin(int a,int b)
    {
        return a>b?b:a;
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-Linked List Cycle

By Kubi Code

发表于 2014-07-05

LeetCode地址：https://leetcode.com/problems/linked-list-cycle/

Problem:
Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean ret=false;
        
        if(head==null)
            return ret;
        
        ListNode singleStepNode=head,
                doubleStepNode=head;
        
        while(singleStepNode.next !=null && 
                doubleStepNode.next!=null &&
                doubleStepNode.next.next !=null)
        {
            singleStepNode=singleStepNode.next;
            doubleStepNode=doubleStepNode.next.next;
            
            if(singleStepNode.next==doubleStepNode.next)
            {
                ret=true;
                break;
            }
        }
        
        
        return ret;
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

Kubi Code'Blog

The palest ink is better than the best memory.

LeetCode-Number of 1 Bits

LeetCode-Single Number II

LeetCode-Linked List Cycle II

LeetCode-Single Number

LeetCode-Evaluate Reverse Polish Notation

LeetCode-Clone Graph

LeetCode-Candy

LeetCode-Reorder List

LeetCode-Best Time to Buy and Sell Stock III

LeetCode-Linked List Cycle