nuniok

typedef struct intset {
    //编码方式
    uint32_t encoding;
    //元素数目
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

apt-get install maven

import java.util.*;

public class ThreeSum {

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resp = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) break;
            int l = i + 1;
            int r = nums.length - 1;
            if (i > 0 && nums[i-1] == nums[i]) continue;
            while (l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if ( sum> 0) r--;
                else if (sum < 0) l++;
                else if (sum == 0){
                    resp.add(Arrays.asList(nums[i], nums[l] , nums[r]));
                    while (l < r && nums[l] == nums[l+1]) l++;
                    while (l < r && nums[r] == nums[r-1]) r--;
                    l++;
                    r--;
                }
            }
        }
        return resp;
    }
}

[---
title: 51. N皇后
date: 2019-08-20
tags: [算法, leetcode]
id: 1
---
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

import java.util.ArrayList;
import java.util.List;

public class GenerateParenthesis {
    public static void main(String[] args) {
        GenerateParenthesis obj = new GenerateParenthesis();
        List<String> stringList = obj.generateParenthesis(3);
        System.out.println(stringList);
    }

    public List<String> generateParenthesis(int n) {
        List<String> collect = new ArrayList<>();
        gen(collect, "", n, n);
        return collect;
    }

    public void gen(List<String> collect, String cur, int left, int right) {
        if (left == 0 && right == 0) {
            collect.add(cur);
            return;
        }
        if (left > 0) {
            gen(collect, cur + "(", left - 1, right);
        }
        if (right > 0 && right > left) {
            gen(collect, cur + ")", left, right - 1);
        }
    }
}

import java.util.*;

public class Anagram {
    public static void main(String[] args) {
        System.out.println(isAnagram("anagram", "nagaram"));
        System.out.println(isAnagram2("anagram", "nagaram"));
        groupAnagrams(new String[]{"eat", "ate", "aaa"});
    }

    public static boolean isAnagram(String s, String t) {
        if (null == s && null == t) {
            return true;
        } else if (null == s || null == t) {
            return false;
        } else if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> left = new HashMap<>();
        Map<Character, Integer> right = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            left.put(s.charAt(i), left.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int j = 0; j < t.length(); j++) {
            right.put(t.charAt(j), right.getOrDefault(t.charAt(j), 0) + 1);
        }
        for (Map.Entry<Character, Integer> c : left.entrySet()) {
            if (!c.getValue().equals(right.getOrDefault(c.getKey(), 0))) {
                return false;
            }
        }

        return true;
    }

    public static boolean isAnagram2(String s, String t) {
        if (null == s && null == t) {
            return true;
        } else if (null == s || null == t) {
            return false;
        } else if (s.length() != t.length()) {
            return false;
        }
        char[] left = s.toCharArray();
        char[] right = t.toCharArray();
        Arrays.sort(left);
        Arrays.sort(right);
        for (int i = 0; i < left.length; i++) {
            if (left[i] != right[i]) {
                return false;
            }
        }
        return true;
    }

    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> res = new HashMap<>();
        for (String sr : strs) {
            char[] chars = sr.toCharArray();
            Arrays.sort(chars);
            String sortedSr = new String(chars);
            if (!res.containsKey(sortedSr)) {
                res.put(sortedSr, new ArrayList<>());
            }
            List<String> mapVal = res.get(sortedSr);
            mapVal.add(sr);
        }
        List<List<String>> rep = new ArrayList<>();
        for (Map.Entry<String, List<String>> entry : res.entrySet()) {
            rep.add(entry.getValue());
        }
        return rep;
    }
}

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SolveNQueens {
    public static void main(String[] args) {
        SolveNQueens queens = new SolveNQueens();
        System.out.println(queens.solveNQueens(5));
    }

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> resp = new ArrayList<>();
        Set<Integer> cols = new HashSet<>();
        Set<Integer> pie = new HashSet<>();
        Set<Integer> na = new HashSet<>();
        dfs(n, 0, new ArrayList<>(), resp, cols, pie, na);
        return resp;
    }

    public void dfs(int max, int row, List<String> curState, List<List<String>> resp,
                    Set<Integer> cols, Set<Integer> pie, Set<Integer> na) {
        // 终结条件
        if (row >= max) {
            if (curState.size() == max) {
                resp.add(curState);
            }
            return;
        }
        // 循环列
        for (int col = 0; col < max; col++) {
            if (cols.contains(col) || pie.contains(row + col) || na.contains(row - col)) {
                continue;
            }
            cols.add(col);
            pie.add(row + col);
            na.add(row - col);
            curState.add(trans(col, max));
            int size = curState.size();
            List<String> newState = (max - row == 1) ? new ArrayList<String>() {{
                addAll(curState);
            }} : curState;
            // 递归层
            dfs(max, row + 1, newState, resp, cols, pie, na);
            cols.remove(col);
            pie.remove(row + col);
            na.remove(row - col);
            curState.remove(size - 1);
        }
    }

    public String trans(int point, int max) {
        char[] chars = new char[max];
        for (int i = 0; i < max; i++) {
            chars[i] = i == point ? 'Q' : '.';
        }
        return String.valueOf(chars);
    }
}

