尚硅谷Java面试题

再找不到工作怎么办

基础篇

i++热身

只要记住i++和++i的区别即可,i++就是先把i的原值进行操作,操作完后进行加,所以输出的是2,然后i的值加了1*,所以第三行i++的值还是2,而++i则表示先给i+1,然后进行操作,所以会先改变i的值,当然如果是单独的i++或者++i是一样的.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class IPlusPlus {
    public static void main(String[] args) {
        int i = 1;

        System.out.println("i: " + i);  // 1
        System.out.println("++i: " + ++i);  // 2
        System.out.println("i++: " + i++); // 2
        System.out.println("i: " + i); // 3
        System.out.println("--i: " + --i); // 2
        System.out.println("i--: " + i--); // 2
        System.out.println("i: " + i); // 1
    }
}

你知道服务可用性多少个9是什么意思

可用性级别,9越多,可用性越高
20240724104946

Arrays.asList()把数组转换成集合大坑

使用Arrays.asList()得到的ArrayList是继承自AbstractList,实现了List接口,它重写的add(),remove()等修改List结构的方法,并直接抛出异常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}

/**
 * @serial include
 */
private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable

// =================
public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

对于集合和数组之间的转换,还有一个list.toArray(),将集合转换为数组,这样的转换生成的数组是一个新的数组,和原集合没有关系,所以修改集合的值,并不会影响数组的值,反之亦然.

但是如果实在想改:

1
2
3
4
5
6
7
// 如果真想用asList后还想修改
public static void test() {
    Integer[] array = new Integer[]{1, 2, 3, 4, 5};
    List<Integer> list = new ArrayList<>(Arrays.asList(array));
    list.add(6);
    list.forEach(System.out::println);
}

遍历集合时remove或add操作注意事项

遍历迭代时remove掉一个元素,会导致程序抛出异常:java.util.ConcurrentModificationException

不要在foreach循环里进行元素的remove/add操作,remove元素请使用iterator方式,如果并发操作,需要对iterator对象加锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class IteratorRemoveDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(11);
        list.add(12);
        list.add(13);
        list.add(14);
        list.add(15);

        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer value = iterator.next();
            if (value == 12) {
                // list.remove(value); java.util.ConcurrentModificationException
                iterator.remove();
            }
        }
        list.forEach(System.out::println);
    }
}

源码:

1
2
3
4
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

hashcode冲突案例

java中什么是hashcode?它属于哪个类的方法？
hashcode是一个对象方法,用于返回对象的散列码,这个方法是Object类中的

题外题:说出Object的5个常用方法:

  1. equals
  2. hashCode
  3. toString
  4. wait
  5. notify

哈希冲突是什么意思,你写一个冲突的案例看看

哈希冲突是指不同对象得到的哈希值相同

一般来说10万以上才会起冲突

案例:使用HashSet来存放对象的hashcode,判断集合中是否有这个hashcode,有了就是重复了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package com.zzmr;

import java.util.HashSet;

/**
 * @author zzmr
 * @create 2024-07-26 13:52
 */
public class HashConflictDemo {
    static class Book {
        int id;
    }

    public static void main(String[] args) {
        // m1();

        // 正常new对象时，new多少次会有可能出现hash编码冲突
        HashSet<Integer> hashSet = new HashSet<>(); // 无序无重复
        for (int i = 1; i <= 11 * 10000; i++) {
            int bookHashCode = new Book().hashCode();
            if (hashSet.contains(bookHashCode)) {
                // 重复了
                System.out.println("发生了hash冲突,在: " + i + "值是: " + bookHashCode);
                /**
                 * 发生了hash冲突,在: 105713值是: 2134400190
                 * 109999
                 */
            } else {
                hashSet.add(bookHashCode);
            }
        }

        System.out.println(hashSet.size());

    }

    private static void m1() {
        System.out.println("AA".hashCode());
        System.out.println("BB".hashCode());
        System.out.println("+==+");

        System.out.println("Aa".hashCode());
        System.out.println("BB".hashCode());
        System.out.println("+==+");

        System.out.println("柳柴".hashCode());
        System.out.println("柴柕".hashCode());
        System.out.println("+==+");
    }
}

