leetcode-C++笔记

数组部分暂时这样，之后再看，接下来是单链表部分
单链表部分结束，以下是字符串部分。
字符串到此为止，接下来开始树/

1.小技巧

1.判断两个浮点数a，b是否相等时abs(a-b)是否小于
一个阈值，例如1e-9.

2.用char的值作为数组下标，需要考虑可能出现负数，
需要强转unsigned char 

3.善用C++中的STL，详见《算法笔记》

1.给定一个有序数组，去除重复值保证独一无二，不使用额外空间，返回最终数组的长度值。

Given a sorted array, remove the duplicates in place such that each element appear only once
and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

给定一个有序数组，去除重复值保证独一无二，
不使用额外空间，返回最终数组的长度值。

解法：

使用两个下标值，一个index，一个i
i是用来遍历array的，
如果array为空，直接return 0；
其他
index和i都从0开始
因为给定的是有序array
所以如果index下标处的值和i下标处的值不相等
那么++index，并将i下标处的值拷贝到新的index下标处
	如果相等，那么新数组不需要存储i下标处的值
	所以只有i++，index不变。
	index代表了新数组的最后一个下标，
	所以新数组的最终长度=index+1；
所以最终return index+1。

算法是这样，可以只记一个超短的答案

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
return distance(nums.begin(), unique(nums.begin(), nums.end()));
}
};

2.根据上一题改编，如果要求重复出现次数最多两次呢？

Follow up for ”Remove Duplicates”: What if duplicates are allowed at most twice?
For example, Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3]

根据上一题改编，如果要求重复出现次数最多两次呢？

分析：加一个变量记录一下元素出现的次数，
因为是已经排序的数组，所以一个变量即可
如果是没有排序的数组，需要引用一个hashmap来记录出现的次数。

解法：

因为每个数都有和前面的数相同的可能，最特殊的就是每个数
都与数组中其他的数都不同，这时候就需要遍历解决。
所以，应该有一个递增为1的for循环。
另外，不管数组里面的数相等与否，当数组的总长度<=2的，
处理的结果还是原数组，所以可以直接返回原数组的大小。

本题的前提还是基于sorted 数组，所以还是在纸上模拟操作好理解。
然后就是核心思想：
最多保存两次，那么当前值要不要保存，与前一个值有关吗？
答案是不确定的：
	1.当前一个值和对当前值不等时，当然保存！
	2.当前一个值和当前值相等时，不确定！因为最多可以保存两个相，不确定现在是几个了

这里的算法充分利用了sorted这一条件：
将当前值与已保存数组的前2个值进行比较：
	1.前2个值与当前值不等时，
		那么现在不论保存的前1个值是否与当前值相等，
		根据最多可以重复保存两次的原则，
		当前值都应该进行保存；
	2.前2个值与当前值相等时：
		根据sorted原则，也就是说明前2个值和前1个值都与当前值相等
		同样根据最多重复保存两次相等的原则，
		当前值绝对不能进行保存，否则就=3，>2了。
	同样的，3次呢？还是根据这样扩展，代码中相应的地方改成3就可以了。

推荐使用略长一点，但是扩展性好一些的代码，例如将occur<3，
就编程了允许重复最多3次。

// LeetCode, Remove Duplicates from Sorted Array II
// ????? O(n)?????? O(1)
// @author hex108 (https://github.com/hex108)
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() <= 2) return nums.size();
int index = 2;
for (int i = 2; i < nums.size(); i++){
if (nums[i] != nums[index - 2])
nums[index++] = nums[i];
}
return index;
}
};

3.给定了一个sorted数组，给定一个值进行查找但是注意，这里还对sorted数组进行了旋转，且假设了这个数组中值互不相等

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

题目给定了一个sorted数组，给定一个值进行查找
但是注意，这里还对sorted数组进行了旋转，且假设了
这个数组中值互不相等
如果值存在就返回其下标，如果不存在，就返回-1

分析：
二分查找，难度主要在于左右边界的确定。

解法：
具体关系还是在纸上画一画就很显然了。
初始化first=0，last=nums.size();还有mid

1.如果要找的target正好等于对应的mid下标对应处的值，
也就是找到了，直接返回mid作为下标即可；
2.否则，如果first处的值<=mid处的值，说明什么呢？
别忘了，因为是sorted数组，所以说明从first到mid，
数组里的数是递增的。
就是根据这一点就更好定位了。
此时，如果target大于等于first处的值，并且小于mid处的值，
说明下一轮循环查找应该在first-mid这个范围找，
所以last=mid;
否则，也就是不在这一段，应该first=mid+1;

3.同样的，剩下的可能是first-mid这个区间并不是递增的。
	这个说明什么了呢？
	对立面，因为是将数组旋转了，所以，
	mid-(last-1)这个区间是递增的。用target比较这个区间
	最大最小值，也就是比较边界值mid处值和last-1处值。
	如果target大于mid处的值，并且小于等于last-1处的值
	那么说明下一轮查找应该在这个区间展开，
	也就是first=mid+1;
	否则，也就是应该在另一半区间进行查找：
	last=mid.



// LeetCode, Search in Rotated Sorted Array
// ????? O(log n)?????? O(1)
class Solution {
public:
int search(const vector<int>& nums, int target) {
int first = 0, last = nums.size();
while (first != last) {
const int mid = first + (last - first) / 2;
if (nums[mid] == target)
return mid;
if (nums[first] <= nums[mid]) {
if (nums[first] <= target && target < nums[mid])
last = mid;
else
first = mid + 1;
} else {
if (nums[mid] < target && target <= nums[last-1])
first = mid + 1;
else
last = mid;
}
}
return -1;
}
};

4.如果sorted旋转数组中的数字是重复元素呢？那应该怎么解决

Search in Rotated Sorted Array II
??
Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

如果sorted旋转数组中的数字是重复元素呢？那应该怎么解决。

分析：

允许重复元素，则上一题中如果mid处的值>=first处的值，
那么，first-mid为递增序列的假设就不能成立，
如1,3,1,1,1
如果mid处的值>=first处的值不能确定递增，那就把它拆成两个条件：
	1.如果mid处的值>first处的值，则first-mid区间一定递增；
	2.如果mid处的值=first处的值，first++，往下看一步。

总结一下与上一题的解法变化：
就是单独将first处的值和mid处的值相等时列出：
并设置first++，即可。

	// LeetCode, Search in Rotated Sorted Array II
	// ????? O(n)?????? O(1)
	class Solution {
	public:
	bool search(const vector<int>& nums, int target) {
	int first = 0, last = nums.size();
	while (first != last) {
	const int mid = first + (last - first) / 2;
	if (nums[mid] == target)
	return true;
	if (nums[first] < nums[mid]) {
	if (nums[first] <= target && target < nums[mid])
	last = mid;
	else
	first = mid + 1;
	} else if (nums[first] > nums[mid]) {
	if (nums[mid] < target && target <= nums[last-1])
	first = mid + 1;
	else
	last = mid;
	} else
	//skip duplicate one
	first++;
	}
	return false;
	}
	};

5.Median of Two Sorted Arrays

Median of Two Sorted Arrays
??
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted
arrays. The overall run time complexity should be O(log(m + n))

分析：

这是一个非常经典的题。
这道题更为通用的形式是：给定两个已经排好序的数组，
找到两者所有元素中第k大的元素。
Om+n的解法比较直观，直接merge两个数组，然后求第k大的元素。
不过我们仅仅需要第k大的元素，是不需要“排序”这么昂贵的操作的。
可以用一个计数器，记录但施工前已经找到第m大的元素了。
同时我们使用两个指针pa和pb，分别指向a数组和b数组的第一个元素。
使用类似于merge sort的原理，
如果数组a当前元素小，那么pa++，同时m++；
如果数组b当前元素小，那么pb++，同时m++；
最终当m==k的时候，就得到了我们的答案，Ok时间，O1空间。
但是，当k很接近m+n的时候，这个方法还是Om+n的。

