设计模式

工厂模式

工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。

在工厂模式中,我们在创建对象时不会对客户端暴露创建逻辑,并且是通过使用一个共同的接口来指向新创建的对象。

主要解决:主要解决接口选择的问题。

优点: 1、一个调用者想创建一个对象,只要知道其名称就可以了。 2、扩展性高,如果想增加一个产品,只要扩展一个工厂类就可以。 3、屏蔽产品的具体实现,调用者只关心产品的接口。

缺点:每次增加一个产品时,都需要增加一个具体类和对象实现工厂,使得系统中类的个数成倍增加,在一定程度上增加了系统的复杂度,同时也增加了系统具体类的依赖。这并不是什么好事。

使用场景: 1、日志记录器:记录可能记录到本地硬盘、系统事件、远程服务器等,用户可以选择记录日志到什么地方。 2、数据库访问,当用户不知道最后系统采用哪一类数据库,以及数据库可能有变化时。 3、设计一个连接服务器的框架,需要三个协议,"POP3"、"IMAP"、"HTTP",可以把这三个作为产品类,共同实现一个接口。

注意事项:作为一种创建类模式,在任何需要生成复杂对象的地方,都可以使用工厂方法模式。有一点需要注意的地方就是复杂对象适合使用工厂模式,而简单对象,特别是只需要通过 new 就可以完成创建的对象,无需使用工厂模式。如果使用工厂模式,就需要引入一个工厂类,会增加系统的复杂度。

单例模式

单例模式(Singleton Pattern)是 Java 中最简单的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。

这种模式涉及到一个单一的类,该类负责创建自己的对象,同时确保只有单个对象被创建。这个类提供了一种访问其唯一的对象的方式,可以直接访问,不需要实例化该类的对象。

意图:保证一个类仅有一个实例,并提供一个访问它的全局访问点。

主要解决:一个全局使用的类频繁地创建与销毁。

何时使用:当您想控制实例数目,节省系统资源的时候。

如何解决:判断系统是否已经有这个单例,如果有则返回,如果没有则创建。

关键代码:构造函数是私有的。

应用实例:

  • 1、一个班级只有一个班主任。
  • 2、Windows 是多进程多线程的,在操作一个文件的时候,就不可避免地出现多个进程或线程同时操作一个文件的现象,所以所有文件的处理必须通过唯一的实例来进行。
  • 3、一些设备管理器常常设计为单例模式,比如一个电脑有两台打印机,在输出的时候就要处理不能两台打印机打印同一个文件。

优点:

  • 1、在内存里只有一个实例,减少了内存的开销,尤其是频繁的创建和销毁实例(比如管理学院首页页面缓存)。
  • 2、避免对资源的多重占用(比如写文件操作)。

缺点:没有接口,不能继承,与单一职责原则冲突,一个类应该只关心内部逻辑,而不关心外面怎么样来实例化。

使用场景:

  • 1、要求生产唯一序列号。
  • 2、WEB 中的计数器,不用每次刷新都在数据库里加一次,用单例先缓存起来。
  • 3、创建的一个对象需要消耗的资源过多,比如 I/O 与数据库的连接等。

注意事项:getInstance() 方法中需要使用同步锁 synchronized (Singleton.class) 防止多线程同时进入造成 instance 被多次实例化。

建造者模式

主要解决:主要解决在软件系统中,有时候面临着"一个复杂对象"的创建工作,其通常由各个部分的子对象用一定的算法构成;由于需求的变化,这个复杂对象的各个部分经常面临着剧烈的变化,但是将它们组合在一起的算法却相对稳定。

适配器模式

适配器模式(Adapter Pattern)是作为两个不兼容的接口之间的桥梁。这种类型的设计模式属于结构型模式,它结合了两个独立接口的功能。

这种模式涉及到一个单一的类,该类负责加入独立的或不兼容的接口功能。举个真实的例子,读卡器是作为内存卡和笔记本之间的适配器。您将内存卡插入读卡器,再将读卡器插入笔记本,这样就可以通过笔记本来读取内存卡。

意图:将一个类的接口转换成客户希望的另外一个接口。适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。

image

观察者模式

当对象间存在一对多关系时,则使用观察者模式(Observer Pattern)。比如,当一个对象被修改时,则会自动通知依赖它的对象。观察者模式属于行为型模式。

意图:定义对象间的一种一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并被自动更新。

主要解决:一个对象状态改变给其他对象通知的问题,而且要考虑到易用和低耦合,保证高度的协作。

