Monthly Archives: January 2017

LeetCode Odd Even Linked List

LeetCode Odd Even Linked List Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example: Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL. Note: The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on …

链表题，要求把链表中的奇数位节点连接起来，偶数位节点也连接起来，最后这两个链表连接起来。要求O(1)的空间复杂度和O(n)的时间复杂度。因为奇数链表和偶数链表都是从原链表中隔一个取一个，立马联想到快慢指针，在这个题里，我们设置两个快指针fast1和fast2，分别指向奇数节点和偶数节点，然后分别取下来，接到odd和even链表中。最后把odd的tail指向even的head就搞定了。符合O(1)空间复杂度和O(n)时间复杂度。完整代码如下： [cpp] class Solution { public: ListNode* oddEvenList(ListNode* head) { if (head == NULL)return head; ListNode *odd = new ListNode(0), *even = new ListNode(0); ListNode *otail = odd, *etail = even; ListNode *fast1 = head, *fast2 = head->next; while (fast1 || fast2) { otail->next = fast1; etail->next = fast2; if (otail)otail = otail->next; if (etail)etail = etail->next; if (fast2)fast1 = fast2->next; else fast1 = NULL; if (fast1)fast2 = fast1->next; else fast2 = NULL; } otail->next = even->next; return odd->next; } }; [/cpp] 本代码提交AC，用时16MS。二刷。其实不用快慢指针，直接根据奇偶性就可以了，更简洁的代码如下： [cpp] class Solution { public: ListNode* oddEvenList(ListNode* head) { ListNode *odd = new ListNode(0), *even = new ListNode(0); int cnt = 1; ListNode *cur = head, *otail = odd, *etail = even; while(cur) { if(cnt & 1) { otail->next = cur; otail = otail->next; } else { etail->next =cur; etail = etail->next; } cur = cur->next; ++cnt; } otail->next = even->next; etail->next = NULL; // caution!!! return odd->next; } }; [/cpp] 本代码提交AC，用时19MS。]]>

LeetCode License Key Formatting

Leave a reply

LeetCode License Key Formatting Now you are given a string S, which represents a software license key which we would like to format. The string S is composed of alphanumerical characters and dashes. The dashes split the alphanumerical characters within the string into groups. (i.e. if there are M dashes, the string is split into M+1 groups). The dashes in the given string are possibly misplaced. We want each group of characters to be of length K (except for possibly the first group, which could be shorter, but still must contain at least one character). To satisfy this requirement, we will reinsert dashes. Additionally, all the lower case letters in the string must be converted to upper case. So, you are given a non-empty string S, representing a license key to format, and an integer K. And you need to return the license key formatted according to the description above. Example 1:

Input: S = "2-4A0r7-4k", K = 4
Output: "24A0-R74K"
Explanation: The string S has been split into two parts, each part has 4 characters.

Example 2:

Input: S = "2-4A0r7-4k", K = 3
Output: "24-A0R-74K"
Explanation: The string S has been split into three parts, each part has 3 characters except the first part as it could be shorter as said above.

Note:

The length of string S will not exceed 12,000, and K is a positive integer.
String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
String S is non-empty.

题目有点长，其实很简单。题意是一个被dash插乱的字符串，现在要格式化它，规则就是以长度K分组，每组之间用dash连接，但是第一组的长度可以不是K，另外还要把小写字母转换为大写字母。解法：首先把所有dash删掉，并把小写转换为大写，得到一个新的字符串strNew，然后计算strNew.size()%K，如果等于0，表明第一组的长度也为K；否则第一组的长度就是strNew.size()%K。接下来就是把每K长度的字符串用dash拼接起来了。完整代码如下： [cpp] class Solution { public: string licenseKeyFormatting(string S, int K) { string strNew = ""; for (int i = 0; i < S.size(); ++i) { if (S[i] == ‘-‘)continue; strNew += toupper(S[i]); } string ans = ""; int offset = strNew.size() % K; if (offset != 0) { ans = strNew.substr(0, offset) + "-"; } while (offset < strNew.size()) { ans += strNew.substr(offset, K) + "-"; offset += K; } return ans.substr(0, ans.size() – 1); } }; [/cpp] 本代码提交AC，用时9MS。]]>

