Fighting！

潜行者的沉默

发表于 分类于

简述

2020年，真的是特殊的的一年无论是对个人，国家，甚至全球。我们经历了难以想象的疫情，全国封禁宅家，停工停学，降薪裁员，这场疫情真的改变改变了很多人的命运，同样还有我。这一年，利用疫情全身心的投入跳槽换工作的准备，历时3个月，面了小影，有赞，快手，滴滴，字节，还投递了钉钉无反应。。。面过的都是拿到了书面或者口头offer最终选择去了字节哈。

面试准备

  1. 一份清晰的能展示自己的简历
  2. 扎实的基础知识
  3. 有调理和深度的项目经历
  4. 扎实的算法数据结构及代码设计能力

如何一步步进入想入的公司

明确自己的目标公司后，首先还是要问问自己有没有把握一次命中。没有，则需要沉淀自己，通过选择备选公司去打磨自己，目的是

  1. 打磨自己的简历，查漏补缺
  2. 在面试中学习，沟通过程中会有很多idea，可以展示在下一场面试
  3. 做到熟背简历，提高语言表达能力
  4. 多拿几个offer，是其他公司的谈判筹码

最后

坦诚清晰的沟通，对自己的未来有明确的规划，有上进心，有责任心，要能看出潜力，不卑不亢，自信但不要自负。

发表于 分类于

导读

在软件设计的过程中设计模式占着举足轻重的作用，高可用的程序必定是建立在良好的设计上的，而设计模式正式这些良好设计的积累总结。设计模式又是符合面向的对象的六大原则而拓展出来的，如同抽象的具体实现，给软件开发者以指导作用。因此面向对象的设计原则是重中之重，下面将一一分析这六大原则。

谈谈对面向对象编程的原则的理解

当面试官问这道题是，他想考察什么内容呢？

  • 是否了解面向对象的原则及作用
  • 是否了解面向对象语言（Java）的特性
  • 是否有对原则有过深入的实战经验

面向对象编程的原则

面向对象编程的原则分别有六个

  • 单一职责原则：就一个类而言，应该仅有一个能引起他变化的原因
  • 开放与关闭原则：面对修改关闭，面对拓展开发
  • 里氏替换原则：在引用基类的地方，可以用子类去替换，且不会影响程序的稳定性
  • 依赖倒置原则：高层不依赖底层，都应该依赖抽象。底层不依赖细节，应该依赖抽象
  • 接口隔离原则：暴露给客户端的接口，应该建立在最小的原则，不需暴露客户不需要的接口
  • 迪米特原则：最少知道原则，一个类应该尽量减少持有过多的引用

Java的特性

  • 封装：确保数据的安全
  • 继承：保证了程序的拓展能力
  • 多态：保证了程序的灵活性

深入理解

踏出优化的第一步—>单一职责原则

单一职责原则英文为Single Resposibility Principle，简单来说，一个类中应该是一组相关性很高的函数、数据的封装。但关于单一职责的划分界限并不是那么清晰，很多时候需要靠个人经验的界定。在开发功能之初，往往会将功能实现放在第一位。变量，方法都会堆积在一个类中方便调用，如一个简单的图片加载器包括：缓存的功能，网络图片的加载，未优化前代码如下

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
public class ImageLoader {
    LruCache<String, Bitmap> mImageCache;
    ExecutorService mExecutorService = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
    Handler mHandler = new Handler(Looper.getMainLooper());

    public ImageLoader() {
        initImageCache();
    }

