输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。import java.util.ArrayList;import java.util.List;

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。public class Solution {public int MoreThanHalfNum_Solution(int [] array) {

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。import java.util.*;

连续子数组的最大和HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题 分(divide) 成一些小的问题然后递归求解，而 治(conquer) 的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。流程：首先将数组对半分为两个部分，然后分别对左右两边进行排序；最后对整体进行外排；重点关注：最后整体的外排

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)x 坐标为 L - 1，y 坐标为 R + 1，两边分别表示小于 num 和大于 num 的值，当前位置坐标为 cur，然后依次向右遍历，如果该数小于 num，则该数和小于区域最右边下标（x）的下一个坐标元素交换，小于区域向右扩充（即 x + 1），如果该数等于 num ,则 cur 指向下一个元素，如果大于 num，则该数和大于区域最左边区域的前一个坐标元素交换，大于区域向左扩充一个（即 y - 1），然后这里交换回来的数还需要按照上面的标准进行判断，直到 cur 和 又边界相遇停止；

| 算法名称 | 时间复杂度 | 时间复杂度 | 算法种类 | 是否稳定 | 原因 || -------- | ---------------------------- | ---------- | ---------- | -------------------- | ------------------------------------------------------------ || 冒泡排序 | $O({N}^{2})$ | $O(1)$ | 基于比较 | 稳定 | 在冒泡的时候，如果遇到前后相同的值两者不交换即可，只有前者比后者大才交换； |

package cn.test;/**

目标：实现一个特殊的栈，在实现栈的基础功能上，再实现返回栈中最小元素的操作；要求：pop、push、getMin 的操作的时间复杂度都是 O（1），同时设计的栈类型可以使用现成的栈结构；解答思路： 因为时间复杂度要求：O(1)，因此不能使用遍历，因为遍历的结果就是 O（N），这里使用两个栈；一个栈为 Data 栈，用于存放数据，另一个栈为 min 栈，用于存放最小值，两个栈一起增长；

实现一种狗猫队列的结构，要求如下：

package cn.test;import java.util.Stack;/**

【题目】 分别实现反转单向链表和反转双向链表的函数。【要求】 如果链表长度为N，时间复杂度要求为O(N)，额外空间复杂度要求为O(1)图解

二叉树的示例结构为：实际函数访问结点的顺序为：1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1 结束

【平衡二叉树概念】当二叉树的任意一棵子树的左子树的高度和右子树的高度相差不超过 1 时，该二叉树为平衡二叉树。【解答方案】根据定义可知，要确认一个二叉树是否是平衡二叉树势必要遍历所有结点。即将问题分解为：只要保证以每个结点为根节点的树是否平衡；而遍历到每个结点时，要想知道以该结点为根结点的子树是否是平衡二叉树，首先判断该结点的左子树是否平衡，然后判断该结点的右子树是否平衡，如果两个子树都平衡，分别计算左子树和右子树的高度。因此我们要收集两个信息：

【题目】 现在有一种新的二叉树节点类型如下：public class Node {public int value;

解决方案：

【搜索二叉树 BST 概念】对于二叉树的任意一棵子树，其左子树上的所有结点的值小于该子树的根节点的值，而其右子树上的所有结点的值大于该子树的根结点的值，并且整棵树上任意两个结点的值不同（重复的结点的值可以通过 List 的形式进行存放）。【解答方案】 根据二叉树的中序遍历看是否递增根据定义，搜索二叉树的中序遍历打印将是一个升序序列。因此我们可以利用二叉树的中序遍历的非递归方式，比较中序遍历时相邻两个结点的大小，只要有一个结点的值小于其后继结点的那就不是搜索二叉树。

[TOC]哈希函数的概念是：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。下面是一幅示意图：

Manacher算法是由题目“求字符串中最长回文子串的长度”而来。比如abcdcb的最长回文子串为bcdcb，其长度为5。我们可以遍历字符串中的每个字符，当遍历到某个字符时就比较一下其左边相邻的字符和其右边相邻的字符是否相同，如果相同则继续比较其右边的右边和其左边的左边是否相同，如果相同则继续比较……，我们暂且称这个过程为向外“扩”。当“扩”不动时，经过的所有字符组成的子串就是以当前遍历字符为中心的最长回文子串。我们每次遍历都能得到一个最长回文子串的长度，使用一个全局变量保存最大的那个，遍历完后就能得到此题的解。但分析这种方法的时间复杂度：当来到第一个字符时，只能扩其本身即1个；来到第二个字符时，最多扩两个；……；来到字符串中间那个字符时，最多扩(n-1)/2+1个；因此时间复杂度为1+2+……+(n-1)/2+1即O(N^2)。但Manacher算法却能做到O(N)。

介绍窗口以及窗口内最大值或者最小值的更新结构（单调双向队列）什么是窗口：就是一个数组------有L和R指针，默认两个指针均位于数组的最左边即下标为 -1 的位置， 当有数字进入时R向右移动 当有数字删除时则L向右移动 且L 和R 不会回退且 L 不能到 R 右边~

给定一个字符串类型的数组 strs，找到一种拼接方式，使得把所有字符串拼接起来之后形成的字符串具有最低的字典序。分析此题的比较策略即为贪心策略，但是不一定其它也是两者一样的。

【题目】 给定一个整型正方形矩阵matrix，请把该矩阵调整成顺时针旋转90度的样子。【要求】 额外空间复杂度为O(1)。解答： 还是一圈圈的旋转，首先旋转最外面，然后逐层向里，在旋转的时候唯一需要注意的就是元素之间的位置替换；

No exerpt.

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。利用一个结论：一个二进制数n减1后与原二进制数进行&运算( 即n&(n-1) )会消去最右边的1。

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。这道题就是将数组分为奇数部分和偶数部分，每遍历到一个奇数，就迭代地将其放入前面奇数部分，每遍历到一个偶数，就继续遍历。相当于任意奇数都小于任意偶数，所有奇数都相等，所有偶数都相等，然后使用快速排序排序数组。

输入一个链表，输出该链表中倒数第k个结点。/*public class ListNode {

输入一个链表，反转链表后，输出新链表的表头。

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义：源二叉树8

从上往下打印出二叉树的每个节点，同层节点从左至右打印。通过上面的具体例子分析，可以找到规律：每一次打印一个节点的时候，如果该节点有子节点，则把该节点的子节点放到一个队列的尾部。接下来到对队列的头部取出最早进入队列的节点放到ArrayList 中，重复前面的操作，直至队列中所有的节点都存到ArrayList中。

二叉搜索树的后序遍历序列输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

二叉树中和为某一值的路径输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）/*public class RandomListNode {

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。