LeetCode Minimum Number of Arrows to Burst Balloons

Leave a reply

LeetCode Minimum Number of Arrows to Burst Balloons There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 10⁴ balloons. An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_end bursts by an arrow shot at x if x_start ≤ x ≤ x_end. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons. Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]
Output:
2
Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

平面上（可以看成是直线上）摆了很多个气球，气球有长度，占据了[s,t]的位置，气球之间可能会有重叠，现问最少用多少支箭能把所有气球射穿。我们肯定希望把箭射在重叠气球最多的区域，但是不和其他气球重叠的气球终究要被射穿。我们可以采用贪心的策略，气球的区域用pair存储了，我们对所有气球的pair排序，得到先按start排序，再按end排序的一系列气球。然后我们贪心的求重叠气球最多的区域，对于第一个气球，我们可以射[s1,t1]，如果第二个气球的区域[s2,t2]和[s1,t1]有重叠，即s2<=t1，则这一箭可以射在重叠的区域，即[max(s1,s2),min(t1,t2)]，我们再看第三个气球是否和[max(s1,s2),min(t1,t2)]有重叠，有的话又可以一箭三雕，此时又要更新重叠区域，如此循环下去。具体怎样实现好呢，我们用end来记录当前重叠区域的结束位置。因为已经按pair排序了，如果后面气球的s小于等于前面重叠区域的end，则后面气球肯定会和重叠区域重叠，此时我们还需要更新新的重叠区域的end为之前的end和后面气球的t的最小值。这样相当于重叠区域在一步步收窄。当某个气球的s不再小于等于end时，前一个贪心阶段结束，需要新开一个重叠区域。完整代码如下： [cpp] class Solution { public: int findMinArrowShots(vector<pair<int, int>>& points) { if (points.size() == 0)return 0; sort(points.begin(), points.end()); int i = 0, j = 1, end, ans = 0; while (i < points.size()) { end = points[i].second; while (j < points.size() && points[j].first <= end) { end = min(end, points[j].second); ++j; } ++ans; i = j++; } return ans; } }; [/cpp] 本代码提交AC，用时445MS。参考：http://www.cnblogs.com/grandyang/p/6050562.html]]>

LeetCode Reconstruct Original Digits from English

Leave a reply

LeetCode Reconstruct Original Digits from English Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order. Note:

Input contains only lowercase English letters.
Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.
Input length is less than 50,000.

Example 1:

Input: "owoztneoer"
Output: "012"

Example 2:

Input: "fviefuro"
Output: "45"

给定一个用英文单词表示数字的字符串，要求恢复出这个数字字符串，英文字符串是被打乱了的。这题纯粹是个找规律的题，先写出10个数字的英文单词，然后找找那个字符是每个单词特有的字符，比如可以确定的有：

找完上述5个单词之后，剩下的5个单词中每个单词特有的字符为：

