2016年2月4日 星期四

LEET code -- Maximum Product of Word Lengths

     Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".
Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".
Example 3:


Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.

原本想暴力解  太是太蠢了

看了一下別人解法
把每個字行都利用1bit來代表  而一個int 有32bit可以表示  綽綽有餘
所以就可以比較了

要注意的是double pointer
是pointer of pointer
所以直接words[i][j]就好  因為外面是*words[] 再去每個malloc

     
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
int maxProduct(char** words, int wordsSize) {
    if(wordsSize==0 || words==NULL)return 0;
    int valuse[wordsSize];
    for(int i=0;i<wordsSize;i++){
        valuse[i]=0;
        int length=strlen(words[i]);
        for(int j =0;j<length;j++){
            valuse[i] |= 1<<(words[i][j]-'a');
        }
    }
    int max=0;
    for(int i=0;i<wordsSize;i++){
        for(int j=i+1;j<wordsSize;j++){
            if( (valuse[i] & valuse[j] )==0){
                int a=strlen(words[i]);
                int b=strlen(words[j]);
                max = max>(a*b)? max:a*b;
            }
        }
    }
    return max;
}
張貼者： 於 沒有留言:
標籤：

LEET code -- Bulb Switcher

 There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:

Given n = 3. 

At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 

So you should return 1, because there is only one bulb is on.







笨蛋法


用一個陣列去記你現在的倍數


但是太慢了






 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int bulbSwitch(int n) {
    if(n==0)return 0;
    int *tag=(int *)malloc(sizeof(int)*n);
    memset(tag,1,sizeof(int)*n);
    int ans=1;
    for(int i=1;i<n;i++){
        for(int j=i;j<n;j+=(i+1)){
            tag[j]++;
        }
        if(tag[i]%2!=0)ans++;
    }
    return ans;
}













-------------------




我想說換一個判斷是不是質數來算


但是還是太慢








 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


int bulbSwitch(int n) {
    if(n==0)return 0;
    if(n==1)return 1;
    int *prims = (int*)malloc(sizeof(int)*n);
    int Size=0,ans=1;
    for(int i=2;i<=n;i++){
        int total = Isprime(prims,&Size,i);
        if(total%2==0)ans++;
    }
    return ans;
    
}

int Isprime(int *prims,int *primeSize,int target){
    int temp =target;
    int accum=0,total=1;
    for(int i=0;i<*primeSize;i++){
        if(prims[i] > target || temp==0)break;
        while(temp%prims[i]==0){
            //printf("(W %d %d)",temp,prims[i]);
            temp/=prims[i];
            accum++;
        }
        total*=(accum+1);
    }
    if(total<=1){
        prims[*primeSize]=target;
        *primeSize+=1;
        //printf("(P %d )",target);
        return 1;
    }else{
        return total-1;
    }
    if(total==1){
        prims[*primeSize]=target;
        *primeSize++;
    }
    return total; 
}











-------------------


最簡單方法


開平方


1 --------- 1



2 --------- 1, 2



3 --------- 1, 3



4 --------- 1, 2, 4



5 --------- 1, 5



6 --------- 1, 2, 3, 6



7 --------- 1, 7



8 --------- 1, 2, 4, 8



9 --------- 1, 3, 9



所以找平方數字有多少個就好







1
2
3
4
5
6
7


int bulbSwitch(int n) {
    int count=0;
    for(int i =1;i*i<=n;i++){
        count++;
    }
    return count;
}





















張貼者：



於





沒有留言:
  

















標籤：

















          

        

          

        

2016年2月3日 星期三


          

        









LEET code -- Majority Element










Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.



You may assume that the array is non-empty and the majority element always exist in the array.





起手式 先sort

但是事實上可以不用for去找

因為他說一定會超過一半的數量

所以直接中位數就好










 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


int cmp(const void * s1, const void *s2){
    int a=*(int*)s1;
    int b=*(int*)s2;
    if(a>b)return 1;
    if(a==b)return 0;
    else return -1;
}