    private void initImageCache() {
        int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);
        final int cacheSize = maxMemory / 4;
        mImageCache = new LruCache<String, Bitmap>(cacheSize) {
            @Override
            protected int sizeOf(String key, Bitmap value) {
                return value.getRowBytes() * value.getHeight() / 1024;
            }
        };
    }

    public void dispalyImage(String imageUrl, ImageView imageView) {
        Bitmap bitmap = mImageCache.get(imageUrl);
        if (bitmap != null) {
            imageView.setImageBitmap(bitmap);
            return;
        }
        imageView.setTag(imageUrl);

        mExecutorService.submit(new Runnable() {

            @Override
            public void run() {
                Bitmap bitmap1 = downloadImage(imageUrl);
                if (bitmap1 == null) {
                    return;
                }
                if (imageView.getTag().equals(imageUrl)) {
                    updateImageView(bitmap1, imageView);
                }
                mImageCache.put(imageUrl, bitmap1);
            }
        });
    }


    public void updateImageView(Bitmap bitmap, ImageView imageView) {
        mHandler.post(new Runnable() {
            @Override
            public void run() {
                imageView.setImageBitmap(bitmap);
            }
        });
    }

    public Bitmap downloadImage(String imageUrl) {
        Bitmap bitmap = null;
        try {
            URL url1 = new URL(imageUrl);
            HttpURLConnection urlConnection = (HttpURLConnection) url1.openConnection();
            bitmap = BitmapFactory.decodeStream(urlConnection.getInputStream());
            urlConnection.disconnect();
        } catch (MalformedURLException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return bitmap;

    }
}

但如果了解单一职责的原则，我们就应该将他分为两个类进行实现ImageCache负责缓存，ImageLoader负责加载图片。优化后代码如下，

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
public class ImageLoaderV1 {
    ImageCacheV1 mImageCache; // 将缓存的初始化及添加获取方法移到同一个类
    ExecutorService mExecutorService = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

    Handler mHandler = new Handler(Looper.getMainLooper());

    public ImageLoaderV1() {
        mImageCache = new ImageCacheV1();
    }

    public void dispalyImage(String imageUrl, ImageView imageView) {
        // ....
        mExecutorService.submit(new Runnable() {

            @Override
            public void run() {
                Bitmap bitmap1 = downloadImage(imageUrl);
                if (bitmap1 == null) {
                    return;
                }
                if (imageView.getTag().equals(imageUrl)) {
                    updateImageView(bitmap1, imageView);
                }
                mImageCache.put(imageUrl, bitmap1);
            }
        });
    }
 		// ....
}

// 缓存类
public class ImageCacheV1 {
    LruCache<String, Bitmap> mImageCache;

    public ImageCacheV1() {
        initImageCache();
    }

    private void initImageCache() {
        int maxMemory = (int) (Runtime.getRuntime().maxMemory() / 1024);
        final int cacheSize = maxMemory / 4;
        mImageCache = new LruCache<String, Bitmap>(cacheSize) {
            @Override
            protected int sizeOf(String key, Bitmap value) {
                return value.getRowBytes() * value.getHeight() / 1024;
            }
        };
    }

    public void put(String url, Bitmap bitmap) {
        mImageCache.put(url, bitmap);
    }

    public void remove(String url) {
        mImageCache.remove(url);
    }

    public Bitmap get(String url) {
        return mImageCache.get(url);
    }
}

单一职责原则充分体现了面向对象特性中的封闭

让程序更稳定，更灵活—>开闭原则

开闭原则英文为Open Close Principle，是Java最基础的设计原则，它指导我们设计更稳定和灵活的系统。它的定义为对修改封闭，对扩展开放，要确保原有软件模块的正确性以及尽量少的影响原有模块就应该遵循开闭原则。通过分析上面的图片加载器，我们发现上面的图片加载器只是内存的缓存，我们需要扩展出磁盘缓存可用用户选择，这时我么会发现添加新的缓存方式需要修改原有的代码，且如果还需要扩展双缓存机制(内存+磁盘),则又需要修改原来的代码，这时候我们发现ImageCache这个类不支持缓存的拓展。这时候我们就应该考虑将缓存类进行抽象，定义出不同的缓存实现供ImageLoader引用，动态的添加不同的缓存方式，使程序更加稳定和灵活。代码如下

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
//  缓存接口
public interface IImageCache {

    void put(String url, Bitmap bitmap);