更好的方案？
我们可以考虑从k入手。
如果我们每次都能够删除一个一定在第k大元素之前的元素，
那么我们需要进行k次。
但是如果每次我们都删除一半呢？
由于a和b都是有序的，我们可以使用二分查找，
也是充分利用了“有序”。

假设a和b的元素个数都大于k/2，我们将a的第k/2个元素，
即a[k/2-1]和b的第k/2个元素，即b[k/2-1]进行比较，
有以下三种情况，为了简化，这里先假设k为偶数，所得到的结论对于
k为奇数也是同样成立。
	1.a[k/2-1] == b[k/2-1]
	2.a[k/2-1] > b[k/2-1]
	3.a[k/2-1] < b[k/2-1]

如果a[k/2-1] < b[k/2-1],意味着a[0]到a[k/2-1]的肯定在topk元素的范围内
也就是说，a[k/2-1]不可能大于第k大元素。
因此，我们可以放心的删除a数组的这k/2个元素。
同理，b也是。
而当a[k/2-1] == b[k/2-1]时，说明找到了第k大的元素，
直接返回其中任意一个即可。

可以写一个递归函数，那么函数什么时候应该终止呢？
	1.当a或b为空时，直接返回b[k-1]或a[k-1];
	2.当k=1时，返回min(a[0],b[0]);
	3.当a[k/2-1] == b[k/2-1]时，返回其中任意一个。

	// LeetCode, Median of Two Sorted Arrays
	// ????? O(log(m+n))?????? O(log(m+n))
	class Solution {
	public:
	double findMedianSortedArrays(const vector<int>& A, const vector<int>& B) {
	const int m = A.size();
	const int n = B.size();
	int total = m + n;
	if (total & 0x1)
	return find_kth(A.begin(), m, B.begin(), n, total / 2 + 1);
	else
	return (find_kth(A.begin(), m, B.begin(), n, total / 2)
	+ find_kth(A.begin(), m, B.begin(), n, total / 2 + 1)) / 2.0;
	}
	private:
	static int find_kth(std::vector<int>::const_iterator A, int m,
	std::vector<int>::const_iterator B, int n, int k) {
	//always assume that m is equal or smaller than n
	if (m > n) return find_kth(B, n, A, m, k);
	if (m == 0) return *(B + k - 1);
	if (k == 1) return min(*A, *B);
	//divide k into two parts
	int ia = min(k / 2, m), ib = k - ia;
	if (*(A + ia - 1) < *(B + ib - 1))
	return find_kth(A + ia, m - ia, B, n, k - ia);
	else if (*(A + ia - 1) > *(B + ib - 1))
	return find_kth(A, m, B + ib, n - ib, k - ib);
	else
	return A[ia - 1];
	}
	};

6.给定一个无序整数数组，计算出该数组最长连续数序列的长度

Longest Consecutive Sequence
??
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1,
2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

题目：给定一个无序整数数组，
计算出该数组最长连续数序列的长度。

分析：

如果允许Onlogn的复杂度，那么可以先排序，但是本题要求On
由于序列里面的元素是无序的，有要求On，首先想到用哈希表。
用一个哈希表unordered_map<int,bool> used 记录每个元素是否
使用，对每个元素，以该元素为中心，往左右扩张，直到不连续位置，记录下
最长的长度。

解法：

先将给定的数的bool都统一设定为false；
如果一个值的bool为true，
1.说明我们之前已经遍历过他，并且将其修改为true；
我们遍历初始找的一定是false值开始的。
unordered_map<int,bool>默认bool值同样是false
找到一个length自然为1；
然后就是让其向左向右分别遍历，如果隔壁的bool也是false，
那么这个值可能没遍历访问过，也可能根本就没有往里面存储过。
但是我们在for循环中有map.find()!=map.end()
如果我们根本就没有往里面存储过，那么这条语句就会起到过滤作用。
1.过滤边界问题；
2.过滤掉根本没有存储过的false情况。
之后括号里面符合的只有我们往里面存储过，但是没有访问遍历过的情况。
这样之后再设置为true就没有问题了。情形比较简单，不用在纸上画图也可以理解。

// Leet Code, Longest Consecutive Sequence
// ????? O(n)?????? O(n)
class Solution {
public:
int longestConsecutive(const vector<int> &nums) {
unordered_map<int, bool> used;
for (auto i : nums) used[i] = false;
int longest = 0;
for (auto i : nums) {
if (used[i]) continue;
int length = 1;
used[i] = true;
for (int j = i + 1; used.find(j) != used.end(); ++j) {
used[j] = true;
++length;
}
for (int j = i - 1; used.find(j) != used.end(); --j) {
used[j] = true;
++length;
}
longest = max(longest, length);
}
return longest;
}
};

7.给定一个整数数组，给定一个目标数，找2个数组里面的数和=目标数。并且返回这两个数的下标值，要求两个数下标值不同。并且假设输入数据只有唯一解。

Two Sum
??
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where
index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not
zero-based.
2.1 ?? 11
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目：

给定一个整数数组，给定一个目标数，
找2个数组里面的数和=目标数。
并且返回这两个数的下标值，要求两个数下标值不同。
并且假设输入数据只有唯一解。

分析：

1.暴力On^2；
2.hash，用一个hash表，存储每个数对应的下标，On
3.先排序，然后左右夹逼，排序NlogN，左右夹逼ON,
但是注意这题需要返回下标，而不是数字本身，因此这个方法不行。

有一个注意点，就是题目还要求下标值不是从0开始。

8.给定一个整数数组，求所有的3元祖，3个数的和为0

3Sum
??
Given an array S of n integers, are there elements a,b,c in S such that a + b + c = 0? Find all unique
triplets in the array which gives the sum of zero.
Note:
? Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
? The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4}.
A solution set is:
(-1, 0, 1)
(-1, -1, 2)

给定一个整数数组，
求所有的3元祖，3个数的和为0

分析：

先排序，然后左右夹逼，复杂度On*n 
这个方法，可以推广到k——sum，先排序，然后做k-2次循环，
在最内层循环左右夹逼
注意跳过重复的数。

解法：

解法中为什么有if (i > nums.begin() && *i == *(i-1)) continue;呢？
因为如果当前元素值和前一个值相等，那么结果应该也与前一个相同；
不必重复一次；
1.如果前一个可以组成一个3元祖，那么当前值也是组成同样的3元祖，
重复，对于本题是没有必要的工作量；
2.如果前一个没有组成一个3元祖，那么当前值也不可能组成。
同样是没有必要的工作。

同理，后面的内层循环里面的两个while操作也是为了过滤这些重复工作。

另外要注意nums.end()指向的并不是最后一个元素，而是最后一个元素的后面。
所以需要-1才是指向最后一个元素。相应的，-2是倒数第二个元素。

还有最后需要检查自己的算法有没有考虑了所有情况，
有没有漏掉可能的3元祖。

总结：i循环遍历
		内部，定住i，然后根据与target的大小关系，
		分情况左右调节j和k。
		如果正好找到满足的3元组，便将其push进定义好的vector中。

还有一个注意点，因为给定的数组中每个数都不一样。
所以当相等时，需要j和k都移动。
而且内层中的每个while都需要加入j<k这个条件，切不可忘记。

