寫CODE，會想到騎車也在想.....

2016年2月1日星期一

LEET code -- Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:

You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Subscribe to see which companies asked this question

只要分別去走(LL->left, LL->right) (LL->right, RR->left) (RR->left, RR->right)
就可以了且next預設是NULL

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  struct TreeLinkNode *left, *right, *next;
 * };
 *
 */
void connect(struct TreeLinkNode *root) {
    if(root==NULL)return;
    //if(root->right!=NULL)root->right->next=NULL;
    root->next=NULL;
    parse(root->left,root->right);
}

void parse(struct TreeLinkNode *LL,struct TreeLinkNode *RR ){
    if(LL==NULL || LL->next!=NULL)return;
    //if(RR->right!=NULL)RR->right->next=NULL;
    LL->next=RR;
    
    parse(LL->left,LL->right);
    parse(LL->right,RR->left);
    parse(RR->left,RR->right);
}

-------------------
更好的解法:
事實上就是DFS

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  struct TreeLinkNode *left, *right, *next;
 * };
 *
 */
void connect(struct TreeLinkNode *root) {
    if(root==NULL)return;
    //if(root->right!=NULL)root->right->next=NULL;
    
    parse(root);
}

void parse(struct TreeLinkNode *rt){
    if(rt->left==NULL)return;
    //if(RR->right!=NULL)RR->right->next=NULL;
    rt->left->next=rt->right;
    rt->right->next = rt->next==NULL? NULL:rt->next->left;
    parse(rt->left);
    parse(rt->right);
}

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

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

訂閱：文章 (Atom)

2016年2月1日 星期一

2016年1月30日 星期六

2016年1月29日 星期五

2016年1月28日 星期四

2016年2月1日星期一

2016年1月30日星期六

2016年1月29日星期五

2016年1月28日星期四