寫CODE，會想到騎車也在想.....: 1月 2016

2016年1月30日星期六

LEET code --Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.
For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.
Note:
You may assume the string contains only lowercase alphabets.
Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Subscribe to see which companies asked this question

這題很簡單把字串轉成ASCII 存起來在比較就好

bool isAnagram(char* s, char* t) {
    int sizeS=strlen(s);
    int sizeT=strlen(t);
    if(sizeS!=sizeT)return false;
    int ASCIIS[256];
    int ASCIIT[256];
    memset(ASCIIS,0,256*sizeof(int));
    memset(ASCIIT,0,256*sizeof(int));
    
    for(int i=0;i<sizeS;i++){
        ASCIIS[(int)s[i]]+=1;
        ASCIIT[(int)t[i]]+=1;
    }
    int fail=0;
    for(int i=0;i<256;i++){
        if( ASCIIS[i]!= ASCIIT[i]){
            fail=1;
            return false;
        }
    }
    return fail==0? true:false;
    
}

2016年1月29日星期五

LEET code --Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

用除法一下就寫完
麻煩的是要怎麼只用乘法做完
每個答案都可以看成是 {某個數字的左邊所有乘積*某個數字的右邊所有乘積}
EX:
以3來說左邊所有乘積是1*2，右邊所有乘積是4，最後可以兩者相乘得出答案

因此可以先計算出所有的左邊累積乘積，最後從後面開始回頭算出右邊乘積
兩者相乘可以得出答案

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    *returnSize=numsSize;
    int *LeftAccum=(int*)malloc(sizeof(int)*numsSize);
    LeftAccum[0]=1;
    for(int i =1;i<numsSize;i++){
        LeftAccum[i] = nums[i-1]*LeftAccum[i-1];
    }
    int right=1;
    for(int i=numsSize-1;i>=0;i--){
        LeftAccum[i]*=right;
        right*=nums[i];
    }
    return LeftAccum;
}

LEET code -- Reverse Linked List

Reverse a singly linked list.

反轉link list
用指標跑一圈就可以
要注意回傳的是pre 不是ret
因為ret停止地方會是NULL

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* pre=NULL,*ret=head,*frn;
    while(ret!=NULL){
        frn=ret->next;
        ret->next=pre;
        pre=ret;
        ret=frn;
    }
    return pre;
}

LEET code-- Single Number II

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?

Subscribe to see which companies asked this question

類似題目萬能解法:
把每個數字的bit各自加起來，在去除他要的需求

// e.g. , 5,5,5,2 - 101 101 101 010 - 313 - answer is 3%3,1%3,3%3 - 010

一開始忘記memset那邊要多乘sizeof(int)，而我要了32個int 不能只寫32.....

int singleNumber(int* nums, int numsSize) {
    
    int bit[32];
    memset(bit,0,32*sizeof(int));

    for(int i=0;i<32;i++){
        for(int j =0;j<numsSize;j++){
            if(nums[j]&(1<<i))bit[i]++;
            
        }
    }
    int ret=0;
    for(int i=0;i<32;i++){
        if(bit[i]%3!=0){
            ret+=(1<<i);
        }
    }
    return ret;
}

----------------
更好的解法
不用再多一個for
反正每個bit跑完就去看他有沒有餘3 在or起來就好(不用考慮%3==0 反正or也會是0)

int singleNumber(int* nums, int numsSize) {
    
    int bit[32];
    memset(bit,0,32*sizeof(int));
    int ret=0;
    for(int i=0;i<32;i++){
        for(int j =0;j<numsSize;j++){
            if(nums[j]&(1<<i))bit[i]++;
            
        }
        if(bit[i]%3)ret=ret | (1<<i);
    }
    
    return ret;
}

--------------
特紓解
一個for就可解完的神解釋
方式:
這題是每個都會重複三次所以可以做成state machine
The solution use two bit (a,b) to represent the initial state:

00: appear 3n times
01: appear 3n+1 times
10: appear 3n+2 times

The target state can be easily deducted that we want:
if data incoming: 00 -> 01 ->10 -> 00 if no data incoming, no change.
As a result, we can calculate the table in ziyihao's post:

current   incoming  next
a b            c    a b
0 0            0    0 0
0 1            0    0 1
1 0            0    1 0
0 0            1    0 1
0 1            1    1 0
1 0            1    0 0

其中a代表出現兩次了，b代表出現1次了，c是下一次近來的bit
所以可以利用a b來做出類似XOR的功能因為出現三次的都會被消掉

https://leetcode.com/discuss/54970/an-general-way-to-handle-all-this-sort-of-questions

public class Solution {

    public int singleNumber(int[] nums) {
        //we need to implement a tree-time counter(base 3) that if a bit appears three time ,it will be zero.
        //#curent  income  ouput
        //# ab      c/c       ab/ab
        //# 00      1/0       01/00
        //# 01      1/0       10/01
        //# 10      1/0       00/10
        // a=~abc+a~b~c;
        // b=~a~bc+~ab~c;
        int a=0;
        int b=0;
        for(int c:nums){
            int ta=(~a&b&c)|(a&~b&~c);
            b=(~a&~b&c)|(~a&b&~c);
            a=ta;
        }
        //we need find the number that is 01,10 => 1, 00 => 0.
        return a|b;

    }
}

LEET code -Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

找了半個小時的BUG 跟白癡依樣

left紀錄0的位置，right去找0右邊第一個出現非0的數字

void moveZeroes(int* nums, int numsSize) {
    int left=0,right=0,i=0;
    for( i=0;i<numsSize;i++){
        if(nums[i]!=0)continue;
        left=right=i;
        while(right<numsSize && nums[right]==0)right++;
        if(nums[left]==0 && nums[right]!=0  &&left<numsSize&&right<numsSize){
            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
        }
    }

2016年1月28日星期四

LEET code--Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

反正就是找回文
太久沒寫沒手感阿
字串處理根本忘光

暴力解又太慢....
因為沒有處理重複字元的關係

char* longestPalindrome(char* s) {
    if(s==NULL){
        return NULL;
    }
    int size = strlen(s);
    int i=0,max=0,start=0;
    
    for(i=0;i<size;i++){

        int last = size-1;
        while( last>=i){
            if(s[i] == s[last]){
                
                int j=0;
                while(s[i+j]==s[last-j] &&last-j>=i+j)j++;
                
                if ( (last-i+1)%2==0 ){
                    if(i+j - (last-j) ==1){
                        if(last-i+1 > max){
                            max=last-i+1;
                            start=i;
                        }
                    }
                }else{
                    if(i+j - (last-j) ==2){
                        if(last-i+1 > max){
                            max=last-i+1;
                            start=i;
                        }
                    }
                }

            }
            last--;
        }
    }
    char *head=(char*)malloc(sizeof(char)*max);
    strncpy(head,s+start,max);
    return head;
}

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

最佳解:
用三種指標
最左邊，中間，最右邊
每次先讓最右邊去跑重複字串，最左邊跟中間再慢慢增加，這樣可以避免重複字串浪費時間

char* longestPalindrome(char* s) {
    if(s==NULL){
        return NULL;
    }
    int size = strlen(s);
    if(size==1)return s;
    int i=0,max=0,start=0;
    int left=0,right=0;
    for(i=0;i<size;){
        if(max/2 > size-i)break;
        left=i;
        right=i;
        while(s[right] == s[right+1] && right<size-1)right++;
        i=right+1;
        while(left>0 &&right<size-1 && s[left-1]==s[right+1]){left--;right++;}
        if(right-left+1 > max){
            max=right-left+1;
            start=left;
        }
    }
    char *head=(char*)malloc(sizeof(char)*max);
    strncpy(head,s+start,max);
    head[max]='\0';
    return head;
}

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

2016年1月30日 星期六