Huahua’s Tech Road

花花酱 LeetCode 647. Palindromic Substrings

By zxi on March 10, 2018

Problem:

https://leetcode.com/problems/palindromic-substrings/description/

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"

Output: 3

Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"

Output: 6

Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Note:

The input string length won’t exceed 1000.

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

int countSubstrings(string s) {

int ans = 0;

for (int i = 0; i < s.length(); ++i) {

ans += count(s, i, i); // odd length

ans += count(s, i, i + 1); // even length

}

return ans;

}

private:

int count(const string& s, int l, int r) {

int ans = 0;

while (l >= 0 & r < s.length() && s[l--] == s[r++])

++ans;

return ans;

}

};

花花酱 LeetCode 206. Reverse Linked List

By zxi on March 8, 2018

题目大意：反转一个单向链表

Problem:

https://leetcode.com/problems/reverse-linked-list/description/

Reverse a singly linked list.

Solution 1:

Tracking prev / curr / next node

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

ListNode* reverseList(ListNode* head) {

ListNode* prev = nullptr;

ListNode* curr = head;

ListNode* next;

while (curr) {

next = curr->next;

curr->next = prev;

prev = curr;

curr = next;

}

return prev;

}

};

Java

// Author: Huahua

// Running time: 0 ms

class Solution {

public ListNode reverseList(ListNode head) {

ListNode prev = null;

ListNode curr = head;

ListNode next;

while (curr != null) {

next = curr.next;

curr.next = prev;

prev = curr;

curr = next;

}

return prev;

}

Python 3

"""

Author: Huahua

Running time: 48 ms

"""

class Solution:

def reverseList(self, head):

prev, curr, nxt = None, head, None;

while curr:

nxt, curr.next = curr.next, prev

prev, curr = curr, nxt

return prev

花花酱 LeetCode 697. Degree of an Array

By zxi on March 8, 2018

题目大意：求”度”相同的最短子数组的长度。

Problem:

https://leetcode.com/problems/degree-of-an-array/description/

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: [1, 2, 2, 3, 1]

Output: 2

Explanation:

The input array has a degree of 2 because both elements 1 and 2 appear twice.

Of the subarrays that have the same degree:

[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]

The shortest length is 2. So return 2.

Example 2:

1 2	Input: [1,2,2,3,1,4,2] Output: 6

Solution 1: Hashtable

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 33 ms (beats 90.96%)

class Solution {

public:

int findShortestSubArray(vector<int>& nums) {

unordered_map<int, vector<int>> indices;

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

indices[nums[i]].push_back(i);

size_t degree = 0;

for (const auto& p : indices)

degree = max(degree, p.second.size());

int ans = nums.size();

for (const auto& p : indices) {

if (p.second.size() != degree) continue;

ans = min(ans, p.second.back() - p.second.front() + 1);

}

return ans;

}

};

花花酱 LeetCode 349. Intersection of Two Arrays

By zxi on March 8, 2018

题目大意：求2个数组的交集。

Problem:

https://leetcode.com/problems/intersection-of-two-arrays/description/

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

Each element in the result must be unique.
The result can be in any order.

C++ using std::set_intersection

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

vector<int> intersection(max(nums1.size(), nums2.size()));

std::sort(nums1.begin(), nums1.end());

std::sort(nums2.begin(), nums2.end());

// Inputs must be in ascending order

auto it = std::set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), intersection.begin());

intersection.resize(it - intersection.begin());

std::set<int> s(intersection.begin(), intersection.end());

return vector<int>(s.begin(), s.end());

}

};

C++ hashtable

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

unordered_set<int> m(nums1.begin(), nums1.end());

vector<int> ans;

for (int num : nums2) {

if (!m.count(num)) continue;

ans.push_back(num);

m.erase(num);

}

return ans;

}

};

花花酱 LeetCode 506. Relative Ranks

By zxi on March 8, 2018

题目大意：给你一些人的分数，让你输出他们的排名，前三名输出金银铜牌。

Problem:

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:

Input: [5, 4, 3, 2, 1]

Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal".

For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

N is a positive integer and won’t exceed 10,000.
All the scores of athletes are guaranteed to be unique.

Solution 1: Sorting ( + Binary Search)

C++

class Solution {

public:

vector<string> findRelativeRanks(vector<int>& nums) {

vector<string> ans;

vector<int> s(nums);

std::sort(s.begin(), s.end());

vector<string> medals{"Gold", "Silver", "Bronze"};

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

int rank = s.end() - std::lower_bound(s.begin(), s.end(), nums[i]);

if (rank <= 3)

ans.push_back(medals[rank - 1] + " Medal");

else

ans.push_back(std::to_string(rank));

}

return ans;

}

};

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<string> findRelativeRanks(vector<int>& nums) {

vector<pair<int, int>> s;

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

s.emplace_back(nums[i], i);

vector<string> medals{"Gold", "Silver", "Bronze"};

std::sort(s.rbegin(), s.rend());

vector<string> ans(nums.size());

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

ans[s[i].second] = i < 3 ? (medals[i] + " Medal") : std::to_string(i + 1);

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 647. Palindromic Substrings

花花酱 LeetCode 206. Reverse Linked List

花花酱 LeetCode 697. Degree of an Array

花花酱 LeetCode 349. Intersection of Two Arrays

花花酱 LeetCode 506. Relative Ranks