9.和上一题类似，但是需要找出3元组之和与target比较最为接近的

3Sum Closest
??
Given an array S of n integers, find three integers in S such that the sum is closest to a given number,
target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

题目：和上一题类似，
但是需要找出3元组之和与target比较最为接近的。

分析：

先排序，然后左右夹逼，复杂度On*n
返回和。
prev函数是返回向前移动参数n步的位置。

代码中这些函数起的作用实际上和前一题代码中的相同。
这道题的代码比上一题简单很多。

// LeetCode, 3Sum Closest
// ???????????????? O(n^2)?????? O(1)
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int result = 0;
int min_gap = INT_MAX;
sort(nums.begin(), nums.end());
for (auto a = nums.begin(); a != prev(nums.end(), 2); ++a) {
auto b = next(a);
auto c = prev(nums.end());
while (b < c) {
const int sum = *a + *b + *c;
const int gap = abs(sum - target);
if (gap < min_gap) {
result = sum;
min_gap = gap;
}
if (sum < target) ++b;
else --c;
}
}
return result;
}
};

10.还有四个数之和的题，不看了，以后又机会又感兴趣再看。

11.给定一个数组和一个值，删除该值的所有实例并返回新的长度。元素的顺序可以改变。你留下的新长度并不重要。

Remove Element
??
Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

题目：

 给定一个数组和一个值，删除该值的所有实例并返回新的长度。
元素的顺序可以改变。你留下的新长度并不重要。

分析：

很简单。

// LeetCode, Remove Element
// ????? O(n)?????? O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int target) {
int index = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != target) {
nums[index++] = nums[i];
}
}
return index;
}
};


第二种解法：
// LeetCode, Remove Element
// ?? remove()?????? O(n)?????? O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int target) {
return distance(nums.begin(), remove(nums.begin(), nums.end(), target));
}
};

12.Next Permutation

Next Permutation
??
Implement next permutation, which rearranges numbers into the lexicographically next greater permu-
tation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascend-
ing order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the
right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

// LeetCode, Next Permutation
// ????? O(n)?????? O(1)
class Solution {
public:
void nextPermutation(vector<int> &nums) {
next_permutation(nums.begin(), nums.end());
}
template<typename BidiIt>
bool next_permutation(BidiIt first, BidiIt last) {
// Get a reversed range to simplify reversed traversal.
const auto rfirst = reverse_iterator<BidiIt>(last);
const auto rlast = reverse_iterator<BidiIt>(first);
// Begin from the second last element to the first element.
auto pivot = next(rfirst);
// Find `pivot`, which is the first element that is no less than its
// successor. `Prev` is used since `pivort` is a `reversed_iterator`.
while (pivot != rlast && *pivot >= *prev(pivot))
++pivot;
// No such elemenet found, current sequence is already the largest
// permutation, then rearrange to the first permutation and return false.
if (pivot == rlast) {
reverse(rfirst, rlast);
return false;
}
// Scan from right to left, find the first element that is greater than
// `pivot`.
auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot));
swap(*change, *pivot);
reverse(rfirst, pivot);
return true;
}
};
??题?
? Permutation Sequence, ? §2.1.1

13.

The set [1,2,3,?,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.

	使用next_permutation()
	// LeetCode, Permutation Sequence
	// ?? next_permutation()?TLE
	class Solution {
	public:
	string getPermutation(int n, int k) {
	string s(n, '0');
	for (int i = 0; i < n; ++i)
	s[i] += i+1;
	for (int i = 0; i < k-1; ++i)
	next_permutation(s.begin(), s.end());
	return s;
	}
	template<typename BidiIt>
	bool next_permutation(BidiIt first, BidiIt last) {
	// ?????题 Next Permutation
	}
	};

数组部分暂时这样，之后再看，接下来是单链表部分

1.给定两个单链表分别代表两个非负数，并且数字是逆序的，每个链表节点包含一个数尝试将两个数相加并将结果返回为单链表。

Add Two Numbers
??
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse
order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

题目：
给定两个单链表分别代表两个非负数，
并且数字是逆序的，每个链表节点包含一个数
尝试将两个数相加并将结果返回为单链表。

// LeetCode, Add Two Numbers
// ? Add Binary ???
// ????? O(m+n)?????? O(1)
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode dummy(-1); // ???
int carry = 0;
ListNode *prev = &dummy;
for (ListNode *pa = l1, *pb = l2;
pa != nullptr || pb != nullptr;
pa = pa == nullptr ? nullptr : pa->next,
pb = pb == nullptr ? nullptr : pb->next,
prev = prev->next) {
const int ai = pa == nullptr ? 0 : pa->val;
const int bi = pb == nullptr ? 0 : pb->val;
const int value = (ai + bi + carry) % 10;
carry = (ai + bi + carry) / 10;
prev->next = new ListNode(value); // ???
}
if (carry > 0)
prev->next = new ListNode(carry);
return dummy.next;
}
};

2.反转单链表II

Reverse Linked List II
??
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example: Given 1->2->3->4->5->nullptr, m = 2 and n = 4,
return 1->4->3->2->5->nullptr.
Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

题目：

反转单链表II
??
将位置m到n的单链表部分反转。在原地一次通过。
例如：给定1-> 2-> 3-> 4-> 5-> nullptr，m = 2且n = 4，
return 1-> 4-> 3-> 2-> 5-> nullptr。
注意：给定m，n满足以下条件：1≤m≤n≤列表长度。

解法：1.见代码注释部分；
2.纸上画图，一看便知。

ListNode* reverseBetween(ListNode* head,int m,int n){
	
	if((m<0 || n<0)||(m>=n)){
		return head;
	}

	
	ListNode dummy(-1);
	dummy.next = head;
	
	ListNode* prev = &dummy;
	
	for(int i=0;i<m-1;i++){
		prev = prev->next;
		
	}//此时prev指向m-1位置的结点 
	
	ListNode* const head2 = prev;//此时head2指向m-1 
	
	prev = head2->next;//此时prev指向m
	
	ListNode* cur = prev->next;//此时cur指向m+1
	
	for(int i=m;i<n;++i){//i的范围是m到n-1，对应的prev的范围也是m到n-1 
		prev->next =  cur->next;
		cur->next = head2->next;
		head2->next = cur;
		cur = prev->next; 
		
		
	} 
	
	return dummy.next;
	
	
	
	
}

3.将单链表分区：

Partition List
??
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater
than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.

题目：
将单链表分区：
给定一个单链表和一个数x，
依据x进行分区，
给定一个链表和一个值x，对其进行分区，使所有小于x的节点都排在大于或等于x的节点之前。

您应该保持两个分区中每个节点的原始相对顺序。

例如,给出1 - > 4 - > 3 - > 2 - > 5 - > 2和x = 3,返回1 - > 2 - > 2 - > 4 - > 3 - > 5。


	// LeetCode, Partition List
	// ????? O(n)?????? O(1)
	class Solution {
	public:
	ListNode* partition(ListNode* head, int x) {
	ListNode left_dummy(-1); // ???
	ListNode right_dummy(-1); // ???
	auto left_cur = &left_dummy;
	auto right_cur = &right_dummy;
	for (ListNode *cur = head; cur; cur = cur->next) {
	if (cur->val < x) {
	left_cur->next = cur;
	left_cur = cur;
	} else {
	right_cur->next = cur;
	right_cur = cur;
	}
	}
	left_cur->next = right_dummy.next;
	right_cur->next = nullptr;
	return left_dummy.next;
	}
	};

4，给定一个sorted单链表，删除其中值相同的元素只保留一个，并返回

Remove Duplicates from Sorted List
??
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

