作业一、
直接使用 java 的 LinkdList 测试(有交叉)：
public class Runner {
public static void main(String[] args) {
List<String> linkedList1 = new LinkedList<>(); linkedList1.add("a"); linkedList1.add("b"); System.out.println("linkedList1: " + linkedList1); List<String> linkedList2 = new LinkedList<>(); linkedList2.add("d"); linkedList2.add("e"); linkedList2.add("f"); System.out.println("linkedList2: " + linkedList2); List<String> linkedList3 = new LinkedList<>(); linkedList3.add("x"); linkedList3.add("y"); linkedList3.add("z"); System.out.println("linkedList3: " + linkedList3);
System.out.println("Cross...."); linkedList1.addAll(linkedList3); System.out.println("linkedList1: " + linkedList1); linkedList2.addAll(linkedList3); System.out.println("linkedList2: " + linkedList2);
int diff = Math.abs(linkedList1.size() - linkedList2.size()); if (linkedList1.size() > linkedList2.size()) { linkedList1 = linkedList1.subList(diff, linkedList1.size()); } else { linkedList2 = linkedList2.subList(diff, linkedList2.size()); }
String cross = null; for (int i = 0; i < linkedList1.size(); i++) { String data1 = linkedList1.get(i); String data2 = linkedList2.get(i); if(data1.equals(data2)){ cross = data1; break; } } if(null == cross){ System.out.println("No cross found!"); }else{ System.out.println("Cross found: data is " + cross); } }}
复制代码
结果：
linkedList1: [a, b]linkedList2: [d, e, f]linkedList3: [x, y, z]Cross....linkedList1: [a, b, x, y, z]linkedList2: [d, e, f, x, y, z]Cross found: data is x
Process finished with exit code 0
复制代码
无交叉：
public class Runner {
public static void main(String[] args) {
List<String> linkedList1 = new LinkedList<>(); linkedList1.add("a"); linkedList1.add("b"); System.out.println("linkedList1: " + linkedList1); List<String> linkedList2 = new LinkedList<>(); linkedList2.add("d"); linkedList2.add("e"); linkedList2.add("f"); System.out.println("linkedList2: " + linkedList2); List<String> linkedList3 = new LinkedList<>(); linkedList3.add("x"); linkedList3.add("y"); linkedList3.add("z"); System.out.println("linkedList3: " + linkedList3);
//System.out.println("Cross...."); //linkedList1.addAll(linkedList3); //System.out.println("linkedList1: " + linkedList1); //linkedList2.addAll(linkedList3); //System.out.println("linkedList2: " + linkedList2);
int diff = Math.abs(linkedList1.size() - linkedList2.size()); if (linkedList1.size() > linkedList2.size()) { linkedList1 = linkedList1.subList(diff, linkedList1.size()); } else { linkedList2 = linkedList2.subList(diff, linkedList2.size()); }
String cross = null; for (int i = 0; i < linkedList1.size(); i++) { String data1 = linkedList1.get(i); String data2 = linkedList2.get(i); if(data1.equals(data2)){ cross = data1; break; } } if(null == cross){ System.out.println("No cross found!"); }else{ System.out.println("Cross found: data is " + cross); } }}
复制代码
结果：
linkedList1: [a, b]linkedList2: [d, e, f]linkedList3: [x, y, z]No cross found!
Process finished with exit code 0
复制代码
时间复杂度 O(n)、空间复杂度 O(1)。
作业二、
数据结构：
数据的逻辑结构有以下两大类：
线性结构：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。
线性表是一个典型的线性结构。数组、链表、队列、栈等都是线性结构。
非线性结构：在该类结构中至少存在一个数据元素,它具有两个或者两个以上的前驱或后继。
如树和二叉树集合结构和多维数组、广义表、图、堆等数据结构都是非线性结构。
算法：
算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括：
（1）可行性；
（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；
（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；
（4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
时间复杂度：
定义：设问题的规模为 n，把一个算法的时间耗费 T(n)称为该算法的时间复杂度，它是问题规模为 n 的函数。
常用的算法的时间复杂度的顺序：（比较时只看最高次幂）
for ( i = 1 , i < = 10 , i++ ) x=x+c； =>O(1)for ( i = 1 , i < = n , i++ ) x=x+n； =>O(n)多嵌套一个for，则为 =>O(n^2) 以此类推真题难点：i = 1，while（i < = n)i = i * 3；=>O(log3^n)i = i * 2；=>O(log2^n) 以此类推
复制代码
评论