huihancarl
BAN USERvoid PushZeros(int[] arr ){
int pos = 0 ;
for(int i = 0 ; i < arr.length ; i++){
if(arr[i]!= 0) arr[pos++] = arr[i];
}
for(int i = pos ; i < arr.length ; i++)
arr[i] = 0;
}
void PushZeros(int[] arr ){
int pos = 0 ;
for(int i = 0 ; i < arr.length ; i++){
if(arr[i]!= 0) arr[pos++] = arr[i];
}
for(int i = pos ; i < arr.length ; i++)
arr[i] = 0;
}
public Set<String> decode(String prefix , String code){
Set<String> set = new HashSet<String>();
if(code.length() == 0){
set.add(prefix);
return set;
}
if(code.charAt(0)=='0'){
return set;
}
set.addAll(decode(prefix+(char)(code.charAt(0) - '1' + 'a'), code.substring(1)));
if(code.length() <2) return set;
int tem = (code.charAt(0)-'0') *10 + code.charAt(1) - '0';
if(tem > 26) return set;
set.addAll(decode(prefix + (char)(tem + 'a' -1) , code.substring(2));
return set;
}
1. Method: plus 1 to n named SUM : n*(n-1)/2
SUM - sum of array -> result
2. Method: scan num-> arr[num]*=-1(num = n will do nothing)
scan second time -> find the positive num -> if have then the index is missing
-> if don't have , then n is missing
public void findString(String L , String[] V){
Hashtable<String , Integer > ht = new Hashtable<String ,Integer>();
int unitNum = V.length;
if(unitNum == 0) return;
int unitLen = V[0].length();
for(int i = 0 ; i < V.length ; i++){
for(String t : v) ht.put(t , -1);
stringSearch(L , i , ht , unitNum , unitLen);
}
}
public void stringSearch(String L , int start , Hashtable<String , Integer> ht , int unitNum , int unitLen){
int curNum = 0 , begin = 0;
while( start+unitLen <= L.length() ){
String tem = L.substring(start, start+unitLen);
if(!ht.containsKey(tem)){
curNum = 0 ;
begin = start+unitLen;
}
else{
int t = ht.get(tem);
if(t >= begin){
curNum -= (t - begin )/unitLen +1;
begin = t+unitLen;
}
ht.put(tem , start);
start+=unitLen;
curNum++;
}
if(curNum == unitNum){
System.out.println(L.substring(begin , start));
}
}
}
public class Solution{
public int findFirstNotIn(int[] arr){
byte[] ret = new byte[(1<<30)+1];
for(int a in arr){
if(a>0)
ret[a>>2] = 1;
}
for(int i = 0 ; i < ret.length ; i++){
if(ret[i] == 0) return i;
}
return 0;
}
}
public class Solution{
ArrayList<String> res;
public ArrayList<String>Patten( String str ){
res = new ArrayList<String>();
Patten_DP(str, new StringBuffer() , 0);
return res;
}
private void Patten_DP(String str,StringBuffer buf , int index){
if(index == str.length()) res.add(buf.toString());
switch(str.charAt(index)){
case '1':
buf.add('1');
break;
case '0':
buf.add('0');
break;
case '?':
String buf2 = new StringBuffer(buf);
buf.add('0');
buf2.add('1');
Patten_DP(str,buf , index+1);
Patten_DP(str,buf2 , index+1);
break;
}
}
}
import java.util.HashSet;
public class Solution{
public int[] Interval(int[] arr){
HashSet<Integer> ht = new HashSet<Integer>();
for(int i = 0 ; i < arr.length ; i++)
ht.add(arr[i]);
int res = 0 ;
for(int i = 0 ; i < arr.length ; i++)
if(ht.contains(arr[i]))
res = Math.max(res, scan(ht , arr[i]));
return res;
}
public int scan(Hashset ht, int k ){
if(!ht.contains(k)) return 0;
ht.remove(k);
return 1+scan(ht,k-1) + scan(ht,k+1);
}
}
public class Solution{
public int find_maximum( int[] arr ){
int len = arr.length,p=0, q = 1,res = 0;
if(len <= 1) return 0;
int[] minList = int[len] , maxList = int[len];
minList[0] = arr[0];
maxList[len-1] = arr[len-1];
for(int i = 1; i < len ; i++)
minList[i] = Math.min(arr[i] , minList[i-1]);
for(int i = len -2 ; i> 0 ; i--)
maxList[i] = Math.max(arr[i] , maxList[i+1]);
while(p < len && q< len){
if(maxList[q] > minLIst[p] )
q++;
else
p++;
res = math.max(q-p , res);
}
return res;
}
}
public class Solution{
public int Island(int[][] matrix){
if(matrix == null) return 0;
int row = matrix.length,column = matrix[0].length,res = 0;
if(row*column == 0) return 0;
for(int i = 0 ; i < row ;i++)
for(int j = 0 ; j < column ; j++)
if(matrix[i][j] == 1)
{
res++;
mark(matrix,i,j);
}
return res;
}
public void mark(int[][] matrix, int x , int y){
int row = matrix.length,column = matrix[0].length;
if(x<0 || x>= row || y<0 ||y>=column) return;
if(mark[x][y] == 1) mark[x][y] = 0;
else return;
mark(matrix,x+1,y+1);
mark(matrix,x+1,y-1);
mark(matrix,x-1,y+1);
mark(matrix,x-1,y-1);
}
}
I think the sort comparator should like this and
it can compare "5566"with"5566557" or "5566554"
DP from"5566" "5566557"
to"5566" "557"
public class Solution{
public void printPermutation(ArrayList<String> strs){
Comparator<String> com = new Comparator<String>(){
@override
public int compare(String a , String b){
if(a.length()*b.length() ==0) return 0;
int key = a.charAt(0);
if(key > b.charAt(0)) return 1;
if(key < b.charAt(0)) return -1;
return compare_DP( a, b);
}
public int compare_DP(String a, String b){
if(a.length() < b.length()) {
String tem = a;
a = b;
b = a;
}
int lena = a.length();
int lenb = b.length();
for(int i = 0 ; i < lenb ; i++){
if(a.charAt(i) > b.charAt(i)) return 1;
if(a.charAt(i) < b.charAt(i)) return -1;
}
if(lena == lenb) return 0;
a = a.substring(lenb);
return compare_DP(a,b);
}
}
Collections.sort(strs, com);
printPermutation_DP(strs , 0);
}
public void printPermutation_DP(ArrayList<String> strs , int index){
if(index == strs.size()){
for(String str : strs){
printf(str);
}
println("");
return ;
}
for(int j = index ; j < strs.size() ; j++){
String tem = strs.get(start);
strs.set(start,strs.get(j));
strs.set(j,tem);
printPermutation_DP(strs,index+1);
reverse(strs, j , strs.size()-1);
}
}
public void revers(ArrayList<String> strs , int p , int q){
for(int i = p , j = q ; i < j ;i++,j-- ){
String tem = strs.get(i);
strs.set(i,strs.get(j));
strs.set(j,tem);
}
}
}
public class Solution(){
public String getAction(String str){
int len = str.length();
str = str.toLowerCase();
StringBuffer buf = new StringBuffer();
int x = 0 , y = 0;
for(int i = 0 ; i < len ; i++){
int t = str.charAt(i) - 'a';
int row = t/5;
int col = t%5;
while(row > y) {
buf.append('u');
y++;
}
while(row < y) {
buf.append('d');
y--;
}
while(col > x) {
buf.append('r');
x++;
}
while(col < x) {
buf.append('l');
x--;
}
buf.append('!');
}
return buf.toString();
}
}
My idea is:
1 keep a min heap and the max value,
2 each time choose the smallest one to cal the window size and update it to its next
3 O(n)time the min windows size is come out when the small one don't have next appearance.
Am I right? I don't think it for many times
public class Solution{
public int smallWindow(ArrayList<ListNode<Integer>> arr){
Comparator<ListNode> com = new Comparator<ListNode>() {
@Override
public int compare(ListNode n1 , ListNode n2)
{
if(n1.val < n2.val) return -1;
if(n1.val > n2.val ) return 1;
return 0;
}
};
PriorityQueue<ListNode> qe = new PriorityQueue<ListNode>(arr.size(),com);
int max = 0 , window_len = Integer.MAX_VALUE;
for(ListNode a : arr){
qe.offer(a);
max = Math.max(a.val , max);
}
while( qe.peek().next !=null ){
ListNode min_node = qe.poll();
window_len = Math.min(window_len, max - min_node.val);
qe.offer(min_node.next);
max = Math.max(min_node.next.val , max);
}
return window_len;
}
}
public class Solution{
public ArrayList<Integer> sortedOrder(int len){
PriorityQueue<Word> qe = new PriorityQueue<Word>(2*len , Word.com );
ArrayList<Integer> res = new ArrayList<Integer> ();
qe.add(new Word(2,2));
qe.add(new Word(3,3));
qe.add(new Word(5,5));
qe.add(new Word(7,7));
int k = 0;
while( k < len ){
k++;
Word t = qe.poll();
res.add(t.val);
switch( t.calss ){
case 2:
qe.add(new Word(2,2 * t.val));
qe.add(new Word(3,3* t.val));
qe.add(new Word(5,5* t.val));
qe.add(new Word(7,7* t.val));
break;
case 3:
qe.add(new Word(3,3* t.val));
qe.add(new Word(5,5* t.val));
qe.add(new Word(7,7* t.val));
break;
case 5:
qe.add(new Word(5,5* t.val));
qe.add(new Word(7,7* t.val));
break;
case 7:
qe.add(new Word(7,7* t.val));
break;
}
}
return res;
}
}
public class Word{
int class;
int val;
public Word(int cla, int v)
{
class = cla;
val = v;
}
public static Comparator<Word> com = new Comparator<Word>(){
@override
public int compare(Word a , Word b){
if(a.val > b.val ) return 1;
if(a.val < b.val ) return -1;
return 0;
}
}
}
- huihancarl February 17, 2014