题目：
给定一个sorted单链表，删除其中值相同的元素只保留一个，并返回。

递归版
// LeetCode, Remove Duplicates from Sorted List
// ????????? O(n)?????? O(1)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if (!head) return head;
ListNode dummy(head->val + 1); // ???? head ????
dummy.next = head;
recur(&dummy, head);
return dummy.next;
}
private:
static void recur(ListNode *prev, ListNode *cur) {
if (cur == nullptr) return;
if (prev->val == cur->val) { // ?? head
prev->next = cur->next;
delete cur;
recur(prev, prev->next);
} else {
recur(prev->next, cur->next);
}
}
};


迭代版
// LeetCode, Remove Duplicates from Sorted List
// ????????? O(n)?????? O(1)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if (head == nullptr) return nullptr;
for (ListNode *prev = head, *cur = head->next; cur; cur = prev->next) {
if (prev->val == cur->val) {
prev->next = cur->next;
delete cur;
} else {
prev = cur;
}
}
return head;
}
};

5.给定一个sorted单链表，凡是出现相同值的元素都delete，只剩下没有出现过相同值的元素组成最后的单链表。

Remove Duplicates from Sorted List II
??
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers
from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

题目：
给定一个sorted单链表，凡是出现相同值的元素都delete，
只剩下没有出现过相同值的元素组成最后的单链表。

分析：
为了删除最后一个重复元素，这里设置了一个bool类型重复标志duplicated

迭代版
// LeetCode, Remove Duplicates from Sorted List II
// ????????? O(n)?????? O(1)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if (head == nullptr) return head;
ListNode dummy(INT_MIN); // ???
dummy.next = head;
ListNode *prev = &dummy, *cur = head;
while (cur != nullptr) {
bool duplicated = false;
while (cur->next != nullptr && cur->val == cur->next->val) {
duplicated = true;
ListNode *temp = cur;
cur = cur->next;
delete temp;
}
if (duplicated) { // ???????????
ListNode *temp = cur;
cur = cur->next;
delete temp;
continue;
}
prev->next = cur;
prev = prev->next;
cur = cur->next;
}
prev->next = cur;
return dummy.next;
}
};


递归版
// LeetCode, Remove Duplicates from Sorted List II
// ????????? O(n)?????? O(1)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if (!head || !head->next) return head;
ListNode *p = head->next;
if (head->val == p->val) {
while (p && head->val == p->val) {
ListNode *tmp = p;
p = p->next;
delete tmp;
}
delete head;
return deleteDuplicates(p);
} else {
head->next = deleteDuplicates(head->next);
return head;
}
}
};

递归版很妙，可是我为什么写不出来呢？对递归的恐惧？？？？

6.给定一个单链表，将其向右旋转k个位置，k为非负数。

Rotate List
??
Given a list, rotate the list to the right by k places, where k is non-negative.
For example: Given 1->2->3->4->5->nullptr and k = 2, return 4->5->1->2->3->nullptr.

题目：
给定一个单链表，将其向右旋转k个位置，k为非负数。

分析：
先遍历一遍，得出链表长度len，注意k可能大于len，
因此令k%=len。将尾节点next指针指向首节点，形成一个环，
接着往后跑len-k步，从这里断开，就是要求的结果了。

// LeetCode, Remove Rotate List
// ????? O(n)?????? O(1)
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if (head == nullptr || k == 0) return head;
int len = 1;
ListNode* p = head;
while (p->next) { // ???
len++;
p = p->next;
}
k = len - k % len;
p->next = head; // ????
for(int step = 0; step < k; step++) {
p = p->next; //?????
}
head = p->next; // ?????
p->next = nullptr; // ???
return head;
}
};

7.给定一个单链表和一个n，删除倒数第n个节点，并将新的单链表返回。 n的值是合法的，无需检测；要求一次遍历解决。

Remove Nth Node From End of List
??
Given a linked list, remove the n th node from the end of list and return its head.
For example, Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
? Given n will always be valid.
? Try to do this in one pass.

题目：
给定一个单链表和一个n，删除倒数第n个节点，并将新的单链表返回。
n的值是合法的，无需检测；
要求一次遍历解决。

解法：
设两个指针p、q，让q先走n步，然后p和q一起走，
直到q走到尾节点，删除p->next即可。

设置头结点的好处之一，让走n步，就到了第n个节点，顺序对应。


// LeetCode, Remove Nth Node From End of List
// ????? O(n)?????? O(1)
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode dummy{-1, head};
ListNode *p = &dummy, *q = &dummy;
for (int i = 0; i < n; i++) // q ?? n ?
q = q->next;
while(q->next) { // ???
p = p->next;
q = q->next;
}
ListNode *tmp = p->next;
p->next = p->next->next;
delete tmp;
return dummy.next;
}
};

8.给定一个单链表，交换每两个相邻的节点，并返回头结点。不能修改节点中的值，只能修改节点本身。

Swap Nodes in Pairs
??
Given a linked list, swap every two adjacent nodes and return its head.
For example, Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes
itself can be changed.

题目：
给定一个单链表，交换每两个相邻的节点，并返回头结点。
不能修改节点中的值，只能修改节点本身。

也就是说
下面这种写法很简洁，但是题目规定了不能这样做。
// LeetCode, Swap Nodes in Pairs
// ????? O(n)?????? O(1)
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* p = head;
while (p && p->next) {
swap(p->val, p->next->val);
p = p->next->next;
}
return head;
}
};

正确的做法：


ListNode* swapPairs(ListNode* head){
	
	if(head == nullptr  
	|| head->next == nullptr){
		return head;//如果是空链表，或者只有一个元素，直接返回链表头结点 
	}
	ListNode dummy(-1);
	dummy.next = head;
	
	
	//初始化prev指向头结点，cur指向第一个节点，next指向第二个节点 
	for(ListNode* prev = &dummy,*cur = prev->next,*next = cur->next
	;next
	;prev = cur,cur = cur->next,next=cur?cur->next:nullptr){
		
		prev->next = next;
		cur->next = next->next;
		next->next = cur; 
		

	} 
	
	return dummy.next;
}

9.给定一个单链表和一个k数，返回修改过后的单链表。每k个节点就反转一次，不足k个不反转，保持原有顺序。只允许修改节点，不能修改节点的值已完成要求。

Reverse Nodes in k-Group
??
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example, Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

题目：
给定一个单链表和一个k数，返回修改过后的单链表。
每k个节点就反转一次，不足k个不反转，保持原有顺序。
只允许修改节点，不能修改节点的值已完成要求。

递归版： 
// LeetCode, Reverse Nodes in k-Group
// ????????? O(n)?????? O(1)
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
if (head == nullptr || head->next == nullptr || k < 2)
return head;
ListNode *next_group = head;
for (int i = 0; i < k; ++i) {
if (next_group)
next_group = next_group->next;
else
return head;
}
// next_group is the head of next group
// new_next_group is the new head of next group after reversion
ListNode *new_next_group = reverseKGroup(next_group, k);
ListNode *prev = NULL, *cur = head;
while (cur != next_group) {
ListNode *next = cur->next;
cur->next = prev ? prev : new_next_group;
prev = cur;
cur = next;
}
return prev; // prev will be the new head of this group
}
};

