Monthly Archives: November 2016

LeetCode Excel Sheet Column Number

171. Excel Sheet Column Number

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...

Example 1:

Input: "A"
Output: 1

Example 2:

Input: "AB"
Output: 28

Example 3:

Input: "ZY"
Output: 701

LeetCode Excel Sheet Column Title的反过程,要把字符串转换为数字,比前一题简单,扫一遍字符串,和’A’作差,然后结果不断乘26。完整代码如下:

class Solution {
public:
    int titleToNumber(string s)
    {
        int ans = 0;
        for (int i = 0; i < s.size(); i++) {
            ans = ans * 26 + (s[i] – ‘A’) + 1;
        }
        return ans;
    }
};

本代码提交AC,用时3MS。

LeetCode Excel Sheet Column Title

168. Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
    ...

Example 1:

Input: 1
Output: "A"

Example 2:

Input: 28
Output: "AB"

Example 3:

Input: 701
Output: "ZY"

本题要求把数字转换为Excel中的列的名称,规则就是题中给出的例子。 可以看到是26进制,比如1048,除以26余数为8,商为40,则最后一个字母就是’A’+8-1=’H’;然后用40继续循环,40除以26余数为14,商为1,则倒数第二个字母为’A’+14-1=’N’,第一个字母为’A’。 需要注意能整除26的情况,比如26,余数为0,此时应该是字母’Z’,然后在n/=26的基础上,把n减1。完整代码如下:

class Solution {
public:
    string convertToTitle(int n)
    {
        string ans = "";
        while (n > 0) {
            int r = n % 26;
            char c = r – 1 + ‘A’;
            n /= 26;
            if (r == 0) {
                ans = ‘Z’ + ans;
                n–;
            }
            else {
                ans = c + ans;
            }
        }
        return ans;
    }
};

本代码提交AC,用时0MS。

LeetCode Linked List Cycle II

142. Linked List Cycle II

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up:
Can you solve it without using extra space?


本题在LeetCode Linked List Cycle的基础上更进一步,需要求出链表中环的起点位置。 接上一题,相遇位置在Z,此时如果令slower=head,然后slower和faster都以相同的速度走a步,则slower刚好能到环的起点位置Y,那么faster会在哪里呢。 上一题推出来相遇的时候有:a+b=(n-2m)c,如果faster在相遇点走a步,则相当于走了a=(n-2m)c-b,(n-2m)c相当于绕圈n-2m次,(n-2m)c-b的意思就是在z点绕圈n-2m次的基础上,退回b步,看图,退回b步正好到达了环的起点Y。 所以快慢指针再走a步之后,正好在环的起点相遇了! 于是本题的思路就是:先用上一题的方法找到相遇位置,然后slower回到head节点,slower和faster都再次单步走,再次相遇时,就是环的起点。 完整代码如下:

class Solution {
public:
    ListNode* detectCycle(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return NULL;
        ListNode *faster = head, *slower = head;
        while (faster->next != NULL && faster->next->next != NULL) {
            faster = faster->next->next;
            slower = slower->next;
            if (faster == slower)
                break;
        }
        if (faster->next == NULL || faster->next->next == NULL)
            return NULL;
        slower = head;
        while (slower != faster) {
            slower = slower->next;
            faster = faster->next;
        }
        return slower;
    }
};

本代码提交AC,用时13MS。

LeetCode Linked List Cycle

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?


本题要判断一个链表中是否包含环,注意这里的环可能是局部的环,并不一定是链表头尾相连那种环,比如下图。 解题思路是使用快慢指针,如果链表中有环,则快慢指针一定会在某处相遇,证明请看这篇博客,我试着重述一遍: 首先请看示意图,假设链表起点为X,环的起点为Y,环的总长度为c,快慢指针在环的Z点相遇,YZ=b,XY=a。则有

a+b+mc=s—(1)

a+b+nc=2s—-(2)

(1)和(2)式分别为慢快指针的等式,其中s表示慢指针走过的节点,则快指针走过两倍的s,m和n分别为慢快指针绕圈的圈数,显然n>m。 把(1)代入(2)得到a+b=(n-2m)c。假设真的存在环,则a和c是链表的固有值,是已知量,所以如果能找到m,n,b的一组解,则说明假设成立,真的存在环。 令m=0,n=a,b=ac-a,则这一组解是满足上面的方程(1)和(2)的,也满足n>m。因为环的长度>1,所以b也是大于0的。既然找到一组解,说明假设成立,即存在环。也就是说,我们可以用这种方法判断环是否存在。 完整代码如下:

class Solution {
public:
    bool hasCycle(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return false;
        ListNode *faster = head, *slower = head;
        while (faster->next != NULL && faster->next->next != NULL) {
            faster = faster->next->next;
            slower = slower->next;
            if (faster == slower)
                return true;
        }
        return false;
    }
};

