算法题

作者：office多多 链接：https://www.nowcoder.com/discuss/374134?type=0&order=0&pos=67&page=1

1. 写代码，类似高考成绩，一个表中有很多数据（无序的），给你一个成绩，查出在表中的排名
2. 找出这两个链表是否有相交的点
3. 判断链表有没有环，环起点在哪儿。
4. 手撕topk，时间复杂度是多少。
5. 写个算法，实现抢红包随机获取金额的过程参考
6. 链表反转
7. 两数之和（leetcode第一题～、～）
8. 判断一个字符串是否为另一个字符串子串（暴力写的）
9. 股票最大利润
10. 实现单链表前后交叉排序：1,2,3,4,5,6 变成 1,4,2,5,3,6
11. 因式分解
12. 有序二叉树，一种遍历方法使之有序，中序遍历。
13. 非递归实现先序遍历
14. 找无序数组中第k个数（一开始说用堆实现、后来我又想着用快排的partation实现）
15. 算法题：从字符串S变到T，插入消耗2、删除消耗2、替换消耗3、求最小消耗
16. 算法题：两个栈实现一个队列（实现push、pop、count三个函数）（简单）
17. strcpy的实现
18. 给出两个链表，找出相同的链接。a->b->c->d->f、b1->a1->c1->d->f
19. 二叉树的遍历方式，手写先序遍历(参考代码：https://www.cnblogs.com/anzhengyu/p/11083568.html)
20. 两个字符串的最长公共子串(参考代码：https://www.cnblogs.com/anzhengyu/p/11166708.html)
21. 查找二叉树最大深度
22. 二叉树遍历
23. 写代码判断IP地址(https://blog.csdn.net/u014259820/article/details/78833196?utm_source=distribute.pc_relevant.none-task)
24. 在字符串中找出不重复字符的个数
25. 找出两个只出现一次的数字，其余的数字都出现了两次
26. 给n元钱，m个人，写个随机分钱的函数
27. 两个栈实现一个队列
28. 给个数组求连续子序列最大和
29. 写一个程序；给一个数组，a【2 -2 3 3 6 -9 7】输出a【2 -2 3 -9 3 6 7】输入正负数都有数组，输出数组正负交替出现，多的那一类都放在后面；
30. 给定一个数组 输出和为k的两个数的位置 a【2 7 3 5 11】k=9 输出 0 1 https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/
31. 算法题：实现两个String字符串寻找最大公共子字符串
32. 让写一个洗牌的函数，写完问我为啥那样写、再写一个打印牌的函数，问我洗完牌之后345不连在一起的概率 如何模拟一副扑克牌的洗牌过程
33. 查找字符串中重复的子串，并输出重复的次数 https://blog.csdn.net/zouheliang/article/details/80649584
34. 判断是否为平衡二叉树
35. 找出一个字符串的最长不重复子串(https://www.cnblogs.com/linghu-java/p/9037262.html)

数组

• 数组求并集（利用set集合的元素唯一性）
• 一个数组中有正数和负数，找出来和最大的子数组
• 16瓶水中有1瓶水有毒，小白鼠喝了有毒的水1个小时后会死，一个小白鼠可以喝多瓶水，一瓶水也可以被多个小白鼠喝，现在给1个小时时间，最少需要几只小白鼠能够判断出来14瓶水是无毒的？
• 小白鼠问题。16瓶正常水，1瓶毒水，小白鼠喝下毒水后一小时死亡，只给一小时时间，最少用多少只小白鼠可以检测出14瓶正常水？

链表

二叉树

动态规划

• 最长公共子序列

dp[i][j]：表示子串A[0...i]（数组长度为n）和子串B[0...j]（数组长度为m）的最长公共子序列

当A[i] == B[j]时，dp[i][j] = dp[i-1][j-1] + 1;

否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

最优解为dp[n-1][m-1];

JAVA代码实现：

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str1 = scanner.nextLine().toLowerCase();
            String str2 = scanner.nextLine().toLowerCase();
            System.out.println(findLCS(str1, str1.length(), str2, str2.length()));
        }
    }
 
    public static int findLCS(String A, int n, String B, int m) {
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
                }
            }
        }
        return dp[n][m];
    }
}

• 最长回文子串

https://blog.csdn.net/wolfGuiDao/article/details/104590791

• 最长上升子序列

https://blog.csdn.net/zangdaiyang1991/article/details/94555112

• 最长上升子串

https://blog.csdn.net/qq_41706331/article/details/90271543

递归

• 不用循环找出最大值

数组

字符串

Tip：本来有很多我准备的资料的，但是都是外链，或者不合适的分享方式，所以大家去公众号回复【资料】好了。

现在免费送给大家，在我的公众号 好好学java 回复 资料 即可获取。

有收获？希望老铁们来个三连击，给更多的人看到这篇文章

1、老铁们，关注我的原创微信公众号「好好学java」，专注于Java、数据结构和算法、微服务、中间件等技术分享，保证你看完有所收获。

2、给俺一个 star 呗，可以让更多的人看到这篇文章，顺便激励下我继续写作，嘻嘻。