int majorityElement(int* nums, int numsSize) {
    if(numsSize==1)return nums[0];
    qsort(nums,numsSize,sizeof(int),cmp);
    int max=0,ans=0;
    for(int i=0;i<numsSize;){
        if(nums[i]!=nums[i+1])i++;
        else {
            int localmax=0;
            for(int j=i;j<numsSize;j++){
                if(nums[i]==nums[j])localmax++;
                else{
                    printf("%d",localmax);
                    break;
                }
                i=j;
            }
            if(localmax > max){
                max = localmax;
                ans = nums[i];
            }
        }
    }
    return ans;
}

















 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


int cmp(const void * s1, const void *s2){
    int a=*(int*)s1;
    int b=*(int*)s2;
    if(a>b)return 1;
    if(a==b)return 0;
    else return -1;
}

int majorityElement(int* nums, int numsSize) {
    qsort(nums,numsSize,sizeof(int),cmp);
    return nums[numsSize/2];
}










-------------

特殊解法



Boyer–Moore majority vote algorithm



https://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html





只能用在 重複數字超過 總數/2 以上的時機點

演算法:

利用一個counter來計算次數，跟candidate代表可能答案

一開始先把counter=1,candidate=第一個數字

如果下一個遇到依樣的counter++



如果不一樣就counter--

如果counter==0 就把candidate更新，再把counter=1



因為重複出現的超過總數/2  所以這演算法可以成功












 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


int majorityElement(int* nums, int numsSize) {
    int candidate = nums[0], counter=1;
    for(int i =1;i< numsSize;i++){
        if(nums[i] == candidate){
            counter++;
        }else{
            if(counter==0){
                candidate=nums[i];
                counter=0;
            }else{
                counter--;
            }
        }
    }
    return candidate;
}



















張貼者：



於





沒有留言:
  

















標籤：

















          

        

          

        

2016年2月2日 星期二


          

        









LEET code -- Single Number III










 Given an array of numbers nums, in which exactly two 
elements appear only once and all the other elements appear exactly 
twice. Find the two elements that appear only once.


For example:


Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].


Note:




    

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
    2. 

  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
    3. 








我想說用quick sort去跑 再去找哪個沒重複的

但是他quick sort出來是錯的.....



測資:[1403617094,-490450406,-1756388866,-967931676,1878401007,1878401007,-74743538,1403617094,-1756388866,-74743538,-490450406,-1895772685]



但是我自己測試這個側資可以   網路上不給過....



而且這版本沒有線性












 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(const void* s1, const void* s2){
    return *(int*)s2 - *(int*)s1;
}
int* singleNumber(int* nums, int numsSize, int* returnSize) {
    //if(nums==NULL)return NULL;
    int *ans=(int *)malloc(2*sizeof(int));
    qsort(nums,numsSize,sizeof(int),cmp);
    for(int i=0;i<numsSize;i++){
        printf("%d ",nums[i]);
    }
    int index=0;
    for(int i=0;i<numsSize;){
        if(i==numsSize-1){
            ans[index++]=nums[i];
            ++i;
        }else  if(nums[i]==nums[i+1]){
            i+=2;
        } else{
            ans[index++]=nums[i];
            ++i;
        }
        if (index ==2)break;
    }
    *returnSize=2;
    return ans;
}










---------------

我知道位甚麼上面的quick會錯了

因為那個側資 數值很大  直接用相減會容易overflow

所要改判斷式










 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(const void* s1, const void* s2){
    int c = *(int *)s1;
      int d = *(int *)s2;
      if(c < d) {return -1;}               //傳回 -1 代表 s1 < s2
      else if (c == d) {return 0;}      //傳回   0 代表 s1 = s2
      else return 1;                          //傳回  1 代表 s1>s2
    
}
int* singleNumber(int* nums, int numsSize, int* returnSize) {
    //if(nums==NULL)return NULL;
    int *ans=(int *)malloc(2*sizeof(int));
    qsort(nums,numsSize,sizeof(int),cmp);
    for(int i=0;i<numsSize;i++){
        printf("%d ",nums[i]);
    }
    int index=0;
    for(int i=0;i<numsSize;){
        if(i==numsSize-1){
            ans[index++]=nums[i];
            ++i;
        }else  if(nums[i]==nums[i+1]){
            i+=2;
        } else{
            ans[index++]=nums[i];
            ++i;
        }
        if (index ==2)break;
    }
    *returnSize=2;
    return ans;
}