本代码提交AC,用时9MS。
证明参考:
https://stackoverflow.com/a/6110767/2468587
https://math.stackexchange.com/a/913529/161019

LeetCode Single Number

136. Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

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

已知一个数组中除了一个数字,其他数字都出现了两次,现在需要找出这个只出现一次的数字。要求线性时间复杂度,且不使用额外的空间。 这是一个位运算的题,我们知道两个相同的数按位异或之后结果为0,因为异或操作是相同为0,不同为1。所以可以把数组中的所有数字都进行异或运算,那么所有出现两次的数字异或之后都等于0,最终只剩下出现次数为1次的那个数字。思路还是很巧妙的,完整代码如下:

class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            ans ^= nums[i];
        }
        return ans;
    }
};

本代码提交AC,用时16MS。

LeetCode Palindrome Linked List

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space? 234. Palindrome Linked List


本题要判断一个单向链表是否为回文链表。之前LeetCode Valid Palindrome判断的是数组,可以直接访问数组的头尾元素,但是链表不可以随机访问。 仔细观察一下,下面两条回文链表:

  1. 1->2->3->4->5->4->3->2->1
  2. 1->2->3->4->4->3->2->1

判断回文链表最原始的方法是从左往右读一遍和从右往左读一遍,如果读得的结果一样就是回文,比如第1条回文,从左往右是123454321,从右往左也是123454321,所以它是回文。 但是其实我们可以不用完整读一遍,我们只读一半就可以了,比如回文1的前半部分是1234,后半部分是4321,前半部分顺着读和后半部分倒着读都是1234,这样就足以说明是回文串了。 紧接着,对于链表,我们就有这样一种解题思路:首先找到链表的中间节点,然后把后半部分链表逆序,最后看看逆序的后半部分和顺序的前半部分是否相同。 找链表的中间节点的常规思路就是快慢指针,这个在很多题中都用到了,需要指出的是,回文链表有两种情况,一种是形如1的奇数个元素,另一种是形如2的偶数个元素。如果用快慢指针找中点,1能找到真正的中点5,2能找到前一个中点4,所以我们判断回文的时候,只需要把中点后面的链表逆序,然后只比较后半部分的链表元素。比如1的情况,逆序后半部分之后得到1->2->3->4,那么前半部分也只需要比较1->2->3->4,不需要比较5,因为这是奇数链表的中点,前后链表共享的元素;2的情况,逆序后半部分之后得到1->2->3->4,前半部分也是1->2->3->4,偶数长度的情况就会把中间的两个元素分到前后两部分。 完整代码如下:

class Solution {
public:
    bool isPalindrome(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return true;
        ListNode *faster = head, *slower = head;
        while (faster->next != NULL && faster->next->next != NULL) {
            faster = faster->next->next;
            slower = slower->next;
        } //bool odd = faster->next == NULL ? true : false; // 链表长度是否为奇数
        ListNode *head2 = slower, *prior = slower->next, *tail;
        head2->next = NULL;
        while (prior != NULL) { // 逆序后半段链表
            tail = prior->next;
            prior->next = head2->next;
            head2->next = prior;
            prior = tail;
        }
        head2 = head2->next;
        while (head2 != NULL) {
            if (head->val != head2->val)
                return false;
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};

本代码提交AC,用时25MS。

二刷。同样的思路:

class Solution {
public:
	bool isPalindrome(ListNode* head) {
		if (head == NULL || head->next == NULL)return true;
		// 快慢指针
		ListNode *fast = head, *slow = head;
		while (fast != NULL && fast->next != NULL) {
			fast = fast->next->next;
			slow = slow->next;
		}
		// 逆序后半段
		ListNode *dummy = new ListNode(0);
		ListNode *par = slow, *child = slow->next;
		while (par != NULL) {
			child = par->next;
			par->next = dummy->next;
			dummy->next = par;
			par = child;
		}
		// 判断是否相等
		slow = head;
		fast = dummy->next;
		while (fast != NULL) {
			if (slow->val != fast->val)return false;
			slow = slow->next;
			fast = fast->next;
		}
		return true;
	}
};

本代码提交AC,用时28MS。

LeetCode Valid Palindrome

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

本题要判断一个字符串是否是回文串,回文串的意思是从左往右读和从右往左读出来的字符串是一样的。本题在判断是否为回文时,只考虑数字和字母,并且忽略字母的大小写。 思路很简单,两个指针i,j,分别指向字符串的头尾,各自跳过所有非数字和字母的字符,然后把大写字母转换为小写字母,如果出现头尾字符不一样的情况,则不是回文,立即返回false。如果比完整个字符串都相等,则是回文,返回true。 完整代码如下:

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
    if (c >= ‘A’&& c <= ‘Z’)
        return c + 32;
    return c;
}
class Solution {
public:
    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() – 1;
        while (i < s.size() && j >= 0) {
            while (!isAlphaNum(s[i]) && i < s.size())
                i++;
            if (i >= s.size())
                break;
            char c1 = upper2lower(s[i]);
            while (!isAlphaNum(s[j]) && j >= 0)
                j–;
            if (j < 0)
                break;
            char c2 = upper2lower(s[j]);
            if (c1 != c2)
                return false;
            i++;
            j–;
        }
        return true;
    }
};

