LeetCode OJ – 第45页 – 柳婼の blog

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;

}

};

LeetCode 162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.size() == 1 || (nums[0] > nums[1]))
            return 0;
        if(nums[nums.size() - 1] > nums[nums.size() - 2]) {
            return nums.size() - 1;
        }
        for(int i = 1; i < nums.size() - 1; i++) {
            if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
    }
};

class Solution {

public:

int findPeakElement(vector<int>& nums) {

if(nums.size() == 1 || (nums[0] > nums[1]))

return 0;

if(nums[nums.size() - 1] > nums[nums.size() - 2]) {

return nums.size() - 1;

}

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

if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {

return i;

}

};

LeetCode 268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int *book = new int [nums.size() + 1];
        for(int i = 0; i <= nums.size(); i++) {
            book[i] = 0;
        }
        for(int i = 0; i < nums.size(); i++) {
            book[nums[i]] = 1;
        }
        for(int i = 0; i <= nums.size(); i++) {
            if(book[i] == 0) {
                return i;
            }
        }
    }
};

class Solution {

public:

int missingNumber(vector<int>& nums) {

int *book = new int [nums.size() + 1];

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

book[i] = 0;

}

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

book[nums[i]] = 1;

}

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

if(book[i] == 0) {

return i;

}

};