算法面试笔记
本科面试笔记
一、树
1.红黑树
- 红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。
- 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树
性质：
1. 每个节点非红即黑
2. 根节点是黑的;
3. 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的;
4. 如果一个节点是红色的，则它的子节点必须是黑色的。
5. 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;2.AVL树
平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。
3.map底层为什么用红黑树实现
红黑树在查找，插入删除的性能都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层实现都是使用的红黑树。
4.Top(K)问题
1、直接全部排序（只适用于内存够的情况）
当数据量较小的情况下，内存中可以容纳所有数据。则最简单也是最容易想到的方法是将数据全部排序，然后取排序后的数据中的前K个。
这种方法对数据量比较敏感，当数据量较大的情况下，内存不能完全容纳全部数据，这种方法便不适应了。即使内存能够满足要求，该方法将全部数据都排序了，而题目只要求找出top K个数据，所以该方法并不十分高效，不建议使用。
2、快速排序的变形 （只使用于内存够的情况）
这是一个基于快速排序的变形，因为第一种方法中说到将所有元素都排序并不十分高效，只需要找出前K个最大的就行。
这种方法类似于快速排序，首先选择一个划分元，将比这个划分元大的元素放到它的前面，比划分元小的元素放到它的后面，此时完成了一趟排序。如果此时这个划分元的序号index刚好等于K，那么这个划分元以及它左边的数，刚好就是前K个最大的元素；如果index > K，那么前K大的数据在index的左边，那么就继续递归的从index-1个数中进行一趟排序；如果index < K，那么再从划分元的右边继续进行排序，直到找到序号index刚好等于K为止。再将前K个数进行排序后，返回Top K个元素。这种方法就避免了对除了Top K个元素以外的数据进行排序所带来的不必要的开销。
3、最小堆法
这是一种局部淘汰法。先读取前K个数，建立一个最小堆。然后将剩余的所有数字依次与最小堆的堆顶进行比较，如果小于或等于堆顶数据，则继续比较下一个；否则，删除堆顶元素，并将新数据插入堆中，重新调整最小堆。当遍历完全部数据后，最小堆中的数据即为最大的K个数。
4、分治法
将全部数据分成N份，前提是每份的数据都可以读到内存中进行处理，找到每份数据中最大的K个数。此时剩下N K个数据，如果内存不能容纳N K个数据，则再继续分治处理，分成M份，找出每份数据中最大的K个数，如果M*K个数仍然不能读到内存中，则继续分治处理。直到剩余的数可以读入内存中，那么可以对这些数使用快速排序的变形或者归并排序进行处理。
5、Hash法
如果这些数据中有很多重复的数据，可以先通过hash法，把重复的数去掉。这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间。处理后的数据如果能够读入内存，则可以直接排序；否则可以使用分治法或者最小堆法来处理数据。
5.红黑树较AVL树的优点：
AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。
6.二叉树的层序遍历并输出（手写代码）
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> resultList = new ArrayList<>();
if (root == null) {
return resultList;
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {
TreeNode nowNode = q.peek();
q.poll();
resultList.add(nowNode.val);
if (nowNode.left != null) {
q.add(nowNode.left);
if (nowNode.right != null) {
q.add(nowNode.right);
return resultList;
}7.序列化和反序列化二叉树。（手写代码）
//题目：请实现两个函数，分别用来序列化和反序列化二叉树。
public class SerializeBinaryTrees {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
String Serialize(TreeNode node) {
StringBuilder sb = new StringBuilder();
if (node == null) {
sb.append("$,");
} else {
sb.append(node.val + ",");
sb.append(Serialize(node.left));
sb.append(Serialize(node.right));
return sb.toString();
int index = 0;
TreeNode Deserialize(String str) {
TreeNode node = null;
if (str == null || str.length() == 0)
return node;
int start = index;
while (str.charAt(index) != ',')
index++;
if (!str.substring(start, index).equals("$")) {
node = new TreeNode(Integer.parseInt(str.substring(start, index)));
index++; // 这条语句位置别放错了
node.left = Deserialize(str);
node.right = Deserialize(str);
} else {
index++;
return node;
}8.最近公共祖先
有一棵无穷大的满二叉树，其结点按根结点一层一层地从左往右依次编号，根结点编号为1。现在有两个结点a，b。请设计一个算法，求出a和b点的最近公共祖先的编号。
给定两个int a,b。为给定结点的编号。请返回a和b的最近公共祖先的编号。注意这里结点本身也可认为是其祖先。
测试样例： 2，3
返回： 1
//思路：满二叉树的子节点与父节点之间的关系为root = child / 2
//利用这个关系，如果a ！= b，就让其中的较大数除以2， 如此循环知道a == b，
//即是原来两个数的最近公共祖先
//代码如下：
class LCA {
public:
int getLCA(int a, int b) {
// write code here
while(a != b)
if(a > b)
a /= 2;
b /= 2;
return a;
};二、堆和栈
1.说一说你理解的stack overflow，并举个简单例子导致栈溢出
栈溢出概念：
栈溢出指的是程序向栈中某个变量中写入的字节数超过了这个变量本身所申请的字节数，因而导致栈中与其相邻的变量的值被改变。
栈溢出的原因：
-
局部数组过大。当函数内部的数组过大时，有可能导致堆栈溢出。局部变量是存储在栈中的，因此这个很好理解。解决这类问题的办法有两个，一是增大栈空间,二是改用动态分配，使用堆（heap）而不是栈（stack）。
-
递归调用层次太多。递归函数在运行时会执行压栈操作，当压栈次数太多时，也会导致堆栈溢出。
-
指针或数组越界。这种情况最常见，例如进行字符串拷贝，或处理用户输入等等。
2.堆和栈的区别
1）申请方式： 栈由系统自动分配和管理，堆由程序员手动分配和管理。
2）效率：
栈由系统分配，速度快，不会有内存碎片。
堆由程序员分配，速度较慢，可能由于操作不当产生内存碎片。
3）扩展方向
栈从高地址向低地址进行扩展，堆由低地址向高地址进行扩展。
4）程序局部变量是使用的栈空间，new/malloc动态申请的内存是堆空间，函数调用时会进行形参和返回值的压栈出栈，也是用的栈空间。
3.大小根堆特点
堆是一棵完全二叉树（如果一共有h层，那么1~h-1层均满，在h层可能会连续缺失若干个右叶子）。
1）小根堆
若根节点存在左子女则根节点的值小于左子女的值；若根节点存在右子女则根节点的值小于右子女的值。
2）大根堆
若根节点存在左子女则根节点的值大于左子女的值；若根节点存在右子女则根节点的值大于右子女的值。
堆和普通树的区别
堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：
节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。
内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来存储数组，且不使用指针。
平衡。二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。
搜索。在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。
4.两个栈实现一个队列 和 用队列实现栈（手写代码）
public class Main {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
//进栈操作呢
public void appendTail(int item){
stack1.push(item);
//出栈操作
public int deleteHead(){
while(!stack2.isEmpty()){
return stack2.pop();
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
return stack2.pop();
}用队列实现栈
class MyStack {
Queue<Integer> que;
/** Initialize your data structure here. */
public MyStack() {
que = new LinkedList<Integer>();
/** Push element x onto stack. */
public void push(int x) {
que.add(x);
int num=que.size();
while(num>1){
que.add(que.poll());
num--;
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return que.poll();
/** Get the top element. */
public int top() {
return que.peek();
/** Returns whether the stack is empty. */
public boolean empty() {
return que.isEmpty();
}三、数组
1.数组与链表的区别
数组的优点：
-
随机访问性强
-
查找速度快
数组的缺点:
-
插入和删除效率低
-
可能浪费内存
-
内存空间要求高，必须有足够的连续内存空间。
-
数组大小固定，不能动态拓展
链表的优点:
-
插入删除速度快
-
内存利用率高，不会浪费内存
-
大小没有固定，拓展很灵活。
链表的缺点:
- 不能随机查找，必须从第一个开始遍历，查找效率低
2.二分法
int binary_search(T arr[], int n, T target) {
int l = 0, r = n - 1;
while (l <= r) {
int mid = (r + l) / 2; // ☆
if (arr[mid] = target) return mid;
if (target > arr[mid]) l = mid + 1;
else r = mid - 1;
return -1;
}四、排序
1.各种排序算法及时间复杂度
插入排序：对于一个带排序数组来说，其初始有序数组元素个数为1，然后从第二个元素，插入到有序数组中。对于每一次插入操作，从后往前遍历当前有序数组，如果当前元素大于要插入的元素，则后移一位；如果当前元素小于或等于要插入的元素，则将要插入的元素插入到当前元素的下一位中。
希尔排序：先将整个待排序记录分割成若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，在对全体记录进行一次直接插入排序。其子序列的构成不是简单的逐段分割，而是将每隔某个增量的记录组成一个子序列。希尔排序时间复杂度与增量序列的选取有关，其最后一个值必须为1.
归并排序：该算法采用分治法；对于包含m个元素的待排序序列，将其看成m个长度为1的子序列。然后两两合归并，得到n/2个长度为2或者1的有序子序列；然后再两两归并，直到得到1个长度为m的有序序列。
冒泡排序：对于包含n个元素的带排序数组，重复遍历数组，首先比较第一个和第二个元素，若为逆序，则交换元素位置；然后比较第二个和第三个元素，重复上述过程。每次遍历会把当前前n-i个元素中的最大的元素移到n-i位置。遍历n次，完成排序。
快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
选择排序：每次循环，选择当前无序数组中最小的那个元素，然后将其与无序数组的第一个元素交换位置，从而使有序数组元素加1，无序数组元素减1.初始时无序数组为空。
堆排序：堆排序是一种选择排序，利用堆这种数据结构来完成选择。其算法思想是将带排序数据构造一个最大堆（升序）/最小堆（降序），然后将堆顶元素与待排序数组的最后一个元素交换位置，此时末尾元素就是最大/最小的值。然后将剩余n-1个元素重新构造成最大堆/最小堆。
2.稳定排序哪几种？
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序
3.请问求第k大的数的方法以及各自的复杂度是怎样的？
解法1： 我们可以对这个乱序数组按照从大到小先行排序，然后取出前k大，总的时间复杂度为O(n*logn + k)。
解法2： 利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况： 1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数； 2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)
解法3：维护一个k大小的最小堆，对于数组中的每一个元素判断与堆顶的大小，若堆顶较大，则不管，否则，弹出堆顶，将当前值插入到堆中。时间复杂度O(n * logk)
解法4：利用hash保存数组中元素Si出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n)
4.冒泡排序(手写代码) O(n^2)
public static void BubbleSort1(int [] arr){
int temp;//临时变量
boolean flag;//是否交换的标志
for(int i=0; i<arr.length-1; i++){ //表示趟数，一共 arr.length-1 次
// 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换
flag = false;
for(int j=arr.length-1; j>i; j--){ //选出该趟排序的最大值往后移动
if(arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = true; //只要有发生了交换，flag就置为true
// 判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
if(!flag) break;
}5.选择排序 O(n^2)
public static void select_sort(int array[],int lenth){
for(int i=0;i<lenth-1;i++){
int minIndex = i;
for(int j=i+1;j<lenth;j++){
if(array[j]<array[minIndex]){
minIndex = j;
if(minIndex != i){
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}6.快速排序（手写代码）O(Nlog2N)
public static void quickSort(int a[],int l,int r){
if(l>=r)
return;
int i = l; int j = r; int key = a[l];//选择第一个数为key
while(i<j){
while(i<j && a[j]>=key)//从右向左找第一个小于key的值
if(i<j){
a[i] = a[j];
while(i<j && a[i]<key)//从左向右找第一个大于key的值
if(i<j){
a[j] = a[i];
//i == j
a[i] = key;
quickSort(a, l, i-1);//递归调用
quickSort(a, i+1, r);//递归调用
}7.归并排序（手写代码）O(Nlog2N)
public static void merge_sort(int a[],int first,int last,int temp[]){
if(first < last){
int middle = (first + last)/2;
merge_sort(a,first,middle,temp);//左半部分排好序
merge_sort(a,middle+1,last,temp);//右半部分排好序
mergeArray(a,first,middle,last,temp); //合并左右部分
//合并 ：将两个序列a[first-middle],a[middle+1-end]合并
public static void mergeArray(int a[],int first,int middle,int end,int temp[]){
int i = first;
int m = middle;
int j = middle+1;
int n = end;
int k = 0;
while(i<=m && j<=n){
if(a[i] <= a[j]){
temp[k] = a[i];
}else{
temp[k] = a[j];
while(i<=m){
temp[k] = a[i];
while(j<=n){
temp[k] = a[j];
for(int ii=0;ii<k;ii++){
a[first + ii] = temp[ii];
}8.堆排序O(Nlog2N)
//构建最小堆
public static void MakeMinHeap(int a[], int n){
for(int i=(n-1)/2 ; i>=0 ; i--){
MinHeapFixdown(a,i,n);
//从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
public static void MinHeapFixdown(int a[],int i,int n){
int j = 2*i+1; //子节点
int temp = 0;
while(j<n){
//在左右子节点中寻找最小的
if(j+1<n && a[j+1]<a[j]){
if(a[i] <= a[j])
break;
//较大节点下移
temp = a[i];
a[i] = a[j];
a[j] = temp;
i = j;
j = 2*i+1;
public static void MinHeap_Sort(int a[],int n){
int temp = 0;
MakeMinHeap(a,n);
for(int i=n-1;i>0;i--){
temp = a[0];
a[0] = a[i];
a[i] = temp;
MinHeapFixdown(a,0,i);
}五、哈希
1.hash表的实现
（1）构造哈希
主要包括直接地址法、平方取中法、除留余数法等。
（2）处理哈希冲突
最常用的处理冲突的方法有开放定址法、再哈希法、链地址法、建立公共溢出区等方法。
开放定址法: 当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
再哈希法：当发生哈希冲突时使用另一个哈希函数计算地址值，直到冲突不再发生。这种方法不易产生聚集，但是增加计算时间，同时需要准备许多哈希函数。
链地址法：将所有哈希值相同的Key通过链表存储。key按顺序插入到链表中
建立公共溢出区：采用一个溢出表存储产生冲突的关键字。如果公共溢出区还产生冲突，再采用处理冲突方法处理。2.哈希表的桶个数为什么是质数，合数有何不妥？
哈希表的桶个数使用质数，可以最大程度减少冲突概率，使哈希后的数据分布的更加均匀。如果使用合数，可能会造成很多数据分布会集中在某些点上，从而影响哈希表效率。
六、动态规划
动态规划，利用问题的最优子结构性质，以自底向上的方式递归的从子问题的最优解逐步构造出整个问题的最优解。 对于重叠子问题，一个典型的问题是求斐波那契数列的第N项，如果用递归的方法做会存在大量的重叠子问题，而利用动态规划的方法就是解决了重叠子问题。 建立表格不断填表，相当于备忘录，也就是解决重叠子问题的技巧，典型的问题是斐波那契数列、背包问题等，许多动态规划问题都是定义数组，进行递推过程填充数组（模拟备忘录）。 马尔科夫性，是随机过程中某事件的发生只取决于它的上一事件、是“无记忆”过程。而动态规划具有“记忆性”。
1.最长公共子序列（手写代码）
最长公共子序列问题：
给定两个字符串A、B，求A与B的最长公共子序列（子序列不要求是连续的）
举例：
字符串A： abcdef
字符串B：baaecd
输出：acd
import java.util.Scanner;
public class 最长公共子序列 {
public static void main(String args[])
Scanner input=new Scanner(System.in);
String str1=input.next();
String str2=input.next();
int m=son(str1,str2);//传两个字符串
System.out.println(m);
public static int son(String str1,String str2)
//因为要形成上图的表格，所以给两个字符串头多添了一个字符
//使第一行和第一列都变为0
String s1="2"+str1;
String s2="1"+str2;
int [][]check=new int[str1.length()+1][str2.length()+1];
for(int i=0;i<s1.length();i++)
for(int j=0;j<s2.length();j++)
if(i==0||j==0)//定义第一个格子为0
check[i][j]=0;
else if(s1.charAt(i)==s2.charAt(j))
check[i][j]=(check[i-1][j-1]+1);
{ //取上一个数和左边的数中大的数
if(check[i-1][j]>check[i][j-1])
check[i][j]=check[i-1][j];
check[i][j]=check[i][j-1];
//返回数组的最后一位
return check[s1.length()-1][s2.length()-1];
}2.最长公共子串
对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。
给定两个字符串A和B，同时给定两串的长度n和m。
测试样例： "1AB2345CD",9,"12345EF",7
返回：4
string getLCS(string str1, string str2) {
vector<vector<int> > record(str1.length(), vector<int>(str2.length()));
int maxLen = 0, maxEnd = 0;
for(int i=0; i<static_cast<int>(str1.length()); ++i)
for (int j = 0; j < static_cast<int>(str2.length()); ++j) {
if (str1[i] == str2[j]) {
if (i == 0 || j == 0) {
record[i][j] = 1;
else {
record[i][j] = record[i - 1][j - 1] + 1;
else {
record[i][j] = 0;
if (record[i][j] > maxLen) {
maxLen = record[i][j];
maxEnd = i; //若记录i,则最后获取LCS时是取str1的子串
return str1.substr(maxEnd - maxLen + 1, maxLen);3.求一个字符串最长回文子串(手写代码)
子串：小于等于原字符串长度由原字符串中任意个连续字符组成的子序列
回文：关于中间字符对称的文法，即“aba”(单核)、“cabbac”(双核)等
最长回文子串：1.寻找回文子串；2.该子串是回文子串中长度最长的。
import java.util.Scanner;
* 求最长回文子串
* @author autumn_leaf
* @Date 2019/03/23
public class PalindSubstring {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
String s = sc.nextLine();
//将一串字符转化为字符数组
char[] str = s.toCharArray();
int len = str.length;
int[][] dp = new int[len+10][len+10];
//dp数组初始化
for(int i=0; i<len; i++) {
dp[i][i] = 1;
//dp中相邻元素
for(int i=0; i<len-1; i++) {
if(str[i] == str[i+1]) {
dp[i][i+1] = 2;
}else {
dp[i][i+1] = 1;
/**dp中至少相隔一个元素*/
/**k代表相隔的区间长度*/
for(int k=2; k<len; k++) {
//i代表区间起始位置
for(int i=0; i+k<len; i++) {
//j代表区间末尾位置
int j = i+k;
if(str[i] == str[j]) {
dp[i][j] = dp[i+1][j-1] + 2;
}else {
dp[i][j] =Math.max(dp[i+1][j], dp[i][j-1]);
System.out.println(dp[0][len-1]);
}Manacher算法用一个辅助数组Len[i]表示以字符T[i]为中心的最长回文字串的最右字符到T[i]的长度，比如以T[i]为中心的最长回文字串是T[l,r],那么Len[i]=r-i+1。
对于上面的例子，可以得出Len[i]数组为:
Len数组有一个性质，那就是Len[i]-1就是该回文子串在原字符串S中的长度，至于证明，首先在转换得到的字符串T中，所有的回文字串的长度都为奇数，那么对于以T[i]为中心的最长回文字串，其长度就为2*Len[i]-1,经过观察可知，T中所有的回文子串，其中分隔符的数量一定比其他字符的数量多1，也就是有Len[i]个分隔符，剩下Len[i]-1个字符来自原字符串，所以该回文串在原字符串中的长度就为Len[i]-1。
有了这个性质，那么原问题就转化为求所有的Len[i]。下面介绍如何在线性时间复杂度内求出所有的Len。
4.硬币表示
有数量不限的硬币，币值为25分、10分、5分和1分，请编写代码计算n分有几种表示法。
给定一个int n，请返回n分有几种表示法。保证n小于等于100000，为了防止溢出，请将答案Mod 1000000007。
测试样例： 6
返回：2
int fun(int n, int coin)
int nextcoin=0;
switch(coin)
case 25:
nextcoin=10; break;
case 10:
nextcoin=5; break;
case 5:
nextcoin=1; break;
case 1:
return 1;
int res=0;
for(int i=0;i*coin<=n;i++)
res+=fun(n-i*coin, nextcoin)%1000000007;
return res%1000000007;//%1000000007
}5.字符混编
A、B和C。如果C包含且仅包含来自A和B的所有字符，而且在C中属于A的字符之间保持原来在A中的顺序，属于B的字符之间保持原来在B中的顺序，那么称C是A和B的混编。实现一个函数，判断C是否是A和B的混编。
给定三个字符串A,B和C，及他们的长度。请返回一个bool值，代表C是否是A和B的混编。保证三个串的长度均小于等于100。
测试样例： "ABC",3,"12C",3,"A12BCC",6
返回：true
import java.util.*;
public class Mixture {
public boolean chkMixture(String A, int n, String B, int m, String C, int v) {
// 边界情况处理
if (m + n != v)
return false;
// 默认初始化为false
boolean[][] dp = new boolean[101][101];
dp[0][0] = true;
// 初始化第0行
for (int i = 1; i <= m; ++i) {
if (B.charAt(i - 1) == C.charAt(i - 1))
dp[0][i] = true;
break;
// 初始化第0列
for (int i = 1; i <= n; ++i) {
if (A.charAt(i - 1) == C.charAt(i - 1))
dp[i][0] = true;
break;
* 状态转移方程
* dp[i][j] =
* case 1: dp[i][j-1] == true && B[j-1] == C[i+j-1]
* case 2: dp[i-1][j] == true && A[i-1] == C[i+j-1]
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (!dp[i][j]) {
// dp[i-1][j] = true && A[i-1] == C[i+j-1]
if (dp[i - 1][j] && A.charAt(i - 1) == C.charAt(i + j - 1))
dp[i][j] = true;
// dp[i][j-1] == true && B[j-1] == C[i+j-1]
if (dp[i][j - 1] && B.charAt(j - 1) == C.charAt(i + j - 1))
dp[i][j] = true;
return dp[n][m];
}七、链表
1.如何合并两个有序链表(手写代码)
/**
*Definition for singly-linked list
class ListNode{
int val;
ListNode next;
ListNode(int x){
val = x;
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = null;
if (l1.val <= l2.val){
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
return head;
}2.反转链表（手写代码）
递归
public Node reverse(Node head) {
if (head == null || head.next == null)
return head;
Node temp = head.next;
Node newHead = reverse(head.next);
temp.next = head;
head.next = null;
return newHead;
}遍历
public static Node reverseList(Node node) {
Node pre = null;
Node next = null;
while (node != null) {
next = node.next;
node.next = pre;
pre = node;
node = next;
return pre;
}3.判断一个链表是否为回文链表，说出你的思路并手写代码
- 简单粗暴的做法就是：将链表反转生成一个新的链表，然后依次比较两个链表的每一个元素，如果均相等则是回文结构。这里我们可以不用反转链表，而是借助一个栈，将链表的数据全部压入栈中，然后从栈顶依次取出元素和原链表头部取出元素比较。栈的特点是先进后出，正好可以构成一个反转的链表。
- 根据回文结构的特点，链表前半部分和后半部分反转之后顺序是一致的，所以可以考虑不用反转整个链表，而是后半部分。要找到后半部分，需要两个指针，他们都从头部开始遍历，一个指针遍历的速度是另一个指针的两倍，这样，当快的指针遍历完成的时候，慢的指针位置就正好是中间位置。再把中间位置到链表尾部的所有节点放入一个堆栈，构成一个反转的链表，后面的判断就回到第一个办法的判断了。
4.如何判断两个单向链表是否相交
判断两个链表是否相交
1）方法1：
链表相交之后，后面的部分节点全部共用，可以用2个指针分别从这两个链表头部走到尾部，最后判断尾部指针的地址信息是否一样，若一样则代表链表相交！
2）方法2：
可以把其中一个链表的所有节点地址信息存到数组中，然后把另一个链表的每一个节点地址信息遍历数组，若相等，则跳出循环，说明链表相交。进一步优化则是进行hash排序，建立hash表。
八、高级算法
1.单向加密
1）定义
单向加密又称为不可逆加密算法，其密钥是由加密散列函数生成的。
2）例子
-
MD5（Message Digest Algorithm 5）：是RSA数据安全公司开发的一种单向散列算法，非可逆，相同的明文产生相同的密文；
-
SHA（Secure Hash Algorithm）：可以对任意长度的数据运算生成一个160位的数值。其变种由SHA192，SHA256，SHA384等；
3）算法特征：
输入一样，输出必然相同；
雪崩效应，输入的微小改变，将会引起结果的巨大变化；
定长输出，无论原始数据多大，结果大小都是相同的；
不可逆，无法根据特征码还原原来的数据；
2.对称加密
采用单钥密码系统的加密方法，同一个密钥可以同时用作信息的加密和解密，这种加密方法称为对称加密，也称为单密钥加密。
特点：
1、加密方和解密方使用同一个密钥；
2、加密解密的速度比较快，适合数据比较长时的使用；
3、密钥传输的过程不安全，且容易被破解，密钥管理也比较麻烦；
优点：对称加密算法的优点是算法公开、计算量小、加密速度快、加密效率高。
缺点：对称加密算法的缺点是在数据传送前，发送方和接收方必须商定好秘钥，然后使双方都能保存好秘钥。其次如果一方的秘钥被泄露，那么加密信息也就不安全了。另外，每对用户每次使用对称加密算法时，都需要使用其他人不知道的唯一秘钥，这会使得收、发双方所拥有的钥匙数量巨大，密钥管理成为双方的负担。
3.非对称加密
非对称密钥加密也称为公钥加密，由一对公钥和私钥组成。公钥是从私钥提取出来的。可以用公钥加密，再用私钥解密，这种情形一般用于公钥加密，当然也可以用私钥加密，用公钥解密。常用于数字签名，因此非对称加密的主要功能就是加密和数字签名。
特征：
1）秘钥对，公钥(public key)和私钥(secret key)
2）主要功能：加密和签名
发送方用对方的公钥加密，可以保证数据的机密性（公钥加密）。
发送方用自己的私钥加密，可以实现身份验证（数字签名）。
3）公钥加密算法很少用来加密数据，速度太慢，通常用来实现身份验证。
常用的非对称加密算法
RSA：由 RSA公司发明，是一个支持变长密钥的公共密钥算法，需要加密的文件块的长度也是可变的；既可以实现加密，又可以实现签名。
DSA（Digital Signature Algorithm）：数字签名算法，是一种标准的 DSS（数字签名标准）。
ECC（Elliptic Curves Cryptography）：椭圆曲线密码编码。
4.LRU缓存
LRU(最近最少使用)算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高
实现：使用一个链表保存缓存数据，将新数据插入到头部，每当缓存命中时，则将命中的数据移动到链表头部，当链表满的时候，将链表尾部的数据丢弃。
九、字符串处理
1.给你一个字符串，找出第一个不重复的字符，如“abbbabcd”，则第一个不重复就是c
使用哈希的思想，建立256个bool数组array，初始都为false,从头开始扫描字符串，扫到一个，将以其ascii码为下标的元素置true。例如扫描到A的时候，执行：array['A']=true。第二边扫描，扫到一个字母就以其ascii码为下标，去array数组中看其值，如果是true,返回改字母，如果是false，继续扫描下一个字母。
十、贪心算法
1.安置路灯
小Q正在给一条长度为n的道路设计路灯安置方案。
为了让问题更简单,小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示。
小Q现在要在道路上设置一些路灯, 对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。
小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯。
输入描述: 输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数 接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。 第二行一个字符串s表示道路的构造,只包含'.'和'X'。
输出描述: 对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = scanner.nextLine();
int caseNumber = Integer.parseInt(string);
while (scanner.hasNext()) {
String nString = scanner.nextLine();
int n = Integer.parseInt(nString);
String road = scanner.nextLine();
int result = 0;
for (int i = 0; i < n; i++) {
if (road.substring(i,i+1).equals(".")){
result++;
i+=2;
System.out.println(result);
}十一、实战题目
1.九宫格解锁方案（Vivo）
1、问题定义
问题很简单：安卓的手势解锁是3*3的点阵，在这个点阵上的解锁手势一共有多少种情况？这里一个合格的解锁手势轨迹必须满足以下两个条件：
- 至少连接点阵中的四个点。
- 手势的轨迹不能跨过一个还没有经过的节点。
- 不允许重复经过某个定点两次。
2、问题转化
为了方便，这里将点阵中的每个点用一个数字代替，1到9九个数字分别代表点阵中的一个点。这样，一个解锁手势可以对应到一个由1到9数字组成的字符串(该字符串中没有重复)。
去掉第二个限制条件，一种解锁手势正好对应一种1到9的排列。连接四个点的解锁手势的所有情况就是9选4的全排列，连接5个点的就是9选5的全排列，以此类推。
计算全排列的比较容易，接下来要解决的就是如何剔除那些不符合限制条件(手势的轨迹不能跨过一个还没有经过的节点)的手势。在3*3的点阵中，不符合条件的情况(也就是两个点的连接过程中跨过点的情况)比较有限，这里我们将其全部列出。
from itertools import chain, permutations
impossible = {'13': '2', '46': '5', '79': '8', '17': '4', '28': '5', '39': '6', '19': '5', '37': '5', '31': '2', '64': '5', '97': '8', '71': '4', '82': '5', '93': '6', '91': '5', '73': '5'}
def counts_n(n):
iterlst = permutations('123456789', n)
count = 0
for i in iterlst:
stri = ''.join(i)
for k, v in impossible.items():
if k in stri and v not in stri[:stri.find(k)]:
break
else:
count += 1
return count
sum = 0
print("len num sum")
for i in range(4,10):
temp = counts_n(i)
sum = sum + temp
print(str(i)+" "+str(temp)+" "+str(sum))
len num sum
4 1624 1624
5 7152 8776
6 26016 34792
7 72912 107704
8 140704 248408
9 140704 3891122.爬楼梯算法
第一种题目（递归实现）
假设一个楼梯有 N 阶台阶，人每次最多可以跨 M 阶，求总共的爬楼梯方案数。
例如楼梯总共有3个台阶，人每次最多跨2个台阶，也就是说人每次可以走1个，也可以走2个，但最多不会超过2个，那么楼梯总共有这么几种走法：
private static int calculateCount(int ladder, int maxJump) {
int jump = 0;
if (ladder == 0) {
return 1;
if (ladder >= maxJump) {
// 剩下的楼梯大于最大可跳跃数
for (int i = 1; i <= maxJump; i++) {
jump += calculateCount(ladder - i, maxJump);
} else {
// 剩下的楼梯不足最大可跳跃数
jump = calculateCount(ladder, ladder);
return jump;
}这题有一道变体（非递归方式实现）：
假设一个楼梯有 N 阶台阶，人每次最多可以跨 2 阶，求总共的爬楼梯方案数，要求不用递归实现随着楼梯数n的增加，爬法总数呈现斐波那契数列规律增加，即f（n） = f（n-1） + f（n-2）
/**
* @param ladder 台阶数量
* @return 总的爬法
private static int count(int ladder) {
if (ladder == 1 || ladder == 2) {
return ladder;
int n1 = 1;
int n2 = 2;
for (int i = 3; i <= ladder; i++) {
int tmp = n2;
n2 = n1 + n2;
n1 = tmp;
return n2;
}3.两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
1.解法一：使用for循环遍历
2.解法二：使用HashMap的性质
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++){
if (map.containsKey(target - nums[i])){
return new int[]{map.get(target - nums[i]), i};
}else{
map.put(nums[i], i);
return null;
}三数之和
/**
* 时间复杂度：n2
* 空间复杂度：1
* 代码执行过程：
* 总结：
* ***********************************/
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return 0;
Arrays.sort(nums);
int comp = Integer.MAX_VALUE;
int result = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
// 如果和之前那个数据相同，则会是重复事件
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
int leftIndex = i + 1;
int rightIndex = nums.length - 1;
// 滑动列表
while (leftIndex < rightIndex) {
int tmp = nums[leftIndex] + nums[rightIndex] + nums[i];
if (comp > Math.abs(tmp - target)) {
comp = Math.abs(tmp - target);
result = tmp;
if (tmp > target) {
rightIndex--;
} else if (tmp < target) {
leftIndex++;
} else {
// 差值为0，最爽了，直接返回
return tmp;
return result;
}4.最大回撤
题目形式：有一个数组，求其中两个数x,y，满足x的索引小于y的索引，使得 x-y 最大。例如 arr = [3,7,2,6,4,1,9,8,5]， 最大回撤是6，对应的x=7,y=1。
解法一
算法实现有很多，简单粗暴的方法比如把每一天的值和其他天作差值计算，找到差值最大的那一天，但这个方法并不好。从时间复杂度上看是O(n!)，差不多算是最差的了。
解法二
/**
* 计算最大回撤
* @author qcy
class FundTools {
* 由净值序列x，直接计算最大回撤
* @param x
* 累计份额净值序列
* @return 最大回撤
public double calc_max_dd(double[] x) {
double max_unit_value = x[0];
double max_dd = 0;
double dd = 0;
for (int i = 1; i < x.length; i++) {
max_unit_value = Math.max(x[i], max_unit_value);
dd = x[i] / max_unit_value - 1;
max_dd = Math.min(dd, max_dd);
return max_dd;
* 根据每日收盘后份额净值和截止前一日的最大回撤、最高水位，计算今日的最大回撤
* @param max_dd
* 截止到i-1日的最大回撤
* @param max_unit_value
* 截止到i-1日的最高累计份额净值
* @param today_unit_value
* i日的累计份额净值
* @return 第i日的最大回撤
public double calc_max_dd(double max_dd, double max_unit_value,
double today_unit_value) {
max_unit_value = Math.max(max_unit_value, today_unit_value);
double dd = today_unit_value / max_unit_value - 1;
return Math.min(dd, max_dd);
}5.合并两个有序数组
题目形式：
给定两个按升序排列的有序数组，将它们合并成一个新的有序数组。例如：a = [1,2,6,8], b = [2,4,7,10]，输出为 arr = [1,2,2,4,6,7,8,10]
解法一：开个新的数组，填充上去
解法二：因原数组都是有序数组，只需要从两个数组的最后一个元素开始对比，寻找最大值赋值给最终数组。
如果数组二元素耗尽，则得到最终数组。 如果数组一元素耗尽，则需要将原数组二剩余元素赋值给最终数组。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
if(m ==0 ) {
System.arraycopy(nums2,0,nums1,0, n);
int i1 = m -1;
int i2 = n -1;
while(i2>=0){
if(i1 < 0){
System.arraycopy(nums2,0,nums1,0,i2+1);
break;
if(nums1[i1] >= nums2[i2]) {
nums1[i1 + i2 +1]=nums1[i1--];
}else{
nums1[i1 + i2 +1]=nums2[i2--];
}6.最大连续子数组和
题目形式：
给定一个数组，求其最大连续子数组的和。例如：arr = [1,5,-10,2,5,-3,2,6,-3,1]. 输出为：12。对应的连续子数组为 [2,5,-3,2,6]。
public static int maxSunArray(int[] array) {
if (array.length==0 || array==null) {
return 0;
int Sum = 0;
int max = 0;
for (int i = 0; i < array.length; i++) {
if(Sum<=0){ //如果当前连续n项的和小于等于0,则没必要与后面的元素相加
Sum = array[i]; //Sum重新赋值
}else{
Sum += array[i]; //如果Sum的值大于0,则继续与后面的元素相加,
if(Sum>max){ //每次改变Sum的值都有与max进行比较
max = Sum; //如果Sum的值大于max,则将Sum的值赋值给max
return max;
}动态规划
//解法二：使用动态规划:
//F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变
//F（i）=max（F（i-1）+array[i] ， array[i]）
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int res = array[0]; //记录当前所有子数组的和的最大值
int max = array[0]; //包含array[i]的连续数组最大值
for (int i = 1; i < array.length; i++) {
max=Math.max(max+array[i], array[i]);
res=Math.max(max, res);
return res;
}7.最长不重复子串
题目形式：
给定一个字符串，找出没有重复字符的最长的子串。例如输入“abcbefgf”，答案是 “cbefg”。
我的方法：（时间复杂度较大）
public static int lengthOfLongestSubstring(String s) {
int start, end;
String count = "";
String str = "";
for(start=0; start<s.length(); start++){
for(end=start+1; end<=s.length(); end++){
str = s.substring(start, end);
if(end == s.length()){
if(count.length() < str.length()){//对比长度
count = str;
break;
}else{
if(str.contains(s.substring(end, end+1))){//当有重复时候，处理，跳出循环让start++
if(count.length() < str.length()){//对比长度
count = str;
break;
return count.length();
}2、滑动窗口思想：如果确定子串s[i,j]（假设表示字符串的第i个字符到第j-1个字符表示的子串），那么只需要比较s[j]是否与子串s[i,j]重复即可
若重复：记录此时滑动窗口大小，并与最大滑动窗口比较，赋值。然后滑动窗口大小重定义为1，头位置不变，并右移一个单位。
若不重复：滑动窗口头不变，结尾+1，整个窗口加大1个单位。继续比较下一个。
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
// try to extend the range [i, j]
if (!set.contains(s.charAt(j))){
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
else {
set.remove(s.charAt(i++));
return ans;
}3、使用HashMap(这是一道动态规划+哈希查找的综合应用题)
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
return ans;
}8.全排列(这是一道动态规划+排列组合的综合应用题)
题目形式：
给定一个数组，找出其所有可能的排列。例如: arr = [1,1,3]，输出为 [[1,1,3],[1,3,1],[3,1,1]]。
（1）确定第一位的字符 数组arr从start到end的所有记录都可以出现在第一个位置，所以直接一个for循环，考虑了这所有的情况。在for循环中，swap方法就是交换i和start位置的数，保证当前i指向的记录出现在第一个位置，也就是start指向的位置
（2）剩下的记录继续做全排列 这个就是一个递归函数的调用，只需要修改起始位置，也就是start+1，因为start的位置已经放了记录，所以只需要继续做从start+1到end的全排列即可 2
public class Main {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4 };
fullSort(arr, 0, arr.length - 1);
public static void fullSort(int[] arr, int start, int end) {
// 递归终止条件
if (start == end) {
for (int i : arr) {
System.out.print(i);
System.out.println();
return;
for (int i = start; i <= end; i++) {
swap(arr, i, start);
fullSort(arr, start + 1, end);
swap(arr, i, start);
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}拓展应用：图书排列
题目描述：将编号为1~10的10本书排放在书架上，要求编号相邻的书不能放在相邻的位置。 请计算一共有多少种不同的排列方案。
注意，需要提交的是一个整数，不要填写任何多余的内容。
解题思路：这个题目有很多解法，这里只说明用全排列怎么解决，先求出全排列，也就是所有的排列方案，然后去掉不满足条件的情况，也就是编号相邻的书不能相邻这一条件。
完整代码如下：
public class BookSort {
public static void main(String[] args) {
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
fullSort(arr, 0, arr.length - 1);
System.out.println(res);
static int res = 0;
static void fullSort(int[] arr, int start, int end) {
// 递归终止条件
if (start == end) {
// 求出了全排列的一种情况，然后检查是否满足条件
if (check(arr))
res++;
return;
for (int i = start; i <= end; i++) {
swap(arr, start, i);
fullSort(arr, start + 1, end);
swap(arr, start, i);
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
static boolean check(int[] arr) {
for (int i = 1; i < arr.length; i++) {
if (Math.abs(arr[i] - arr[i - 1]) == 1)
return false;
return true;
}9.穷举法
平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。 如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。 请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。
import java.util.*;
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(bf.readLine());
int [] x1 = new int[num];
int [] y1 = new int[num];
int [] x2 = new int[num];
int [] y2 = new int[num];
if(num < 2 || num > 50)
return;
else{
String [] str = bf.readLine().split(" +");
for(int i = 0;i<num;i++){
x1[i] = Integer.parseInt(str[i]);
str = bf.readLine().split(" +");
for(int i = 0;i<num;i++){
y1[i] = Integer.parseInt(str[i]);
str = bf.readLine().split(" +");
for(int i = 0;i<num;i++){
x2[i] = Integer.parseInt(str[i]);
str = bf.readLine().split(" +");
for(int i = 0;i<num;i++){
y2[i] = Integer.parseInt(str[i]);
System.out.println(solution(num,x1,y1,x2,y2));
public static int solution(int num,int[]x1,int[]y1,int[]x2,int[]y2){
int temp=0,max=0;
for(int x:x1)
for(int y:y1){
for(int i = 0; i<num ; i++){
if(x>=x1[i] && x<x2[i]&& y>=y1[i]&&y<y2[i])
temp++;
if(max < temp)
max = temp;
temp = 0;
return max;
}题目描述
牛牛准备参加学校组织的春游, 出发前牛牛准备往背包里装入一些零食, 牛牛的背包容量为w。 牛牛家里一共有n袋零食, 第i袋零食体积为v[i]。 牛牛想知道在总体积不超过背包容量的情况下,他一共有多少种零食放法(总体积为0也算一种放法)。
输入描述:
输入包括两行 第一行为两个正整数n和w(1 <= n <= 30, 1 <= w <= 2 * 10^9),表示零食的数量和背包的容量。 第二行n个正整数v i ,表示每袋零食的体积。
输出描述: 输出一个正整数, 表示牛牛一共有多少种零食放法。
注意：总数sum要表示成long型，不然会越界
import java.util.Scanner;
public class Main {
private static int result = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String strTemp = scanner.nextLine();
if (strTemp.isEmpty()){
return;
String[] str = strTemp.split(" ");
int n = Integer.parseInt(str[0]);
int m =Integer.parseInt(str[1]);
String [] size = scanner.nextLine().split(" ");
int [] sizeArray = new int[size.length];
long sum = 0;
for (int i = 0; i < size.length; i++) {
sizeArray[i] = Integer.parseInt(size[i]);
sum += sizeArray[i];
if (sum<=m){
System.out.println((int)Math.pow(2,n));
}else {
sum = 0;
result +=1;
dfs(sizeArray, sum, m, 0);
System.out.println(result);
private static void dfs(int[] arraySize, long sum, int m, int position){
if (position<arraySize.length){
if (sum>=m){
return;
dfs(arraySize, sum, m, position+1);
if (sum+arraySize[position]<m){
result +=1;
sum += arraySize[position];
dfs(arraySize, sum,m,position+1);
return;
}题目描述
小易有一些立方体，每个立方体的边长为1，他用这些立方体搭了一些塔。 现在小易定义：这些塔的不稳定值为它们之中最高的塔与最低的塔的高度差。 小易想让这些塔尽量稳定，所以他进行了如下操作：每次从某座塔上取下一块立方体，并把它放到另一座塔上。
注意，小易不会把立方体放到它原本的那座塔上，因为他认为这样毫无意义。 现在小易想要知道，他进行了不超过k次操作之后，不稳定值最小是多少。
输入描述:
第一行两个数n,k (1 <= n <= 100, 0 <= k <= 1000)表示塔的数量以及最多操作的次数。
第二行n个数，ai(1 <= ai <= 104)表示第i座塔的初始高度。输出描述:
第一行两个数s, m，表示最小的不稳定值和操作次数(m <= k)
接下来m行，每行两个数x,y表示从第x座塔上取下一块立方体放到第y座塔上。示例1
输入
3 2
5 8 5输出
0 2
2 3每次都把数组进行排序，然后最大值-1，最小值+1，用ArrayList记录这一操作的痕迹。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String strTemp = scanner.nextLine();
String[] str = strTemp.split(" ");
int n = Integer.parseInt(str[0]);
int k =Integer.parseInt(str[1]);
String [] size = scanner.nextLine().split(" ");
int[] sizeArray = new int[n];
for (int i = 0; i < size.length; i++) {
sizeArray[i] = Integer.parseInt(size[i]);
int count = 0;
ArrayList<Integer> list1 = new ArrayList<>();
ArrayList<Integer> list2 = new ArrayList<>();
for (int i = 0; i < k; i++) {
int max = findMaxPosition(sizeArray);
int min = findMinPosition(sizeArray);
if (sizeArray[max]-sizeArray[min]<=1){
break;
count++;
sizeArray[max]--;
sizeArray[min]++;
list1.add(max+1);
list2.add(min+1);
System.out.println(sizeArray[findMaxPosition(sizeArray)] - sizeArray[findMinPosition(sizeArray)] +" "+count);
for (int i = 0; i < list1.size(); i++) {
System.out.println(list1.get(i) + " " + list2.get(i));
public static int findMaxPosition(int[] arraySize){
int[] temp = Arrays.copyOfRange(arraySize, 0,arraySize.length);
Arrays.sort(temp);
int max = temp[temp.length-1];
int position = 0;
for (int i = 0; i < arraySize.length; i++) {
if (max == arraySize[i]){
position = i;
break;
return position;
public static int findMinPosition(int[] arraySize){
int[] temp = Arrays.copyOfRange(arraySize, 0,arraySize.length);
Arrays.sort(temp);
int min = temp[0];
int position = 0;
for (int i = 0; i < arraySize.length; i++) {
if (min == arraySize[i]){
position = i;
break;
return position;
}10.数学
今天上课，老师教了小易怎么计算加法和乘法，乘法的优先级大于加法，但是如果一个运算加了括号，那么它的优先级是最高的。例如：
1+2*3=7
1*(2+3)=5
1*2*3=6
(1+2)*3=9现在小易希望你帮他计算给定3个数a，b，c，在它们中间添加"+"， "*"， "("， ")"符号，能够获得的最大值。
输入描述: 一行三个数a，b，c (1 <= a, b, c <= 10)
输出描述: 能够获得的最大值
规律： 最小的数小于等于1时，那么最大的结果便是a+b的和再乘以c 若最小数大于1，则最大结果必然是三数的积
11.动态规划
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<>();
if (str != null && str.length() > 0) {
PermutationHelper(str.toCharArray(), 0, res);
Collections.sort(res);
return res;
private static void PermutationHelper(char[] cs, int i, ArrayList<String> list) {
if(i == cs.length - 1) { //解空间的一个叶节点
list.add(String.valueOf(cs)); //找到一个解
} else {
for(int j = i; j < cs.length; ++j) {
if(j == i || cs[j] != cs[i]) {
SwapUtil.swap(cs, i, j);
PermutationHelper(cs, i + 1, list);
SwapUtil.swap(cs, i, j); //复位
}12.不用动态规划简单些
给出2n(n≤100)个自然数(小于等于30000)。将这2n个自然数排成一列，游戏双方A和B从中取数，只允许从两端取数。A先取，然后双方轮流取数。取完时，谁取得数字总和最大为取胜方；若双方和相等，属B胜。试问A方是否有必胜策略？
输入
共2行，第1行一个整数n；第2行有2*n个自然数。
输出
只有1行，若A有必胜策略，则输出“YES”，否则输出“NO”。
样例输入
4 7 9 3 6 4 2 5 3
样例输出
YES
思路
因为第一手先走的人有，可以全奇数项或者全拿偶数项， 所以只需要判断一下奇数项的和和偶数项的和是不是相等就可以了。
13.拼多多笔试题
高程图
思路：使用机器人邹迷宫寻找递归的方法
import java.util.Scanner;
public class Mian1 {
private static int[][] array;
private static int N;
private static int M;
private static int first = 0;
private static int left = 1;
private static int right = 2;
private static int up = 3;
private static int down = 4;
public static void main(String[] args) {
Scanner scanner = new Scanner("5 5\n1 3 1 2 1\n2 1 3 1 1\n1 4 2 6 1\n1 3 1 3 1\n1 1 5 1 1\n");
while(scanner.hasNextLine()){
String [] strings = scanner.nextLine().split(" ");
N = Integer.parseInt(strings[0]);
M = Integer.parseInt(strings[1]);
array = new int[N][M];
int sumStart = 0;
for (int i = 0; i < N; i++) {
String [] str = scanner.nextLine().split(" ");
for (int j = 0; j < M; j++) {
array[i][j] = Integer.parseInt(str[j]);
sumStart += array[i][j];
for (int i = 1; i < N-1; i++) {
for (int j = 1; j < M-1; j++) {
array[i][j] = findMin(array, i, j,first);
int sumEnd = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
sumEnd += array[i][j];
System.out.println(sumEnd-sumStart);
public static int findMin(int[][] array, int X, int Y,int direction){
int nextX = X;
int nextY = Y;
if (nextX ==0 || nextX ==N-1 || nextY==0 || nextY==M-1){
return array[X][Y];
if (array[X][Y]>array[X][Y-1] && array[X][Y]>array[X][Y+1] && array[X][Y]>array[X-1][Y] && array[X][Y]>array[X+1][Y])
return array[X][Y];
int nextLeft;
int nextRight;
int nextUp;
int nextDown;
switch (direction){
case 0:
nextLeft = findMin(array,X,Y-1,right);
nextRight = findMin(array,X,Y+1, left);
nextUp = findMin(array,X-1,Y, down);
nextDown = findMin(array,X+1,Y, up);
return Math.max(Math.min(Math.min(nextRight,nextLeft), Math.min(nextDown, nextUp)),array[X][Y]);
case 1:
nextRight = findMin(array,X,Y+1, left);
nextUp = findMin(array,X-1,Y, down);
nextDown = findMin(array,X+1,Y, up);
return Math.max(Math.min(nextRight, Math.min(nextDown, nextUp)),array[X][Y]);
case 2:
nextLeft = findMin(array,X,Y-1,right);
nextUp = findMin(array,X-1,Y, down);
nextDown = findMin(array,X+1,Y, up);
return Math.max(Math.min(nextLeft, Math.min(nextDown, nextUp)),array[X][Y]);
case 3:
nextLeft = findMin(array,X,Y-1,right);
nextRight = findMin(array,X,Y+1, left);
nextDown = findMin(array,X+1,Y, up);
return Math.max(Math.min(Math.min(nextRight,nextLeft), nextDown),array[X][Y]);
case 4:
nextLeft = findMin(array,X,Y-1,right);
nextRight = findMin(array,X,Y+1, left);
nextUp = findMin(array,X-1,Y, up);
return Math.max(Math.min(Math.min(nextRight,nextLeft), nextUp),array[X][Y]);
return 0;
}14.利用一个数组实现两个栈
方法1：利用奇偶位，分别存储栈1和栈2的数据；
方法2：从中间开始将数组一分为二，左边为栈1，右边为栈2；
方法3：栈1从头开始增长，栈2从尾向头进行增长，相遇后，增容；
15.装满箱子
题目描述
有重量分别为3，5，7公斤的三种货物，和一个载重量为X公斤的箱子（不考虑体积等其它因素，只计算重量）需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）
输入描述:
输入箱子载重量X(1 <= X <= 10000)，一个整数。输出描述:
如果无法装满，输出 -1。
如果可以装满，输出使用货物的总个数。示例1
输入
4输出
-1说明:无法装满
import java.util.Scanner;
public class Main {
static int temp = 0;
public static void dfs(int count, int rest) {
if (rest < 0) {//如果-3，-5或者-7小于0了，说明凑不齐，赶紧溜了
return;
if (rest == 0) {
System.out.println(temp*15+count);
System.exit(0);
dfs(count + 1, rest - 7);
dfs(count + 1, rest - 5);
dfs(count + 1, rest - 3);
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
temp = n / 105;
dfs(0, n % 105);
System.out.println(-1);
}16.回文子串
回文子串的个数
链接：https://www.nowcoder.com/questionTerminal/003482c395bd41c68082f6adc545a600
来源：牛客网
public class Solution14_回文子串 {
* 方法一：中心扩散法
static int ans = 0;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String s = bf.readLine();
for (int i = 0; i < s.length(); i++) {
//考虑两种情况：aba 和 abba
centerSpread(s, i, i);
centerSpread(s, i, i + 1);
System.out.println(ans);
//判断回文串的中心扩散法
private static void centerSpread(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
ans++;
//方法二：动态规划
private static int dp(String s) {
int n = s.length(), ans = 0;
boolean[][] dp = new boolean[n][n];
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i <= 2 || dp[i + 1][j - 1]);
if (dp[i][j]) ans++;
return ans;
}最长回文子串
链接：https://www.nowcoder.com/questionTerminal/003482c395bd41c68082f6adc545a600
来源：牛客网
//1.动态规划
public static String longestPalindrome(String s) {
int n = s.length();
if (n < 2) return s;
int maxLen = 1;
String res = s.substring(0, 1);
boolean[][] dp = new boolean[n][n];
//左边界一定小于右边界，因此从右边界开始
for (int r = 1; r < n; r++) { //表示右边界
for (int l = 0; l < r; l++) { //表示左边界
// 区间应该慢慢放大
// 状态转移方程：如果头尾字符相等并且中间也是回文
// 在头尾字符相等的前提下，如果收缩以后不构成区间（最多只有 1 个元素），直接返回 True 即可
// 否则要继续看收缩以后的区间的回文性
if (s.charAt(l) == s.charAt(r) && ((r - l) <= 2 || dp[l + 1][r - 1])) {
dp[l][r] = true;
if (r - l + 1 > maxLen) {
maxLen = r - l + 1;
res = s.substring(l, r + 1);
return res;
}最长不连续回文子串
链接：https://www.nowcoder.com/questionTerminal/003482c395bd41c68082f6adc545a600
来源：牛客网
public int longestPalindrome(String s) {
int n = s.length();
int[][] dp = new int[n][n];//dp[l][r]表示l-r中的最长回文串
for (int r = 0; r < n; r++) {
dp[r][r] = 1;
for (int l = r - 1; l >= 0; l--) {
if (s.charAt(l) == s.charAt(r)) {
dp[l][r] = dp[l + 1][r - 1] + 2;
} else {