本代码提交AC,用时12MS。

二刷。其实i,j不用走完全程,只需要走到他们交错之后就可以了,也就是只需要判断整个字符串的前半段和后半段是否逆序相等。
至于代码,其实就是把while循环和if条件判断改一下,如下:

bool isAlphaNum(char c) { return (c >= ‘A’&& c <= ‘Z’) || (c >= ‘a’&& c <= ‘z’) || (c >= ‘0’&& c <= ‘9’); }
char upper2lower(char c)
{
    if (c >= ‘A’&& c <= ‘Z’)
        return c + 32;
    return c;
}
class Solution {
public:
    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() – 1;
        while (i <= j) {
            while (!isAlphaNum(s[i]) && i <= j)
                i++;
            if (i > j)
                break;
            char c1 = upper2lower(s[i]);
            while (!isAlphaNum(s[j]) && i <= j)
                j–;
            if (i > j)
                break;
            char c2 = upper2lower(s[j]);
            if (c1 != c2)
                return false;
            i++;
            j–;
        }
        return true;
    }
};

本代码提交AC,用时9MS。

三刷。更简洁的代码:

class Solution {
public:
	bool IsValid(char c) {
		return (c >= '0'&&c <= '9') || (c >= 'a'&&c <= 'z');
	}
	bool isPalindrome(string s) {
		int n = s.size();
		if (n == 0 || n == 1)return true;
		int i = 0, j = n - 1;
		while (i < j) {
			s[i] = tolower(s[i]);
			s[j] = tolower(s[j]);

			if (!IsValid(s[i]))++i;
			else if (!IsValid(s[j]))--j;
			else {
				if (s[i] != s[j])break;
				else {
					++i;
					--j;
				}
			}
		}
		return i >= j;
	}
};

本代码提交AC,用时16MS。

LeetCode Edit Distance

72. Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

本题要求两个字符串的编辑距离,很经典的一道动态规划题。 两个字符串的编辑距离是指通过插入、删除和替换这三种操作,将word1变换为word2(或者将word2变换为word1)。 编辑距离本科算法课就学过了,把word1和word2摆成一个表格的形式,然后从左往右,从上往下填表格,然后编辑距离就是表格右下角的值。 假设word1水平方向摆放,word2竖直方向摆放,令dp[row][col]表示把word2[:row]变换为word1[:col]需要的编辑距离,则这种变换可以通过三种方法获得:

  1. 删掉字符word2[row],然后把word2[:row-1]变换为word1[:col],删除代价为1,所以dp[row][col]=dp[row-1][col]+1
  2. 在word2[:row]变换为word1[:col-1]的基础上,在word2[:row]末尾插入字符word1[col],这样就把word2[:row]变为了word1[:col],插入代价为1,所以dp[row][col]=dp[row][col-1]+1
  3. 如果word1[col]==word2[row],则word2[:row]变为word1[:col]就相当于word2[:row-1]变为word1[:col-1],此时dp[row][col]=dp[row-1][col-1];如果word1[col]!=word2[row],则可以在word2[:row-1]变为word1[:col-1]的基础上,将word2[row]替换为word1[col],替换代价为1,所以dp[row][col]=dp[row-1][col-1]+1

综合以上三种情况(实际是四种情况),得到的递归公式为:
dp[row][col]=min(min(dp[row-1][col],dp[row][col-1])+1,dp[row-1][col-1]+(word1[col]==word2[row]?0:1))
完整的代码如下:

class Solution {
public:
    int minDistance(string word1, string word2)
    {
        if (word1.size() == 0 || word2.size() == 0)
            return max(word1.size(), word2.size());
        vector<vector<int> > dp(word2.size() + 1, vector<int>(word1.size() + 1, 0));
        for (int row = 1; row <= word2.size(); row++)
            dp[row][0] = row;
        for (int col = 1; col <= word1.size(); col++)
            dp[0][col] = col;
        for (int row = 1; row <= word2.size(); row++) {
            for (int col = 1; col <= word1.size(); col++) {
                dp[row][col] = min(dp[row – 1][col], dp[row][col – 1]) + 1;
                dp[row][col] = min(dp[row][col], dp[row – 1][col – 1] + (word1[col – 1] == word2[row – 1] ? 0 : 1));
            }
        }
        return dp[word2.size()][word1.size()];
    }
};