整型包装类Integer

Integer的构造方法从java8以后有变动,在java17中,Integer的构造方法已经被弃用了
20240726144148

推荐使用的是Integer.valueOf(xxx)

Integer在使用时,数值如何比较

阿里手册:所有整型包装类对象之间值的比较,全部使用equals方法比较
对于Integer var = ?在-128至127之间的赋值,Integer对象是在IntegerCache.cache产生,会复用已有对象,这个区间内的Integer值可以直接使用==进行判断,但是这个区间之外的所有数据,都会在堆上产生,并不会复用已有的对象,这是一个大坑,推荐使用equals进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class IntegerBugDemo {

    public static void main(String[] args) {
        // Integer i = Integer.valueOf(123);

        Integer a = Integer.valueOf(600);
        Integer b = Integer.valueOf(600);
        int c = 600;
        System.out.println(a == b);  // 这两个不相等是因为比较的是对象,而600>127,所以对象没有复用,所以不相等
        System.out.println(a.equals(b)); // equals比较大小
        System.out.println(a == c); // 比较大小,没得说

        System.out.println("===============");

        Integer x = Integer.valueOf(99);
        Integer y = Integer.valueOf(99);
        System.out.println(x == y);  // 在127以内,所以对象复用,所以相等
        System.out.println(x.equals(y));
    }
}

源码:
20240726150253

BigDecimal的坑

金额处理使用什么类型?精度如何处理?

BigDecimal用于对超过16位有效位的数进行精确运算

由BigDecimal创建的对象不能使用传统的+-*/等算术运算符直接对其对象进行数学运算,而必须调用其相应的方法,方法中的参数也必须是BigDecimal的对象,构造器是类的特殊方法,专门用来创建对象,特别是带有参数的对象

阿里手册

  1. BigDecimal的等值比较应使用compareTo()方法,而不是equals()方法,因为compareTo会忽略精度比较,equals比较1.0和1.00时,得到的结果为false
  2. 禁止使用构造方法BigDecimal(double)的方式把double值转化为BigDecimal对象-存在精度损失风险
  3. 浮点数之间的等值判断,基本数据类型不能使用==进行比较,包装数据类型不能使用equals进行判断
  4. 除法商的结果,需要指定精度,BigDecimal的8种RoundingMode舍入模式:https://my.oschina.net/u/3644969/blog/4927776,记住ROUND_HALF_UP,即四舍五入
  5. 科学计数

总结就是,如果要创建BigDecimal对象,最好使用new BigDecimal(String)的构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class BigDecimalDemo {
    public static void main(String[] args) {
        // m1();

        // m2();

        // m3();

        // m4();

        m5();

    }

    private static void m5() {
        // BigDecimal b1 = BigDecimal.valueOf(113213121312.431228491323);
        BigDecimal b1 = new BigDecimal("113213121312.431228491323");  // 建议这种
        System.out.println(b1);
        System.out.println(b1.toPlainString());  // 不使用科学计数法
    }

    private static void m4() {
        BigDecimal b1 = new BigDecimal("0.2");
        BigDecimal b2 = new BigDecimal("0.3");
        System.out.println(b1.divide(b2, 2, RoundingMode.HALF_UP)); // 四舍五入,保留两位
    }

    private static void m1() {
        BigDecimal bigDecimal1 = new BigDecimal(0.1); // 精度损失
        BigDecimal bigDecimal2 = new BigDecimal("0.1"); // 没问题-优先推荐
        System.out.println(bigDecimal1);
        System.out.println(bigDecimal2);
        BigDecimal bigDecimal3 = BigDecimal.valueOf(0.3); // 没问题
        System.out.println(bigDecimal3);
        System.out.println(bigDecimal3.subtract(bigDecimal2));
    }

    private static void m2() {
        /**
         * double类型的两个参数相减会转换为二进制,因为double有效位数为16位,这就会出现存储小数位数不够的情况,这种情况下就会出现误差
         */
        double d1 = 0.03;
        double d2 = 0.01;
        System.out.println(d1 - d2); // 0.019999999999999997
    }

    private static void m3() {
        BigDecimal b1 = new BigDecimal("0.10");
        BigDecimal b2 = new BigDecimal("0.1");
        System.out.println(b1.equals(b2));  // false  不建议这么比
        System.out.println(b1 == b2);  // false   不建议这么比
        System.out.println(b1.compareTo(b2));  // 0 表示一样大
    }
}

