Code – 第249页

LeetCode 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v(2);
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                if(nums[i] + nums[j] == target) {
                    v[0] = i;
                    v[1] = j;
                }
            }
        }
        return v;
    }
};

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

vector<int> v(2);

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

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

if(nums[i] + nums[j] == target) {

v[0] = i;

v[1] = j;

}

return v;

}

};

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *h = new ListNode(0);
        ListNode *p = h;
        int temp = 0;
        while(l1 != NULL && l2 != NULL) {
            p->next = new ListNode((temp + l1->val + l2->val) % 10);
            temp = (temp + l1->val + l2->val) / 10;
            p = p->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while(l1 != NULL) {
            p->next = new ListNode((temp + l1->val) % 10);
            temp = (temp + l1->val) / 10;
            p = p->next;
            l1 = l1->next;
        }
        while(l2 != NULL) {
            p->next = new ListNode((temp + l2->val) % 10);
            temp = (temp + l2->val) / 10;
            p = p->next;
            l2 = l2->next;
        }
        if(temp) {
            p->next = new ListNode(1);
        }
        return h->next;
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

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

* };

class Solution {

public:

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

ListNode *h = new ListNode(0);

ListNode *p = h;

int temp = 0;

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

p->next = new ListNode((temp + l1->val + l2->val) % 10);

temp = (temp + l1->val + l2->val) / 10;

p = p->next;

l1 = l1->next;

l2 = l2->next;

}

while(l1 != NULL) {

p->next = new ListNode((temp + l1->val) % 10);

temp = (temp + l1->val) / 10;

p = p->next;

l1 = l1->next;

}

while(l2 != NULL) {

p->next = new ListNode((temp + l2->val) % 10);

temp = (temp + l2->val) / 10;

p = p->next;

l2 = l2->next;

}

if(temp) {

p->next = new ListNode(1);

}

return h->next;

}

};

LeetCode 142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL) {
            return NULL;
        }
        set<ListNode *> s;
        ListNode *p = head;
        int cnt = 0;
        while(p->next != NULL) {
            s.insert(p);
            if(cnt == s.size()) {
                return p;
            }
            cnt = s.size();
            p = p->next;
        }
        return NULL;
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

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

* };

class Solution {

public:

ListNode *detectCycle(ListNode *head) {

if(head == NULL) {

return NULL;

}

set<ListNode *> s;

ListNode *p = head;

int cnt = 0;

while(p->next != NULL) {

s.insert(p);

if(cnt == s.size()) {

return p;

}

cnt = s.size();

p = p->next;

}

return NULL;

}

};

LeetCode 80. Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”:
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

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

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty())
            return 0;
        int len = 1;
        vector<int> v(nums.size());
        int cnt = 1;
        v[0] = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] == nums[i - 1]) {
                cnt++;
            } else {
                cnt = 1;
            }
            if(cnt <= 2) {
                v[len++] = nums[i];
            }
        }
        for(int i = 0; i < len; i++) {
            nums[i] = v[i];
        }
        return len;
    }
};

class Solution {

public:

int removeDuplicates(vector<int>& nums) {

if(nums.empty())

return 0;

int len = 1;

vector<int> v(nums.size());

int cnt = 1;

v[0] = nums[0];

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

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

cnt++;

} else {

cnt = 1;

}

if(cnt <= 2) {

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

}

for(int i = 0; i < len; i++) {

nums[i] = v[i];

}

return len;

}

};

LeetCode 48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

//原地旋转90度。
//1.沿主对角线所有元素交换
//2.沿着垂直中轴线方向所有元素交换

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        for(int i = 0; i < matrix.size(); i++)
            for(int j = 0; j <= i; j++)
                swap(matrix[i][j], matrix[j][i]);
                
        for(int i = 0, j = matrix.size() - 1; i < j; i++, j--)
            for(int k = 0; k < matrix.size(); k++)
                swap(matrix[k][i], matrix[k][j]);
    }
};

//原地旋转90度。

//1.沿主对角线所有元素交换

//2.沿着垂直中轴线方向所有元素交换

class Solution {

public:

void rotate(vector<vector<int>>& matrix) {

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

for(int j = 0; j <= i; j++)

swap(matrix[i][j], matrix[j][i]);

for(int i = 0, j = matrix.size() - 1; i < j; i++, j--)

for(int k = 0; k < matrix.size(); k++)

swap(matrix[k][i], matrix[k][j]);

}

};

LeetCode 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int cnt0 = 0, cnt1 = 0, cnt2 = 0;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == 0) {
                cnt0++;
            } else if (nums[i] == 1) {
                cnt1++;
            } else {
                cnt2++;
            }
        }
        for(int i = 0; i < cnt0; i++) {
            nums[i] = 0;
        }
        for(int i = cnt0; i < cnt0 + cnt1; i++) {
            nums[i] = 1;
        }
        for(int i = cnt1 + cnt0; i < nums.size(); i++) {
            nums[i] = 2;
        }
    }
};

class Solution {

public:

void sortColors(vector<int>& nums) {

int cnt0 = 0, cnt1 = 0, cnt2 = 0;

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

if(nums[i] == 0) {

cnt0++;

} else if (nums[i] == 1) {

cnt1++;

} else {

cnt2++;

}

for(int i = 0; i < cnt0; i++) {

nums[i] = 0;

}

for(int i = cnt0; i < cnt0 + cnt1; i++) {

nums[i] = 1;

}

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

nums[i] = 2;

}

};

分类： Code

LeetCode 1. Two Sum

LeetCode 2. Add Two Numbers

LeetCode 142. Linked List Cycle II

LeetCode 80. Remove Duplicates from Sorted Array II

LeetCode 48. Rotate Image

LeetCode 75. Sort Colors