Python 知识小结

如何在Python运行环境里查看Python版本?用sys就可以。

>>> import sys
>>> sys.version_info
sys.version_info(major=2, minor=7, micro=16, releaselevel='final', serial=0)

xrange和range的区别?

>>> range(10)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> xrange(10)
xrange(10)

range返回的是一个list,xrange是个object。range直接占用一片内存。xrange object可以像list一样使用

r = xrange(10)
>>> r[0]
0
>>> r[1]
1
>>> r[3]
3
>>> dir(r)
['__class__', '__delattr__', '__doc__', '__format__', '__getattribute__', '__getitem__', '__hash__', '__init__', '__iter__', '__len__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__']
>>> len(r)
10

算法练习 Leetcode 力扣 518. Coin Change 2解法

作为lc322 coin change的follow up,leetcode标记为medium,而且acceptance rate为47%,高于coin change的34.2%。个人做下来觉得很难,比322要难。写出一个逻辑正确的解法还算OK,但是OJ会超时。

Python 版本 top down dfs + backtrace

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        cur_path = []
        paths = set()
        self.dfs(amount, coins, cur_path, paths)
        return len(paths)
        
    def dfs(self, amount, coins, cur_path, paths):
        if amount == 0:
            path = tuple(sorted(cur_path))
            paths.add(path)
            return
        if amount < 0:
            return
        for coin in coins:
            cur_path.append(coin)
            self.dfs(amount - coin, coins, cur_path, paths)
            del cur_path[-1]
        

Python 版本 bottom up dp

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        dp = [None] * (amount + 1)
        dp[0] = set()
        dp[0].add(())
        for i in range(1, amount + 1):
            combos = set()
            for coin in coins:
                rest = i - coin
                if rest >= 0 and dp[rest] is not None:
                    for rest_combo in dp[rest]:
                        combo = tuple(sorted(rest_combo + (coin,)))
                        combos.add(combo)
            if len(combos) > 0:
                dp[i] = combos
                
        return len(dp[amount]) if dp[amount] is not None else 0 

以上两种都超时。

实在想不到能过OJ的算法,以下dp算法也是我从网上大神们那学到了。盯着看了2天才算想明白了其中道理。写得非常简短。

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        dp = [1] + [0] * amount
        for coin in coins:
            for i in xrange(amount - coin + 1):
                if dp[i]:
                    dp[i + coin] += dp[i]
        return dp[amount]

算法练习 Leetcode 力扣 322. Coin Change 解法

leetcode 322 coin change

题目在这里

自己想的答案,bottom up dp不太好想,从top down + cache开始,写了几次,每次简化一点,最终写成这样通过OJ。

Python 版本。

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        cache = {0:0}
        self.dfs(coins, amount, cache)
        return cache[amount]
        
    def dfs(self, coins, amount, cache):
        if amount in cache:
            return cache[amount]
        if amount == 0:
            return 0
        if amount < 0:
            return -1
        ans = float('inf')
        for coin in coins:
            rest_cnt = self.dfs(coins, amount - coin, cache)
            if rest_cnt != -1:
                ans = min(ans, rest_cnt + 1)
        if ans == float('inf'):
            cache[amount] = -1
            return -1
        
        cache[amount] = ans
        return ans 

为了更好理解算法,加了些log,记录dfs被call了几次和cache hit,和每个cache key被写入次数(使用cache和不用cache的情况。

用coins = [1, 2, 5]和amount = 11为例子

用了cache

dfs call: 34
cache hit: 15
key write times
1: 1
2: 1
3: 1
4: 1
5: 1
6: 1
7: 1
8: 1
9: 1
10: 1
11: 1

不用cache

dfs call: 928
cache hit: 0
key write times
1: 128
2: 75
3: 44
4: 26
5: 15
6: 9
7: 5
8: 3
9: 2
10: 1
11: 1

运行完后cache的内容如下

0: 0
1: 1
2: 1
3: 2
4: 2
5: 1
6: 2
7: 2
8: 3
9: 3
10: 2
11: 3

正是从0到11每个amount的最少硬币数。从此出发,想到bottom up dp正是需要构建如上cache的内容。dp[0] = 0,amount是0,当然一个硬币不用。dp[amount]就看amount – coin值是不是正,而且之前是否有非-1的值。当算到amount的时候,前面dp[0]到d][amount-coin]都算过了。对所有的coin值都算一遍,把所有dp[amount – coin]的非-1最小值找出来,加1,就是dp[amount]。时间复杂度为O(amount * len(coins))。空间为 O(amount)。

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [0] * (amount + 1)
        for i in range(1, amount + 1):
            rest_min_cnt = -1
            for coin in coins:
                rest = i - coin
                if rest >= 0 and dp[rest] != -1:
                    if rest_min_cnt == -1:
                        rest_min_cnt = dp[rest]
                    else:
                        rest_min_cnt = min(rest_min_cnt, dp[rest])
            dp[i] = rest_min_cnt + 1 if rest_min_cnt != -1 else -1
            
        
        return dp[amount]                                    

