k-sum & 图2016-08-02

[dayang]

18 4Sum 133 Clone Graph

[wolfogre]

// AC 133 Clone Graph
/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
 import java.util.Hashtable;

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null)
            return null;
        visited = new Hashtable<UndirectedGraphNode, UndirectedGraphNode>();
        return cloneGraphHelp(node);
    }

    private UndirectedGraphNode cloneGraphHelp(UndirectedGraphNode node) {
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        visited.put(node, newNode);
        for(UndirectedGraphNode n : node.neighbors){
            if(visited.containsKey(n))
                newNode.neighbors.add(visited.get(n));
            else
                newNode.neighbors.add(cloneGraphHelp(n));
        }
        return newNode;
    }

    private Hashtable<UndirectedGraphNode, UndirectedGraphNode> visited;
}

[dayang]

/**
 * [AC] LeetCode 18 4Sum
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
    if (nums.length < 4)
        return [];
    let res = [];
    nums.sort(function(a,b){
        return a - b;
    });
    for (let i = 0; i < nums.length - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1])
            continue;
        for (let j = i + 1; j < nums.length - 1; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1])
                continue;
            let l = j + 1, h = nums.length - 1;
            let t = target - nums[i] - nums[j];
            let visited = {};
            while (l < h) {
                if (nums[l] + nums[h] === t && visited[nums[l]] !== true) {
                    res.push([nums[i], nums[j], nums[l], nums[h]]);
                    visited[nums[l]] = true;
                    visited[nums[h]] = true;
                    l++;
                    h--;
                } else if (nums[l] + nums[h] < t) {
                    l++;
                } else {
                    h--;
                }
            }
        }
    }
    return res;
};

[SnackMen]

/*
*[AC] LeetCode 18 4Sum
*/
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        int length=nums.length;
        if(length<4 || nums==null)
            return list;
        int i=0;
        while(i<length-3){
            int j=i+1;
            while(j<length-2){
                int start=j+1;
                int end=length-1;
                while(start<end){
                    int sum=nums[i]+nums[j]+nums[start]+nums[end];
                    if(sum==target){
                        list.add(Arrays.asList(nums[i],nums[j],nums[start],nums[end]));
                        do{
                            start++;
                        }
                        while(start<end && nums[start]==nums[start-1]);
                        do{
                            end--;
                        }
                        while(start<end && nums[end]==nums[end+1] );

                    }else if(sum<target){
                        start++;
                    }else{
                        end--;
                    }
                }
                do{
                    j++;
                }
                while(j<length-2 && nums[j]==nums[j-1]);
            }
            do{
                    i++;
            }while(i<length-3 && nums[i]==nums[i-1]);
        }
        return list;
    }
}

[dayang]

/**
 * [AC] LeetCode 133 Clone Graph
 * Definition for undirected graph.
 * function UndirectedGraphNode(label) {
 *     this.label = label;
 *     this.neighbors = [];   // Array of UndirectedGraphNode
 * }
 */

/**
 * @param {UndirectedGraphNode} graph
 * @return {UndirectedGraphNode}
 */
var cloneGraph = function(graph) {
    if(graph === null)
        return null;
    let nodes = {};

    function dfs(node){
        if(nodes[node.label])
            return;
        nodes[node.label] = new UndirectedGraphNode(node.label);
        for(let i = 0; i < node.neighbors.length; i++){
            dfs(node.neighbors[i]);
            nodes[node.label].neighbors.push(nodes[node.neighbors[i].label]);
        }
    }
    dfs(graph);
    return nodes[graph.label];
};

[zhaokuohaha]

18 - KSUM - C#

public class Solution
{
    public IList<IList<int>> FourSum(int[] nums, int target)
    {
        List<IList<int>> res = new List<IList<int>>();
        if(nums.Length < 4) return res;
        Array.Sort(nums);
        KSum(res, new List<int>(), nums, target, 4, 0, nums.Length - 1);
        return res;
    }

    private void KSum(IList<IList<int>> res, IList<int> cur, int[] nums, int target, int k, int start, int end)
    {
        if(k == 0 || start > end)
        {
            return;
        }
        if (k == 1)
        {
            for (int i = start; i <= end; i++)
            {
                if (nums[i] == target)
                {
                    cur.Add(nums[i]);
                    res.Add(new List<int>(cur));
                    return;
                }
            }
        }

        if(k == 2)
        {
            while(start < end)
            {
                int sum = nums[start] + nums[end];
                if(sum == target)
                {
                    cur.Add(nums[start]);
                    cur.Add(nums[end]);
                    res.Add(new List<int>(cur));
                    cur.RemoveAt(cur.Count - 1);
                    cur.RemoveAt(cur.Count - 1);
                    while (start < end && nums[start] == nums[start + 1]) start++;
                    start++;
                    while (start < end && nums[end] == nums[end - 1]) end--;
                    end--;
                }
                else if(sum < target)
                {
                    while (start < end && nums[start] == nums[start + 1]) start++;
                    start++;
                }
                else
                {
                    while (start < end && nums[end] == nums[end - 1]) end--;
                    end--;
                }
            }
            return;
        }

        //剪枝
        if (k * nums[start] > target || k * nums[end] < target) return;

        for(int i= start; i<=(end -k +1); i++)
        {
            if (i > start && nums[i] == nums[i - 1]) continue;
            if(k * nums[i] <= target)
            {
                cur.Add(nums[i]);
                KSum(res, cur, nums, target - nums[i], k - 1, i + 1, end);
                cur.RemoveAt(cur.Count - 1);
            }
        }
    }
}

[zhaokuohaha]

别人的代码 , 神一样的深搜, 看不太懂

public class Solution
{
    private Dictionary<UndirectedGraphNode, UndirectedGraphNode> visit = new Dictionary<UndirectedGraphNode, UndirectedGraphNode>();
    public UndirectedGraphNode CloneGraph(UndirectedGraphNode node)
    {
        if (node == null) return null;
        if (!visit.ContainsKey(node))
        {
            visit[node] = new UndirectedGraphNode(node.label);
            foreach (var neibor in node.neighbors)
            {
                visit[node].neighbors.Add(CloneGraph(neibor));
            }
        }
        return visit[node];
    }
}