迭代版：
// LeetCode, Reverse Nodes in k-Group
// ????????? O(n)?????? O(1)
ListNode* reverseKGroup(ListNode* head,int k){
	
	if(head ==nullptr || head->next ==nullptr || k<2){
		return head;
	}//如果是空表或者链表只有一个元素，或者k<2，就没有反转的必要，直接返回 
	
	ListNode dummy(-1);
	dummy.next = head;
	
	//初始化prev指向头结点，end指向第一个节点 
	for(ListNode* prev = &dummy,*end = head
	;end
	;end = prev->next){
		
		for(int i = 1;i < k && end; i++){
			
			end = end->next; //end指向第整数k倍的节点	
		}
		
		if(end == nullptr){
			break;//不足4个 
		} 
		
		prev = reverseList(prev,prev->next,end);
		//现在给函数传递的信息。prev指向头结点，end指向第整数k倍的节点
		
	}
	
	return dummy.next;
}

//prev 是first前一个元素，begin，end闭区间，保证三者都不为null
//返回反转后的倒数第1个元素。、
ListNode* reverseList(ListNode* prev,ListNode* begin,ListNode* end){
	
	ListNode* end_next = end->next;//记录下一个k段的开始节点
	
	//初始化p为第一个元素，cur为第二个元素，next为第三个元素 
	for(ListNode* p = begin,*cur = p->next,*next = cur->next
	;cur != end_next
	;p = cur,cur = next,next = next?next->next:nullptr){
		
		cur->next = p;//将第二个元素指向第一个元素 
			
		
	} 
	
	begin->next = end_next;//将前一个k段的第一个元素指向下一个k段的第一个元素怒 
	prev->next = end;//让前一个k段的“头结点”指向反转后的第一个节点，即指向之前的末尾节点。 
	return begin;

	
}

10.复制带有随机指针的链表啊一个链表中每个节点都带有一个随机指针，随机指针指向链表中的任意一个节点或者null 返回对这个链表的复制链表。

Copy List with Random Pointer
??
A linked list is given such that each node contains an additional random pointer which could point to
any node in the list or null.
Return a deep copy of the list.

题目：
复制带有随机指针的链表
啊一个链表中每个节点都带有一个随机指针，
随机指针指向链表中的任意一个节点或者null
返回对这个链表的复制链表。

剑指offer上面也有同样的题。
// LeetCode, Copy List with Random Pointer
// ?????????? O(n)?????? O(1)
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
for (RandomListNode* cur = head; cur != nullptr; ) {
RandomListNode* node = new RandomListNode(cur->label);
node->next = cur->next;
cur->next = node;
cur = node->next;
}
for (RandomListNode* cur = head; cur != nullptr; ) {
if (cur->random != NULL)
cur->next->random = cur->random->next;
cur = cur->next->next;
}
// ???????
RandomListNode dummy(-1);
for (RandomListNode* cur = head, *new_cur = &dummy;
cur != nullptr; ) {
new_cur->next = cur->next;
new_cur = new_cur->next;
cur->next = cur->next->next;
cur = cur->next;
}
return dummy.next;
}
};

11.给定一个链表，判断该链表是否存在环

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?

题目：
给定一个链表，判断该链表是否存在环
规定：不使用额外空间。

分析：
最容易想到的方法是，用一个哈希表unordered_map<int，bool>
visited，记录每个元素是否被访问过，一旦出现某个元素被重复访问，
说明存在环。空间复杂度On，时间复杂度On。

最好的方法是时间复杂度On，空间复杂度O1.
设置两个指针，一个快，一个慢，
快的指针每次走两步，慢的指针一次走一步。
如果快指针和慢指针相遇，则说明有环。


bool hasCycle(ListNode* head){
	//设置两个指针，一个快，一个慢
	ListNode* slow =  head;
	ListNode* fast = head;
	while(fast && fast->next){
		slow = slow->next;
		fast = fast->next->next;
		if(slow == fast){
			
			return true;
		}
		
	} 
	
	return false;
	
	
}

12.1.题目有环，输出环开始的节点； 2.题目无环，输出null

Linked List Cycle II
??
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up: Can you solve it without using extra space?

题目：
1.题目有环，输出环开始的节点；
2.题目无环，输出null
规定：不使用额外空间。

分析：
当fast和slow相遇时，slow肯定没有遍历玩链表，而fast
已经在环内循环了n圈。假设slow走了s步，fast走了2s步，
设环长为r，则
2s = s +nr
s = nr
设整个链表长L，环入口点与相遇点距离为a，起点到环入口点为x，
x+a = nr =(n-1)r + r =(n-1)r + L -x
x = (n-1)r +(L-x-a)

L-x-a 为相遇点到环入口点的距离，由此可见，从链表头到环入口点
等于n-1圈内环+相遇点到环入口点，于是我们可以从head开始
另设一个指针slow2，两个满指针每次前进一步，
他两一定会在环入口点相遇。

解法：
就是在上一题的基础上，
在确定有环的时候，开始位置设置slow2指针
让slow和是slow2指针开始一步一步走，
两者相遇点就是环的开始位置。

ListNode* detectCycle(ListNode* head){
	
	ListNode* slow = head;
	ListNode* fast = head;
	
	while(fast && fast->next){
		slow = slow->next;
		fast = fast->next->next;
		
		if(slow == fast){
			ListNode* slow = head;
			
			while(slow2 != slow){
				slow2 = slow2->next;
				slow = slow->next;
			}
			
			return slow2;
		}
		
		
	}
	
	return nullptr;
	
}

13.

Reorder List
??
Given a singly linked list L : L 0 → L 1 → ··· → L n?1 → L n , reorder it to: L 0 → L n → L 1 →
L n?1 → L 2 → L n?2 → ···
You must do this in-place without altering the nodes’ values.
For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

题目：有题中序列可知。

分析：
可以找到中间节点，断开，把后半截单链表reverse一下，
最后合并两个单链表。

void reorderList(ListNode* head){
	
	if(head == nullptr || head->next == nullptr){
		return;
	}
	
	ListNode* slow = head, *fast = head, *prev = nullptr;
	while(fast && fast->next){
		prev = slow;			//prev指向要分开链表的节点处。中间节点的前一个节点，向下取整 
		slow = slow->next;		//slow一步一步走 
		fast = fast->next->next;//fast两步两步走 
		
		
	}
	
	//上面这一段执行结果
	//假设总节点数为n，n/2并且向下取整=s 
	//则最后prev指向第s个节点，slow指向第s+1个节点。 
	
	
	prev->next = nullptr; 
	slow = reverseList(slow);
	
	//合并连个单链表
	
	ListNode* curr = head;
	
	while(curr->next){
		ListNode* tmp = curr->next;
		curr->next = slow;
		slow = slow->next;
		curr->next->next = tmp;
		curr = tmp;
		
		
	} 
	
	curr->next = slow;
	
}

ListNode* reverseList(ListNode* head){
	
	if(head == nullptr || head->next == nullptr){
		return head;//如果为空表或者只有一个元素，直接返回 
	}
	
	ListNode* prev = head;
	for(ListNode* cur = head->next,*next = cur->next
	;cur
	;prev = cur,cur=next,next = next?next->next:nullptr){
		
		cur->next = prev;
		
	}//截止条件是cur为null，也就是cur之前的一个位置是最后一个节点位置
	//也就是反转之后的头结点的位置是prev指向处 
	
	head->next = nullptr;
	
	return prev;
	
}

14.LRU Cache

LRU Cache
??
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the
following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise
return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its
capacity, it should invalidate the least recently used item before inserting a new item.

题目：
设计并实现最近最少使用（LRU）缓存的数据结构。它应该支持以下操作：get和set。
get（key） - 如果密钥存在于缓存中，则获取密钥的值（将始终为正），否则
返回-1。
set（key，value） - 如果该键尚未存在，则设置或插入该值。当缓存达到其容量时，它应该在插入新项之前使最近最少使用的项无效。