过了多日以后自己重新想的Python写法, 看看是否已经内化并掌握. 对比上面, 做了一些改进, dp list init成全部-1, 代表一开始都不可能. dp[0]设成0, 代表一个coin都不取. 新解法省了rest_min_cnt一个变量.

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [-1] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for j in coins:
                k = i - j
                if k >= 0 and dp[k] != -1:
                    if dp[i] == -1:
                        dp[i] = dp[k] + 1
                    else:
                        dp[i] = min(dp[i], dp[k] + 1)
        return dp[amount]
        

Java版本的bottom up dp解法

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            int restMinCoins = -1;
            for (int coin : coins) {
                int remainder = i - coin;
                if (remainder >= 0 && dp[remainder] != -1) {
                    if (restMinCoins == -1) {
                        restMinCoins = dp[remainder];
                    } else {
                        restMinCoins = Math.min(restMinCoins, dp[remainder]);
                    }
                }
            }
            if (restMinCoins == -1) {
                dp[i] = -1;
            } else {
                dp[i] = restMinCoins + 1;
            }
        }
        return dp[amount];
    }
}

Gson入门 | Quick tutorial to Gson

Gson是Google的开源的处理Json的library。个人觉得比Jackson好用。

gson添加到build.gradle的dependency里,gradle入门请参考之前博文”怎样用gradle建立一个新的Java项目 | how to create a new Java project using gradle“。

dependencies {
    implementation 'com.google.code.gson:gson:2.8.6'
}
点击Intelij Idea Gradle Plugin左上角的“刷新”
刷新后,在左边项目结构的External Libraries里看到gson,就是添加成功了

使用Gson例子

Gson gson = new Gson();
String json = gson.toJson(someObject)

这里json是紧凑型的

Gson gson = new GsonBuilder().setPrettyPrinting().create();
String json = gson.toJson(someObject);

这里的json是pretty print的

例子


import com.google.gson.Gson;
import com.google.gson.GsonBuilder;

public class GsonDemo {
    public String name;
    public String url;
    public String description;

    @Override
    public String toString() {
        Gson gson = new GsonBuilder()
                .setPrettyPrinting()
                .create();
        return gson.toJson(this);
    }

    public static void main(String[] args) {
        GsonDemo gsonDemo = new GsonDemo();
        gsonDemo.name = "Feellikelearning";
        gsonDemo.url = "feellikelearning.com";
        gsonDemo.description = "feellikelearning.com - The blog about learning technology";

        System.out.println(gsonDemo);
    }
}

运行结果

{
  "name": "Feellikelearning",
  "url": "feellikelearning.com",
  "description": "feellikelearning.com - The blog about learning technology"
}

怎样用gradle建立一个新的Java项目 | how to create a new Java project using gradle

Gradle是什么?

Gradle是Java的build tool,是maven, ant的后代产品。Gradle也是是现在Android的默认build tool。Gradle由Gradle公司团队维护和开发。build.gradle是代替maven里的pom.xml的项目配置文件,其作用类似于C/C++里的Makefile。

Gradle入门

本文用Intelij Idea 2019.3.3为例子创立新的Java项目。

Create New Project
选gradle,右边选Java, 然后右下角Next
给project起名字,选目录,选Finish
Project就成功建立了
添加代码,就可以编译运行了
plugins {
    id 'java'
}

group 'org.example'
version '1.0-SNAPSHOT'

sourceCompatibility = 1.8

repositories {
    mavenCentral()
}

dependencies {
    testCompile group: 'junit', name: 'junit', version: '4.12'
}