编码最佳实践

ArithmeticUtils.java下载

如何去除list中的重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public class ListDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(92, 20, 99, 1, 2, 99, 3, 4, 4, 5));
        System.out.println(list);

        // m1(list);
        // m2(list);
        // m3(list);
        // m4(list);
        // m5(list);

    }

    /**
     * 根据值来删除
     *
     * @param list
     */
    private static void m5(List<Integer> list) {
        List<Integer> newList = new ArrayList<>(list);
        for (int i = 0; i < newList.size() - 1; i++) {
            for (int j = newList.size() - 1; j > i; j--) {
                if (newList.get(i).equals(newList.get(j))) {
                    newList.remove(i);
                }
            }
        }
        System.out.println("去重后: " + newList);
    }

    private static void m4(List<Integer> list) {
        // 使用两个集合来实现,一个集合负责遍历,一个集合负责删除
        List<Integer> newList = new ArrayList<>(list);
        for (Integer i : list) {
            if (newList.indexOf(i) != newList.lastIndexOf(i)) {
                newList.remove(newList.indexOf(i));
            }
        }
        System.out.println("去重后: " + newList);

        // 使用迭代器
        /*Iterator<Integer> iterator = list.iterator();

        while (iterator.hasNext()) {
            Integer value = iterator.next();
            if (list.indexOf(value) != list.lastIndexOf(value)) {
                // 重复-删除
                iterator.remove();
            }
        }
        System.out.println("去重后: " + list);
        */
    }

    /**
     * 流式计算
     *
     * @param list
     */
    private static void m3(List<Integer> list) {
        List<Integer> newList = new ArrayList<>();
        newList = list.stream().distinct().collect(Collectors.toList());
        System.out.println("去重后: " + newList);
    }

    /**
     * for循环遍历是否存在
     *
     * @param list
     */
    private static void m2(List<Integer> list) {
        List<Integer> newList = new ArrayList<>();
        for (Integer i : list) {
            if (!newList.contains(i)) {
                // 有
                newList.add(i);
            }
        }
        System.out.println("去重后: " + newList);
    }

    /**
     * 使用HashSet去重
     *
     * @param list
     */
    private static void m1(List<Integer> list) {
        // 去重
        Set<Integer> set = new HashSet<>(list);
        // 去重且保留原位置-因为LinkedHashSet是有序无重复的
        // Set<Integer> set = new LinkedHashSet<>(list);
        System.out.println("去重后: " + set);
    }
}