分析：
为了使查找、插入和删除都具有较高的性能，
我们使用一个双向链表和一个哈希表。
因为：
1.哈希表保存每个节点的地址，可以保证在O1的时间内查找节点。
2.双向链表插入和删除效率高，单向链表插入和删除时，还要查找节点的前驱节点。

// LeetCode, LRU Cache
// ????? O(logn)?????? O(n)
class LRUCache{
private:
struct CacheNode {
int key;
int value;
CacheNode(int k, int v) :key(k), value(v){}
};
public:
LRUCache(int capacity) {
this->capacity = capacity;
}


int get(int key) {
if (cacheMap.find(key) == cacheMap.end()) return -1;
// ??????????????????? map ???????
cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
cacheMap[key] = cacheList.begin();
return cacheMap[key]->value;
}
void set(int key, int value) {
if (cacheMap.find(key) == cacheMap.end()) {
if (cacheList.size() == capacity) { //?????????????????
cacheMap.erase(cacheList.back().key);
cacheList.pop_back();
}
// ??????????, ??? map ??????
cacheList.push_front(CacheNode(key, value));
cacheMap[key] = cacheList.begin();
} else {
//?????????????????????, ???? map ???????
cacheMap[key]->value = value;
cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
cacheMap[key] = cacheList.begin();
}
}
private:
list<CacheNode> cacheList;
unordered_map<int, list<CacheNode>::iterator> cacheMap;
int capacity;
};

单链表部分结束，以下是字符串部分。

1. 有效回文

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.

题目：
有效回文
??
给定一个字符串，确定它是否是回文，只考虑字母数字字符并忽略
案例。
例如，
“一个男人，一个计划，一个运河：巴拿马”是一个回文。
“赛车”不是回文。
注意：您是否认为该字符串可能为空？这是一个很好的问题
专访。
出于此问题的目的，我们将空字符串定

bool isPalindrome(string s){
	transform(s.begin(),s.end(),s.begin(),::tolower);
	//就是将字符串s的所有部分都小写化，并重新写入字符串s中 
	auto left = s.begin(),right = prev(s.end());//此处prev就是指向s最后一个字符 
	
	while(left < right){
		if(!isalnum(*left)){
			
			++left;//左边如果不是数字和字母就忽略 
		}else if(!isalnum(*right)){
			
			--right;//右边如果不是数字和字母就忽略 
		}else if(*left != *right){
			return false;//如果对称的左右位置处内容不同，直接返回false 
		}else{
			left++;
			right--;//对称位置匹配，检查下一组对称位置。 
		}
		 
		
		
		
	} 
	
	return true; 
	
}

2.实现strStr（）

Implement strStr()
??
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

题目：

实现strStr（）
??
实现strStr（）。
返回指向haystack中第一次出现needle的指针，如果needle不是haystack的一部分，则返回null。

分析：
字符串匹配问题，有KMP算法，面试中暴力算法就足够了，
不过要写的没有bug。

也就是haystack是给定的字符串，在haystack中匹配needle字符串。


int strStr(const string& haystack,const string& needle){
	
	if(needle.empty()){
		return 0;//如果needle是空的，返回0； 
	}	
	
	const int N = haystack.size() -needle.size()+1;
	//设置N是因为没有必要全部匹配，因为如果在N之后
	//是不可能匹配成功的，因为长度，已经不可能了
	
	for(int i=0;i<N;i++){//遍历i到n-1 
		int j=i;//初始化j为每次遍历开始的母串开始下标
		int k=0;//每次遍历开始，模式串都要从0开始
		
		while(j<haystack.size() //因为没有规定两个字符串谁长谁短，所有都需要检测 
		&& k<needle.size()
		&& haystack[j] == needle[k]) {//如果当前字符相等，继续匹配下一组字符，否则就是不匹配 
			
			j++;
			k++;
			
		}
		
		if(k == needle.size()){
			return i;//如果k的大小等于needle的大小，也就是说明成功匹配，返回匹配的首字符对应下标 
		}
		
	}
	
	return -1;//没有成功匹配。 
	
}

3.实现atoi函数

String to Integer (atoi)
??
Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and
ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are respon-
sible to gather all the input requirements up front.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace
character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by
as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored
and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such
sequence exists because either str is empty or it contains only whitespace characters, no conversion is per-
formed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the
range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

题目：实现atoi函数
将字符串转换为整数

分析：
细节题：注意：
1.不规则输入，但是有效，“-3924x8fc”，“+413”
2.无效格式：“++c”，“++1”；
3.溢出数据，“2147483648”

public:
int myAtoi(const string &str) {
int num = 0;
int sign = 1;
const int n = str.length();
int i = 0;
while (str[i] == ' ' && i < n) i++;
if (str[i] == '+') {
i++;
} else if (str[i] == '-') {
sign = -1;
i++;
}
for (; i < n; i++) {
if (str[i] < '0' || str[i] > '9')
break;
if (num > INT_MAX / 10 ||
(num == INT_MAX / 10 &&
(str[i] - '0') > INT_MAX % 10)) {
return sign == -1 ? INT_MIN : INT_MAX;
}
num = num * 10 + str[i] - '0';
}
return num * sign;
}

4.///

5.最长的回文子串

Longest Palindromic Substring
??
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length
of S is 1000, and there exists one unique longest palindromic substring

题目：
最长的回文子串
??
给定一个字符串S，找到S中最长的回文子字符串。您可以假设最大长度
S是1000，并且存在一个独特的最长的回文子串

分析：

最长回文子串，经典题
1.暴力枚举，以每个元素为中间元素，同时从左右出发，复杂度On*n
2.记忆化搜索，复杂度On*n 设f[i][j]表示i和j之间最长回文子串，递推。
3.动态规划，On*n 表示i到j是否是回文串，状态转移方程如下：
	f(i,j) =
	true ,i = j
	S[i] = S[j] ,j = i + 1
	S[i] = S[j] and f(i + 1,j ? 1) ,j > i + 1

推荐用动规
可能看代码不太直观，但是当遍历大范围的时候，之前的j到i已经检测过并填充好了。


string longestPalindrome(const string& s){
	
	const int n = s.size();
	bool f[n][n];
	fill_n(&f[0][0],n*n,false);
	//用vector会超时
	
	int max_len = 1;
	int start = 0;
	//初始化最长回文子串的长度的起点。
	
	for(int i = 0; i < n; i++){
		f[i]][i] = true;//单个字母一定是回文串
		
		for(int j = 0; j < i; j++){
			//j到i表示是否为回文串
			f[j][i] = (s[j] == s[i]
					  && (i-j<2 || f[j+1][i-1]));
			//对称位置字符相等
			//1.如果总共检测的只有2个或者3个，一定是回文串
			//2.如果长度还有，检测下一组对曾位置。 
						
			if(f[j][i] && max_len < (i - j +1)){
				
				max_len = i - j+1;
				start = j;
			
			}
						
		
			
			
		} 
		
		
	} 
	
	return s.substr(start,max_len);
	
	
}

字符串到此为止，接下来开始树/

1.1二叉树的遍历

1.二叉树非递归前序遍历