输入: 4
输出: 2

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

public class MySqrt {
    public static void main(String[] args) {
        MySqrt mySqrt = new MySqrt();
        System.out.println(mySqrt.mySqrt(2147395599));

    }

    // 边界问题
    // 1. 0\1边界
    //  类型长度越界
    public int mySqrt(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1;
        return mySqrt(x, 0, x);
    }

    public int mySqrt(long x, long left, long right) {
        long cur = (right - left) / 2 + left;
        long cur2 = cur * cur;
        if (cur2 == x) {
            return (int) cur;
        } else if (right - left == 1) {
            return (int) left;
        }

        if (cur2 < x) {
            left = cur;
        } else if (cur2 > x) {
            right = cur;
        } else {
            return (int) cur;
        }
        return mySqrt(x, left, right);
    }
}

  2
 / \
1   3

  5
 / \
1   4
     / \
    3   6

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root){
        return forEachNode(root, new ArrayList<>());
    }

    public boolean forEachNode(TreeNode node, List<Integer> val){
        if (null == node) {
            return true;
        }
        if (!forEachNode(node.left, val)){
            return false;
        }
        if (!validOrAdd(val, node)){
            return false;
        }
        if (!forEachNode(node.right, val)){
            return false;
        }
        return true;
    }
    public boolean validOrAdd(List<Integer> val, TreeNode node){
        if(val.size() > 0 && val.get(val.size() - 1) >= node.val){
            return false;
        }else{
            return val.add(node.val);
        }
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root){
        return subValidBSTLeft(root, null, null);
    }

    public boolean subValidBSTLeft(TreeNode node, Integer min, Integer max) {
        if (null == node){
            return true;
        }
        if (null == min && null == max){
        }else if (null == min && null !=max && node.val < max){
        }else if (null != min && null == max && min < node.val){
        }else if (null != min && null != max && min < node.val && node.val < max){
        }else {
            return false;
        }
        // left
        if (!subValidBSTLeft(node.left, min, node.val)){
            return false;
        }
        // right
        if (!subValidBSTLeft(node.right, node.val, max)){
            return false;
        }
        return true;
    }
}

  3
 / \
9  20
  /  \
 15   7

[
  [3],
  [9,20],
  [15,7]
]

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resp = new ArrayList<>();
        levelOrder(root, 0, resp);
        return resp;
    }
    public void levelOrder(TreeNode cur, int cur_level, List<List<Integer>> resp) {
        if(null == cur){
            return;
        }
        if(cur_level == resp.size()){
            resp.add(new ArrayList<>());
        }
        resp.get(cur_level).add(cur.val);
        levelOrder(cur.left, cur_level+1, resp);
        levelOrder(cur.right, cur_level+1, resp);
    }
}

  3
 / \
9  20
  /  \
 15   7

class Solution {
    public int maxDepth(TreeNode root) {
        return maxDepth(root, 0);
    }
    public int maxDepth(TreeNode cur, int level) {
        if(null == cur) return level;
        int left_level = maxDepth(cur.left, level + 1);
        int right_level = maxDepth(cur.right, level + 1);
        return left_level > right_level ? left_level: right_level;
    }
}

  3
 / \
9  20
  /  \
 15   7

class Solution {
    public int minDepth(TreeNode root) {
        return minDepth(root, 0);
    }

    public int minDepth(TreeNode cur, int level) {
        if (null == cur) return level;
        if (null == cur.left && null == cur.right) {
            return level + 1;
        } else if (null != cur.left && null == cur.right) {
            return minDepth(cur.left, level + 1);
        } else if (null == cur.left && null != cur.right) {
            return minDepth(cur.right, level + 1);
        } else {
            int left_level = minDepth(cur.left, level + 1);
            int right_level = minDepth(cur.right, level + 1);
            return left_level > right_level ? right_level : left_level;
        }
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        HashSet<Integer> points = new HashSet<Integer>();
        ListNode cur = head;
        while (null != cur){
            int curHashCode = cur.hashCode();
            if(points.contains(curHashCode)){
                return true;
            }
            points.add(curHashCode);
            cur = cur.next;
        }
        return false;
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (null == head){
            return false;
        }else if (null == head.next){
            return false;
        }else if (head == head.next.next){
            return true;
        }
        ListNode minCur = head.next;
        ListNode maxCur = head.next.next;
        while (minCur != maxCur){
            if (null == minCur.next){
                return false;
            }else if (null == maxCur.next){
                return false;
            }else if (null == maxCur.next.next){
                return false;
            }
            minCur = minCur.next;
            maxCur = maxCur.next.next;
            if (minCur == maxCur){
                return true;
            }
        }
        return false;
    }
}