    Bitmap get(String url);

}
// 内存缓存 同ImageCacheV1，只添加接口实现
public class ImageCacheV2 implements IImageCache{
   // ....
}
// 磁盘缓存
public class ImageDiskCacheV2 implements IImageCache{
    String cacheDie = "/Sdcard/cache/";

    public void put(String url, Bitmap bitmap) {
        FileOutputStream outputStream = null;
        try {
            outputStream = new FileOutputStream(cacheDie + url);
            bitmap.compress(Bitmap.CompressFormat.JPEG, 100, outputStream);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } finally {
            if (outputStream != null) {
                try {
                    outputStream.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }

            }
        }
    }

    public Bitmap get(String url) {
        return BitmapFactory.decodeFile(cacheDie + url);
    }
}

// ImageLoader
public class ImageLoaderV2 {
    ImageCacheV2 mImageCache;
    ExecutorService mExecutorService = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());

    Handler mHandler = new Handler(Looper.getMainLooper());
    
    public ImageLoaderV2() {
    }

		// 通过用户传入指定的缓存实现，注入缓存实现
    public void setmImageCache(ImageCacheV2 mImageCache) {
        this.mImageCache = mImageCache;
    }
		// ......
}

由此，我们可以愉快的进行缓存的拓展，同时不需要修改原来的代码，符合开闭原则

构建扩展性更好的系统->里氏替换原则

里氏替换原则英文是Liskov Substitution Principle, 定义为所有引用基类的地方必须能透明的使用其子类的对象，里氏替换原则就是依赖于java特性中的继承和多态两大特性，而核心就是抽象，能使子类替换父类就是继承。

继承的优点

  • 代码重用，减少创建类的成本，每个子类都拥有父类的属性和方法
  • 子类和父类基本相似
  • 提高代码的可扩展性

缺点

  • 继承是侵入性的，只有继承就必须拥有父类的属性和方法
  • 可能造成子类代码冗余、灵活性降低，因为子类必须拥有父类的属性和方法

上面内存缓存和磁盘缓存都可以替代ImageLoader的变量，IImageCache就是体现了里氏替换原则原则。里氏替换原则和开闭原则往往是生死相依，不弃不离，里氏替换达到了对扩展开放对修改封闭的效果，两者都强调了一个重点特性抽象

让项目拥有变化的能力—>依赖倒置

发表于 分类于

导读

本人从事Android客户端开发，最近在在深入Framwork学习，希望我的学习分享能帮到你。首先我们看一下关于Android系统的启动流程我们应该如何去分析，这里通过一张思维导图帮助大家整理思路。思维导图一方面罗列了本文的大纲，另一方面也是希望读者朋友可以保存图片至自己的复习资料里。以便随时通过该大纲去复习，可以关注我，收藏文章进一步沟通学习！

跟我学：Android高级面试之说说Android系统的启动流程

说说Android系统的启动流程

面对这道面试题，面试官试想考察什么呢？

  • Android中有哪些主要的系统进程
  • 这些系统进程是怎么启动的
  • 进程启动之后主要做了什么事

系统进程

Android中有哪些系统进程，具体我们可以在init.rc的配置找到相应的启动代码

1
2
3
4
start zygote
start servicemanager
start surfaceflinger
....

上面几个熟悉的服务进程都是通过init单独创建启动的，还有 一个我们熟悉的SystemServer，这个服务进程是通过Zygote进程创建而不是init进程。

Zygote的启动流程

关于Zygote的的相关知识可以参考跟我学：Android面试之深入Android Framework谈谈对Zygot的理解

它的启动流程是

  1. init进程fork出zygote进程
  2. zygote创建虚拟机，注册jni函数
  3. 预加载系统资源
  4. 启动SystemServer
  5. 进入 Socket LOOP循环（工作原理）

SystemServer的启动

