# 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;
}
};

# 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"

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;
}
};

# LeetCode 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?

class Solution {
public:
{
return NULL;
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;
while (slower != faster) {
slower = slower->next;
faster = faster->next;
}
return slower;
}
};

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.


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

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:
{
return false;
while (faster->next != NULL && faster->next->next != NULL) {
faster = faster->next->next;
slower = slower->next;
if (faster == slower)
return true;
}
return false;
}
};

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

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

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

Could you do it in O(n) time and O(1) space?

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

class Solution {
public:
{
return true;
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;
while (prior != NULL) { // 逆序后半段链表
tail = prior->next;
prior = tail;
}
return false;
}
return true;
}
};

class Solution {
public:
// 快慢指针
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;
}
// 判断是否相等
fast = dummy->next;
while (fast != NULL) {
if (slow->val != fast->val)return false;
slow = slow->next;
fast = fast->next;
}
return true;
}
};

# 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

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;
}
};

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;
}
};

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;
}
};

# LeetCode 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')

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()];
}
};

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()];
}
};

# LeetCode Majority Element II

229. Majority Element II

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]

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;
}
};

# 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

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

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;
}
};