Dijkstra Algorithm with Leetcode

Dijkstra Algo(How to pronouce) is a way to find the shortest path between two points in a graph with:
Directed graph: edge (1, 3) != edge (3, 1)
potential circles: edge (1, 3) (3, 2), (2, 1)
positive weights. each edge must have positive weight.

Leetcode Problems: 743, 1102

public class DijkstraAlgo {
    int[] dist;    //dist[i] means the shortest path from starting point to node i; 
    int[] preNode; //the previous node for shortest path, we could build the path with this record;
    PriorityQueue<Integer> pq; 
    
   /**
   edges -> [[0,3,2],[1,3,4]]   [edge From, edge To, edge Cost]
   start -> start point of the graph
   N     -> total node number in the graph
   */
    public int[] findShortestPath(int[][] edges, int start, int N) {
        List<int[]>[] graph = buildGraph(edges, N); 
        dist = new int[N];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0; 
        
        preNode = new int[N];
        Arrays.fill(preNode, -1); 
        preNode[start] = start;

        pq = new PrirorityQueue<>((a, b) -> {return dist[a] - dist[b];});
        pq.add(start);
        
        while (!pq.isEmpty()) {
            int curr = pq.poll();
            int cost = dist[curr];
            
            for (int[] next: graph[curr]) { // visit all the adj, int[] next -> [curr, next, cost]
                int nextIdx = next[1], edgeCost = next[2];
                if (cost + edgeCost < dist[nextIdx]) {
                    if (preNode[nextIdx] != -1) {
                       pq.remove(nextIdx);
                    }
                    dist[nextIdx] = cost + edgeCost;
                    preNode[nextIdx] = curr;
                    pq.add(nextIdx);
                }
            }
        }

        return dist;
    }

    /*for each node, find its adjcent(next) nodes.*/
    private List<int[]>[] buildGraph(int[][] edges, int N) {
        List<int[]>[] graph = new List[N];
        for (int i = 0; i < N; i++) graph[i] = new ArrayList<>();
        for (int[] edge: edges) graph[edge[0]].add(edge);
        return graph;
    }
}

【Leetcode 397】 一道有趣的数学题

Given a positive integer n and you can do operations as follow:

  1. If n is even, replace n with n/2.
  2. If n is odd, you can replace n with either n + 1 or n - 1.

  3. What is the minimum number of replacements needed for n to become 1?

这道题做出来之后看了一下原来的方式大概都是递归。应该不能称之为一种合格的解法。但我的解法仍可以改进，明显适用于bit manipulation.

首先是要找出规律。什么时候加一，什么时候减一。

以37作为一个例子。

37 = 32 + 4 + 1 =》 32 + 4  =》  16 + 2  =》  8 + 1  =》  8   =》  4   =》  2  =》 1

在这种情况下， 很显然所有的加一减一的决策中都应该选择减一。

那么什么情况下应该选择加一呢？

15 = 8 + 4 + 2 +1 = 》 16 = 》 8 =》4 =》 2 =》 1;

观察得到， 此时加一为最佳。

原理如下 ：

任一一个数， 可以拆成2的多少次方的和。（其实我们就是在探讨二进制）。

 15 = 2^3 + 2^2 + 2^1 + 2^0

也就是说， 不考虑余数的情况下，15 三次除二之后即可得到1;

小时候奥数课学过一种方法叫做除二倒取余数法来进行二进制的转换。

那么假设现在已经完成了二进制的转换。有以下数字：

111

1001

100

可以推理出以下规律。

  1. 除最高位的1之外， 每一个单独的1都意味着需要单独减一。 result++；
  2. 除最高位的1之外， 连续的1 可以通过加一之后伴随除二再减一。也就是完成进位后再减一来处理。 result = result +2;

做到这里几乎已经解决了百分之九十的问题，但我在自己实验的时候发现了一个corner case. 187.

发现以上两条规律上有一个漏洞。也就是中间间隔只有一个0的两条连续的1可以合并。

给出代码如下：

class Solution {
public int integerReplacement(int n) {

    int result = 0;
    int temp = 0;
    Deque<Integer> q=new ArrayDeque<Integer>();

    while(n != 1){
        temp = n / 2;
        int extraOne = n % 2;
        result++;
        q.addLast(extraOne);

        n = temp;
    }

    boolean exIsOne = false;
    while (q.peekFirst() != null) {
        int cur = q.removeFirst();
        if (cur == 0) {
            ;
        } else if (cur == 1) {
            Integer next = q.peekFirst(); 
            if (next == null) {
                result++;
                if (exIsOne) {
                    result++;
                }
            } else {
                if (next == 1) {
                    exIsOne = true;
                } else {   // next == 0
                    if (exIsOne) {
                        q.removeFirst();
                        q.addFirst(1);
                        result++;
                        exIsOne = false;
                    } else {
                        result++;
                        exIsOne = false;
                    }
                }
            } 


        }
    }



    return result;
}

}