Binary Tree Preorder Traversal
??
Given a binary tree, return the preorder traversal of its nodes’ values.
For example: Given binary tree {1,#,2,3},
1

2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?

题目：
二叉树非递归前序遍历

分析：
用栈或者镜像遍历

解法：
用栈，固定解法。
初始化，栈内最先存根；之后push用栈，先右孩子，再左孩子。

vector<int> preorderTraverse(TreeNode* root){
	
	vector<int> result;
	stack<const TreeNode*> s;
	
	if(root != nullptr){
		s.push(root);
	}
	
	while(!s.empty()){
		
		const TreeNode* p = s.top();
		s.pop();
		result.push_back(p->val);
		
		if(p->right != nullptr){
			s.push(p->right);
		
		}
		
		if(p->left != nullptr){
			
			s.push(p->left);
		}
		
		
	}
	
	return result;
	
}

2.二叉树非递归中序遍历，同样是用栈

5.1.2 Binary Tree Inorder Traversal
??
Given a binary tree, return the inorder traversal of its nodes’ values.
For example: Given binary tree {1,#,2,3},
1

2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?

题目：
二叉树非递归中序遍历，同样是用栈，
解法固定，需要记住。

vector<int> inorderTraverse(TreeNode* root){
	vector<int> result;
	stack<const TreeNode*> s;
	const TreeNode* p = root;
	
	while(!s.empty() 
		  || p!=nullptr){//也就是只有栈为空且p指向也为空时才算遍历结束
			
		if(p != nullptr){//此时p指向不为空，push进栈，并寻找左孩子。
			s.push(p);
			p = p->left;
		}else{//此时p指向为空，只有一个可能，栈中不为空,自然就是从栈中取元素，并且还需要寻找有孩子
			
			p = s.top();
			s.pop();
			result.push_back(p->val);
			p = p->right;	
			
		}	
					
	}
	
	return result;
	
}

3.二叉树非递归后序遍历

Binary Tree Postorder Traversal
??
Given a binary tree, return the postorder traversal of its nodes’ values.
For example: Given binary tree {1,#,2,3},
1

2
/
3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

题目：
二叉树非递归后序遍历

vector<int> postorderTraverse(TreeNode* root){
	
	vector<int> result;
	
	stack<const TreeNode*> s;
	
	//*p,正在访问的节点，q刚刚访问过的节点。
	const TreeNode* p = root,*q = nullptr;
	
	do{
		while(p!=nullptr){ 
			s.push(p);
			p = p->left;
			
		}
		
		q = nullptr;
		while(!s.empty()){
			p = s.top();
			s.pop();
			//右孩子不存在或已被访问，访问
			if(p->right ==  q){
				result.push_back(p->val);
				q = p;//保存刚访问过的节点。 
				
			}else{
				//当前节点不能访问，需要二次进栈
				s.push(p);
				//先处理右子树
				p = p->right;
				break; 
				
			} 
			
			
		}
		
		
		
		
	}while(!s.empty()); 
	
	return result;
		
}

4.二叉树层序遍历

Binary Tree Level Order Traversal
??
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by
level).
For example: Given binary tree {3,9,20,#,#,15,7},
3
/
9 20
/
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

题目：
二叉树层序遍历

//迭代版

vector<vector<int> > levelOrder(TreeNode* root){
	
	vector<vector<int> > result;
	queue<TreeNode*> current,next;
	
	
	//如果树为空，直接返回；如果树非空，根节点入队列 
	if(root == nullptr){
		return result;
		
	}else{
		current.push(root);
	}
	
	while(!current.empty()){//如果队列中有元素
		 
		vector<int> level;//存放一层的所有元素
		while(!current.empty()){
			TreeNode* node = current.front();
			current.pop();
			level.push_back(node->val);
			if(node->left != nullptr){
				next.push(node->left);
				
			}
			if(node->right != nullptr){
				
				next.push(node->right);
			}
			
			
		} 
		//执行到这里，当前层的所有元素都已经输出。 
		
		result.push_back(level);//一层用一个数组，所有层用二维数组result保存 
		swap(next,current);//这里是个关键，next存放的是下一层的所有节点 
		//这里也就是将当前层刷新为下一层，开启下一循环。 
		
	} 
	
	return result;
	
	
}

5.二叉树倒序层序遍历

Binary Tree Level Order Traversal II
??
Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right,
level by level from leaf to root).
For example: Given binary tree {3,9,20,#,#,15,7},
3
/
9 20
/
15 7
return its bottom-up level order traversal as:
[
[15,7]
[9,20],
[3],
]

题目：二叉树倒序层序遍历

分析，就是上一题多加了一行reverse函数。

//迭代版

vector<vector<int> > levelOrder(TreeNode* root){
	
	vector<vector<int> > result;
	queue<TreeNode*> current,next;
	
	
	//如果树为空，直接返回；如果树非空，根节点入队列 
	if(root == nullptr){
		return result;
		
	}else{
		current.push(root);
	}
	
	while(!current.empty()){//如果队列中有元素
		 
		vector<int> level;//存放一层的所有元素
		while(!current.empty()){
			TreeNode* node = current.front();
			current.pop();
			level.push_back(node->val);
			if(node->left != nullptr){
				next.push(node->left);
				
			}
			if(node->right != nullptr){
				
				next.push(node->right);
			}
			
			
		} 
		//执行到这里，当前层的所有元素都已经输出。 
		
		result.push_back(level);//一层用一个数组，所有层用二维数组result保存 
		swap(next,current);//这里是个关键，next存放的是下一层的所有节点 
		//这里也就是将当前层刷新为下一层，开启下一循环。 
		
	} 
	
	reverse(result.begin(),result.end());//比上一题多了这一行
	return result;
	
	
	
}

6.二叉树Z字形的层序遍历

Binary Tree Zigzag Level Order Traversal
??
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right,
then right to left for the next level and alternate between).
For example: Given binary tree 3,9,20,#,#,15,7,
3
/
9 20
/
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

题目：
二叉树Z字形的层序遍历

分析：
广度优先遍历，用一个bool记录是从左到右还是从右到左，每一层结束就翻转一次。

vector<vector<int> > zigLevelOrder(TreeNode* root){
	
	vector<vector<int> > result;
	queue<TreeNode*> current,next;
	bool left_to_right = true;
	
	if(root == null){
		
		return result;
	}else{
		current.push(root);
		
	}
	
	while(!current.empty()){
		vector<int> level;//存放一层中的所有元素
		
		while(!current.empty()){
			TreeNode* node = current.front();
			current.pop();
			level.push_back(node->val);
			if(node->left != nullptr){
				next.push(node->left);
				
			}
			
			if(node->right != nullptr){
				next.push(node->right);
			}
			
		} 
		
		if(!left_to_right){
			reverse(level.begin(),level.end());
			
		}
		
		result.push_back(level);
		left_to_right = !left_to_right;
		swap(next,current);
		
	}
	
	return result;
	
}

7.二叉查找树，其中有两个元素互换了，要求不改变树的结构，恢复正确的二叉查找树

Recover Binary Search Tree
??
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note: AsolutionusingO(n)spaceisprettystraightforward. Couldyoudeviseaconstantspacesolution?

题目：
二叉查找树，其中有两个元素互换了，要求不改变树的结构，恢复正确的二叉查找树

解法：
On空间解法：
开一个指针数组，中序遍历，将节点指针一次存放
到数组里面，然后寻找两个逆向的位置，
先是从前往后找第一个逆序的位置，
然后从后往前查找第二个逆序的位置，交换这两个指针的值。

8.给定两颗二叉树，编写函数判断两棵树是否相等。

Same Tree
??
Given two binary trees, write a function to check if they are equal or not.
Twobinarytreesareconsideredequaliftheyarestructurallyidenticalandthenodeshavethesamevalue.

题目：
给定两颗二叉树，编写函数判断两棵树是否相等。

递归判断比较简单。

bool isSameTree(TreeNode* p.TreeNode* q){
	
	if( !p && !q){
		return true;//终止条件:一定是双方同时为空 
	}
	
	if(!p || !q){
		return false;//通过了第一个if，还满足第二个if
					//只有一种可能，就是其中一个为空，一个不为空，一定不same 
	} 
	
	return p->val == q->val 
		   && isSameTree(p->left,q->left);
		   && isSameTree(p->right,q->right);
	
	
}

9.给定两颗二叉树，判断两者是否对称

Symmetric Tree
??
Given two binary trees, write a function to check if they are equal or not.
Twobinarytreesareconsideredequaliftheyarestructurallyidenticalandthenodeshavethesamevalue.

题目：对称二叉树
给定两颗二叉树，判断两者是否对称

// LeetCode, Symmetric Tree
// ????????? O(n)?????? O(logn)
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if (root == nullptr) return true;
return isSymmetric(root->left, root->right);
}
bool isSymmetric(TreeNode *p, TreeNode *q) {
if (p == nullptr && q == nullptr) return true; // ????
if (p == nullptr || q == nullptr) return false; // ????
return p->val == q->val // ????
&& isSymmetric(p->left, q->right)
&& isSymmetric(p->right, q->left);
}
};

