描述： 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
描述：给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
描述：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
描述：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
描述： 把一个0-1（只包含0和1的串）进行排序，0在一边，1在另一边，你可以交换任意两个位置，问最少交换多少次？
输入 ： str = "00101110101100101" 输出：5
那如果每次只能相邻两个数交换，最少多少次呢
描述：给定一个字符串str和长度leftSize，请把字符串leftSize左边的整体部分与右边交换 ,要求额外空间复杂度O(1)
输入：str = "abdesfc" leftSize = 3 输出："esfcabd"
如果对时间复杂度有要求呢？？
描述：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
提示：中序数组分成左右两部分后递归遍历
private static TreeNode buildTreeUtil(int[] preOrder, int preStart, int preEnd,int [] inorder,int inStart,int inEnd){}
描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
描述：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
输入: "abcabcbb"
输出: 3
描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
* 输入：matrix = [
* [1, 2, 3],
* [4, 5, 6],
* [7, 8, 9]
* ]
* 输出：[1,2,3,6,9,8,7,4,5]
思路 定义top、bottom、left、right四个子针
* 39
* / \
* 24 64
* / \ /
* 23 30 53
* \
* 60
* 先序遍历：根左右 : 39 24 23 30 64 53 60
* 中序遍历：左根右 : 23 24 30 39 53 60 64
* 后序遍历：左右根 : 23 30 24 60 53 64 39
描述：输入两个链表，找出它们的第一个公共节点（节点相同，并非节点的内容相同）。
输入：intersectVal = 8,
listA = [4,1,8,4,5], listB = [5,0,1,8,4,5],
skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在B中，相交节点前有 3 个节点。
* eg:
* 39
* / \
* 24 64
* / \ /
* 23 30 53
* \
* 60
输出：39, 24, 64, 23, 30, 53, 60
提示可以用队列解决
- 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
- 要求时间复杂度为O(n)。
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路：带上你比我大我就要，比我小丢弃
思想：
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数
eg:
输入：arr = [5,4,7,1,2,8,9]
输出：[1,2,4,5,7,8,9]
思想：
- 将两个或两个以上的有序序列合并成一个新的有序序列
- 合并的方法是比较各子序列的第一个记录的键值，最小的一个就是排序的第一个记录的键值。
- 取出这个记录，继续比较各子序列现有的第一个记录的键值，便可以找出排序后的第二个键值。
- 然后开始递归，最终得到排序结果。
eg:
输入：arr = [5,4,7,1,2,8,9]
输出：[1,2,4,5,7,8,9]
需要借助一个临时数组
翻转一棵二叉树。
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
描述： 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
- 不占用额外内存空间能否做到？
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
描述：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
输入：nums = [9,1,7,9,7,9,7]
输出：1
描述：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
双指针解法
描述：数组为{3,2,2,3,1},查询为（0,3,2）,意思是在数组里下标0-3这个范围上，有几个2？ 返回2。
假设给你一个数组arr，对这个数组的查询非常频繁，请返回所有查询结果
输入：arr={3,2,2,3,1},
startId = 0, endId = 3, queryId = 2
输出：2
思路: 借助hashMap，问题转换为顺序数组指定范围查找
描述：给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
思路：从第二格到N-2格，依次计算每格的可以装水的容量，最后相加。Math.(leftMax,rightMax) - arr[i]
第二种，考虑动态规划
描述：给你一个二维数组matrix,所有数据都是整数，请你把其中所有的0做上下左右方向的延迟，放回处理之后的matrix 比如：注意其中有两个0，那么每个0都向上下左右延伸
要求：整个处理过程都直接在matrix上发生，除此之外额外空间复杂度请做到O(1),也就是只用有限介个变量
输入:
arr = {
{7 ,0 ,1 ,4 ,6},
{6 ,5 ,3 ,2 ,1},
{4 ,2 ,1 ,0 ,3},
{8 ,2 ,1 ,2 ,9},
{0 ,3 ,6 ,4 ,8}
};
输出：
0 0 0 0 0
0 0 3 0 1
0 0 0 0 0
0 0 1 0 9
0 0 0 0 0
思路：把为0的坐标标记在第一行和第一列标记0，还得标记第一行和第一列是否有原生的0（两个变量标记） ，然后处理从第二行第二列开始， 最后处理第一行和第一列
- 描述：给定一个只由0和1组成的二维数组matrix，每一行都可以保证所有的0在左侧，1在右侧，将那些行拥有最多的1，请放入一个列表返回
输入：
0 0 0 0 1 1
0 0 0 0 0 1
0 0 1 1 1 1
1 1 1 1 1 1
0 0 0 0 0 0
1 1 1 1 1 1
输出：[3,5]
思路：每一行从右向左扫描，记录最大值，放入一个临时空间，最终的结果应该是右上到左下的一个过程
如果每一行的数据很大可以用二分查找1进行优化
描述：给定一个长度为N的数组，和一个大于1的正整数K，如果有那些数次数大于等于N/K,就放回这些数
- 要求：时间复杂度O(N),额外空间复杂度O(k)
输入：arr = [4,1,7,5,5,5,8,2,7] k = 3
输出：[5]
这题重点是额外空间复杂度O(k)