在ZygoteInit.java的代码逻辑中，可以看到启动的关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int pid = Zygote.forkSystemServer(...) // 通过Zygote创建子线程
handleSystemServerProcess(...)  // 然后初始化SystemServer
ZygoteInit.zygoteInit(...)
ZygoteInit.nativeZygoteInit(...); // 这里面会启动启动binder机制，创建了Binder线程
RuntimeInit.applicationInit(...) // 调用SystemServer.java类的入口函数main。内部基于反射实现
       
// SystemServer的main方法
public static void main(String[] args) {
        new SystemServer().run();
}

run方法中主要以下几件事
1. Looper.prepareMainLooper(); // 为主线程创建loop
2. System.loadLibrary("android_servers"); // 加载android的共享库，native层的代码
3. createSystemContext(); // 创建系统上下文
4. 分批启动服务startBootstrapServices();startCoreServices();startOtherServices();
5. Looper.loop(); // 进入loop循环，主线程不会退出

系统服务的启动

系统服务的启动指startBootstrapServices();startCoreServices();startOtherServices();内部的服务启动。启动startBootstrapServices()中包括了熟悉的AMS，PMS，StartPowerManager等等。startCoreServices()包含了BatteryService，UsageStatsService，WebViewUpdateService等等。以及startOtherServices()中的其他服务。

系统服务如何房补，让应用程序可见

通过源码的阅读，我们可以发现最终服务是通过ServiceManager.addService(…) 将服务进行注册，然后才可以可被其他进程可见和使用

系统服务运行在什么线程中？

主线程：并没有找到哪个系统服务是在主线程的中的

工作线程： AMS，PMS运行在自己的工作线程，或者在公用的工作线程DisplayThread，FgThread, IoThread, UiThread。

Binder线程：应用在跨进程调用时肯定是在binder线程里的，然后再去切换线程

如何解决系统服务启动的相互依赖

从上小结的startBootstrapServices();startCoreServices();startOtherServices();我们可以看出解决方式为

  • 分批启动：先启动AMS，PMS等，因为很多其他service都需要依赖他们
  • 分阶段启动：在每个阶段去启动相应需要的服务

桌面启动

当AMS等其他服务都启动完毕，会调用mActivityManagerService.systemReady(()，在这里面会通过startHomeActivityLocked(currentUserId, “systemReady”);启动桌面应用的activity， Launcher.java。启动后会通过PMS查找所有的已安装的应用，然后显示在界面上

最后

看到最后，我相信你一定对Android系统的启动流程有一定了解了吧。回头看看第一部分的考查内容讲讲呗，对于每一个点的重点我都细心的为你做了高亮。还有纸上得来终觉浅，绝知此事要躬行。本文参考了Android api28的源码，希望你也去踩着点过一遍源码，肯定能加深理解！

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！

发表于 分类于

导读

刷算法题需要一定的节奏，同样对待每一道算法题也需要认真的对待不可操之过急，否则会导致：算法虐我千万遍，我待算法如初恋！如果这句话是从对算法态度上说爱如初恋那必须得肯定你的态度，但如果是每一道算法题，反复都能虐你千万遍，那这个初恋的滋味肯定不好受。我们应该是面对新题对待如初恋，对待已经做过的题应该是勾勾手指，手到擒来的老司机，否则就是白刷。不仅浪费时间而且浪费精力，所以刷题必须讲究方式方法，建议反复阅读此文跟我学：LeetCode刷题大法。下面这里通过一张思维导图帮助大家整理这道题的思路。思维导图一方面罗列了本文的大纲，另一方面也是希望读者朋友可以保存图片至自己的复习资料里，以便随时通过该大纲去复习，注意关注标红的重点解法。

跟我学：LeetCode刷题之3. 无重复字符的最长子串

看题总结

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

Related Topics

哈希表

双指针

字符串

Sliding Window

通过对题目的阅读，我们可以得出以下几个结论

  1. 题目类型为数组
  2. 要求是返回最长的不含重复字母的子串长度
  3. 输入的字符串可能为空串，输入判断

多解法及复杂度分析

解法一：暴力法，多重循环

首先希望读者能写出双重循环的模板代码，在此再次强调此代码是数组问题暴力法的套路墙裂建议背诵默写，如果还是不能随手写出回过头看一下此文跟我学：LeetCode刷题之1.两数之和，好了继续此问题的暴力解决法就是通过双重循环，加内部一层循环判断[i,j]之间的元素是否是唯一的，然后做相应的移动和记录最大值。注意此处的双重循环的i，j范围，是由于allUnique()方法的for循环范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }

复杂度分析

时间复杂度：O(n^3)，三重循环

空间复杂度：O(min(n, m))O(min(n,m))，我们需要 O(k)的空间来检查子字符串中是否有重复字符，其中 k 表示 Set 的大小。而 Set 的大小取决于字符串 n 的大小以及字符集/字母 m 的大小。

解法二：双指针+滑动串口

该题的实现思路主要是基于：滑动窗口。

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！如左出右进变为bca

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

  • 哈希法的实现可以基于Map定义key为字符串的中的每个字符，value为该字符的位置i+1(方便计算长度）
  • 通过数组实现，应为字符串由字母组成所以可以根据ASCII码的字符大小128，存放字符的位置i+1。

这里推荐使用数组，数组的存取都是O(1)的实现，当然Map在此种情况下也是的。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] hash = new int[128];
        int start = 0;
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            start = Math.max(ans, hash[s.charAt(i)]);
            ans = Math.max(ans, i - start + 1);
            hash[s.charAt(i)] = i + 1;
        }
        return ans;
    }

复杂度分析

时间复杂度：O(n)，只进行一次遍历

空间复杂度：O(m)，m 是字符集的大小128

两种解法，充分体现了以空间换时间思想的，来一次加快算法处理速度。所以在算法题中哈希表数组和Map的代码也需要背诵记忆，才能游刃有余。

同类题相关

992. K 个不同整数的子数组

若你反复AC，且充分理解了本题解法，可以尝试去解答同类题992该题是困难题不过无妨，同类题的意思就是变形，往往是增加了特定的条件或者是针对不同的场景。所以同类题的目的是，透过现象看本质，一时的解不出不碍事，按我说的方法跟我学：LeetCode刷题大法，通过此种方法一定是越来越自信的刷题。

技巧与心得

  1. 开一个github仓库用来记录各种题解
  2. 在idea或者vscode中都提供了leecode的插件刷题，方便调试断走流程
  3. 遇到不会的题不要慌，稳住心态直接看题解
  4. 文字类的表述不如视图类的直观，图文并茂精选图解优先或者参考leetcode国际站的大牛题解
  5. 图解依旧看着吃力也无妨，可以在哔哩哔哩或者YouTube上，通过leecode + 题号，搜索高收视率的视频观看
  6. 多看几次本文跟我学：跟我学：LeetCode刷题大法，相信我你肯定能越刷越自信

最后的最后

看到最后，我相信你对本题应该有不一样的感受了吧！在此若有不对之处或建议等，留言告诉我；若有疑惑或者不一样的看法，也请告诉我，我们可以一起探讨学习！

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！

发表于 分类于

导读

本题是LeetCode第二题，难度标记为中等。此题为链表题，不出意外遇到链表题都是画图解题，因为链表题的核心是在符合条件下的链表next指针的变化，除了链表的增删改查之外，如何反转链表的代码，我墙裂建议你先理解背诵，刷链表题基础必备代码，如下

1
2
3
4
5
6
7
8
9
10
11
pubic ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode cur = head;

    while(cur != null){
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
}

这里通过一张思维导图帮助大家整理思路。思维导图一方面罗列了本文的大纲，另一方面也是希望读者朋友可以保存图片至自己的复习资料里，以便随时通过该大纲去复习。

跟我学：LeetCode刷题之2.两数相加

看题总结

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

1
2
3
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

Related Topics

链表

数学