from collections import OrderedDict

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self._cache = OrderedDict()
        self._size = capacity

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self._cache:
            return -1
        val = self._cache.pop(key)
        self._cache[key] = val
        return val

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self._cache:
            self._cache.pop(key)
            self._cache[key] = value
        else:
            if len(self._cache) == self._size:
                self._cache.popitem(last=False)
            self._cache[key] = value


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

public class ReverseLinkedList {
    public static void main(String[] args) {
        ListNode listNode = ListNode.of(
                1,
                ListNode.of(
                        2,
                        ListNode.of(
                                3,
                                ListNode.of(
                                        4,
                                        ListNode.of(
                                                5, null
                                        )
                                )
                        )
                )
        );
        ListNode next = listNode;
        while (null != next) {
            System.out.println(next.val);
            next = next.next;
        }

        System.out.println("===");
        ListNode reverse = reverse3(listNode);

        ListNode next2 = reverse;
        while (null != next2) {
            System.out.println(next2.val);
            next2 = next2.next;
        }
    }

    /**
     * 官方推荐的
     * @param head
     * @return
     */
    public static ListNode reverse2(ListNode head) {
        // prev -> curr -> nextTemp
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    /**
     * 自己写的
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head) {
        // cur -> prev -> tmp
        ListNode cur = head;
        ListNode next = head.next;
        head.next = null;
        while (null != cur) {
            ListNode tmp = null;
            if (null != next) {
                tmp = next.next;
                next.next = cur;
            }
            if (null == next) {
                break;
            }
            cur = next;
            next = tmp;
        }
        return cur;
    }

    /**
     * 复写的
     * 1. 记录前一个节点，当前节点
     * 2. 迭代
     * 3. 取出当前节点到临时变量
     * 4. -- 现在有 prev -> curr -> next 三个节点
     * 5. 将 curr.next -> prev，改变指向方向
     * 6. 依次挪动节点位置 prev = curr , curr = nextTemp
     * 7. 最后返回 prev
     *
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * @param head
     * @return
     */
    public static ListNode reverse3(ListNode head) {
        // prev -> curr -> next
        ListNode prev = null;
        ListNode curr = head;
        while (null != curr) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

public class Trie {
    private final int SIZE = 26;
    private Node root;

    private class Node {
        private boolean isStr;
        private int num;
        private Node[] child;

        public Node() {
            child = new Node[SIZE];
            isStr = false;
            num = 1;
        }
    }

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        if (null == word || word.isEmpty()) {
            return;
        }
        Node pNode = this.root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (pNode.child[index] == null) {
                Node tmp = new Node();
                pNode.child[index] = tmp;
            } else {
                pNode.child[index].num++;
            }
            pNode = pNode.child[index];
        }
        pNode.isStr = true;
    }

    public boolean search(String word) {
        if (null == word || word.isEmpty()) {
            return false;
        }
        Node pNode = this.root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (pNode.child[index] == null || (word.length() - i == 1 && pNode.child[index].isStr == false)) {
                return false;
            }
            pNode = pNode.child[index];
        }
        return true;
    }

    public boolean startsWith(String prefix) {
        if (null == prefix || prefix.isEmpty()) {
            return false;
        }
        Node pNode = this.root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (pNode.child[index] == null) {
                return false;
            }
            pNode = pNode.child[index];
        }
        return true;
    }
}

import java.util.PriorityQueue;

public class KthLargest {
    private PriorityQueue<Integer> minHeap;
    private int kSize;

    public KthLargest(int k, int[] nums) {
        kSize = k;
        minHeap=new PriorityQueue<Integer>(kSize);
        for (int i = 0; i< nums.length; i++){
            add(nums[i]);
        }
    }

    public int add(int val) {
        if (minHeap.size() < kSize){
            minHeap.offer(val);
        }else if (minHeap.peek() < val){
            minHeap.poll();
            minHeap.offer(val);
        }
        return minHeap.peek();
    }
}

