黑马程序员技术交流社区

标题: 【石家庄校区】java中常用的算法 [打印本页]

作者: xiekai_sjz 时间: 2018-7-19 15:41
标题: 【石家庄校区】java中常用的算法
本帖最后由 xiekai_sjz 于 2018-7-19 15:52 编辑

1 去重1.1 去重

[Java] 纯文本查看 复制代码

//去重复，需要额外定义一个List

    public static void RemoveRepeat(List<Integer> arrs) {

        List<Integer> tmp = new ArrayList<Integer>();

        Iterator<Integer> it = arrs.iterator();

        while (it.hasNext()) {

            int a = it.next();

            if (tmp.contains(a))

                it.remove();

            else

                tmp.add(a);

        }

    }

1.2 去不重

[Java] 纯文本查看 复制代码

public static void RemoveNotRepeat(List<Character> arrs)

    {

        Map<Character,Integer> tmp=new HashMap();

        for(char c:arrs)

        {

            if(tmp.containsKey(c))

                tmp.put(c,tmp.get(c)+1);

            else

                tmp.put(c,1);

        }

        Iterator<Character> it=arrs.iterator();



        while (it.hasNext())

        {

            Character c=it.next();

            if(tmp.get(c)==1)

                it.remove();

        }

    }

2 随机分配
定义方法实现，把两个List中的内容随机配对，并保存到Map中。

[Java] 纯文本查看 复制代码

public static Map<String, String> TicketDispatch(List<String> customers, List<String> tickets) {

        Map<String, String> result = new HashMap<String, String>();



        Random r = new Random();

        int iCustomer;

        int iTicket;

        for (int i = customers.size(); i > 0; i--) {

            // 取值范围[0,i)

            iCustomer = r.nextInt(i);

            iTicket = r.nextInt(tickets.size());



            result.put(customers.get(iCustomer), tickets.get(iTicket));

            customers.remove(iCustomer);

            tickets.remove(iTicket);

        }



        return result;

    }

3 递归

[Java] 纯文本查看 复制代码

//Java递归删除一个目录下文件和文件夹

    private static void deleteDir(File dir) {

        if (dir.isDirectory()) {

            String[] children = dir.list();

            // 递归删除目录中的子目录下

            for (int i=0; i<children.length; i++) {

               deleteDir(new File(dir, children));               

            }

        }

        dir.delete();

    }

4 内部排序变形
4.1 取数组中未出现的最小整数

[Java] 纯文本查看 复制代码
public static Integer GetNotExitMinInteger(Integer[] arr)
{
      Integer minIndex;
      Integer tmp;
      Integer first=0;
      for(int i=0;i<arr.length;i++)
      {
         minIndex=i;
         for(int j=i+1;j<arr.length;j++)
         {
            if(arr[minIndex]>arr[j])
                  minIndex=j;
         }

         if(arr[minIndex]-first>1)
            return first+1;
         else
         {
            first=arr[minIndex];
         }

         if(minIndex!=i)
         {
            tmp=arr;
            arr=arr[minIndex];
            arr[minIndex]=tmp;
         }
      }
      return arr[arr.length-1]+1;
}

上面问题其他解决方案：
也可先排序（快速排序，若范围可确定，且不到，可用桶排序），在先后比较arr[next]-arr[one]>1
HashMap实现
[Java] 纯文本查看 复制代码
public static Integer GetNotExitMinIntegerByHashMap(Integer[] arr) {
      Integer minKey=Integer.MAX_VALUE;
      Integer maxKey=Integer.MIN_VALUE;
      Map<Integer,Integer> map=new HashMap<Integer,Integer>();

      for(int i=0;i<arr.length;i++)
      {
         map.put(arr,arr);
         if(minKey>arr)
            minKey=arr;
         if(maxKey<arr)
            maxKey=arr;
      }

      Integer pre=minKey;

      if(minKey>1)
         return minKey-1;

      while(pre<=maxKey) {
         if(map.get(pre+1)==null)
            return pre+1;
         else
            ++pre;
      }

      return maxKey+1;
}
5 字符串
5.1 全排序
思路：
n个字符
前n-1个固定，第n个，不能再互换，打印排列
前n-2个固定，第n-1个和n位置互换，得到排列
前n-3个固定，第n-2个分别和最后两个位置互换
...

[Java] 纯文本查看 复制代码
public class FullPermutation {
public static void main(String[] args)
{
      char[] arr=new char[]{'A','B','C','D'};
      Permutatition(arr);
}

public static void Permutatition(char[] arr)
{
      recursivePermutation(arr,0,arr.length-1);
}

private static void recursivePermutation(char[] arr,int start,int end)
{
      if(start==end) {
         for (int i = 0; i <= end; i++)
            System.out.print(arr);
         System.out.println();
      }
      else {
         for (int i = start; i <= end; i++) {
            swap(arr, start, i);
            recursivePermutation(arr, start+1, end);
            swap(arr, start, i);
         }
      }
}

private static void swap(char[] arr,int left,int right)
{
      char tmp=arr[left];
      arr[left]=arr[right];
      arr[right]=tmp;
}
}

5.2 出现频率最高10位数
hashmap按值，按排序

[Java] 纯文本查看 复制代码
public static void main(String[] args) {
      Map<String, String> map = new HashMap<String, String>();
      map.put("c", "ccccc");
      map.put("a", "aaaaa");
      map.put("b", "bbbbb");
      map.put("d", "ddddd");

      List<Map.Entry<String,String>> list = new ArrayList<Map.Entry<String,String>>(map.entrySet());
      Collections.sort(list,new Comparator<Map.Entry<String,String>>() {
         //升序排序
         public int compare(Entry<String, String> o1,
                  Entry<String, String> o2) {
            return o1.getValue().compareTo(o2.getValue());
         }

      });

      for(Map.Entry<String,String> mapping:list){
            System.out.println(mapping.getKey()+":"+mapping.getValue());
      }
   }

Lambda简化版

[Java] 纯文本查看 复制代码
public static void main(String[] args)
{
      Map<String, String> map = new HashMap<String, String>();
      map.put("c", "ccccc");
      map.put("a", "daaaa");
      map.put("b", "bbbbb");
      map.put("d", "ddddd");

      List<Map.Entry<String, String>> list=new ArrayList<Map.Entry<String,String>>(map.entrySet());
      list.sort((o1,o2)-> o1.getValue().compareTo(o2.getValue()));

      for(Map.Entry<String,String> mapping:list){
            System.out.println(mapping.getKey()+":"+mapping.getValue());
      }
}

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2