Monthly Archives: November 2016

LeetCode Excel Sheet Column Number

LeetCode Excel Sheet Column Number
Related to question Excel Sheet Column Title
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

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

LeetCode 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

本题要求把数字转换为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

LeetCode 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.
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

LeetCode Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?


本题要判断一个链表中是否包含环,注意这里的环可能是局部的环,并不一定是链表头尾相连那种环,比如下图。

解题思路是使用快慢指针,如果链表中有环,则快慢指针一定会在某处相遇,证明请看这篇博客,我试着重述一遍:
首先请看示意图,假设链表起点为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

LeetCode Single Number
Given an 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?


已知一个数组中除了一个数字,其他数字都出现了两次,现在需要找出这个只出现一次的数字。要求线性时间复杂度,且不适用额外的空间。
这是一个位运算的题,我们知道两个相同的数按位异或之后结果为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

LeetCode Palindrome Linked List
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?


本题要判断一个单向链表是否为回文链表。之前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。

LeetCode Valid Palindrome

LeetCode Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.


本题要判断一个字符串是否是回文串,回文串的意思是从左往右读和从右往左读出来的字符串是一样的。本题在判断是否为回文时,只考虑数字和字母,并且忽略字母的大小写。
思路很简单,两个指针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。

LeetCode Edit Distance

LeetCode Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character


本题要求两个字符串的编辑距离,很经典的一道动态规划题。
两个字符串的编辑距离是指通过插入、删除和替换这三种操作,将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

LeetCode Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
Hint:

  1. How many majority elements could it possibly have?
  2. Do you have a better hint? Suggest it!

本题要求一个数组中出现次数大于 ⌊ 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

LeetCode 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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.


要求出一个数组中的多数元素,这里的多数元素是指出现次数多于数组长度的一半。
很有意思的一个题目,前几天听旁边一个组的同学面试回来就说被问到了这个题。
常规思路是把数组排序,然后取⌊ 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。果然比之前的快很多。