本代码提交AC,用时28MS。

DP题一般都要填表格,很多情况下,填第row行表格可能只需要利用第row-1行的信息,所以可以只保留两行的结果,用于缩减空间复杂度。下面这种实现只利用了额外的2*min(row,col)空间:

class Solution {
public:
    int minDistance(string word1, string word2)
    {
        if (word2.size() < word1.size()) {
            swap(word1, word2);
        }
        if (word1.size() == 0)
            return word2.size();
        vector<int> dp1(word1.size() + 1, 0), dp2(word1.size() + 1, 0);
        for (int col = 1; col <= word1.size(); col++)
            dp1[col] = col;
        for (int row = 1; row <= word2.size(); row++) {
            dp1[0] = row – 1; // caution
            dp2[0] = row; // caution
            for (int col = 1; col <= word1.size(); col++) {
                dp2[col] = min(dp1[col], dp2[col – 1]) + 1;
                dp2[col] = min(dp2[col], dp1[col – 1] + (word1[col – 1] == word2[row – 1] ? 0 : 1));
            }
            swap(dp1, dp2);
        }
        return dp1[word1.size()];
    }
};

本代码提交AC,用时19MS,确实要比之前的快一点。

LeetCode Majority Element II

229. Majority Element II2

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2] Output: [1,2]29. Majority Element II

本题要求一个数组中出现次数大于 ⌊ n/3 ⌋的所有数字,上一题LeetCode Majority Element是求数组中出现次数大于 ⌊ n/2 ⌋的数字,而且保证数组中有且仅有一个这样的众数。 在本题中,并不一定存在符合题意的众数存在,如果存在,最多有2个这样的众数,可以用反证法,如果有3个这样的众数,那么每个元素的出现次数最多是n/3,不可能超过。 思路还可以用上一题的摩尔投票法,即我们假设最多存在两个这样的众数,且随便设置这两个不同的众数为0和1,然后用摩尔投票法过一遍数组,看看最终记录的众数是哪两个。 最后再过一遍数组,统计一下这两个数的次数是否超过n/3。 完整代码如下:

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums)
    {
        int num1 = 0, num2 = 1, cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == num1) { // (1)
                cnt1++;
            }
            else if (nums[i] == num2) { // (2)
                cnt2++;
            }
            else if (cnt1 == 0) { // (3)
                num1 = nums[i];
                cnt1++;
            }
            else if (cnt2 == 0) { // (4)
                num2 = nums[i];
                cnt2++;
            }
            else {
                cnt1–;
                cnt2–;
            }
        }
        vector<int> ans;
        cnt1 = 0;
        cnt2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == num1)
                cnt1++;
            else if (nums[i] == num2)
                cnt2++;
        }
        if (cnt1 > nums.size() / 3)
            ans.push_back(num1);
        if (cnt2 > nums.size() / 3)
            ans.push_back(num2);
        return ans;
    }
};

注意代码中的(1)(2)判断必须在(3)(4)判断前面,因为如果遇到[8,8,7,7,7]这样的样例,如果(3)(4)在前面的话,num1和num2就都会被赋值为8,导致丢掉了8这个结果。还有我们一开始必须给num1和num2随便设置不同的两个数。
本代码提交AC,用时16MS。

LeetCode Majority Element

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

要求出一个数组中的多数元素,这里的多数元素是指出现次数多于数组长度的一半。 很有意思的一个题目,前几天听旁边一个组的同学面试回来就说被问到了这个题。 常规思路是把数组排序,然后取⌊ n/2 ⌋这个元素,这种思路的算法复杂度为$O(nlgn)$的代码如下:

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

本代码提交AC,用时52MS。
还有另一种巧妙的思路,假设一个数组是[1,1,2,2,1,1,3,1],多数元素是1,如果从数组中同时删除元素1和2,剩余的数组[1,2,1,1,3,1]中,多数元素还是1。也就是说从数组中删除两个不同的元素,剩余数组中的多数元素和原数组中的多数元素是一样的。这种算法好像叫做摩尔投票法
根据这种思路,我们定义两个变量ans和cnt,初始时cnt=0。当cnt==0时,此时是原始数组或者删除了两个不同的元素。以后每次,遇到和ans相同的元素,cnt++,否则cnt–。cnt–就相当于删掉两个不同的元素。
这种思路只需要遍历一遍原数组,时间复杂度是$O(n)$,完整代码如下:

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        int ans, cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (cnt == 0) {
                ans = nums[i];
                cnt++;
            }
            else {
                if (nums[i] == ans)
                    cnt++;
                else
                    cnt–;
            }
        }
        return ans;
    }
};

本代码提交AC,用时22MS。果然比之前的快很多。