头像

shijiu2012




离线:2019-09-19 12:03


活动打卡代码 AcWing 78. Subsets

shijiu2012
2019-09-01 14:52
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int length = nums.length;

        List<Integer> prevList = new ArrayList<Integer>();
        List<List<Integer>> prevListList = new ArrayList<List<Integer>>();
        prevListList.add(prevList);

        for(int i = 1; i <= length; i++) {
            List<List<Integer>> tempListList = new ArrayList<List<Integer>>();
            for(int k = 0; k < prevListList.size(); k++) {
                List<Integer> tempList = new ArrayList<Integer>(prevListList.get(k));
                tempList.add(nums[i - 1]);
                tempListList.add(prevListList.get(k));
                tempListList.add(tempList);
            }
            prevListList = tempListList;
        }

        return prevListList;
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 547. Friend Circles

shijiu2012
2019-09-01 14:34
class Solution {
    public int findCircleNum(int[][] grid) {
        int circleNum = 0;
        int len = grid.length;
        for(int i=0;i<len;i++){
            for(int j=0;j<len;j++){
                if(grid[i][j] == 1){
                    circleNum++;
                    dfs(grid,i);
                }
            }
        }

        return circleNum;
    }

    public void dfs(int[][] grid,int x){// 格式化某个人的朋友圈
        int len = grid.length;

        grid[x][x] = 0;
        for(int i=1;i<len;i++){
            if(grid[x][i]==1){
                grid[x][i] = 0;
                grid[i][x] = 0;
                dfs(grid,i);
            }
        }
    }
}

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



shijiu2012
2019-09-01 13:48
class Solution {
    public int subarraySum(int[] nums, int k) {
                if (nums == null || nums.length == 0) return 0;
        //dp[i]表示前i个数的和
        int[] dp = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            dp[i] = dp[i - 1] + nums[i - 1];
        }
        int ret = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < dp.length; i++) {
            if (map.containsKey(dp[i] - k))
                ret += map.get(dp[i] - k);
            map.put(dp[i], map.getOrDefault(dp[i], 0) + 1);
        }
        return ret;

    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



shijiu2012
2019-09-01 13:46
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        HashMap<String,Integer> map = new HashMap();
        if(root==null)
            return res;
        saveRoute(root,res,map);
        return res;
    }
    private String saveRoute(TreeNode node, List<TreeNode> res, HashMap<String, Integer> map) {
        if(node==null)
            return "";
        String rout = String.valueOf(node.val)+","+saveRoute(node.left,res,map)+" "+saveRoute(node.right,res,map);
        if(map.get(rout)!=null&&map.get(rout)==1){
            res.add(node);
        }
        map.put(rout, map.getOrDefault(rout, 0) + 1);
        return rout;
 }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 53. Maximum Subarray

shijiu2012
2019-08-28 13:44
class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for(int i =0;i<nums.length;i++){
            if(sum>0){
                sum+=nums[i];
            }else{
                sum = nums[i];
            }
            res = Math.max(sum,res);
        }
        return res;
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 706. Design HashMap

shijiu2012
2019-08-21 12:25
public MyHashMap() {
    HASH_KEY = 10000;
    map = new Node[HASH_KEY];
}

/** value will always be non-negative. */
public void put(int key, int value) {
    int hash_key = key % HASH_KEY;
    if (map[hash_key] == null) {
        Node node = new Node(key, value);
        map[hash_key] = node;
    } else {
        Node node = new Node(-1, 0);
        node.next = map[hash_key];
        while (node.next != null) {
            node = node.next;
            if (node.key == key) {
                node.val = value;
                return;
            }
        }
        node.next = new Node(key, value);
    }
}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
public int get(int key) {
    int hash_key = key % HASH_KEY;
    if (map[hash_key] != null) {
        Node node = new Node(-1, 0);
        node.next = map[hash_key];
        while (node.next != null) {
            node = node.next;
            if (node.key == key) {
                return node.val;
            }
        }
    }
    return -1;
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
    int hash_key = key % HASH_KEY;
    if (map[hash_key] != null) {
        Node dummy = new Node(-1, 0);
        dummy.next = map[hash_key];
        Node node = dummy;
        while (node.next != null) {
            if (node.next.key == key) {
                node.next = node.next.next;
                break;
            }
            node = node.next;
        }
        map[hash_key] = dummy.next;
    }
}