equals和==对比

  • ==可用于基本数据类型和引用数据类型的比较,若为基本,则比较值,若为引用,则比较地址
  • equals是Object的方法,只能用于比较引用类型,但究竟是如何比的,要看是否被重写过,而Object默认的equals如下,也是直接使用==比较,比较地址
    1
    2
    3
    public boolean equals(Object obj) {
        return (this == obj);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class EqualsDemo {
    public static void main(String[] args) {
        String s1 = new String("abc");
        String s2 = new String("abc");
        System.out.println(s1 == s2); // false  new出来的 内存地址不一致
        System.out.println(s1.equals(s2)); // true

        Set<String> set01 = new HashSet<>();
        set01.add(s1);
        set01.add(s2);
        System.out.println(set01.size()); // 1  hashSet的无重复-底层是HashMap,在put时,会使用hashcode方法判断,String类重写了hashcode,所以这里才会为1
        System.out.println(s1.hashCode() + "\t" + s2.hashCode());

        System.out.println("=====================");
        Person p1 = new Person("abc");
        Person p2 = new Person("abc");
        System.out.println(p1 == p2);  // false
        System.out.println(p1.equals(p2));  // false
        Set<Person> set02 = new HashSet<>();
        set02.add(p1);
        set02.add(p2);
        System.out.println(set02.size()); // 2
        System.out.println(p1.hashCode() + "\t" + p2.hashCode());

    }
}

传值还是传引用

  • 基本类型（如 int）是按值传递的， 因此方法内部的修改不会影响原始变量。
  • 对象引用（如 Person）是按引用传递的， 因此方法内部对对象的修改会影响原始对象。
  • 不可变对象（如 String）也是按引用传递的， 但方法内部的重新赋值不会影响方法外的原始引用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class ValueOrRef {

    public void changeValue1(int age) {
        age = 30;
    }

    public void changeValue2(Person person) {
        person.setPersonName("xxx");
    }

    public void changeValue3(String str) {
        str = "xxx";
    }

    public static void main(String[] args) {

        ValueOrRef test = new ValueOrRef();
        int age = 20;
        test.changeValue1(age);
        System.out.println("age----" + age); // 20

        Person person = new Person("abc");
        test.changeValue2(person);
        System.out.println("personName----" + person.getPersonName()); // xxx

        String str = "abc";
        test.changeValue3(str);
        System.out.println("String----" + str);  //  abc

    }

}

深拷贝+浅拷贝

对象拷贝就是将一个对象的属性拷贝到另一个有着相同类型的对象中去

  • 浅拷贝只复制指向某个对象的指针,而不复制对象本身,新旧对象还是共享一块内存,类似一个分支
    • 拷贝基本类型:拷贝的就是基本类型的值
    • 拷贝引用类型:拷贝的就是内存地址,因此如果其中一个对象改变了值,就会影响到另一个对象,即为多个引用指向同一个对象
  • 深拷贝会另外创造一个一摸一样的对象新对象跟原对象不共享内存,修改新对象不会改到原对象,深拷贝拷贝了原对象的所有值,所以即使原对象的值发生变化时,拷贝对象的值也不会改变

20240728153029

深拷贝的作用:

  1. 避免共享引用
  2. 线程安全

Cloneable接口,和序列化Serializable接口一样,都是空的

1
2
public interface Cloneable {
}

如果某个类没有实现Cloneable接口直接使用clone方法,则会抛出异常,实现接口后,可使用clone来实现浅拷贝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
@Data
@AllArgsConstructor
@NoArgsConstructor
public class ShallowDeepDemo implements Cloneable {

    private String name;

    private Integer age;

    public static void main(String[] args) throws CloneNotSupportedException {
        Emp emp = new Emp("z3", 15, "雷军", "CEO");
        System.out.println("原始对象: " + emp.getBoss().getTitle() + " " + emp.getAge());

        Emp emp2 = (Emp) emp.clone();
        System.out.println("拷贝对象: " + emp2.getBoss().getTitle() + " " + emp.getAge());

        System.out.println();
        emp2.getBoss().setTitle("CTO");
        emp2.setAge(20);
        System.out.println("----emp2拷贝对象修改Title=CTO,age=20,是否会影响原始对象");

        // emp对象中的对象属性中的title变了,但是emp的基本属性并没有变
        System.out.println("原始对象: " + emp.getBoss().getTitle() + " " + emp.getAge());
        System.out.println("拷贝对象: " + emp2.getBoss().getTitle() + " " + emp.getAge());

    }
}


@Data
@AllArgsConstructor
@NoArgsConstructor
class Boss implements Cloneable {
    private String bossName;
    private String title;

    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
}

@Data
@NoArgsConstructor
@AllArgsConstructor
class Emp implements Cloneable {
    private String empName;
    private Integer age;

    private Boss boss;

    public Emp(String empName, Integer age, String bossName, String title) {
        this.empName = empName;
        this.age = age;
        this.boss = new Boss(bossName, title);
    }

/*    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }*/

    // 自写深拷贝
    @Override
    protected Object clone() throws CloneNotSupportedException {
        return new Emp(empName, age, boss.getBossName(), boss.getTitle());
    }
}

IDEA工具

如何使用Debug并说出3个常用的Debug快捷键

20240729102916

Trace current stream chain
20240729170016

20240729170628

断点的四种类别

20240729185612

  1. Line Breakpoint 单行断点
  2. Method Breakpoint 接口方法断点
  3. Field Watchpoint 变量断点
  4. Exception Breakpoint 异常断点

20240730162029

Test

单元测试应该是全自动执行的，并且是非交互式的，测试用例通常是被定期执行的，执行过程必须完全自动化才有意义，输出结果需要人工检查的测试不是一个好的单元测试，不能使用System.out()来进行人肉验证,单元测试必须使用assert来验证.

好的单元测试应该遵守AIR原则

  • A自动化
  • I独立性
  • R可重复

简单的断言:

1
2
3
4
5
6
7
8
9
10
@Test
void add() {
    CalcDemo calcDemo = new CalcDemo();
    // System.out.println(calcDemo.add(2, 2)); // 看到绿条不一定正确,不能使用System.out
    int retValue1 = calcDemo.add(2, 2);
    int retValue2 = calcDemo.add(2, 3);
    assertEquals(4, retValue1);
    // 看到绿条+使用了assert断言也不一定正确,为什么单元测试的多样性和覆盖率如此重要---方法逻辑出错-恰好结果和正确的逻辑一样
    assertEquals(5, retValue2);
}

有关覆盖率
20240804201659

还有就是BeforeEach和AfterEach以及BeforeAll和AfterAll

  • BeforeAll:所有@Test测试方法调用前执行一次,在测试类没有实例化之前就已被加载,需要static修饰
  • @AfterAll:所有测试方法调用后执行一次,在测试类没有实例化之前就已被加载,需用static修饰
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class CalcDemoTestV2 {

    CalcDemo calcDemo = null;

    static StringBuffer stringBuffer = null;

    @BeforeAll
    static void m1() {
        stringBuffer = new StringBuffer("abc");
        System.out.println("===================: " + stringBuffer.length());
    }

    @AfterAll
    static void m2() {
        System.out.println("===================: " + stringBuffer.append(" ,end").toString());
    }

    @BeforeEach
    void setUp() {
        System.out.println("---come in BeforeEach");
        calcDemo = new CalcDemo();
    }

    @AfterEach
    void tearDown() {
        System.out.println("---come in AfterEach");
        calcDemo = null;
    }

    @Test
    void add() {
        Assertions.assertEquals(5, calcDemo.add(1, 4));
        assertEquals(5, calcDemo.add(2, 3));
    }

    @Test
    void sub() {
        assertEquals(5, calcDemo.sub(10, 5));
    }
}

输出:

1
2
3
4
5
6
===================: 3
---come in BeforeEach
---come in AfterEach
---come in BeforeEach
---come in AfterEach
===================: abc ,end

LeetCode算法题

概念

一个算法的好坏是通过时间复杂度与空间复杂度来衡量的,简单来说,所花时间与占用内存便是衡量一个算法好坏的标准

常见的时间复杂度

  • 常数阶O(1):hashMap的get
  • 对数阶O(logN):二分查找
  • 线性阶O(N):单层for循环
  • 线性对数阶O(nlogN)
    1
    2
    3
    4
    5
    6
    7
    8
    private static void nlogn(int n) {
        int count = 1;
        for (int i = 0; i < n; i++) {
            while (count <= n) {
                count = count * 2;
            }
        }
    }
  • 平方阶:双层for循环,但是循环条件应该一样,如果循环条件不一样,应该是O(n*m)

如何刷?先从母题开始刷
20240807161440

双指针母题:
20240807161659

双指针技巧

  • 只要数组有序,就应该想到双指针技巧
  • 双指针技巧主要分为两类,左右指针和快慢指针
    • 左右指针,可能想向,可能相背,多用于数组
    • 前后指针-slow/fast

左右指针口诀

  • 结果比目标,小了要变大,左针右移
  • 结果比目标,大了要变小,右针左移

快慢指针口诀

  • 快慢相等值不变,慢针不动快针走
  • 快慢不等值,我是题型一,慢针向前一步走,快针赋值给慢针,快针向前一步走
  • 快慢不等值,我是题型二,快针赋值给慢针,慢针向前一步走,快针向前一步走

1两数之和

这道题,起点亦是终点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class TwoNums {
    public static void main(String[] args) {
        int[] nums = new int[]{2, 5, 5, 11};
        int[] result = twoSum2(nums, 10);
        for (int i : result) {
            System.out.println(i);
        }
    }

    /*
    暴力
     */
    public static int[] twoSum1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

    public static int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            int param = target - nums[i];
            if (map.containsKey(param)) {
                return new int[]{map.get(param), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}

总结就是判断map中是否有,有就可以返回结果了,没有就是将这个数的值作为map的键,下标作为map的值存入map

如果有两个数字相同,比如5,5,target是10,此时,当num[i]第一次等于5时,此时map中不可能有5,所以将这个数以及下标存入map,而当nums[i]又一次等于5时,此时的5和map之前存的5就是target了,所以返回结果return new int[]{map.get(param),i}

344反转字符串

只在原数组上进行操作,不能创建新的数组,所以就可以交换首尾指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void reverse(char[] s) {

    int left = 0;  // 左指针
    int right = s.length - 1;  // 右指针
    while (left < right) {
        // 先交换
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;

        // 移动指针
        left++;
        right--;
    }
}

167两数之和-输入有序数组

和之前的题区别在于,这里是递增的数组,那么就可以使用双指针来解决这个问题

两数相加,大了就让右指针左移,小了就让左指针右移,相等就输出,就这么简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int[] twoSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        if (nums[left] + nums[right] == target) {
            return new int[]{left + 1, right + 1};
        } else if (nums[left] + nums[right] > target) {
            right--;
        } else if (nums[left] + nums[right] < target) {
            left++;
        }
    }
    return null;
}

704二分查找

中间下标就是两下标相加除2,如果这个中间值大了target,那么就让right等于middle-1,如果这个中间值小于target,那么就让left等于middle+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int search(int[] arraySorted, int target) {
    int left = 0;
    int right = arraySorted.length - 1;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (arraySorted[middle] == target) {
            return middle;
        } else if (arraySorted[middle] < target) {
            left = middle + 1;
        } else if (arraySorted[middle] > target) {
            right = middle - 1;
        }
    }
    return -1;
}

