编程题汇总

忘是亡心i 2023-02-17 02:19 5阅读 0赞

原文网址：[编程题汇总\_IT利刃出鞘的博客-CSDN博客][IT_-CSDN]

# 排序 #

## 冒泡排序 ##

[算法系列--排序算法\_feiying0canglang的博客-CSDN博客][--_feiying0canglang_-CSDN]

## 合并n个有序集合 ##

**其他网址**

> [【算法】将n个有序集合合并成一个新的有序集合\_Java\_Crick19931221的博客-CSDN博客][n_Java_Crick19931221_-CSDN]
> 
> [合并两个有序的数组\_牛客题霸\_牛客网][Link 1]

**方案2：外排**

> 将n个有序数集合并成一个新的有序集合,外排方式，时间复杂度list1.size()+...+listn.size()
> 
>     import java.util.*;
>     
>     public class Main {
>     
>     	public static void main(String[] args) {
>     		
>     		List<List<Integer>> lists = new ArrayList<>();
>     
>     		List<Integer> list1 = new ArrayList<>();
>     		list1.add(1);
>     		list1.add(2);
>     		list1.add(4);
>     		list1.add(8);
>     		List<Integer> list2 = new ArrayList<>();
>     		list2.add(1);
>     		list2.add(3);
>     		list2.add(5);
>     		list2.add(7);
>     		List<Integer> list3 = new ArrayList<>();
>     		list3.add(1);
>     		list3.add(6);
>     		list3.add(25);
>     		list3.add(56);
>     		List<Integer> list4 = new ArrayList<>();
>     		list4.add(9);
>     		list4.add(16);
>     		list4.add(25);
>     		list4.add(37);
>     
>     
>     		lists.add(list1);
>     		lists.add(list2);
>     		lists.add(list3);
>     		lists.add(list4);
>     
>     		mergeNSort(lists);
>     	}
>     
>     
>     	public static void mergeNSort(List<List<Integer>> lists) {
>     		List<Integer> result = lists.get(0);
>     
>     		for (int i = 1; i < lists.size(); i++) {
>     			result = mergeTwoSort(result, lists.get(i));
>     		}
>     
>     		for (int x : result) {
>     			System.out.print(x + " ");
>     		}
>     	}
>     
>     
>     	public static List<Integer> mergeTwoSort(List<Integer> list1, List<Integer> list2) {
>     		int p1 = 0, p2 = 0;
>     		List<Integer> list3 = new ArrayList<>();
>     
>     		while (p1 < list1.size() && p2 < list2.size()) {
>     			if (list1.get(p1) < list2.get(p2))
>     				list3.add(list1.get(p1++));
>     			else
>     				list3.add(list2.get(p2++));
>     		}
>     
>     		while (p1 < list1.size())
>     			list3.add(list1.get(p1++));
>     
>     		while (p2 < list2.size())
>     			list3.add(list2.get(p2++));
>     
>     		return list3;
>     	}
>     }

# 查找 #

## 两个数的和等于给定的数字 ##

**题目**

> 有序的数组 找出两个数的和等于给定的数字。要求时间O(n) 空间O(1)。

**分析**

> 1，暴力破解法  
> 就是使用两个for循环，这种效率很差
> 
>   
> public int\[\] twoSum(int\[\] nums, int target) \{  
> int length = nums.length;  
> for (int i = 0; i < length - 1; i++) \{  
> for (int j = i + 1; j < length; j++)  
> if (nums\[i\] + nums\[j\] == target)  
> return new int\[\]\{i+1, j+1\};  
> \}  
> return new int\[\]\{-1, -1\};  
> \}
> 
> 2，使用HashMap解决
> 
> public int\[\] twoSum(int\[\] nums, int target) \{  
> Map<Integer, Integer> m = new HashMap<>();  
> for (int i = 0; i < nums.length; i++) \{  
> if (m.get(target - nums\[i\]) != null) \{  
> return new int\[\]\{m.get(target - nums\[i\])+1, i+1\};  
> \}  
> m.put(nums\[i\], i);  
> \}  
> return new int\[\]\{0, 0\};  
> \}

# 递归与迭代 #

f(0)=0;f(1)=1;f(n)=f(n-1)+f(n-2)。求f(n) （用递归和迭代两种方法）

**程序**

>     package org.example.a;
>     
>     public class Demo {
>         public static void main(String[] args) {
>             System.out.println("recursion: " + f1(6));
>             System.out.println("iteration: " + f2(6));
>         }
>     
>         //递归
>         public static int f1(int n){
>             if(n == 0 || n == 1){
>                 return n;
>             }else{
>                 return (f1(n - 1) + f1(n - 2));
>             }
>         }
>     
>         //迭代
>         public static int f2(int n){
>             int a0, a1, a2;
>             a0 = 0;
>             a1 = 1;
>             a2 = 0;
>             for(int i = 2; i <= n; i++){
>                 a2 = a0 + a1;
>                 a0 = a1;
>                 a1 = a2;
>             }
>             return a2;
>         }
>     }