以上是自动生成的build.gradle文件

Java 反射入门 | A short introduction to Java reflection

反射在Java是个比较奇怪的概念,背后的思想其实很深刻。一般程序包括程序(code)和数据(data)两部分。如果一个程序计算1+1,那么1和1是数据,而加法这个操作是code,code是编译时就决定的,编译后就不能再更改,比如这里的加法。而反射这个概念允许了data也可以是code的概念。比如现在程序变成了f(1, 1),f是一个未知函数,它也是”data”,可以由用户提供。用户提供了乘法,那就是乘法,提供了减法,那就是减法。这样提供一个让程序在运行时修改自己的机制。这样能提高程序的表达力,一些Java的框架比如Spring就大量用到反射。Spring里面很多magical的现象就是这样实现的,比如我明明只写了一个class,另一个地方我就自动有了一个这个class的object,而我明明没有在任何地方初始化这么一个对象。IDE里面自动提示一个class里面的available methods应该也是用到了reflection。在应用中有些坏处也是显而易见,需要小心。在Java里面reflection速度慢还是其次,IDE很难检测到代码被引用,还有很多compiler可以检测到的错误被漏过了,只能在run time出问题。而且允许外部输入代码也带来安全问题。很多网络攻击的原理比如SQL injection就是利用了data也是code的这种特性。关于refelection很多的用法以后我会再写。

本文通过一个简单的Java例子来演示一下Java的reflection。Just get a feeling.

Animal.java

package learn.java.reflection;

public interface Animal {
    public void whoami();
}

Tiger.java

package learn.java.reflection;

public class Tiger implements Animal {
    @Override
    public void whoami() {
        System.out.println("I am a tiger");
    }
}

Lion.java

package learn.java.reflection;

public class Lion implements Animal {
    @Override
    public void whoami() {
        System.out.println("I am a lion");
    }
}

Zoo.java

package learn.java.reflection;

import java.util.Scanner;

public class Zoo {
    public static void main(String[] args) throws ClassNotFoundException, IllegalAccessException, InstantiationException {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Choose [1] for tiger, [2] for lion: ");
        String opt = scanner.nextLine();
        String className = null;
        while (true) {
            if ("1".equals(opt)) {
                className = "learn.java.reflection.Tiger";
                break;
            } else if ("2".equals(opt)) {
                className = "learn.java.reflection.Lion";
                break;
            } else {
                System.out.println("Choose [1] for tiger, [2] for lion: ");
                opt = scanner.nextLine();
            }
        }

        Class cls = Class.forName(className);
        Animal animal = (Animal) cls.newInstance();
        animal.whoami();
    }
}

运行结果

Choose [1] for tiger, [2] for lion: 
1
I am a tiger

Choose [1] for tiger, [2] for lion: 
2
I am a lion

Zoo.java 为主程序。里面的animal是什么要看用户提供的data决定而不是compile time决定的。在IDE里面,都找不到Lion.java和Tiger.java的引用。因为他们是这样被用到的:Class cls = Class.forName(className)。className还是个runtime才能知道的String,连人类都不是很容易能发现,IDE能知道就真的实现人工智能了。

虽然我本人并不是Reflection的粉丝,但是因为合作中同事可能会用到,或者公司所选的框架用到,比如Spring之类也是被广泛使用,还是应该抱有开放的心态学习并驾驭它。

另外,本文提供的小程序程序也包含了Java从键盘输入data的例子。

python 抓取ip地址的正则表达式 | Regular expression for finding ip address using Python

import re
pattern = re.compile('\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}')
matched = re.match(pattern, '192.12.23.32')
print(matched.group())

具体可以参考Python 正则表达式文档。个人觉得不是很容易读懂,只能边用边积累,而且一不用就忘光光。故此写下笔记用作日后查询。

以下解释一下代码。

re是python regular expression的包。
re.compile是把表达式先编译好成状态机,如果要后面重复使用这个pattern的话会快一点。
re.match第一个参数是pattern,第二个参数是string。pattern也可以用string代替。

matched = re.match('\d{1,3}.\d{1,3}.\d{1,3}.\d{1,3}', '192.12.23.32')

match是从头开始找,如果在中间可以用re.search。

\d是数字,{1,3}是一到3个。\d{1,3}是1到3个数字。\.是一个点。如果不加\,.表示任意字符。