LeetCode(84) -- 240, 133

P240. Search a 2D Matrix II (Medium)

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.

My Solution

public class P240_Searcha2DMatrixII {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        int m = matrix.length, n = matrix[0].length;
        int l = 0, r = n - 1;
        for (int i = 0; i < m; i++) {
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (matrix[i][mid] == target) {
                    return true;
                } else if (target < matrix[i][mid]) {
                    r = mid - 1;
                } else if (mid + 1 < n && target >= matrix[i][mid + 1]) {
                    l = mid + 1;
                } else {
                    l = 0;
                    r = mid + 1;
                    break;
                }
            }
        }
        return false;
    }
}

34%

The Best Solution

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        
        if(matrix==null || matrix.length <= 0)
            return false;
     
        int row_index = matrix.length-1;
        int col_index = 0;
        
        while(col_index < matrix[0].length && row_index >=0)
        {
            if(matrix[row_index][col_index] == target)
                return true;
            else if(matrix[row_index][col_index] > target)
                row_index--;
            else
                col_index++;
        }
        
        return false;
        
    }
}

从左下角开始搜索，因为这个矩阵的特性，一路向右上只需要m + n次就能完成。

P133. Clone Graph (Medium)

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Solution

public class P133_CloneGraph {
    private HashMap <Node, Node> visited = new HashMap<>();
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        if (visited.containsKey(node)) {
            return visited.get(node);
        }
        Node cloneNode = new Node(node.val);
        visited.put(node, cloneNode);
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

6%

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class Solution(object):

    def __init__(self):
        # Dictionary to save the visited node and it's respective clone
        # as key and value respectively. This helps to avoid cycles.
        self.visited = {}

    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return node

        # If the node was already visited before.
        # Return the clone from the visited dictionary.
        if node in self.visited:
            return self.visited[node]

        # Create a clone for the given node.
        # Note that we don't have cloned neighbors as of now, hence [].
        clone_node = Node(node.val, [])

        # The key is original node and value being the clone node.
        self.visited[node] = clone_node

        # Iterate through the neighbors to generate their clones
        # and prepare a list of cloned neighbors to be added to the cloned node.
        if node.neighbors:
            clone_node.neighbors = [self.cloneGraph(n) for n in node.neighbors]

        return clone_node

The Best Solution

class Solution {
    public Node cloneGraph(Node node) {
           
        HashMap<Node,Node> hm = new HashMap<Node,Node>();
        return dfs(node,hm);
    }
    
    public Node dfs(Node node,HashMap<Node,Node> hm){
        
        if(hm.containsKey(node))
            return hm.get(node);
        
        Node newNode=new Node(node.val,new ArrayList<Node>());
        hm.put(node,newNode);
        
        for(Node edge:node.neighbors){
            newNode.neighbors.add(dfs(edge,hm));
        }
        
        return newNode;  
    }
}

跟答案其实完全一样，不知道为什么这个计时只有1ms，应该是测试系统有问题。