美团笔试

1.用一个count记录size，用size来记录key 2、最长上升子序列改下判断条件，如果降序也可以，那么求2次比较最大就行 3、直接遍历求大于等于它的？（开始还想着维护一个最大堆），当然如果b不在数组中，就加条件判断一下

用Hashtable实现栈：用一个size记录当前hashtable的大小，然后将size+1作为key,将要放入栈的值当着value,就实现了入栈，然后出栈时候用当前size作为key值，查找出对应的value即可。 最大连续自数组：查找前i最长的连续子数组，记录下最长的连续子数组长度及起始下标index 求数组中位次：先进行快排(大到小)，然后用二分查找找出对应下标，然后用数组大小减去对应下标就得到对应位次。

手动给楼主点赞

等牛客出试卷。谢楼主

1、         private static Hashtable<Integer, Object> table = new Hashtable<Integer, Object>(); private static int length = 0; // 长度 /** * hashtable实现put */ public static void push(Object b) { table.put(length++, b); } /** * Hashtable实现pop * @return */ public static Object pop() { if(table.size() == 0) { return null; } length--; Object obj = table.remove(length); return obj; }

2、 /** * 找到最长连续数组 * @param a */ public static void longestLianXuArray(int a[]) { String s = ""; int maxLen = 1; int i = 0; // 其实元素的下标 while(i < a.length) { int j = i; StringBuilder sb = new StringBuilder(); while(j < a.length && j + 1 < a.length) { if(a[j + 1] == a[j] + 1) { sb.append(a[j]); j++; } else { sb.append(a[j]); break; } } if(sb.toString().length() > s.length()) { s = sb.toString(); } i = j + 1; } System.out.println(s); }

3、 /** * 得到数组元素位次 * @param a */ public static void GetPos(int a[], int val) { int pos = a.length; for(int i = 0; i < a.length; i++) { if(val == a[i]) { pos = i; break; } } if(a.length == pos) { System.out.println("not found"); } else { System.out.println(partation(a, pos, 0, a.length - 1)); } } /** * 分块 * @param a * @param pos * @param low * @param high * @return */ public static int partation(int a[], int pos, int low, int high) { int temp = a[pos]; while(low < high) { while(low < high && temp <= a[high]) { high--; } a[pos] = a[high]; a[high] = temp; while(low < high && temp >= a[low]) { low++; } a[high] = a[low]; a[low] = temp; } return a.length - low; }

4、归并，代码不写啦

5、全排 & 去重。 7、不说了 8、dp

package com.mbc.meituan; //第5题实现组合输出并且去掉重复元素 import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; public class Zuhe { public static void permutation(char[]ss,int i){   HashSet<String>  res=new  HashSet<String>();        ArrayList<String> res1=new ArrayList<String>()  ;      if(ss==null||i<0 ||i>ss.length)      {              return;        }         if(i==ss.length)       {          res1.add(new String(ss));            }       else       {              for(int j=i;j<ss.length;j++)            {                  char temp=ss[j];                 ss[j]=ss[i];                   ss[i]=temp;                   permutation(ss,i+1);                   temp=ss[j];                    ss[j]=ss[i];                   ss[i]=temp;              }         }                                            for(int l=0;l<res1.size();l++)       {                       res.add(res1.get(l));       }              for(Iterator<String> it=res.iterator();it.hasNext();)       {        System.out.println(it.next());       }                   }             public static void main(String args[]){                 String s="see";        char []ss=s.toCharArray();          permutation(ss,0);         }   }

package com.mbc.meituan; import java.util.Scanner; //第4题合并两个有序数组找出第K大数 public class Chazhao {     public static void merge(int a[], int b[],int p )          {              int[] result = new int[a.length+b.length];                 int i=0,j=0,k=0;                        while(i<a.length && j<b.length)                      if(a[i] <= b[j])                      {                         result[k++] = a[i++];                    }                      else                      {                        result[k++] = b[j++];                     }                                  while(i < a.length)                       result[k++] = a[i++];                while(j < b.length)                      result[k++] = b[j++];                 int length=result.length;                                                    System.out.print(result[length-p]);                                                    } public static void main(String[] args) throws Exception {      int [] A={1,2,3};      int [] B={2,4,6};      int n=A.length;      int m=B.length;   Scanner in=new Scanner(System.in); int p=in.nextInt();     merge(A,  B, p); } }

import java.util.Arrays; import  java.util.*; public class Test{ public static void find1(int[] a)      {          int length = a.length;         int[] list = new int[length];// 存储第i个元素之前的最长递增序列值         List<Integer> result = new ArrayList<Integer>(); // 存储最长递增序列         for (int i = 0; i < length; i++)           {             list[i] = 1;             for (int j = 0; j < i; j++)            {                 if (a[j] < a[i] && list[j] + 1 > list[i])                  {                      list[i] = list[j] + 1;                      if (result.isEmpty())                     {                           result.add(list[j]);                     }                     if (!result.contains(list[i]))                      {                         result.add(list[i]);                     }                 }            }         }              int max = list[0];         for (int i = 0; i < length; i++)          {               if (list[i] > max)             {                  max = list[i];              }          }           System.out.println("最长递增序列长度：" + max);         System.out.println("最长递增序列：" + result);     }   public static void main(String[] args) {    int []  A={1,-1,2,-2,3};       find1(A);           } }

第四题O（lgk）算法 http://blog.csdn.net/beiyeqingteng/article/details/7533304

谢谢lz，好人，1024