所以我们首先找到字符和频率的对应关系，然后根据上面的顺序依次减掉相应单词的频率，并把数字放到结果数组中，最后从结果数组中构建结果字符串。完整代码如下： [cpp] class Solution { public: string originalDigits(string s) { vector<int> hash(26, 0); vector<int> digits(10, 0); for (int i = 0; i < s.size(); ++i) { ++hash[s[i] – ‘a’]; } while (hash[‘z’ – ‘a’]) { // 0 ++digits[0]; –hash[‘z’ – ‘a’]; –hash[‘e’ – ‘a’]; –hash[‘r’ – ‘a’]; –hash[‘o’ – ‘a’]; } while (hash[‘w’ – ‘a’]) { // 2 ++digits[2]; –hash[‘t’ – ‘a’]; –hash[‘w’ – ‘a’]; –hash[‘o’ – ‘a’]; } while (hash[‘u’ – ‘a’]) { // 4 ++digits[4]; –hash[‘f’ – ‘a’]; –hash[‘o’ – ‘a’]; –hash[‘u’ – ‘a’]; –hash[‘r’ – ‘a’]; } while (hash[‘x’ – ‘a’]) { // 6 ++digits[6]; –hash[‘s’ – ‘a’]; –hash[‘i’ – ‘a’]; –hash[‘x’ – ‘a’]; } while (hash[‘g’ – ‘a’]) { // 8 ++digits[8]; –hash[‘e’ – ‘a’]; –hash[‘i’ – ‘a’]; –hash[‘g’ – ‘a’]; –hash[‘h’ – ‘a’]; –hash[‘t’ – ‘a’]; } while (hash[‘o’ – ‘a’]) { // 1 ++digits[1]; –hash[‘o’ – ‘a’]; –hash[‘n’ – ‘a’]; –hash[‘e’ – ‘a’]; } while (hash[‘t’ – ‘a’]) { // 3 ++digits[3]; –hash[‘t’ – ‘a’]; –hash[‘h’ – ‘a’]; –hash[‘r’ – ‘a’]; –hash[‘e’ – ‘a’]; –hash[‘e’ – ‘a’]; } while (hash[‘f’ – ‘a’]) { // 5 ++digits[5]; –hash[‘f’ – ‘a’]; –hash[‘i’ – ‘a’]; –hash[‘v’ – ‘a’]; –hash[‘e’ – ‘a’]; } while (hash[‘s’ – ‘a’]) { // 7 ++digits[7]; –hash[‘s’ – ‘a’]; –hash[‘e’ – ‘a’]; –hash[‘v’ – ‘a’]; –hash[‘e’ – ‘a’]; –hash[‘n’ – ‘a’]; } while (hash[‘i’ – ‘a’]) { // 9 ++digits[9]; –hash[‘n’ – ‘a’]; –hash[‘i’ – ‘a’]; –hash[‘n’ – ‘a’]; –hash[‘e’ – ‘a’]; } string ans = ""; for (int i = 0; i < 10; i++) { ans += string(digits[i], ‘0’ + i); } return ans; } }; [/cpp] 本代码提交AC，用时26MS。]]>

LeetCode Intersection of Two Arrays II

Leave a reply

LeetCode Intersection of Two Arrays II Given two arrays, write a function to compute their intersection. Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2]. Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

求两个数组的交集，这里的交集又不同之前LeetCode Intersection of Two Arrays的交集了，这里的交集不再满足集合的互异性，两个数组中有多个同一个数，有几个共有，交集里就有几个，看例子就知道了。这其实简化了问题，我们对其中一个数组hash，建立数字和频率的hash表，然后遍历另一个数组，hash表中有，则加入交集，同时hash中的频率减1，也不需要对结果去重了。完整代码如下： [cpp] class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int, int> hash; vector<int> ans; for (int i = 0; i < nums1.size(); ++i) { ++hash[nums1[i]]; } for (int i = 0; i < nums2.size(); ++i) { if (hash[nums2[i]]>0) { ans.push_back(nums2[i]); –hash[nums2[i]]; } } return ans; } }; [/cpp] 本代码提交AC，用时6MS。回答一下Follow up的三个问题：如果数组已排序，则可以用归并排序的思路求交集，两个指针i,j分别指向两个数组，然后判断nums[i]==nums[j]，如果相等，则加入交集，i,j都往后移；否则根据大小关系选择后移i或j。不过我觉得代码中的Hash思路已经够快了，时间复杂度应该都是O(n1+n2)，只不过Hash毕竟需要计算Hash值，Hash占用的隐性空间也比较大，所以归并的思路可能会快一些。如果nums1.size<nums2.size()，则归并的思路会快一些，因为归并的话，其实复杂度是O(min(n1,n2))，当一个数组的指针走到头之后，算法就结束了，而Hash的话，就必须走完两个数组。如果nums2不能一次load进内存，则分批load内存查Hash。]]>

LeetCode Binary Watch

Leave a reply

LeetCode Binary Watch A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right. For example, the above binary watch reads “3:25”. Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent. Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

