Huahua’s Tech Road

花花酱 LeetCode 796. Rotate String

By zxi on March 10, 2018

题目大意：给你两个字符串A, B, 问能否通过旋转A得到B。

Problem:

https://leetcode.com/problems/rotate-string/description/

We are given two strings, A and B.

A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = 'abcde', then it will be 'bcdea' after one shift on A. Return True if and only if A can become B after some number of shifts on A.

Example 1:

Input: A = 'abcde', B = 'cdeab'

Output: true

Example 2:

Input: A = 'abcde', B = 'abced'

Output: false

Note:

A and B will have length at most 100.

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

bool rotateString(string A, string B) {

if (A.length() != B.length()) return false;

for (int i = 1; i < A.length(); ++i)

if (check(A, B, i)) return true;

return false;

}

private:

bool check(const string& A, const string& B, int offset) {

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

if (A[(i + offset) % A.length()] != B[i])

return false;

return true;

}

};

花花酱 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;

}

};

Huahua's Tech Road

花花酱 LeetCode 796. Rotate String

花花酱 LeetCode 647. Palindromic Substrings

花花酱 LeetCode 206. Reverse Linked List

花花酱 LeetCode 697. Degree of an Array

花花酱 LeetCode 349. Intersection of Two Arrays