26删除有序数组的重复项

快慢指针:

  • 快慢相等值不变,慢针不动快针走
  • 快慢不等值,我是题型一,慢针向前一步走,快针赋值给慢针,快针向前一步走

快指针如果和慢指针的值相等,那么就把快指针++,然后再判断,如果值不相等了,就把慢指针++,然后把快指针的值赋值给慢指针右移后的位置,以此类推,直到快指针遍历整个数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class RemoveNums {
    public static int removeDuplicates(int[] nums) {
        int slow = 0;
        int fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 2, 3, 4, 4, 5};
        int length = removeDuplicates(arr);
        System.out.println(length);
    }
}

283移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序

输入 0 1 0 3 12
输出 1 3 12 0 0

就是判断快指针的值是否是0,如果不是0,就交换,然后快慢都往前
如果是0,那么就快指针往前,慢指针不变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void moveZeros(int[] nums) {
    int slow = 0;
    int fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != 0) {
            // 不等于0，将0后移，交互前者
            int tmp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = tmp;
            slow++;
        }
        fast++;
    }
}

移除数据

快慢指针,3 2 2 3,移除2,则为3 3

首先判断快指针是否不等于要移除的值,如果不等于,就交换

Tmp明天要用的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
CREATE TABLE users (
    id INT AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(100),
    email VARCHAR(100),
    age INT
);


