五一劳动节网页设计素材新网$网站优化

14. 最长公共前缀

1.题目：

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

2.思路：

最长公共前缀：横向扫描

结论：查找字符串数组中的最长公共前缀的方法，依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。

如果在尚未遍历完所有的字符串时，最长公共前缀已经是空串，则最长公共前缀一定是空串，因此不需要继续遍历剩下的字符串，直接返回空串即可。

取第一个字符依次和后续字符比较，更新最长公共前缀。

3.代码：

public String longestCommonPrefix(String[] strs) {String prefix=strs[0];for(int i=1;i<strs.length;i++){prefix=longestCommonPrefix(prefix,strs[i]);if(prefix.length()==0){break;}}return prefix;}public String longestCommonPrefix(String a,String b){int length=Math.min(a.length(),b.length());int index=0;// while(index<length && a.charAt(index)==b.charAt(index)){//     index++;// }for(int i=0;i<length;i++){if(a.charAt(i)==b.charAt(i)){index++;}else{break;}}return a.substring(0,index);}

2. 两数相加

1.题目：

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

2.思路：

要考虑进位（同时添加头指针方便操作）

3.代码：

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode pre=new ListNode(0);ListNode curr=pre;int carry=0;while(l1!=null ||l2!=null){int x=l1==null ? 0:l1.val;int y=l2==null ? 0:l2.val;int sum=x+y+carry;carry=sum/10;sum=sum%10;curr.next=new ListNode(sum);curr=curr.next;if(l1!=null){l1=l1.next;}if(l2!=null){l2=l2.next;}}if(carry==1){curr.next=new ListNode(carry);}return pre.next;}