-------------------

天才解法!!!!

https://leetcode.com/discuss/52369/c-o-n-time-o-1-space-7-line-solution-with-detail-explanation

https://leetcode.com/discuss/68750/why-diff%26-diff-1-can-pick-one-bit-that-is-one



因為所有數列全部XOR起來 X^=every element

最後只會有X=A^B  (A!=B)

因為A跟B不同，所以在X會有一個bit是1

問題就是怎麼找到X裡面出現的1bit位置

笨方法就是用for去找

但是有更快的!!

方法:

X & -X

假設X=01100，那-X=10100

可以發現兩者and起來 會找到右邊第一個出現1bit的位置



或是X=01101   -X=10011



因為-X 會是X的complement+1  造成會有這樣的現象



於是我們可以找到出現1的位置

而這個1 只會屬於A或B其中一個



於是我們把這個1當作是條件再把全部內容作XOR

會得到A或B的某一個數值














 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

int* singleNumber(int* nums, int numsSize, int* returnSize) {
    int *ans=(int *)malloc(2*sizeof(int));
    int allxor=0,ANS1=0,ANS2=0;
    for(int i=0;i<numsSize;i++){
        allxor^=nums[i];
    }
    //after for loop, the allxor will have ANS1 XOR ANS2
    int flag = allxor & -allxor;
    for(int i=0;i<numsSize;i++){
        if(nums[i]&flag)ANS1^=nums[i];
    }
    ANS2=ANS1^allxor;  // becase the ans1 has the anser, 
    ans[0]=ANS1;
    ans[1]=ANS2;
    *returnSize=2;
    return ans;
}























張貼者：



於





沒有留言:
  

















標籤：

























LEET code -- Contains Duplicate










 Given an array of integers, find if the array contains any duplicates. 
Your function should return true if any value appears at least twice in 
the array, and it should return false if every element is distinct.








Subscribe to see which companies asked this question





我原本是用quick sort直接排序在找有沒有重複

但是這樣會超過時間限制



而且quick的方式pivot很容易選到跟left依樣  所以造成一定回傳true












 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


bool containsDuplicate(int* nums, int numsSize) {
    if(numsSize ==1)return false;
    if(numsSize ==0)return false;
    quicksort(nums,0,numsSize-1);
    for(int i=0;i<numsSize;i++){
        if(nums[i]==nums[i+1])return true;
    }
    return false;
}
int partition(int *nums,int left,int right,int pivotIndex){
    int pivot = nums[pivotIndex];
    int Big=left;
    for(int i=left;i<right;i++){
        if( nums[i] <= pivot ){
            swap(nums,i,Big);
            Big++;
        }
    }
    swap(nums,Big,right);
    return Big;
}

void swap(int *nums,int source, int target){
    nums[source] = nums[source]^nums[target];
    nums[target] = nums[source]^nums[target];
    nums[source] = nums[source]^nums[target];
}

void quicksort(int *nums, int left, int right){
    if(left>=right)return;
        int pivotIndex = partition(nums,left,right,(right+left)/2);
        quicksort(nums,left,pivotIndex-1);
        quicksort(nums,pivotIndex,right);

}










---------

用selected sort

並檢查每次有沒有掃到依樣的










 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


bool containsDuplicate(int* nums, int numsSize) {
    if(numsSize ==1)return false;
    if(numsSize ==0)return false;
    
    for(int i=0;i<numsSize-1;i++){
        int min=nums[i],index=i;
        for(int j=i+1;j<numsSize;j++){
            if(nums[i]==nums[j])return true;
            if(nums[j] < min){
                min=nums[j];
                index=j;
            }
        }
        swap(nums,i,index);
    }
    return false;
}
void swap(int *nums,int source, int target){
    nums[source] = nums[source]^nums[target];
    nums[target] = nums[source]^nums[target];
    nums[source] = nums[source]^nums[target];
}