10.平衡二叉树

Balanced Binary Tree
??
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two
subtrees of every node never differ by more than 1.

题目：
平衡二叉树
??
给定二叉树，确定它是否是高度平衡的。
对于这个问题，高度平衡的二叉树被定义为二叉树，其中两者的深度
每个节点的子树永远不会超过1。

bool isBalanced(TreeNode* root){
	return balancedHeight(root) >= 0;
	
}

//如果是平衡树，则返回这棵树的高度
//否则返回-1 

int balancedHeight(TreeNode* root){
	
	if(root == nullptr){
		return 0;//如果是空树，符合平衡树，但是高度为0 
	}
	
	int left = balancedHeight(root->left);
	int right = balancedHeight(root->right);
	
	if(left < 0 || right < 0 || abs(left - right)>1){
		return -1;
	} 
	//1.如果左子树不是平衡树，则此树一定不是平衡树
	//2.如果右子树不是平衡树，则此树一定不是平衡树
	//3.如果子树都是平衡树，但是差值>1，那么一定不是平衡树
	
	return max(left,right)+1;//三方合并 
	
}

判断是否为堆：

// is_heap example
#include <iostream>     // std::cout
#include <algorithm>    // std::is_heap, std::make_heap, std::pop_heap
#include <vector>       // std::vector

int main () {
  std::vector<int> foo {9,5,2,6,4,1,3,8,7};

  if (!std::is_heap(foo.begin(),foo.end()))
    std::make_heap(foo.begin(),foo.end());

  std::cout << "Popping out elements:";
  while (!foo.empty()) {
    std::pop_heap(foo.begin(),foo.end());   // moves largest element to back
    std::cout << ' ' << foo.back();         // prints back
    foo.pop_back();                         // pops element out of container
  }
  std::cout << '\n';

  return 0;
}

leetcode-C++笔记

leetcode-C++笔记

1.给定一个有序数组，去除重复值保证独一无二，不使用额外空间，返回最终数组的长度值。

2.根据上一题改编，如果要求重复出现次数最多两次呢？

3.给定了一个sorted数组，给定一个值进行查找 但是注意，这里还对sorted数组进行了旋转，且假设了 这个数组中值互不相等

4.如果sorted旋转数组中的数字是重复元素呢？那应该怎么解决

5.Median of Two Sorted Arrays

6.给定一个无序整数数组，计算出该数组最长连续数序列的长度

7.给定一个整数数组，给定一个目标数， 找2个数组里面的数和=目标数。 并且返回这两个数的下标值，要求两个数下标值不同。 并且假设输入数据只有唯一解。

8.给定一个整数数组， 求所有的3元祖，3个数的和为0

9.和上一题类似， 但是需要找出3元组之和与target比较最为接近的

10.还有四个数之和的题，不看了，以后又机会又感兴趣再看。

11.给定一个数组和一个值，删除该值的所有实例并返回新的长度。 元素的顺序可以改变。你留下的新长度并不重要。

12.Next Permutation

13.

数组部分暂时这样，之后再看，接下来是单链表部分

1.给定两个单链表分别代表两个非负数， 并且数字是逆序的，每个链表节点包含一个数 尝试将两个数相加并将结果返回为单链表。

2.反转单链表II

3.将单链表分区：

4，给定一个sorted单链表，删除其中值相同的元素只保留一个，并返回

5.给定一个sorted单链表，凡是出现相同值的元素都delete， 只剩下没有出现过相同值的元素组成最后的单链表。

6.给定一个单链表，将其向右旋转k个位置，k为非负数。

7.给定一个单链表和一个n，删除倒数第n个节点，并将新的单链表返回。 n的值是合法的，无需检测； 要求一次遍历解决。

8.给定一个单链表，交换每两个相邻的节点，并返回头结点。 不能修改节点中的值，只能修改节点本身。

9.给定一个单链表和一个k数，返回修改过后的单链表。 每k个节点就反转一次，不足k个不反转，保持原有顺序。 只允许修改节点，不能修改节点的值已完成要求。

10.复制带有随机指针的链表 啊一个链表中每个节点都带有一个随机指针， 随机指针指向链表中的任意一个节点或者null 返回对这个链表的复制链表。

11.给定一个链表，判断该链表是否存在环

12.1.题目有环，输出环开始的节点； 2.题目无环，输出null

13.

14.LRU Cache

单链表部分结束，以下是字符串部分。

1. 有效回文

2.实现strStr（）

3.实现atoi函数

5.最长的回文子串

字符串到此为止，接下来开始树/

1.1二叉树的遍历

1.二叉树非递归前序遍历

2.二叉树非递归中序遍历，同样是用栈

3.二叉树非递归后序遍历

4.二叉树层序遍历

5.二叉树倒序层序遍历

6.二叉树Z字形的层序遍历

7.二叉查找树，其中有两个元素互换了，要求不改变树的结构，恢复正确的二叉查找树

8.给定两颗二叉树，编写函数判断两棵树是否相等。

9.给定两颗二叉树，判断两者是否对称

10.平衡二叉树

3.给定了一个sorted数组，给定一个值进行查找但是注意，这里还对sorted数组进行了旋转，且假设了这个数组中值互不相等

7.给定一个整数数组，给定一个目标数，找2个数组里面的数和=目标数。并且返回这两个数的下标值，要求两个数下标值不同。并且假设输入数据只有唯一解。

8.给定一个整数数组，求所有的3元祖，3个数的和为0

9.和上一题类似，但是需要找出3元组之和与target比较最为接近的

11.给定一个数组和一个值，删除该值的所有实例并返回新的长度。元素的顺序可以改变。你留下的新长度并不重要。

1.给定两个单链表分别代表两个非负数，并且数字是逆序的，每个链表节点包含一个数尝试将两个数相加并将结果返回为单链表。

5.给定一个sorted单链表，凡是出现相同值的元素都delete，只剩下没有出现过相同值的元素组成最后的单链表。

7.给定一个单链表和一个n，删除倒数第n个节点，并将新的单链表返回。 n的值是合法的，无需检测；要求一次遍历解决。

8.给定一个单链表，交换每两个相邻的节点，并返回头结点。不能修改节点中的值，只能修改节点本身。

9.给定一个单链表和一个k数，返回修改过后的单链表。每k个节点就反转一次，不足k个不反转，保持原有顺序。只允许修改节点，不能修改节点的值已完成要求。

10.复制带有随机指针的链表啊一个链表中每个节点都带有一个随机指针，随机指针指向链表中的任意一个节点或者null 返回对这个链表的复制链表。