何时使用:一个对象(目标对象)的状态发生改变,所有的依赖对象(观察者对象)都将得到通知,进行广播通知。

策略模式

意图:定义一系列的算法,把它们一个个封装起来, 并且使它们可相互替换。

主要解决:在有多种算法相似的情况下,使用 if...else 所带来的复杂和难以维护。

何时使用:一个系统有许多许多类,而区分它们的只是他们直接的行为。

如何解决:将这些算法封装成一个一个的类,任意地替换。

关键代码:实现同一个接口。

Python相关知识

迭代器

迭代是访问集合元素的一种方式。迭代器是一个可以记住遍历的位置的对象。迭代器对象从集合的第一 个元素开始访问,直到所有的元素被访问完结束。迭代器只能往前不会后退。

生成器

而生成器本身就是一个迭代器

返回可迭代项集的函数称为生成器。

在 Python 中,使用了 yield 的函数被称为生成器(generator)。

在调用生成器运行的过程中,每次遇到 yield 时函数会暂停并保存当前所有的运行信息,返回 yield 的值, 并在下一次执行 next() 方法时从当前位置继续运行。

内置函数

map()

会根据提供的函数对指定序列做映射

map(function, iterable, ...)

list(map(lambda x: x ** 2, [1, 2, 3, 4, 5]))   # 使用 lambda 匿名函数
>>> [1, 4, 9, 16, 25]

zip()

 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表。

如果各个迭代器的元素个数不一致,则返回列表长度与最短的对象相同,利用 * 号操作符,可以将元组解压为列表。

>>>a = [1,2,3]
>>> b = [4,5,6]
>>> c = [4,5,6,7,8]
>>> zipped = zip(a,b)     # 返回一个对象
>>> zipped
<zip object at 0x103abc288>
>>> list(zipped)  # list() 转换为列表
[(1, 4), (2, 5), (3, 6)]
>>> list(zip(a,c))              # 元素个数与最短的列表一致
[(1, 4), (2, 5), (3, 6)]

zip() 和 * 操作符一起操作可以用来 unzip 一个列表,看下面的代码:

import numpy as np
a=[1,2,3]
b=[4,5,6]
c=[7,8,9]
zz=zip(a,b,c)
print(zz)

x,y,z=zip(*zz)
print(x)
print(y)
print(z)

输出:
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
(1, 2, 3)
(4, 5, 6)
(7, 8, 9)

await/async

async def async_fun():
    return 1

if __name__ == '__main__':
    print(async_fun())  # <coroutine object fun at 0x0000000002156E08>
    print(async_fun().send(None))  # StopIteration: 1
    try:
        async_fun().send(None)
    except StopIteration as e:
        print(e.value)

异步函数的调用返回的是一个协程对象,若改对象通过send()进行调用,会报一个StopIteration错,若要取值,就需要捕获该异常,e.value的形式进行获取。

在协程函数中,可以通过await语法来挂起自身的协程,并等待另一个协程完成直到返回结果:

async def async_function():
    return 1

async def await_coroutine():
    result = await async_function()
    print(result)
    
run(await_coroutine())
# 1

python的GIL

GIL 是python的全局解释器锁,同一进程中假如有多个线程运行,一个线程在运行python程序的时候会霸占python解释器(加了一把锁即GIL),使该进程内的其他线程无法运行,等该线程运行完后其他线程才能运行。如果线程运行过程中遇到耗时操作,则解释器锁解开,使其他线程运行。所以在多线程中,线程的运行仍是有先后顺序的,并不是同时进行。

多进程中因为每个进程都能被系统分配资源,相当于每个进程有了一个python解释器,所以多进程可以实现多个进程的同时运行,缺点是进程系统资源开销大

classmethod 修饰符

classmethod 修饰符对应的函数不需要实例化,不需要 self 参数,但第一个参数需要是表示自身类的 cls 参数,可以来调用类的属性,类的方法,实例化对象等。

class A:

    a=1
    def __init__(self):
        pass
    def do(self):
        print(self.a)
    @classmethod
    def hhh(cls):
        print(cls.a)
        cls.do() ##就会有问题 cls().do()才对,cls在这里相当于A
    
if __name__ == '__main__':
    A.hhh() #不需要实例化

简单题目

1、两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9

输出:[0,1]

解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6

输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6

输出:[0,1]

提示:

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

只会存在一个有效答案

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

注意这种看似简单但不要暴力计算的题,拿一个数组或者哈希表,保存已经计算过的数据