int HASH_KEY;
Node[] map;
class Node {
    int key;
    int val;
    Node next;

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



shijiu2012
2019-08-21 12:19

class Solution{ public List<String> findRepeatedDnaSequences(String s) { List<String> res = new ArrayList<>(); if(s.length() < 10) return res; //储存已经遍历过的子字符串 Set<String> set1 = new HashSet<>(); //储存符合条件的子字符串 Set<String> set2 = new HashSet<>(); for(int i = 0;i + 10 <= s.length();i++){ String seq = s.substring(i,i+10); if(set1.contains(seq)){ set2.add(seq); } set1.add(seq); } res.addAll(set2); return res; } }



活动打卡代码 AcWing 1. Two Sum

shijiu2012
2019-08-19 13:57
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}



活动打卡代码 AcWing 18. 重建二叉树

shijiu2012
2019-08-17 10:38
public class Test {
    /*
     * 二叉树节点类
     */
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            this.val = x;
        }
    }
    /*
     * 给定二叉树的前序遍历和中序遍历,重构二叉树。假设前序遍历和中序遍历都没有重复的数
     */

    /**
     * 
     * @param pre  前序遍历
     * @param in    中序遍历
     * @return        二叉树根节点
     */
     public TreeNode reConstructBinaryTree(int[] pre,int[] in) {
         /*
          * 输入合法性判断, 不能为空,先序和后序长度要一致
          */
         if(pre == null || in == null || pre.length != in.length) 
             return null;

         return construct(pre, 0, pre.length-1, in, 0, in.length-1);
     }
     /**
      * 
      * @param pre    前序遍历
      * @param ps    前序遍历的开始位置
      * @param pe    前序遍历的结束位置
      * @param in    中序遍历
      * @param is    中序遍历的开始位置
      * @param ie    中序遍历的结束位置
      * @return        数的根节点
      */
     private TreeNode construct(int[] pre, int ps, int pe, int[] in, int is, int ie) {
         if(ps > pe) return null;

         // 取前序遍历的第一个数字就是根节点
         int value = pre[ps];
         // 在中序遍历中中寻找根节点
         int index =is;
         while(index <= ie && value != in[index]) {
             index ++;
         }
         // 如果在整个中序遍历的数组中没有找到,说明输入的参数是不合法的,抛出异常 
         if(index > ie) 
             throw new RuntimeException("Invalid Iuput!");

         // 创建当前根节点,并为根节点赋值
         TreeNode node = new TreeNode(value);
         // 递归调用构建当前节点的左子树 
         node.left = construct(pre, ps+1, ps+index-is, in, is, index-1);
         // 递归调用构建当前节点的右子树
         node.right = construct(pre, ps+index-is+1, pe, in, index+1, ie);

         return node;
    }


     private void printTree(TreeNode root) {
         if(root != null) {
             printTree(root.left);
             System.out.println(root.val + " ");
             printTree(root.right);
         }
     }

     public static void main(String[] args) {
        Test test = new Test();
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        TreeNode node = test.reConstructBinaryTree(pre, in);
        test.printTree(node);

    }

}
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 6. ZigZag Conversion

shijiu2012
2019-08-16 08:30
class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        List<StringBuilder> list = new ArrayList<>();
        for (int i=0;i<Math.min(numRows,s.length());i++){
            list.add(new StringBuilder());
        }
        int currow = 0;
        boolean go = false;
        for (char c:s.toCharArray()){
            list.get(currow).append(c);
            if (currow==0||currow==numRows-1)go = !go;
            currow+=go?1:-1;
        }
        StringBuilder ret = new StringBuilder();
        for (StringBuilder stringBuilder:list){
            ret.append(stringBuilder);
        }
        return ret.toString();

    }
}