程序员有一个二进制的手表，如图所示，上面4个灯表示小时，下面6个灯表示分钟。现在告诉你手表上亮着n盏灯，问共有多少种时间的可能，要求输出所有可能的时间。我觉得这应该算中等题，稍微有一点麻烦。首先我们要把亮着的n盏灯分到小时和分钟上，比如小时亮x盏灯，分钟亮y盏灯，x+y=n。对于小时，长度为4bit，要把亮着的x盏灯填入这4bit中，共有$$C_4^x$$种填法，可以用递归的思路实现。对于分钟，长度为6bit，要把亮着的y盏灯填入这6bit中，共有$$C_6^y$$种填法，也可以用递归的思路实现。所以我们可以统一小时和分钟的递归算法，具体看代码comb函数。假设初始的灯的状态为cur，我们就是要在cur的[s,t) bit之间填入ones个1bit，对于小时，长度为4bit，所以传入cur=0, s=0, t=4；对于分钟，长度为6bit，所以传入cur=0, s=0, t=6。注意每次递归调用的时候，s都要更新，否则生成的组合结果会有重复。生成了小时和分钟的组合之后，我们再把小时和分钟字符串组合起来，这个就简单了，不再赘述。完整代码如下： [cpp] class Solution { public: // cur为传入的二进制串，comb要把ones个1填入[s,t)中 void comb(vector<int>& res, int cur, int s, int t, int ones) { if (ones == 0)res.push_back(cur); else { for (int i = s; i < t; ++i) { if ((cur&(1 << i)) == 0) { comb(res, cur | (1 << i), i + 1, t, ones – 1); // 递归把ones-1个1填入[i+1,t)中 } } } } vector<string> readBinaryWatch(int num) { vector<string> ans; for (int hour = 0; hour <= 3; ++hour) { if (hour > num)break; vector<int> hours; comb(hours, 0, 0, 4, hour); vector<int> minutes; comb(minutes, 0, 0, 6, num – hour); for (int i = 0; i < hours.size(); ++i) { if (hours[i] > 11)continue; string tmp_h = to_string(hours[i]); for (int j = 0; j < minutes.size(); ++j) { if (minutes[j] > 59)continue; string tmp_m = to_string(minutes[j]); if (tmp_m.size() < 2)tmp_m = "0" + tmp_m; ans.push_back(tmp_h + ":" + tmp_m); } } } return ans; } }; [/cpp] 本代码提交AC，用时0MS。]]>

LeetCode Longest Palindrome

Leave a reply

LeetCode Longest Palindrome Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters. This is case sensitive, for example "Aa" is not considered a palindrome here. Note: Assume the length of given string will not exceed 1,010. Example:

Input:
"abccccdd"
Output:
7
Explanation:
One longest palindrome that can be built is "dccaccd", whose length is 7.

题意：给定一个字符串，现要从字符串中抽取若干个字符，构成一个回文串，问最长能构成多长的回文串。回文串有两种形式，偶数型abba和奇数型abcba，所以我们先hash统计每个字符出现的次数，然后对于偶数的字符可以直接全拿来用，对于奇数的字符，减1之后只拿偶数个字符，但是我们最后还可以把减去的那个字符拿回来构成奇数型回文串，但也就只能拿回一个字符，所以要提前做好标记。完整代码如下： [cpp] class Solution { public: int longestPalindrome(string s) { unordered_map<char, int> hash; for (int i = 0; i < s.size(); ++i) { ++hash[s[i]]; } int ans = 0; int odd = 0; unordered_map<char, int>::iterator it = hash.begin(); while (it != hash.end()) { if ((it->second) & 1) { odd = 1; ans += it->second – 1; } else { ans += it->second; } ++it; } return ans + odd; } }; [/cpp] 本代码提交AC，用时9MS。]]>

LeetCode Valid Anagram

Leave a reply

242. Valid Anagram 242. Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case? 242. Valid Anagram

“Anagram”这个词的意思是“易位构词游戏”，就是把一个word中的letter打乱。本题要判断两个字符串是否是anagram。简单题，直接对两个字符串hash，分别统计出现字符的频率，如果两个hash的结果完全一样，则是anagram；否则不是。这题和LeetCode Word Pattern类似，也是要保证两个字符串hash到的频率完全一样，即是一个双射。完整代码如下：