这个题就是拿一个数组或者哈希表,要找target,就用list[nun-target]=index保存

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        a={}
        for i,num in enumerate(nums):
            if target-num in a.keys():
                return [i,a[target-num]]
            a[num]=i
class Solution {
    public int[] twoSum(int[] nums, int target) {
         HashMap<Integer,Integer> hashMap=new HashMap<>();
            for(int i=0;i<nums.length;i++){
                if(hashMap.containsKey(target-nums[i])){
                    return new int[]{i,hashMap.get(target-nums[i])};
                }
                else{
                    hashMap.put(nums[i],i);
                }
            }
            return null;
    }
}

7、整数反转

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

示例 1:

输入:x = 123

输出:321

示例 2:

输入:x = -123

输出:-321

示例 3:

输入:x = 120

输出:21

示例 4:

输入:x = 0

输出:0

class Solution {
    public int reverse(int x) {
        long n = 0;
        while(x != 0) {
            n = n*10 + x%10;
            x = x/10;
        }
        return (int)n==n? (int)n:0;
    }
}   

以下就是非常偷懒的做法,但是居然还挺快???

def reverse( x: int) -> int:
    a=x if x>0 else -x
    l=list(str(a))
    l.reverse()
    if x>0:
        ab=int("".join(l))
    else:
        ab=-1*int("".join(l))
    if ab>2147483647 or ab<-2147483648:
        return 0
image.png

9、回文数

给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。

回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。例如,121 是回文,而 123 不是。

示例 1:

输入:x = 121

输出:true

示例 2:

输入:x = -121

输出:false

解释:从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

输入:x = 10

输出:false

解释:从右向左读, 为 01 。因此它不是一个回文数。

示例 4:

输入:x = -101

输出:false

提示:

  • -231 <= x <= 231 - 1

进阶:你能不将整数转为字符串来解决这个问题吗?

双指针,一个从头一个从尾,写就完了


13、罗马数字转整数

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

字符          数值

I             1

V             5

X             10

L             50

C             100

D             500

M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。

X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 

C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III"

输出: 3

示例 2:

输入: "IV"

输出: 4

示例 3:

输入: "IX"

输出: 9

示例 4:

输入: "LVIII"

输出: 58

解释: L = 50, V= 5, III = 3.

示例 5:

输入: "MCMXCIV"

输出: 1994

解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示:

  • 1 <= s.length <= 15
  • s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
  • 题目数据保证 s 是一个有效的罗马数字,且表示整数在范围 [1, 3999] 内
  • 题目所给测试用例皆符合罗马数字书写规则,不会出现跨位等情况。
  • IL 和 IM 这样的例子并不符合题目要求,49 应该写作 XLIX,999 应该写作 CMXCIX 。
  • 关于罗马数字的详尽书写规则,可以参考 罗马数字 - Mathematics 。

我的思路是,罗马数字中只有 IV,IX,XL,XC,CD,CM六中特殊情况,别的是多少加多少就行

所以先计算一个序列中这六种情况,计算完之后从序列中删除

class Solution {
    public int romanToInt(String s) {
        int r=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='I'&&(i+1)<s.length()&&s.charAt(i+1)=='V'){
                r+=4;
                i++;
            }
            else if(s.charAt(i)=='I'&&(i+1)<s.length()&&s.charAt(i+1)=='X'){
                r+=9;
                i++;
            }
            else if(s.charAt(i)=='X'&&(i+1)<s.length()&&s.charAt(i+1)=='L'){
                r+=40;
                i++;
            }
            else if(s.charAt(i)=='X'&&(i+1)<s.length()&&s.charAt(i+1)=='C'){
                r+=90;
                i++;
            }
            else if(s.charAt(i)=='C'&&(i+1)<s.length()&&s.charAt(i+1)=='D'){
                r+=400;
                i++;
            }
            else if(s.charAt(i)=='C'&&(i+1)<s.length()&&s.charAt(i+1)=='M'){
                r+=900;
                i++;
            }
            else if(s.charAt(i)=='I') r+=1;
            else if(s.charAt(i)=='V') r+=5;
            else if(s.charAt(i)=='X') r+=10;
            else if(s.charAt(i)=='L') r+=50;
            else if(s.charAt(i)=='C') r+=100;
            else if(s.charAt(i)=='D') r+=500;
            else if(s.charAt(i)=='M') r+=1000;
        }
        return r;
    }
}

14、最常公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例 1:

输入:strs = ["flower","flow","flight"]