**运行结果**

> recursion: 8  
> iteration: 8

# 路径 #

## 走台阶 ##

**其他网址**

> [字节算法题--N阶台阶，每次走一步或两步，计算共有多少种走法，并将每种走法打印出来。 - 知乎][--N_ -]

**题目**

> 总共100级台阶（任意级都行），小明每次可选择走1步、2步或者3步，问走完这100级台阶总共有多少种走法？

**分析**

> 这个问题本质上是斐波那契数列，
> 
> 假设只有一个台阶，那么只有一种跳法，那就是一次跳一级，f(1)=1；
> 
> 如果有两个台阶，那么有两种跳法，第一种跳法是一次跳一级，第二种跳法是一次跳两级,f(2)=2。
> 
> 如果有大于2级的n级台阶，那么假如第一次跳一级台阶，剩下还有n-1级台阶，有f(n-1)种跳法，假如第一次跳2级台阶，剩下n-2级台阶，有f(n-2)种跳法。这就表示f(n)=f(n-1)+f(n-2)。

**编码**

>     public class Test {
>         static final int s = 100; //自定义的台阶数
>      
>         static int compute(int stair){
>             if ( stair <= 0){
>                 return 0;
>             }
>             if (stair == 1){
>                 return 1;
>             }
>             if (stair == 2){
>                 return 2;
>             }
>             return compute(stair-1) + compute(stair-2);
>         }
>      
>         public static void main(String args[]) {
>             System.out.println("共有" + compute(s) + "种走法");
>         }
>     }

## x\*y的方格 ##

**其他网址**

> [给定一个n\*m矩阵，求从左上角到右下角走的项目3个问题？ - 代码先锋网][n_m_3_ -]

**题目**

> 有x\*y的方格，从左上角走到右下角，每次只能向右或者向下走一格，不能后退，问一共多少种走法？

**方案1：递归**

> **分析**
> 
> 这个问题跟上边的走台阶很像。思路是一样的：
> 
> 确定退出的条件：如果是x \* 1 或者 1 \* y，则只有一种走法
> 
> 对于一个起点，若向右走一格，则还剩f(x - 1, y)种走法；若向下走一格，则还剩f(x, y - 1)种走法，那么将这两者加起来即可：f(x - 1, y) + f(x, y - 1)

> **代码**
> 
>     package org.example.a;
>     
>     public class Demo {
>         public static void main(String[] args) {
>             System.out.println(f(3,2));
>         }
>     
>         private static int f(int x, int y) {
>             if (x == 1 || y == 1) {
>                 return 1;
>             }
>     
>             return f(x - 1, y) + f(x, y - 1);
>         }
>     }

**方案2：迭代**

> 分析：将上边的代码用迭代写法修改

**方案3：组合**

> **分析**
> 
> 组合问题，从左上角各自到右下角各自总共要走m+n-2步，每次可以向下或是向右走，向下走共需n-1步，所以从n+m-2步中选择n-1步（表示选哪个地方下来）。
> 
> 组合的公式：![\_\{\}^\{\}][gif.latex_7B_7D_5E_7B_7D]![C\_\{n\}^\{m\}\\textrm\{\} = \\frac\{P\_\{n\}^\{m\}\\textrm\{\}\}\{(n - m)!\} = \\frac\{n!\}\{m!(n - m)!\}][C_n_m_textrm_ _ _frac_P_n_m_textrm_n - m_ _ _frac_n_m_n - m]

> **代码**
> 
> 略

# 数字 #

## 奇数偶数 ##

**其他网址**

> [输入一个数字n，如果n为偶数则除以2，若为奇数则加1或者减1，直到n为1，求最少次数。写出一个函数 - 简书][n_n_2_1_1_n_1_ -]

**题目**

> 给出一个数字n，如果n是偶数就除以2，如果是奇数就选择+1或者-1，求最少几次能够使n变成1。

**分析**

> 乍一看，这题不是很简单么？奇数-1，偶数除以2，不就是最快的吗？
> 
> 但是，以15为例，如下所示，可以发现，刚开始+1比刚开始-1更快。
> 
> 如果刚开始-1：15 14 7 6 3 2 1
> 
> 如果刚开始+1：15 16 8 4 2 1
> 
> 总结规律：我们在遇到奇数的时候，尽量让操作后的结果（偶数）除以2之后仍然是偶数，这样下一次直接除就可以，可以省一步，可以达到最快。
> 
> 即：遇到奇数的时候，尽量让操作后的结果是4的倍数。

**代码**

>     package org.example.a;
>     
>     public class Demo {
>         public static void main(String[] args) {
>             System.out.println(f(31));
>         }
>     
>         private static int f(int n) {
>             int number = 0;
>             int tmp = n;
>     
>             while (tmp != 1) {
>                 if (tmp % 2 == 0) {
>                     tmp = tmp / 2;
>                 } else {
>                     if ((tmp + 1) % 4 == 0) {
>                         tmp += 1;
>                     } else {
>                         tmp -= 1;
>                     }
>                 }
>                 number++;
>             }
>             return number;
>         }
>     }