-- 增：插入新用户
INSERT INTO users (name, email, age) VALUES ('Jane Doe', 'jane.doe@example.com', 25);

-- 查：读取所有用户
SELECT * FROM users;

-- 改：更新用户信息
UPDATE users SET age = 26 WHERE name = 'Jane Doe';

-- 查：读取更新后的用户信息
SELECT * FROM users WHERE name = 'Jane Doe';

-- 删：删除用户
DELETE FROM users WHERE name = 'Jane Doe';

-- 查：确认用户已删除
SELECT * FROM users;

DROP TABLE IF EXISTS users;

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class InsertionSort {
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6};
        insertionSort(array);
        printArray(array);
    }

    // 插入排序算法
    public static void insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; ++i) {
            int key = array[i];
            int j = i - 1;

            // 将大于key的元素向右移动一个位置
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }

    // 打印数组
    public static void printArray(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; ++i) {
            System.out.print(array[i] + " ");
        } 
        System.out.println();
    }
}

一道面试时问道的题:

给定一个无序数组,再给定一个值,要求查出数组中与这个值最接近的值的下标

具体思路:

  1. 先定义一个最小差值,这个最小差值的初始值定义为Integer.Max
  2. 遍历数组
  3. 计算数组每一项与目标值的差值,这个差值应该用Math.abs()绝对值来操作
  4. 判断当前差值和最小差值谁比较小
  5. 如果当前差值比较小,就把当前差值的值赋值给最小差值
  6. 记录当前数组的位置

