liuchuo – 第255页 – 我不管，反正我最萌～

LeetCode 66. Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
            for(int i = digits.size() - 1; i >= 0; i--) {
                if(digits[i] != 9) {
                    digits[i] = digits[i] + 1;
                    return digits;
                } else {
                    digits[i] = 0;
                }
            }
            digits.insert(digits.begin(), 1);
            
            return digits;
            
    }
};

class Solution {

public:

vector<int> plusOne(vector<int>& digits) {

for(int i = digits.size() - 1; i >= 0; i--) {

if(digits[i] != 9) {

digits[i] = digits[i] + 1;

return digits;

} else {

digits[i] = 0;

}

digits.insert(digits.begin(), 1);

return digits;

}

};

LeetCode 24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head == NULL || head->next == NULL) {
            return head;
        }
        ListNode *p, *q, *h, *t;
        p = head;
        q = head->next;
        h = q;
        while(p != NULL && q != NULL) {
            p->next = q->next;
            q->next = p;
            t = p;
            if(p->next != NULL) {
                p = p->next;
            } else {
                return h;
            }
            if(p->next != NULL) {
                q = p->next;
                t->next = q;
            } else {
                return h;
            }
        }
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* swapPairs(ListNode* head) {

if(head == NULL || head->next == NULL) {

return head;

}

ListNode *p, *q, *h, *t;

p = head;

q = head->next;

h = q;

while(p != NULL && q != NULL) {

p->next = q->next;

q->next = p;

t = p;

if(p->next != NULL) {

p = p->next;

} else {

return h;

}

if(p->next != NULL) {

q = p->next;

t->next = q;

} else {

return h;

}

};

LeetCode 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 != NULL && l2 != NULL) {
            ListNode *p = l1;
            ListNode *q = l2;
            ListNode *t, *h;//t为新链表的连接指针，h为新链表的头指针
            if(p->val > q->val) {
                t = q;
                h = q;
                q = q->next;
            } else {
                t = p;
                h = p;
                p = p->next;
            }
            while(p != NULL && q != NULL) {
                if(p->val > q->val) {
                    t->next = q;
                    t = t->next;
                    q = q->next;
                } else {
                    t->next = p;
                    t = t->next;
                    p = p->next;
                }
                
            }
            while(p != NULL && q == NULL) {
                t->next = p;
                p = p->next;
                t = t->next;
            }
            while(p == NULL && q != NULL) {
                t->next = q;
                q = q->next;
                t = t->next;
            }
            while(p == NULL && q == NULL) {
                return h;
            }
        }
        if(l1 == NULL && l2 != NULL) {
            return l2;
        }
        if(l1 != NULL && l2 == NULL) {
            return l1;
        }
        if(l1 == NULL && l2 == NULL) {
            return NULL;
        }
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

if(l1 != NULL && l2 != NULL) {

ListNode *p = l1;

ListNode *q = l2;

ListNode *t, *h;//t为新链表的连接指针，h为新链表的头指针

if(p->val > q->val) {

t = q;

h = q;

q = q->next;

} else {

t = p;

h = p;

p = p->next;

}

while(p != NULL && q != NULL) {

if(p->val > q->val) {

t->next = q;

t = t->next;

q = q->next;

} else {

t->next = p;

t = t->next;

p = p->next;

}

while(p != NULL && q == NULL) {

t->next = p;

p = p->next;

t = t->next;

}

while(p == NULL && q != NULL) {

t->next = q;

q = q->next;

t = t->next;

}

while(p == NULL && q == NULL) {

return h;

}

if(l1 == NULL && l2 != NULL) {

return l2;

}

if(l1 != NULL && l2 == NULL) {

return l1;

}

if(l1 == NULL && l2 == NULL) {

return NULL;

}

};

LeetCode 326. Power of Three

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

class Solution {
public:
	bool isPowerOfThree(int n) {
		if(n <= 0)
			return false;
		return pow(3, (round)(log(n) / log(3))) == n;
	}
};

class Solution {

public:

bool isPowerOfThree(int n) {

if(n <= 0)

return false;

return pow(3, (round)(log(n) / log(3))) == n;

}

};

LeetCode 231. Power of Two

Given an integer, write a function to determine if it is a power of two.

update v2.0:
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n <= 0)
            return false;
        return pow(2, (round)(log(n) / log(2))) == n;
    }
};


//如果没有考虑n <= 0就会超时。。
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n <= 0)
            return false;
        while(n != 1) {
            if(n % 2 == 0) {
                n = n / 2;
            } else {
                return false;
            }
        }
        return true;
    }
};

update v2.0:

class Solution {

public:

bool isPowerOfTwo(int n) {

if(n <= 0)

return false;

return pow(2, (round)(log(n) / log(2))) == n;

}

};

//如果没有考虑n <= 0就会超时。。

class Solution {

public:

bool isPowerOfTwo(int n) {

if(n <= 0)

return false;

while(n != 1) {

if(n % 2 == 0) {

n = n / 2;

} else {

return false;

}

return true;

}

};

LeetCode 27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It does not matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = 0;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] != val) {
                nums[len++] = nums[i];
            }
        }
        return len;
    }
};

class Solution {

public:

int removeElement(vector<int>& nums, int val) {

int len = 0;

for(int i = 0; i < nums.size(); i++) {

if(nums[i] != val) {

nums[len++] = nums[i];

}

return len;

}

};