## 斐波那契数列 3的倍数 ##

**其他网址**

> [NowCoder数列(PAT)\_小黯-CSDN博客][NowCoder_PAT_-CSDN]

**题目**

> F(0) = 7，F(1) = 11，F(n) = F(n-1) + F(n-2) (n≥2)，数列中第n个数是否是3的倍数。

**分析**

> 这个题其实挺没意思的，就是个找规律题目：
> 
> f（0）=7， f（0）%3=1  
> f（1）=11，f（1）%3=2  
> f（2）=18，f（2）%3=0  
> f（3）=29，f（3）%3=2  
> f（4）=47，f（4）%3=2  
> f（5）=76，f（5）%3=1  
> f（6）=123，f（6）%3=0  
> f（7）=199，f（7）%3=1  
> f（8）=322，f（8）%3=1  
> f（9）=521，f（9）%3=2  
> ......
> 
> 可以发现，8为周期，则对8取余，余数为2， 6则为3的倍数。

# 二叉树 #

## 二叉树的镜像 ##

**其他网址**

> [二叉树的镜像\_牛客题霸\_牛客网][Link 2]

## 找到搜索二叉树两个错误节点 ##

[找到搜索二叉树中两个错误的节点\_牛客题霸\_牛客网][Link 3]

# 栈与队列 #

## 两个栈实现队列 ##

**其他网址**

> [用两个栈实现队列\_牛客题霸\_牛客网][Link 4]

# 字符串 #

## 判断字符串有无重复字符 ##

**其他网址**

> [Java 判断字符串有无重复字符\_覃会程的博客-CSDN博客][Java _-CSDN]

## 字符串最长的无重复字符的子字符串 ##

**其他网址**

> [查找一个字符串中最长不含重复字符的子字符串，计算该最长子字符串的长度 - SegmentFault 思否][- SegmentFault]

**代码**

>     package org.example.a;
>     
>     public class Demo {
>         public static void main(String[] args) {
>             String str = "abcdaefa";
>             System.out.println(longestSubString(str));
>         }
>     
>         private static String longestSubString(String str) {
>             int start = 0;
>             int end = 0;
>             int resultStart = 0;
>             int resultEnd = 0;
>     
>             for (int i = 0; i < str.length(); i++) {
>                 start = i;
>                 for (int j = i + 1; j < str.length(); j++) {
>                     if (str.charAt(j) == str.charAt(i)) {
>                         break;
>                     } else {
>                         end = j;
>                     }
>                 }
>                 // 保留更长的字符串的始末位置
>                 if (end - start > (resultEnd - resultStart)) {
>                     resultStart = start;
>                     resultEnd = end;
>                 }
>             }
>             return str.substring(resultStart, resultEnd);
>         }
>     }
> 
> 执行结果
> 
>     bcdaef

[IT_-CSDN]: https://knife.blog.csdn.net/article/details/106673400
[--_feiying0canglang_-CSDN]: https://blog.csdn.net/feiying0canglang/article/details/106451752
[n_Java_Crick19931221_-CSDN]: https://blog.csdn.net/Crick19931221/article/details/80584940
[Link 1]: https://www.nowcoder.com/practice/89865d4375634fc484f3a24b7fe65665?tpId=117
[--N_ -]: https://zhuanlan.zhihu.com/p/340837146
[n_m_3_ -]: https://www.codeleading.com/article/18312899824/
[gif.latex_7B_7D_5E_7B_7D]: https://latex.codecogs.com/gif.latex?_%7B%7D%5E%7B%7D
[C_n_m_textrm_ _ _frac_P_n_m_textrm_n - m_ _ _frac_n_m_n - m]: https://latex.codecogs.com/gif.latex?C_%7Bn%7D%5E%7Bm%7D%5Ctextrm%7B%7D%20%3D%20%5Cfrac%7BP_%7Bn%7D%5E%7Bm%7D%5Ctextrm%7B%7D%7D%7B%28n%20-%20m%29%21%7D%20%3D%20%5Cfrac%7Bn%21%7D%7Bm%21%28n%20-%20m%29%21%7D
[n_n_2_1_1_n_1_ -]: https://www.jianshu.com/p/d1dc131b6a82
[NowCoder_PAT_-CSDN]: https://blog.csdn.net/qq_44625774/article/details/105797232
[Link 2]: https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=117
[Link 3]: https://www.nowcoder.com/practice/4582efa5ffe949cc80c136eeb78795d6?tpId=117
[Link 4]: https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=117
[Java _-CSDN]: https://blog.csdn.net/HC199854/article/details/104112560
[- SegmentFault]: https://segmentfault.com/a/1190000023179799