原生的Dijkstra”即毫无优化的Dijkstra，但这种Dijkstra的效率较低为n^n，因此面对较大数据量的时候需要对其进行优化，也就是优化所采用的贪心策略的实现，因此就有了Heao+Dijkstra堆优化的Dijkstra，但是堆优化的实现很复杂，而PriorityQueue+Dijkstra优先队列优化的Dijstra的效率虽然略低于堆优化的Dijkstra，但是实现却容易的多，也不容易出错，因为可以借助java类库中的PriorityQueue来实现，因此优先队列优化的Dijkstra是首选，其实java类库PriorityQueue的底层实现原理就是推排序

​​  

public class DijKstra_link_Queue {  

    public   int nodeCount;  

    public   int edgeCount;  

    // 邻接表表头数组  

    public  Node[] firstArray;  

    // 最短路径数组  

//  static int[] dist;  

    // S集合,代表着已经找到最短路径

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

先来看看空间复杂度高的算法，我的想法是利用两个新数组，一个存放奇数，一个存放偶数，然后把两个新数组合并到原来的数组中。比较浪费空间

   public void reOrderArray(int [] array) {

       if(array.length==0)

           return;

       int[] odd=new int[array.length];

       int[] even=new int[array.length];

       int j=0,k=0;

       for(int i=0;i

           {

               even[j++]=array[i];

题目描述

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

如果不加限制这个题目就是小学生的难度，但是现在有限制条件应该就要开动脑筋了，肯定要用到位运算。

解题思路：

1.需利用逻辑与的短路特性实现递归终止。 2.当n==0时，(n>0)&&((sum+=Sum_Solution(n-1))>0)只执行前面的判断，为false，然后直接返回0；

3.当n>0时，执行sum+=Sum_Solution(n-1)，实现递归计算Sum_Solution(n)。

    public int Sum_Solution(int n) {

题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

第一，最简单的最容易想的，一个一个来判断。最直观的想法，求1到n中每个整数中1出现的次数，然后相加即可。而求每个十进制整数中1出现的次数，我们先判断这个数的个位数是否是1，如果这个数大于10，除以10之后再判断个位数是否为1，循环直至求出该整数包含1的个数。由于不想对数运算，直接把数变成了字符串

 public int NumberOf1Between1AndN_Solution(int n) {

        int count=0;

    while(n>0)

        {

        String str=String.valueOf(n);

        char[]ch=str.toCharArray();

        for(int i=0;i

            {

  &nbs

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

先看第一种解法，小编是想来一个数组统计各数字出现的频率，所以空间复杂度是O（n），然后再分别统计各个数字的出现次数，统计过得及标记为* ，直到最后。时间复杂度是O（n*n），当然，这不是最好的方法，但是也是可以通过的。

代码：

public int MoreThanHalfNum_Solution(int [] array) {

        if(array.length==0)

           return 0;

       if(array.length==1)

           return array[0];

       int len=array.length;

       int[]count=new int[len];

        int i=0;

&

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

最容易想到的就是新建一个链表，一个一个将节点连接到新链表中。

代码：

 public ListNode Merge(ListNode list1,ListNode list2) {

         ListNode head=new ListNode(-1);

        ListNode node=null;

        node=head;

         if(list1 == null && list2 == null) return null;

        if(list1 == null) return list2;

        if(list2 == null) return list1;

        while(list1!=null&&list2!=null)

            {

            if(list1.val