输出:"fl"

示例 2:

输入:strs = ["dog","racecar","car"]

输出:""

解释:输入不存在公共前缀。

提示:

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

大概有这五种思路, 一般都会采用第四种, 但是耗时太多

1、所求的最长公共前缀子串一定是每个字符串的前缀子串。所以随便选择一个字符串作为标准,把它的前缀串,与其他所有字符串进行判断,看是否是它们所有人的前缀子串。这里的时间性能是O(m*n*m)。

2、列出所有的字符串的前缀子串,将它们合并后排序,找出其中个数为n且最长的子串。时间性能为O(n*m+m*n*log(m*n))

3、纵向扫描:从下标0开始,判断每一个字符串的下标0,判断是否全部相同。直到遇到不全部相同的下标。时间性能为O(n*m)。

4、横向扫描:前两个字符串找公共子串,将其结果和第三个字符串找公共子串……直到最后一个串。时间性能为O(n*m)。

5、借助trie字典树。将这些字符串存储到trie树中。那么trie树的第一个分叉口之前的单分支树的就是所求。

class Solution {
    public String longestCommonPrefix(String[] strs) {
         if(strs.length==0){
            return "";
        }
        if(strs.length==1){
            return strs[0];
        }
        if(strs[0].length()==0){
            return "";
        }
        String r="";
        int p=0;
        int min=strs[0].length();
        for (String s:strs){
            if(s.length()<min){
                min=s.length();
            }
        }
        while (true){
            if(p>=min){
                r=strs[0].substring(0,p);
                break;
            }
            char temp=strs[0].charAt(p);
            for(int i=1;i<strs.length;i++){
                if(temp==strs[i].charAt(p)){
                    continue;
                }
                else {
                    r=strs[0].substring(0,p);
                    return r;
                }
            }
            p++;

        }
        return r;
    }
}

20、有效的括号

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

示例 1:

输入:s = "()"

输出:true

示例 2:

输入:s = "()[]{}"

输出:true

示例 3:

输入:s = "(]"

输出:false

示例 4:

输入:s = "([)]"

输出:false

示例 5:

输入:s = "{[]}"

输出:true

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

单纯入栈出栈就行了,最简单的一类题目

class Solution {
    public boolean match(char a,char b){
        if((a=='('&&b==')')||(a==')'&&b=='(')) return true;
        if((a=='['&&b==']')||(a==']'&&b=='[')) return true;
        if((a=='{'&&b=='}')||(a=='}'&&b=='{')) return true;
        return false;
    }
    public boolean isValid(String s) {
        LinkedList<Character> heap=new LinkedList<Character>();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='{'||s.charAt(i)=='['||s.charAt(i)=='('){
                heap.add(s.charAt(i));
            }else {
                if(heap.size()==0){
                    return false;
                }
                char t=heap.getLast();
                heap.removeLast();
                if(match(s.charAt(i),t)){
                    continue;
                }else {
                    return false;
                }
            }
        }
        if(heap.size()!=0){
            return false;
        }
        return true;
    }
}

数据库相关

基础概念

1、事务的四大特性

  • 原子性:要么全都执行,要么不执行
  • 隔离性:针对数据资源的并发访问,规定了事务之间相互影响程度
  • 为了避免脏读,所以所有操作全部执行之前其他会话不能看到执行过程
  • 避免幻读,将整张表锁住
  • 一致性:事务执行前后,数据总额要一致
  • 持久性:事务一旦提交,对数据的改变是永久性的

2、索引

  • 索引类型
  • Hash 等值查询效率高,不能拍讯,不能进行范围查找
  • B+ 数据有序,范围查询
  • 索引最大的好处就是提升查询速度
  • 缺点是更新数据效率低
  • 对进行频繁查超的数据建立索引,对频繁更改的数据不建议使用索引

3、为什么用B+树做索引

  • 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

4、Sql优化

  • 尽量走索引
  • 子查询变成left join
  • 慢查询日志
  • 它用来记录在MySQL中响应时间超过阀值的语句,具体指运行时间超过long_query_time值的SQL,则会被记录到慢查询日志中。long_query_time的默认值为10,意思是运行10S以上的语句。

5、JOIN

  • JOIN: 如果表中有至少一个匹配,则返回行
  • LEFT JOIN: 即使右表中没有匹配,也从左表返回所有的行
  • RIGHT JOIN: 即使左表中没有匹配,也从右表返回所有的行
  • FULL JOIN: 只要其中一个表中存在匹配,就返回行