就是这么简单,当时竟然紧张了,愣是想不起来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class GetApproach {

    public static void getData(int[] arr, int target) {

        int minDiff = Integer.MAX_VALUE;
        int closest = 0;
        int closestIndex = -1;

        for (int i = 0; i < arr.length; i++) {
            int diff = Math.abs(arr[i] - target);
            if (diff < minDiff) {
                minDiff = diff;
                closest = arr[i];
                closestIndex = i;
            }
        }

        System.out.println("下标为: " + closestIndex);
        System.out.println("最接近的值为: " + closest);
        System.out.println("差值为: " + minDiff);
    }

    public static void main(String args[]) {
        int[] arr = new int[]{0, 8, 1, 2, 3};
        getData(arr, -1);
    }

}

Mysql

有关索引的建立规则

  • 禁止在更新十分频繁,区分度不高的属性上建立索引
  • 建立组合索引,必须把区分度高的字段放在前面

结论

  • 区分度最高,重复率最低
  • 尽可能满足上述2个条件的字段建索引,效果最好

Innodb的行锁到底锁了什么

首先说一下mysql锁级别

  • 表锁
    • 开销小,加锁快;不会出现死锁;锁定力度大,发生锁冲突的概率最高,并发度最低
  • 行级锁
    • 开销大,加锁慢;会出现死锁;锁定力度最小,发生锁冲突的概率最低,并发度也最高
  • 页面锁(不要求)
    • 开销和加锁时间界于表锁和行锁之间;会出现死锁;锁定粒度界于表锁和行锁之间,并发度一般

行锁会变成表锁?

默认的事务级别是可以避免脏读的,就是无法读到其他事务没有提交的数据

什么时候会变?当where语句的字段没有命中索引时,没有使用索引,就会导致行锁变成表锁

InnoDB的行锁,是通过锁住索引来实现的,如果加锁查询的时候,没有使用倒索引,会将整个聚簇索引都锁住,相当于锁表了
命中索引锁行,没有命中锁表,问题会扩大化

什么是回表

回表是指数据库根据索引(非主键)找到了指定的记录所在行后,还需要根据主键再次倒数据块里获取数据的操作

举例:在字段age上建立了索引,然后根据age查询,这就使用到了索引,那么根据这个索引查到的是该行的id值,再使用id主键索引搜索的过程,就成为回表

B+树中,所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上,而非叶子节点只存储key值信息,这样可以大大加大每个节点存储的key值数量,降低B+树的高度

如果一张表数据量级是千万级别以上的,要给这张表添加索引,你需要怎么做

腾笼换鸟

建新表+建索引+导数据+废旧表

给表添加索引时,是会对表加锁的,如果不慎操作可能出现生产事故,比如过程中发生了数据修改,则可能会读取到不一致或错误的数据

  1. 先创建一张跟原表A数据结构相同的新表B
  2. 在新表B添加需要加上的新索引
  3. 把原表A数据导到新表B
  4. rename新表B为原表的表名A,原表A换别的表名

having和where的区别

用的地方不一样

  • where可以用在select和update等语句中
  • having只能用在select中

执行顺序不一样

  • where的搜索条件是在分组之前
  • having的搜索条件是在分组之后