------------

用內建quick sort

因為內建的pviot選的方式是亂數 會比我的好












 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int com(const void *s1, const void *s2){
    return *(int *)s1 - *(int *)s2;
}

bool containsDuplicate(int* nums, int numsSize) {
    if(numsSize ==1)return false;
    if(numsSize ==0)return false;
    qsort(nums,numsSize,sizeof(int),com);
    for(int i=0;i<numsSize;i++){
        if (nums[i] == nums[i+1])return true;
    }
    return false;
}

















張貼者：



於





沒有留言:
  

















標籤：

















          

        

          

        

2016年2月1日 星期一


          

        









LEET code -- Best Time to Buy and Sell Stock II










Say you have an array for which the ith element is the price of a given stock on day i.



Design an algorithm to find the maximum profit. You may complete as 
many transactions as you like (ie, buy one and sell one share of the 
stock multiple times). However, you may not engage in multiple 
transactions at the same time (ie, you must sell the stock before you 
buy again).



跟第一版不同

這次可以重複購買，但是只能先買在賣



這可以把買賣換成訊號來看

這個問題可以看成找相對高峰



於是改第一版的就可以










 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


int maxProfit(int* prices, int pricesSize) {
    if(prices==NULL || pricesSize <2)return 0;
    int size=pricesSize;
    int max=0,buydate=0,selldate=1,buy=prices[0],sell=prices[1];
    int income=0;
    for(int i =1;i<size;i++){
        if(prices[i] > sell){
            sell = prices[i];
            selldate=i;
        }else if(prices[i] < sell){
            income+=max;
            max=0;
            buy = prices[i];
            buydate = i;
            sell = prices[i];
            selldate=i;
        }
        if(prices[i]< buy){
            buy = prices[i];
            buydate = i;
            sell = prices[i];
            selldate=i;
            //income+=max;
            //max=0;
        }
        if ( selldate > buydate){
            max = (max>(sell-buy))? max:(sell-buy);
        }
    }
    income+=max;
    return income; 
}

















張貼者：



於





沒有留言:
  

















標籤：

























LEET code -- Best Time to Buy and Sell Stock










Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, 
buy one and sell one share of the stock), design an algorithm to find 
the maximum profit.







Subscribe to see which companies asked this question



智障方法

兩個for 去找最大值

但是會超過時間限制










 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


int maxProfit(int* prices, int pricesSize) {
    int size=pricesSize;
    int max=0;
    for(int i =0;i<size;i++){
        for(int j =i;j<size;j++){
            if( prices[j] - prices[i] > max ){
                max = prices[j] - prices[i];
            }
        }
    }
    return max;
}
















---------------

事實上把它當作訊號來看

就是找絕對低峰跟絕對高峰



用兩個指標 一個是買的價錢與天數  一個是賣的價錢與天數

不斷去找有沒有最低價前跟最高價錢     拿後要注意賣的天數要比買的高

還有當設定買的時候，賣也要設定，因為買一改  以前的賣就不行了








 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int maxProfit(int* prices, int pricesSize) {
    if(prices==NULL || pricesSize<2)return 0;
    int size=pricesSize;
    int max=0,buydate=0,selldate=1,buy=prices[0],sell=prices[1];
    for(int i =1;i<size;i++){
        if(prices[i] > sell){
            sell = prices[i];
            selldate=i;
        }
        if(prices[i] < buy){
            buy = prices[i];
            buydate = i;
            sell = prices[i];
            selldate=i;
        }
        if ( selldate > buydate){
            max = (max>(sell-buy))? max:(sell-buy);
        }
    }
    return max; 
}
    

















張貼者：



於





沒有留言:
  

















標籤：

















        

      









訂閱：
文章 (Atom)