题目

• 给定两个整数数组，从两个数组中各取一个元素，要求它们的差值绝对值最小

代码

1. 先排序，后双指针

import java.util.Arrays;public class Main {    public static void main(String[] args) {        int[] arr1 = {1, 3, 5, 11};        int[] arr2 = {4, 7, 9};        Arrays.sort(arr1);        Arrays.sort(arr2);        int i = 0, j = 0;        int minDiff = Integer.MAX_VALUE;        int num1 = -1, num2 = -1;        while (i < arr1.length && j < arr2.length) {            int diff = Math.abs(arr1[i] - arr2[j]);            if (diff < minDiff) {                minDiff = diff;                num1 = arr1[i];                num2 = arr2[j];            }            // 如果不需要记录两个数分别是多少，可以直接使用以下语句            // minDiff = Math.min(minDiff, Math.abs(arr1[i] - arr2[j]));            if (arr1[i] < arr2[j]) {                i++;            } else {                j++;            }        }        System.out.println("两个数组中差值绝对值最小的元素是 " + num1 + " 和 " + num2);        System.out.println("它们的差值绝对值是 " + minDiff);    }}

题目

• 创建三个线程，按指定顺序打印1到100，具体如下：

  • 线程1打印1
  • 线程2打印2
  • 线程3打印3
  • 线程1打印4
  • 线程2打印5
  • 线程3打印6
  • ……
  • 线程3打印99
  • 线程1打印100

• 知识点：wait()/notifyAll()

代码

import java.util.concurrent.atomic.AtomicInteger;/** * @author: LiQiang * @date: 2023/03/30 * @description: 三个线程按顺序打印1到100 */public class Main {    // 锁    private static Object resource = new Object();    // 打印区分标识(值为1~3，初始设置1)    private static int flag = 1;    // 需要打印的值    static AtomicInteger integer = new AtomicInteger(1);    // private static volatile int number = 1;    public static void main(String[] args) {        // 三个线程按顺序打印1~100        new Thread(new Runnable() {            @Override            public void run() {                while (integer.get() <= 100) {                    synchronized (resource) {                        while (flag != 1) {                            try {                                resource.wait();                            } catch (InterruptedException e) {                                e.printStackTrace();                            }                        }                        // 打印操作                        if (integer.get() <= 100) {                            System.out.println(Thread.currentThread().getName() + " --- " + integer.getAndIncrement());                        } else {                            Thread.currentThread().interrupt();                            // break;                        }                        // number ++;                        // 变更标识                        flag = 2;                        // 通知线程2                        resource.notifyAll();                    }                }            }        }, "线程1").start();        new Thread(new Runnable() {            @Override            public void run() {                while (integer.get() <= 100) {                    synchronized (resource) {                        while (flag != 2) {                            try {                                resource.wait();                            } catch (InterruptedException e) {                                e.printStackTrace();                            }                        }                        // 打印操作                        if (integer.get() <= 100) {                            System.out.println(Thread.currentThread().getName() + " --- " + integer.getAndIncrement());                        } else {                            Thread.currentThread().interrupt();                            // break;                        }                        // 变更标识                        flag = 3;                        // 通知线程3                        resource.notifyAll();                    }                }            }        }, "线程2").start();        new Thread(new Runnable() {            @Override            public void run() {                while (integer.get() <= 100) {                    synchronized (resource) {                        while (flag != 3) {                            try {                                resource.wait();                            } catch (InterruptedException e) {                                e.printStackTrace();                            }                        }                        // 打印操作                        if (integer.get() <= 100) {                            System.out.println(Thread.currentThread().getName() + " --- " + integer.getAndIncrement());                        } else {                            Thread.currentThread().interrupt();                            // break;                        }                        // 变更标识                        flag = 1;                        // 通知线程1                        resource.notifyAll();                    }                }            }        }, "线程3").start();    }}

需求

从指定网站中获取不同分类下的所有国自然项目数据，如优青、杰青、面上、重大等分类中的项目数据。

依赖包

• urllib3
• time
• csv

代码

整个过程分为数据获取和数据处理两部分，具体代码如下。

1.网页原始数据获取

import urllib3import timefrom urllib.parse import unquotedef download_content(url):    '''    根据链接下载数据    :param url: 链接    :return: 页面数据    '''    http = urllib3.PoolManager()    # 不登录只能查看20页，所以总页数需要通过查询条件限制在20页以内，建议通过起止时间来限制，便于分类和获取    body = {'startTime': '2016', 'endTime': "2021",            'addcomment_s1': 'D',            'searchsubmit': 'true',            'subcategory': '优秀青年基金项目'}    # letpub网站是POST请求，izaiwen网站（已停用）是GET请求    response = http.request('POST', url, fields=body)    # 从返回结果中获取页面内容，编码一般是utf-8    response_data = response.data    html_content = response_data.decode('utf-8')    unquote(html_content)    # print(html_content)    return html_contentdef save_to_file(filename, content):    '''    保存数据到本地文件    :param filename: 文件名    :param content: 文件内容    :return: 本地文件    '''    fo = open(filename, 'w', encoding='utf-8')    fo.write(content)    fo.close()if __name__ == '__main__':    # url需要根据在letpub网站中点击查询时，控制台中显示的实际地址`Request URL`修改    url_prefix = 'https://www.letpub.com.cn/nsfcfund_search.php?mode=advanced&datakind=list&currentpage='    # 总页数根据网页查询结果调整    page_total = 18    # 保存路径名建议根据查询条件按年份区分    path_prefix = './2016-2021/page-'    path_suffix = '.html'    # 从第一页开始获取，中间加休眠5~10秒左右，防止访问被禁    page_number = 1    while page_number <= page_total:        # 每页的url        url = url_prefix + str(page_number)        # 每页的原始数据        page_data = download_content(url)        # 每页的保存路径        save_path = path_prefix + str(page_number) + path_suffix        # 保存每页的数据        save_to_file(save_path, page_data)        print('page ' + str(page_number) + ' end')        # 休眠10秒        time.sleep(10)        # 访问下一个页面        page_number += 1

2.数据处理

import csvdef save_to_file(filename, content):    fo = open(filename, "w", encoding="utf-8")    fo.write(content)    fo.close()def replace_string(content):    '''    页面数据处理方法（根据网站页面内容自定义，以letpub网站举例）    :param content: 页面内容    :return: 处理后的页面内容    '''    '''    页面数据分割的形式，可以打开原始的页面数据文件看看，找易于分割出需要内容的字符串，像letpub网站有下面两行明显标识，很好分割    '''    content = content.split('<!-- ################## start content ################## -->')[1]    content = content.split('<!-- ################## end content ################## -->')[0]    content = content.split('TR>')[2]    '''    替换页面中重复多次出现的标签    '''    # 此处标签替换为换行符\n是为了区分不同的项目（通常是每页10个项目）    content = content.replace('<tr style="background:#EFEFEF;">', '\n')    content = content.replace(        '<td style="border:1px #DDD solid; border-collapse:collapse; text-align:left; padding:8px 8px 8px 8px;">', '')    content = content.replace(        'style="border:1px #DDD solid; border-collapse:collapse; text-align:left; padding:8px 8px 8px 8px;  font-size:13px; color:#333333;">',        '')    content = content.replace(        '<td style="border:1px #DDD solid; border-collapse:collapse; text-align:left; padding:8px 8px 8px 8px; font-size:13px; color:#333333;"',        '')    # 项目小标题对于实际内容获取没有帮助，直接替换掉；若需要保留，可以只替换</td>标签    content = content.replace('题目</td>', '')    content = content.replace('学科分类</td>', '')    content = content.replace('学科代码</td>', '')    content = content.replace('执行时间</td>', '')    content = content.replace('中文关键词</td>', '')    content = content.replace('英文关键词</td>', '')    content = content.replace('结题摘要</td>', '')    # 此处的替换字符串@@可以修改为任意其他的可以唯一区分的字符串（如##、#%），不建议使用空格、反斜杠等容易出现内容歧义的字符    content = content.replace('</td>', '@@')    content = content.replace('<td', '')    content = content.replace(        'style="border:1px #DDD solid; border-collapse:collapse; text-align:left; padding:8px 8px 8px 8px; color:#3b5998; font-weight:bold;">',        '')    content = content.replace('colspan="6">', '')    content = content.replace('</tr>', '')    content = content.replace('<tr>', '')    '''    单独处理页面中剩余的非通用标签，如下方的表头    '''    content = content.split('批准年份')[1]    content = content.replace('</th>', '')    content = content.replace('<', '')    content = content.replace('</th>', '')    content = content.replace('  ', '')    content = content.replace(' ', '')    # 返回结果    return contentif __name__ == '__main__':    '''    以下参数需要手动指定，以按年份查询区分为例    '''    # 页面文件的存储路径    origin_path_name = './2016-2021/'    # 文件前缀、后准、页面数量    file_name_prefix = 'page-'    file_name_suffix = '.html'    file_number = 18    # 结果输出的目标路径    target_path_name = './flushed_data/2016-2021/'    # 处理后文件的前缀、后缀    target_file_name_prefix = 'flushed-page-'    target_file_name_suffix = '.txt'    '''    需要从页面数据中获取的常用的信息    '''    # 负责人    charge_list = []    # 单位    department_list = []    # 金额 (万)    money_list = []    # 项目编号    project_number_list = []    # 项目类型    project_type_list = []    # 所属学部    xuebu_list = []    # 批准年份    pass_year_list = []    # 题目    title_list = []    # 学科分类    subject_type_list = []    # 学科代码    subject_code_list = []    # 执行时间    execution_time_list = []    # 记录所有页面中的每一行（因为预处理时不可以替换的换行符\n的存在，会出现空行，通过长度判断筛选掉）    lines = []    # 从第1个页面开始处理    page_number = 1    while page_number <= file_number:        # 处理后的页面内容        content = ''        # 页面文件名        file_name = origin_path_name + file_name_prefix + str(page_number) + file_name_suffix        # 打开文件获取数据，按行追加到页面内容中        with open(file_name, 'r+', encoding='utf-8') as f:            for line in f:                content += line        f.close()        # 页面数据处理（方法内容自定义，需要根据页面实际内容调整）        content = replace_string(content)        # print(content)        # 保存各处理后的页面内容到文件中        save_path = target_path_name + target_file_name_prefix + str(page_number) + target_file_name_suffix        save_to_file(save_path, content)        # 打开上一步保存的处理后的页面数据文件        with open(save_path, 'r', encoding='utf-8') as f:            # 将符合筛选要求的行内容添加到列表中（因为预处理时不可以替换的换行符\n的存在，会出现空行，通过长度判断筛选掉）            for line in f:                if (len(line) > 5):                    line = line.replace('\n', '')                    lines.append(line)        f.close()        # 下一个页面        page_number += 1    # 处理列表信息，分到各个单独的列表中    for line in lines:        # 可能因为‘结题摘要’等小项的存在，导致出现一些冗余行，先打印结果看看，在循环中加个筛选        if line.count('@@') >= 9:            # 页面数据处理方法中人为添加的分隔符做分割，按照网页数据中固定顺序分到不同的列表中            items = line.split('@@')            # print(items)            charge_list.append(items[0])            department_list.append(items[1])            money_list.append(items[2])            project_number_list.append(items[3])            project_type_list.append(items[4])            xuebu_list.append(items[5])            pass_year_list.append(items[6])            title_list.append(items[7])            subject_type_list.append(items[8])            subject_code_list.append(items[9])            execution_time_list.append(items[10])    # 把上方的列表合并为一个table    content_to_table = zip(charge_list, department_list, money_list, project_number_list, project_type_list, xuebu_list,                           pass_year_list, title_list, subject_type_list, subject_code_list, execution_time_list)    # 把数据保存到表格中（csv文件如果用word打开乱码，可以用wps打开）    output_table_path = origin_path_name.split('/')[1] + '.csv'    with open(output_table_path, 'w', newline='', encoding='utf-8') as f:        writer = csv.writer(f)        for row in content_to_table:            writer.writerow(row)    f.close()

执行命令 pip uninstall scikit-learn 报错，Cannot uninstall ‘scikit-learn’

具体报错如下：

ERROR: Cannot uninstall 'scikit-learn'. It is a distutils installed project and thus we cannot accurately determine which files belong to it which would lead to only a partial uninstall.

不能卸载“scikit-learn”。这是一个安装了distutils的项目，因此我们不能准确地确定哪些文件属于它，这将导致只有部分卸载。

原因

大概率是其他依赖中包含了scikit-learn，如keras，tensorflow。

解决办法：

先从本地文件夹中搜索如keras，tensorflow等包中是否包含scikit-learn。
若是，则先把这些包卸载掉，然后，找到并删除虚拟环境（以anaconda的虚拟环境为例）中的scikit-learn * .egg-info文件。
最后，重新安装需要版本的scikit-learn，再安装其他被卸载的依赖包（如keras）即可。

题目描述

• 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
• 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
• 问总共有多少条不同的路径？

exampleinput  : m = 3, n = 2output : 3note   : 从左上角开始，总共有 3 条路径可以到达右下角。         1. 向右 -> 向下 -> 向下         2. 向下 -> 向下 -> 向右         3. 向下 -> 向右 -> 向下input  : m = 7, n = 3output : 28

解题思路

思路1 动态规划

• 这是一个标准的动态规划问题，可以完成状态转移

• 转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

• 因为只能向右或向下移动，所以：

  • 对于第一行和第一列的所有格子，都有且仅有一条路径可以直达其位置
  • 对于非第一行或非第一列的格子，到达其位置的路径数 = 到达其上方格子的路径数+到达其左方格子的路径数

• 绘制网格图后，可以通过举例测试确定上述规律

• 时间复杂度:O(m x n)

• 空间复杂度:O(m x n)

  思路2 组合数学

  从左上角到右下角的过程中，需要移动 m+n-2 次，其中有 m-1 次向下移动，n-1 次向右移动。
  因此路径的总数，就等于从 m+n-2 次移动中选择 m-1 次向下移动的方案数，即组合数：

C = (m + n - 2)! / (m - 1)! * (n - 1)!
因此直接计算出这个组合数即可。
化简可得：C = (m + n - 2) * (m + n - 3) * ··· * n / (m - 1)!

• 时间复杂度:O(m)
• 空间复杂度:O(1)

代码（Java）

思路1代码

public class Solution {    public int uniquePaths(int m, int n) {        int[][] pathNum = new int[m][n];        /*        for (int j = 0; j < n; j++) {            pathNum[0][j] = 1;        }        for (int i = 1; i < m; i++) {            pathNum[i][0] = 1;        }        for (int i = 1; i < m; i++) {            for (int j = 1; j < n; j++) {                pathNum[i][j] = pathNum[i - 1][j] + pathNum[i][j - 1];            }        }        */        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (i == 0 || j == 0) {                    pathNum[i][j] = 1;                } else {                    pathNum[i][j] = pathNum[i - 1][j] + pathNum[i][j - 1];                }            }        }        /* 打印动态规划得到的二维数组        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                System.out.print(pathNum[i][j] + "\t");            }            System.out.println();        }        */        return pathNum[m - 1][n - 1];    }}

思路2代码

public class Solution2 {    public int uniquePaths(int m, int n) {        long ans = 1;        for (int x = n, y = 1; y < m; x++, y++) {            // x和y同时前进 m - 2 次，刚好满足化简后的公式            ans = ans * x / y;        }        return (int) ans;    }}

题目描述

• 给定一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

exampleinput  : matrix = [[1,2,3],[4,5,6],[7,8,9]]output : [1,2,3,6,9,8,7,4,5]input  : matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]output : [1,2,3,4,8,12,11,10,9,5,6,7]

解题思路 按层模拟

• 按照题目要求的转圈遍历顺序，使用上下左右四个界限坐标来标记每圈的位置，模拟整个向内环绕的元素获取过程。
• 时间复杂度:O(m×n)
• 空间复杂度:O(1)

代码（Java）

public class Solution {    public List<Integer> spiralOrder(int[][] matrix) {        List<Integer> list = new ArrayList<>();        int length = matrix.length;        int width = matrix[0].length;        int left = 0, right = width - 1, top = 0, bottom = length - 1;        while (left <= right && top <= bottom) {            for (int i = left; i <= right; i++) {                list.add(matrix[top][i]);            }            for (int j = top + 1; j <= bottom; j++) {                list.add(matrix[j][right]);            }            if (left < right && top < bottom) {                for (int p = right - 1; p >= left; p--) {                    list.add(matrix[bottom][p]);                }                for (int q = bottom - 1; q > top; q--) {                    list.add(matrix[q][left]);                }            }            left++;            right--;            top++;            bottom--;        }        return list;    }}

题目描述

• 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。
• 如果链表无环，则返回 null。
• 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
• 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
• 如果 pos 是 -1，则在该链表中没有环。
• 注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
• 不允许修改 链表。

exampleinput  : head = [3,2,0,-4], pos = 1output : tail connects to node index 1note   : 返回索引为 1 的链表节点，链表中有一个环，其尾部连接到第二个节点。input  : head = [1,2], pos = 0output : tail connects to node index 0note   : 返回索引为 0 的链表节点，链表中有一个环，其尾部连接到第二个节点。input  : head = [1], pos = -1output : no cyclenote   : 返回 null，链表中没有环。

解题思路

思路1 快慢指针

• 设快指针是fast，慢指针是slow，两者起点相同
• 快指针以2倍速前进，慢指针以逐步前进；可知fast前进的路程s1是slow前进的路程s2的两倍，即 s1 = 2 * s2
• 设从起点到入环节点的距离（节点个数）是a，入环节点顺序到fast和slow相遇节点的距离为b，相遇节点再顺序到入环节点的距离为c，则有
  • 环长（环内节点总数）为：s3 = b + c
  • fast走过的路程：s1 = a + n(b + c) + b
  • slow走过的路程：s2 = a + b
  • 以上则有：s1 = 2 * s2 => a + n(b + c) + b = 2(a + b)
    • 移项可得：a = c + (n - 1)(b + c)，即，a = c + (n - 1)s3 （⭐）
    • 由⭐可知，从链表起点出发到入环节点的距离a，等于从相遇节点出发向入环节点移动 n - 1 圈再走一个从相遇节点到入环节点的距离
    • 即，两个指针，一个从起始节点，另一个从相遇节点，同时出发，他们最终会经过相等数量的节点，在入环节点处相遇，其中第一个节点一直在环外走，第二个节点一直在环内走
• 时间复杂度:O(N)
• 空间复杂度:O(1)

思路2 哈希表

• 遍历链表，把遍历过的节点存入哈希表中
• 当第一次出现被遍历到的节点已经存在于哈希表中的情况时，这个节点就是环形的入口节点
• 时间复杂度:O(N)
• 空间复杂度:O(N)

代码（Java）

思路1代码

public class Solution1 {    public ListNode detectCycle(ListNode head) {        if (head == null || head.next == null) {            return null;        }        ListNode slow = head, fast = head;        while (fast != null) {            slow = slow.next;            if (fast.next != null) {                fast = fast.next.next;            } else {                return null;            }            if (fast == slow) {                ListNode p = head;                while (p != slow) {                    p = p.next;                    slow = slow.next;                }                return p;            }        }        return null;    }}

思路2代码

public class Solution2 {    public ListNode detectCycle(ListNode head) {        if (head == null || head.next == null) {            return null;        }        Set<ListNode> set = new LinkedHashSet<>();        ListNode slow = head;        while (slow != null){            if (set.contains(slow)){                return slow;            }            set.add(slow);            slow = slow.next;        }        return null;    }}

题目描述

• 给定两个 非空 的链表，表示两个非负的整数。
• 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
• 请将两个数相加，并以相同形式返回一个表示和的链表。
• 可以假设除了数字 0 之外，这两个数都不会以 0 开头。

exampleinput  : l1 = [2,4,3], l2 = [5,6,4]output : [7,0,8]note   : 342 + 465 = 807.input  : l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]output : [8,9,9,9,0,0,0,1]

解题思路

思路1 模拟

• 同时遍历两个链表，并维护进位标志，都不为空时，对应位置的2个节点值和进位标志求和得到sum，在结果链表末尾创建新节点并将其赋值为sum

• 其中一个为空时，继续维护进位标志，只遍历不空的那个链表，对应位置的1个节点值和进位标志求和得到sum1，在结果链表末尾创建新节点并将其赋值为sum1

• 时间复杂度：O(max(m, n))

• 空间复杂度：O(1)

  思路2 递归

• 从思路1变形得到的

• 递归退出边界：两个节点都为null，且进位标志为0，意味着不需要创建新节点；若两个节点为null，但进位标志不为0，说明结果链表末尾需要进位补1，即创建新节点且其值为1

• 递归操作：创建新节点node，其值为两个参数节点的值与进位标志的值之和

• 递归过程：因为原始数值本身以逆序存放在链表中，所以可以做正向的思考，直接把node.next的求解扔进递归即可

• 时间复杂度：O(max(m, n))

• 空间复杂度：O(max(m, n))

  思路3 BigInteger

• 分别遍历两个链表，用StringBuilder记录其逆序数值

• 分别反转两个链表，得到原始数值

• 使用BigInteger分别接收两个原始数组并求和，得到的结果重新赋给StringBuilder

• 逆序遍历结果字符串，将其字符转换成int类型并以此存放到结果链表种

• 时间复杂度：O(max(m, n))

• 空间复杂度：O(1)

  代码（Java）

思路1代码

public class Solution1 {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        int jin = 0;        int sum = 0;        ListNode list = new ListNode(0);        ListNode r = list;        while (l1 != null && l2 != null) {            sum = l1.val + l2.val + jin;            jin = sum / 10;            sum %= 10;            r.next = new ListNode(sum);            r = r.next;            l1 = l1.next;            l2 = l2.next;        }        while (l1 != null) {            sum = l1.val + jin;            jin = sum / 10;            sum %= 10;            r.next = new ListNode(sum);            r = r.next;            l1 = l1.next;        }        while (l2 != null) {            sum = l2.val + jin;            jin = sum / 10;            sum %= 10;            r.next = new ListNode(sum);            r = r.next;            l2 = l2.next;        }        if (jin == 1) {            r.next = new ListNode(1);        }        return list.next;    }    // 以下代码是上方代码的简化版    public ListNode addTwoNumbersSim(ListNode l1, ListNode l2) {        int jin = 0;        ListNode list = new ListNode(0);        ListNode r = list;        while (l1 != null || l2 != null) {            int n1 = l1 == null ? 0 : l1.val;            int n2 = l2 == null ? 0 : l2.val;            int sum = n1 + n2 + jin;            jin = sum / 10;            sum %= 10;            r.next = new ListNode(sum);            r = r.next;            if (l1 != null) {                l1 = l1.next;            }            if (l2 != null) {                l2 = l2.next;            }        }        if (jin == 1) {            r.next = new ListNode(1);        }        return list.next;    }}

思路2代码

public class Solution2 {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        return loop(l1, l2, 0);    }    public ListNode loop(ListNode l1, ListNode l2, int jin) {        if (l1 == null && l2 == null && jin == 0){            return null;        }        int n1 = l1 == null ? 0 : l1.val;        int n2 = l2 == null ? 0 : l2.val;        int sum = n1 + n2 + jin;        jin = sum / 10;        sum %= 10;        ListNode node = new ListNode(sum);        node.next = loop(l1 != null ? l1.next : null, l2 != null ? l2.next : null, jin);        return node;    }}

思路3代码

public class Solution3 {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        StringBuilder m = new StringBuilder();        StringBuilder n = new StringBuilder();        while (l1 != null) {            m.append(l1.val);            l1 = l1.next;        }        while (l2 != null) {            n.append(l2.val);            l2 = l2.next;        }        BigInteger mm = new BigInteger(m.reverse().toString());        BigInteger nn = new BigInteger(n.reverse().toString());        BigInteger res = mm.add(nn);        StringBuilder s = new StringBuilder(res.toString());        ListNode list = new ListNode(0);        ListNode r = list;        for (int i = s.length() - 1; i >= 0; i--){            r.next = new ListNode(s.charAt(i) - '0');            r = r.next;        }        return list.next;    }}

题目描述

• 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
• 只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。
• 设计一个算法来计算所能获取的最大利润。
• 返回可以从这笔交易中获取的最大利润。
• 如果不能获取任何利润，返回 0 。

exampleinput  : prices = [7,1,5,3,6,4]output : 5note   : 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。         注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，不能在买入前卖出股票。input  : prices = [7,6,4,3,1]output : 0note   : 在这种情况下, 没有交易完成, 所以最大利润为 0。

解题思路

思路1 动态规划

• 维护最大利润数组
  • 借助额外的数组 dp，记录在价格数组中，从开始到每个位置的共 n-1 个子区间内，可以获得的最大利润
  • dp[i]表示前i天的子区间内，可以获得的最大利润
  • 初始dp[0] = 0，因为不能在当天操作，所以无法获得利润
  • 动态规划的状态转移方程：dp[i] = Math.max(prices[i] - minPrice, dp[i - 1])
  • 状态转移方程解释：如果当天的价格prices[i]与历史最低价格的差sub，大于前一天可以获得的最大利润dp[i-1]，则把当天可获得的最大利润dp[i]设置为sub；否则把dp[i]设置为与dp[i-1]相同的值，说明可以获得的最大利润的卖出时间在之前的某天，所以只要保证在今天之前卖出，持续到今天依然是能够保证最大利润。
  • 那么遍历结束后，数组dp的最后一个元素值，就是整个时间区间内，可以获得的最大利润值。
  • 时间复杂度O(n)
  • 空间复杂度O(n)
• 只维护最大利润变量
  • 其实是 维护最大利润数组 做法的变形，即直接在遍历过程中通过比较记录最大差额
  • 时间复杂度O(n)
  • 空间复杂度O(1)

    思路2 暴力法（会超出时间限制）

• 仅供参考，实际提交无法通过测试，会超出时间限制
• 双重循环，找到满足以下条件的最大差值就是最大利润，即：
  • Max(prices[j] - prices[i]) && j > i
  • 0 < i < prices.length - 1, i + 1 < j < prices.length
• 时间复杂度O(n^2)
• 空间复杂度O(1)

代码（Java）

思路1代码

public class Solution1 {    public int maxProfitDp1(int[] prices) {        int n = prices.length;        int[] dp = new int[n];        dp[0] = 0;        int minPrice = prices[0];        for (int i = 1; i < n; i++) {            // dp[i] = Math.max(prices[i] - minPrice, dp[i - 1]);            // minPrice = Math.min(minPrice, prices[i]);                        if (prices[i] - minPrice > dp[i - 1]) {                dp[i] = prices[i] - minPrice;            } else {                dp[i] = dp[i - 1];            }            if (minPrice > prices[i]) {                minPrice = prices[i];            }        }        return dp[n - 1];    }        // DP2为动态规划的简化，放弃额外的数组记录，只维护一个最大利润变量，是从DP衍生而来的    public int maxProfitDp2(int[] prices) {        int len = prices.length;        int maxProfile = 0;        int minPrice = prices[0];        for (int i = 1; i < len; i++) {            // maxProfile = Math.max(prices[i] - minPrice, maxProfile);            // minPrice = Math.min(minPrice, prices[i]);            if (prices[i] - minPrice > maxProfile) {                maxProfile = prices[i] - minPrice;            }            if (minPrice > prices[i]){                minPrice = prices[i];            }        }        return maxProfile;    }}

思路2代码

public class Solution2 {    public int maxProfit(int[] prices) {        int len = prices.length;        int maxProf = 0;        for (int i = 0; i < len - 1; i++) {            for (int j = i + 1; j < len; j++) {                maxProf = Math.max(prices[j] - prices[i], maxProf);            }        }        return maxProf;    }}