LeetCode OJ – 第48页

LeetCode 26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

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

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the new length.

//才明白这类题目的意思是 返回的是 length 的值 但是会检验你是不是删除了相同的数字使得符合条件。。然后他检验的时候输出的只是0~length-1的值。。后面的是否符合不用管。。。
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0) {
            return 0;
        }
        int len = 1;
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] != nums[i - 1]) {
                nums[len++] = nums[i];
            }
        }
        return len;
    }
};

//才明白这类题目的意思是返回的是 length 的值但是会检验你是不是删除了相同的数字使得符合条件。。然后他检验的时候输出的只是0~length-1的值。。后面的是否符合不用管。。。

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

if(nums.size() == 0) {

return 0;

}

int len = 1;

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

if(nums[i] != nums[i - 1]) {

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

}

return len;

}

};

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;

}

};