#! /usr/bin/python
# -*- coding:utf-8 -*-
import socket
import sys
def start_tcp_server(ip, port):
    sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    server_address = (ip, port)
    print('Starting listen on ip %s, port %s' % server_address)
    sock.bind(server_address)
    try:
        sock.listen(1)
    except socket.error as exc:
        print('Fail to listen on port %s' % exc)
        return
    while True:
        print("Waiting for connection")
        client, addr = sock.accept()
        data = client.recv(1000)
        client.send(data)
        client.close()
        print(data)
if __name__ == '__main__':
    start_tcp_server('0.0.0.0', 12345)

// 查看当前生效规则
iptables -L -n
// 清空所有规则
iptables --flush
iptables -F

// 安装
sudo apt-get install dsniff
// 使用
...

curl --connect-timeout 10 -m 20 "http://192.168.1.110:12345"

xyz@xyz-pc:~$ curl "http://192.168.1.110:12345"
GET / HTTP/1.1
Host: 192.168.1.110:12345
User-Agent: curl/7.58.0
Accept: */*

xyz@xyz-pc:~$ sudo iptables -L -n
[sudo] xyz 的密码： 
Chain INPUT (policy ACCEPT)
target prot opt source destination         

Chain FORWARD (policy ACCEPT)
target prot opt source destination         

Chain OUTPUT (policy ACCEPT)
target prot opt source destination         
DROP tcp -- 0.0.0.0/0 0.0.0.0/0 tcp dpt:12345 flags:0x17/0x02

xyz@xyz-pc:~$ sudo iptables -F

xyz@xyz-pc:~$ sudo iptables -A OUTPUT -p tcp --syn --dport 12345 -j DROP
xyz@xyz-pc:~$ curl --connect-timeout 10 "http://192.168.1.110:12345"
curl: (28) Connection timed out after 10001 milliseconds

xyz@xyz-pc:~$ sudo iptables -A OUTPUT -p tcp -m state --state ESTABLISHED --dport 12345 -j DROP
xyz@xyz-pc:~$ curl --connect-timeout 10 -m 20 "http://192.168.1.110:12345"
curl: (28) Operation timed out after 20001 milliseconds with 0 bytes received

xyz@xyz-pc:~$ sudo iptables -A OUTPUT -p tcp --dport 12345 -j REJECT
xyz@xyz-pc:~$ curl --connect-timeout 10 -m 20 "http://192.168.1.110:12345"
curl: (7) Failed to connect to 192.168.1.110 port 12345: 拒绝连接

xyz@xyz-pc:~$ sudo tcpkill -iwlp8s0 port 12345
xyz@xyz-pc:~$ curl --connect-timeout 10 "http://192.168.1.110:12345"
GET / HTTP/1.1
Host: 192.168.1.110:12345
User-Agent: curl/7.58.0
Accept: */*
curl: (56) Recv failure: 连接被对方重设

xyz-macdeMacBook-Pro:dev-demo xyz$ python mixin_demo.py 
Init people.
People can eat!
People can drink!
People can 
Traceback (most recent call last):
  File "mixin_demo.py", line 44, in <module>
    people = People()
  File "mixin_demo.py", line 39, in __init__
    print "People can ", self.sleep()
  File "mixin_demo.py", line 30, in sleep
    raise NotImplementedError(u"can't sleep.")
NotImplementedError: can't sleep.

objc[20307]: Class JavaLaunchHelper is implemented in both /Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/bin/java (0x1077344c0) and /Library/Java/JavaVirtualMachines/jdk1.8.0_131.jdk/Contents/Home/jre/lib/libinstrument.dylib (0x10874d4e0). One of the two will be used. Which one is undefined.
Exception in thread "main" org.springframework.beans.factory.NoSuchBeanDefinitionException: No bean named 'teacher2' available
 at org.springframework.beans.factory.support.DefaultListableBeanFactory.getBeanDefinition(DefaultListableBeanFactory.java:775)
 at org.springframework.beans.factory.support.AbstractBeanFactory.getMergedLocalBeanDefinition(AbstractBeanFactory.java:1221)
 at org.springframework.beans.factory.support.AbstractBeanFactory.doGetBean(AbstractBeanFactory.java:294)
 at org.springframework.beans.factory.support.AbstractBeanFactory.getBean(AbstractBeanFactory.java:199)
 at org.springframework.beans.factory.support.CglibSubclassingInstantiationStrategy$LookupOverrideMethodInterceptor.intercept(CglibSubclassingInstantiationStrategy.java:290)
 at com.noogel.xyz.lookup.GetBeanTest$$EnhancerBySpringCGLIB$$e79f57a6.getBean(<generated>)
 at com.noogel.xyz.lookup.GetBeanTest.showMe(GetBeanTest.java:5)
 at LookupTestMain.main(LookupTestMain.java:9)