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

2015年8月10日星期一

LEET code--Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

current 只有再future不一樣的時候才會前進
future會每次循環都向前

這樣是避免連續出現同樣數字，保留current的讓future去找誰重複
如果沒有重複就current向前

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(head==NULL)return head;
    struct ListNode *current=head;
    struct ListNode *future=head->next;
    while(current!=NULL && future!=NULL){
        if(current->val == future->val){
            current->next=future->next;
            free(future);
            future=(current !=NULL) ? current->next: NULL;
        }
        else{
            current=current->next;
            future=(current !=NULL) ? current->next: NULL;
        }
    }
    return head;
}

LEET code--Search Insert Position

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

寫到現在最簡單的一題，這居然不是正確率最高的...
第一次交出去，一次就對XD

反正如果一樣或是比目標大就直接回傳該位置
不然就是最後回傳最後的位置

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

int searchInsert(int* nums, int numsSize, int target) {
    int i;
    for( i=0 ; i &lt; numsSize ; i++ )
    {
        if(target == nums[i] || nums[i]&gt;target)return i;
    }
    return numsSize;
}

LEET code --Excel Sheet Column Number

Excel Sheet Column Number

Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28

原本還在想規律什麼  還跑去EXCEL 看之後到底怎麼排出來

後來突然想到  靠  這不就26進位而已嗎

繞一大圈  直接當作26進位來做就很快了

我算了一下 26進位在int的型態下 應該不會超過7~8位數

所以預先算好這些值，之後直接查表就好了

PS: 寫玩才想起來 明明有內建的可以call pow(26, (s.length() - i))

白癡....

而且 好像也不用需要那個涵式，直接每次*26 就好啦....

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

int titleToNumber(char* s) {
    int num[8];
    num[0]=1;
    for(int i=1;i<8-1;i++){
        num[i]=num[i-1]*26;
    }
    int size=strlen(s);
    int ans=0;
    if(size ==1)return s[0]-'A'+1;
    for(int i=0;i<size;i++){
        ans+=(s[i]-'A'+1)*num[size-i-1];
    }
    return ans;
}

------------------------------------
int titleToNumber(char* s) {
    int len = strlen(s);
    int num = 0;
    int GAP = 'A' - 1;
    for(int i = 0; i < len; ++i)
    {
        num = num * 26 + s[i] - GAP;
    }
    return num;
}

2015年8月9日星期日

LEET code--Invert Binary Tree

Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

     4
   /   \
  7     2
 / \   / \
9   6 3   1

超級簡單   指標全部互相交換就好

沒有到會有神人栽在這題

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root) {
    if(root == NULL) return;
    struct TreeNode *temp=root->left;
    root->left=root->right;
    root->right=temp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

2015年8月7日星期五

LEET code--Same Tree

Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

檢查兩個樹有沒有完全一致(結構上跟val)

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if( p==NULL && q == NULL)return true;
if( p==NULL && q!= NULL )return false;
if( p!=NULL && q==NULL)return false;
if(p->val != q->val)return false;

bool le,ri;
le=isSameTree(p->left,q->left);
ri=isSameTree(p->right, q->right);

return (le==false || ri==false)? false:true;

}

更好的寫法:

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
if(p == NULL && q == NULL) 
    return true;
if(p != NULL && q == NULL) 
    return false;
if(p == NULL && q != NULL) 
    return false;
if(p->val != q->val)
    return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

直接用&& 改回傳只有true的方式  比較簡潔

LEET code--Delete Node in a Linked List

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

一開始只給你要刪除的node的pointer
所以要把該刪除的node內部值改成下一個的
像這樣

    p = node->next;
    if (!p) return;
    node->val = p->val;
    node->next = p->next;
    free(p);

P=上面範例的4

所以把3的內容改成4

再把4刪除

這樣3就不見了

但是更好的寫法是


如果不在乎刪除空間:

*node = *(node->next);

//直接把pointer的值改成下一個
*node是取pointer內部儲存的記憶體空間
直接改成*(node->next) 就可以把3變成4 (直接改記憶體位置)
如果要刪除空間:

struct ListNode* tofree = node->next;
*node = *(node->next);
free(tofree);

LEET code--Maximum Depth of Binary Tree

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

用recursive走一圈就知道
走到最後發現是null 就回傳0

int maxDepth(struct TreeNode* root) {
if(root==NULL)return 0;
int le=0,ri=0;
le=maxDepth(root->left);
ri=maxDepth(root->right);

return (le > ri)? le+1:ri+1;

}

訂閱：文章 (Atom)

2015年8月10日 星期一