通过对题目的阅读，我们可以得出以下几个结论

  • 题目类型为链表
  • 用两个链表表示两个整数，整数在链表中的存储方式是逆序的，通过链表实现两整数的相加操作，返回值也是用逆序的链表存储的整数。
  • 非空链表，非负数整数，除了0之外整数不会以0开头，输入是合法的

多解法及复杂度分析

解法一：非递归实现

  1. 定义一个哑结点dummy（可以避免对头结点的处理），指向当前节点cur，然后定义一个保存进位数值的 carry（因为两数相加可能会产生进位，便用 carry 来保存）
  2. 当 l1 或 l2 不为空时进行遍历，即二者都为空时才退出循环，
  3. 通过设置默认值为 0 的 x和 y，使得当二者中有一个为空时，使用 0 来与另一位相加
  4. 得到 sum 后，将 sum 的个位数连接到链表中，并将十位数赋给 carry,
  5. 移动 cur 使其一直指向链表的尾部

最后要判断 carry 是否大于 0，因为例如 (1 -> 2 -> 3) + (7 -> 8 -> 9) 会得到结果 8 -> 0 -> 3 -> 1，所以在最后判断 l1 和 l2 都已经为空了，但是此时 carry 大于 0，所以要将这最后一位数加入到链表尾部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0; // 保存进位数值的 carry
        while (l1 != null || l2 != null) {
          	// 用0补齐，链表长度
            int x = l1 != null ? l1.val : 0;
            int y = l2 != null ? l2.val : 0;
            int sum = x + y + carry;
            carry = sum / 10;
            ListNode newNode = new ListNode(sum % 10);

            curr.next = newNode;
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        }
  
  			// 存在两链表长度相等，且最高位计算和大于10，需进位创建新节点
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }

        return dummy.next;
    }

解法二：递归实现

首先我们需要理解递归，墙裂建议背诵默写递归的模板代码，递归解法的套路如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void recur(int level, Param param) {
  	// 递归终止条件
    if (level > MAX_VALUE) {
        //process result
        return;
    }

    // 当前层处理处理
    process(param);

    // 进入下一层递归
    recur(level, newParam);

    // 非必要的数据恢复
}

这题使用递归很好理解，两链表的节点从左往右进行相加，进位，直到两链表都到达尾部。

  1. 递归终止条件：两链表都到达尾部
  2. 当前层处理：链表节点相加计算和，得到余数，及carry进位
  3. 进入下一次递归：传入新节点及进位值。

最后代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }

    private ListNode add(ListNode a, ListNode b, int carry) {
        // terminator 终止条件
        if (a == null && b == null) {
            return carry > 0 ? new ListNode(1) : null;
        }

        // current logic  当前层逻辑处理
        // 如果当前节点a,b其中一个为null，则赋值为ListNode(0)，方便计算
        a = a == null ? new ListNode(0) : a;
        b = b == null ? new ListNode(0) : b;

        // 当前两链表节点的和
        int sum = a.val + b.val + carry;
        carry = sum / 10;
        // 将取模结果保存在第一个链表中
        a.val = sum % 10;
        // driil down   进入下一层递归
        a.next = add(a.next, b.next, carry);
        return a;
    }

同类型题相关

若你反复AC，且充分理解了本题的两种题解，我敢保证下面这题解出来只是时间长短问题。

在这里还是提醒刷题的朋友，多看几次本文跟我学：LeetCode刷题大法

LeetCode 445. 两数相加 II

技巧与心得

  1. 开一个github仓库用来记录各种题解
  2. 在idea或者vscode中都提供了leecode的插件刷题，方便调试断走流程
  3. 遇到不会的题不要慌，稳住心态直接看题解
  4. 文字类的表述不如视图类的直观，图文并茂精选图解优先或者参考leetcode国际站的大牛题解
  5. 图解依旧看着吃力也无妨，可以在哔哩哔哩或者YouTube上，通过leecode + 题号，搜索高收视率的视频观看
  6. 多看几次本文跟我学：LeetCode刷题大法，相信我你肯定能越刷越自信

最后的最后