class Solution {
public:
    bool isAnagram(string s, string t)
    {
        unordered_map<char, int> ums, umt;
        for (int i = 0; i < s.size(); ++i) {
            ++ums[s[i]];
        }
        for (int i = 0; i < t.size(); ++i) {
            ++umt[t[i]];
        }
        unordered_map<char, int>::iterator it = ums.begin();
        while (it != ums.end()) {
            if (umt[it->first] != it->second)
                return false;
            ++it;
        }
        it = umt.begin();
        while (it != umt.end()) {
            if (ums[it->first] != it->second)
                return false;
            ++it;
        }
        return true;
    }
};

本代码提交AC，用时16MS。
还有一种方法就是对两个字符串都排个序，然后判等，代码很简单，但是排序复杂度要比直接hash稍高。代码如下：

class Solution {
public:
    bool isAnagram(string s, string t)
    {
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

本代码提交AC，用时26MS。

LeetCode Shuffle an Array

Leave a reply

LeetCode Shuffle an Array Shuffle a set of numbers without duplicates. Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();
// Resets the array back to its original configuration [1,2,3].
solution.reset();
// Returns the random shuffling of array [1,2,3].
solution.shuffle();

本题要对一个数组随机洗牌，也就是随机打乱。第一种思路是，相当于对原数组进行无放回的随机抽样，每次从原数组中随机抽取一个数字，放到新数组中，然后在剩余数组中再随机抽样，直到抽完所有数字。具体实现是这样的，我们先令ans=original，此时我们要从n个数中随机抽样，把随机抽到的数字放到ans的末尾；然后随机抽样的整体减1，也就是n–，从n-1个数中再随机抽样，放到ans的倒数第二个位置。所以我们令pos为随机抽到的数应该放的位置，那么此时的抽样整体长度就是pos+1，每次把抽到的数和pos处的数交换一下。完整代码如下，注意不能自己设置随机种子，要不然会WA！ [cpp] class Solution { private: vector<int> original; public: Solution(vector<int> nums) { original = nums; } /** Resets the array to its original configuration and return it. */ vector<int> reset() { return original; } /** Returns a random shuffling of the array. */ vector<int> shuffle() { //srand(time(NULL)); // caution!! vector<int> ans = original; int pos = ans.size() – 1; while (pos > 0) { int r = rand() % (pos + 1); swap(ans[pos], ans[r]); –pos; } return ans; } }; [/cpp] 本代码提交AC，用时275MS。还有一种思路更简单，遍历数组，对于每一位，都随机生成一个需要交换的位置，然后交换。完整代码如下： [cpp] class Solution { private: vector<int> original; public: Solution(vector<int> nums) { original = nums; } /** Resets the array to its original configuration and return it. */ vector<int> reset() { return original; } /** Returns a random shuffling of the array. */ vector<int> shuffle() { //srand(time(NULL)); // caution!! vector<int> ans = original; for (int i = 0; i < ans.size(); ++i) { int j = rand() % ans.size(); swap(ans[i], ans[j]); } return ans; } }; [/cpp] 本代码提交AC，用时269MS。]]>

LeetCode First Unique Character in a String

Leave a reply

LeetCode First Unique Character in a String Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1. Examples:

s = "leetcode"
return 0.
s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

本题要求找出字符串中第一个没有重复出现的字符。简单题，先对所有字符hash，找出字符和频率的对应关系，然后遍历字符串，返回第一个频率为1的字符。完整代码如下： [cpp] class Solution { public: int firstUniqChar(string s) { unordered_map<char, int> hash; for (int i = 0; i < s.size(); ++i) { ++hash[s[i]]; } for (int i = 0; i < s.size(); ++i) { if (hash[s[i]] == 1)return i; } return -1; } }; [/cpp] 本代码提交AC，用时92MS。]]>

bitJoy > code

Keep calm and carry on coding

Monthly Archives: January 2017

LeetCode Odd Even Linked List

LeetCode License Key Formatting

LeetCode Minimum Number of Arrows to Burst Balloons

LeetCode Reconstruct Original Digits from English

LeetCode Intersection of Two Arrays II

LeetCode Binary Watch

LeetCode Longest Palindrome

LeetCode Valid Anagram

LeetCode Shuffle an Array

LeetCode First Unique Character in a String