看到最后，我相信你对本题应该有不一样的感受了吧！在此若有不对之处或建议等，留言告诉我；若有疑惑或者不一样的看法，也请告诉我，我们可以一起探讨学习！

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！

发表于 分类于

闲聊

不想赘述算法与数据结构本身存在的重要性以及对工作面试的重要性。我只想谈谈如何通过解决一道道算法题，慢慢的改变自己对算法的态度，并且从算法中获得自信，如果以下论述我们产生了些许共鸣！请关注我，让我们一起努力，一起刷爆leetcode吧。

坚定想法

曾几何时，在无数个瞬间。可曾遇到过这些情况

  • 算法很重要，我要刷一刷算法；
  • 背了几题，但不刷刷算法我还是慌的；
  • 算法虽很重要，但我工作上没怎么用上；
  • 我刷过了，但面试我怎么打不出来；
  • 刷了几题，太难了，我放弃；
  • ….

跟我学：LeetCode刷题大法

放弃的理由千千万万

讲真放弃的理由千千往往，坚持的理由我觉得只有兴趣和生存。只要是抱着生存的理由，那放弃的理由分分钟淹没他，除非真的找不到工作活不下去，就算如此，还能转行，直接逃避……，说这些就是想让自己和大家认清本质，坚定一下刷算法的的信念，走出第一步告诉自己：我需要刷题，我要刷题！

如何刷题到自信

当看到这里，我相信刷过题的人都有过类似经验

  1. 第一次平静的打开某算法库官网(这个主要是LeetCode)，
  2. 然后打开第一个题，看了题目有点思路，一写代码结果各种输入判断，代码编译上的错误都会遇到
  3. 千辛万苦ac后发现只打败了30%的人。完全没有考虑过时间复杂度，空间复杂度，不过好歹过了
  4. 然后继续刷，没过多久就遇到了一题懵逼或者死磕磕不出的题，然后看题解
  5. 看懂的题解我们会惊呼怎么想到的，没看懂的题解会沮丧这也太难了，半天看不懂的题解完全就打击到了自信心
  6. 最终刷题结束，然后可能没有然后了，或者过几天再来挣扎一下。
  7. 那些挣扎过并坚持下来的人，我相信算法面试稳了但不一定自信，除非养成了刷题的习惯

这经历完全是自我打击的过程，说到底还是打开的姿势不对。没有找准刷题的基本思想和步骤，试试下面的刷题步骤

  1. 打开一题算法，先看题目，5-10分钟毫无思绪或者无法解决，
  2. 直接看题解，题解一般会有多种解法，找最优解看懂了背下来
  3. 然后不看题解去解题，ac后不急，多默写几遍ac几遍，直到相信自己明天起床也能稳稳的ac
  4. 接着可以再去看题解，去比较其他解法，分析他们的时间复杂度和空间复杂度，看最优解做的优化
  5. 通过比较，肯定是可以加深最优解的印象。最后重新打开这道题
  6. 看题，思考给出各种解法的思路以及复杂度，最后选出最优解，把它写下来。
  7. ac的那一刻，你的自信就来了。
  8. 当隔了一星期，你再来解这道题一次ac，稳如狗就更自信了。否则也不会沮丧，只是查漏补缺而已，几分钟后依旧ac。

跟我学：LeetCode刷题大法

技巧与心得

  1. 遇到不会的题不要慌，看题解
  2. 文字类的表述不如视图类的直观，尽量找图文并茂精选图解，或者看leetcode国际站的大牛题解
  3. 图解依旧看着吃力，可以在哔哩哔哩或者YouTube上，通过leecode + 题号，搜索高收视率的视频观看
  4. 反复研读观看，相信我你最终会懂的

最后的最后

我想说且是重点的，未来我将带领各位盆友一起刷算法题，后续我会通过视频+图文的方式来分享每一题的思路和多种解法代码。同时教会大家更方便，高效的刷题。

我是Yangcy，该吃吃该喝喝，该学还得学，我们一起加油！

0%