算法练习之合并两个有序链表, 删除排序数组中的重复项,移除元素,实现strStr(),搜索插入位置,无重复字符的最长子串详解编程语言

最近在学习java，但是对于数据操作那部分还是不熟悉

因此决定找几个简单的算法写，用php和java分别实现

1.合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：1- 2- 4, 1- 3- 4 

输出：1- 1- 2- 3- 4- 4

java

/** 

 * Definition for singly-linked list. 

 * public class ListNode { 

 * int val; 

 * ListNode next; 

 * ListNode(int x) { val = x; } 

 * } 

class Solution { 

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 

 ListNode rs = new ListNode(0); 

 ListNode point = rs; 

 while (l1!=null l2!=null) { 

 if(l1.val l2.val){ 

 point.next = l1; 

 point = point.next; 

 l1 = l1.next; 

 }else{ 

 point.next = l2; 

 point = point.next; 

 l2 = l2.next; 

 if(l1==null){ 

 point.next = l2; 

 }else{ 

 point.next = l1; 

 return rs.next; 

}

php

/** 

 * Definition for a singly-linked list. 

 * class ListNode { 

 * public $val = 0; 

 * public $next = null; 

 * function __construct($val) { $this- val = $val; } 

 * } 

class Solution { 

 /** 

 * @param ListNode $l1 

 * @param ListNode $l2 

 * @return ListNode 

 function mergeTwoLists($l1, $l2) { 

 $rs = new ListNode(0); 

 $point = $rs; 

 while (!empty($l1) !empty($l2)) { 

 if($l1- val $l2- val){ 

 $point- next = $l1; 

 $point = $point- next; 

 $l1 = $l1- next; 

 }else{ 

 $point- next = $l2; 

 $point = $point- next; 

 $l2 = $l2- next; 

 if($l1==null){ 

 $point- next = $l2; 

 }else{ 

 $point- next = $l1; 

 return $rs- next; 

}

测试

$l1 = new ListNode(5); 

$l11 = new ListNode(2); 

$l1- next = $l11; 

$l12 = new ListNode(4); 

$l11- next = $l12; 

$l2 = new ListNode(1); 

$l21 = new ListNode(2); 

$l2- next = $l21; 

$l22 = new ListNode(4); 

$l21- next = $l22; 

$aa = new Solution(); 

$rs = $aa- mergeTwoLists($l1, $l2);

2.删除排序数组中的重复项

给定一个排序数组，需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1: 

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

不需要考虑数组中超出新长度后面的元素。
 

示例 2: 

给定 nums = [0,0,1,1,1,2,2,3,3,4], 

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 

不需要考虑数组中超出新长度后面的元素。

java

class Solution { 

 public int removeDuplicates(int[] nums) { 

 int i=0; 

 for(int n :nums){ 

 if(i 1||n nums[i-1]){ 

 nums[i++] = n; 

 return i; 

}

php

class Solution { 

 /** 

 * @param Integer[] $nums 

 * @return Integer 

 function removeDuplicates( $nums) { 

 $i = 0; 

 foreach ($nums as $key = $value) { 

 if($i 1||$value $nums[$i-1]){ 

 $nums[$i++] = $value; 

 return $i; 

}

说明：

数组是排序之后的，因此移动的为

a.第一个元素，指向它

b.比指向的数大的元素

3.移除元素

给定一个数组 nums 和一个值 val，需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。不需要考虑数组中超出新长度后面的元素。

示例 1: 

给定 nums = [3,2,2,3], val = 3, 

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 

不需要考虑数组中超出新长度后面的元素。
 

示例 2: 

给定 nums = [0,1,2,2,3,0,4,2], val = 2, 

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。 

注意这五个元素可为任意顺序。 

不需要考虑数组中超出新长度后面的元素。

java

class Solution { 

 public int removeElement(int[] nums, int val) { 

 int i=0; 

 for(int n:nums){ 

 if(val!=n){ 

 nums[i++] = n; 

 return i; 

}

php

class Solution { 

 /** 

 * @param Integer[] $nums 

 * @param Integer $val 

 * @return Integer 

 function removeElement( $nums, $val) { 

 $i = 0; 

 foreach ($nums as $key = $value) { 

 if($value!=$val){ 

 $nums[$i++] = $value; 

 return $i; 

}

4.实现strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1: 

输入: haystack = "hello", needle = "ll" 

输出: 2
 

示例 2: 

输入: haystack = "aaaaa", needle = "bba" 

输出: -1

java

class Solution { 

 public int strStr(String haystack, String needle) { 

 if(needle.isEmpty()||needle.equals(haystack)) return 0; 

 int l=needle.length(); 

 int r = haystack.length()-l; 

 for(int i=0;i i++){ 

 String tempStr=haystack.substring(i,l+i); 

 if(tempStr.equals(needle)) 

 return i; 

 return -1; 

}

php

class Solution { 

 /** 

 * @param String $haystack 

 * @param String $needle 

 * @return Integer 

 function strStr($haystack, $needle) { 

 if(empty($needle)||$needle ==$haystack) return 0; 

 $l=strlen($needle); 

 $r = strlen($haystack)-$l; 

 for($i=0;$i $r+1;$i++){ 

 $tempStr=substr($haystack,$i, $l); 

 if($tempStr==$needle) 

 return $i; 

 return -1; 

}

5.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1: 

输入: [1,3,5,6], 5 

输出: 2
 

示例 2: 

输入: [1,3,5,6], 2 

输出: 1
 

示例 3: 

输入: [1,3,5,6], 7 

输出: 4
 

示例 4: 

输入: [1,3,5,6], 0 

输出: 0

java

class Solution { 

 public int searchInsert(int[] nums, int target) { 

 int i = 0; 

 for(;i nums.length;i++){ 

 if(target =nums[i])break; 

 return i; 

}

php

class Solution { 

 /** 

 * @param Integer[] $nums 

 * @param Integer $target 

 * @return Integer 

 function searchInsert($nums, $target) { 

 $i=0; 

 for($i=0;$i count($nums);$i++){ 

 if($target =$nums[$i]) break; 

 return $i; 

}

 6.无重复字符的最长子串

给定一个字符串，找出其中不含有重复字符的 最长子串 的长度。

示例 1: 

输入: "abcabcbb" 

输出: 3 

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 

示例 2: 

输入: "bbbbb" 

输出: 1 

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 

示例 3: 

输入: "pwwkew" 

输出: 3 

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 

请注意，答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

java

class Solution { 

 public int lengthOfLongestSubstring(String s) { 

 int longSub = 0; 

 if(s.isEmpty()) return 0; 

 if(s.length()==1) return 1; 

 char[] arr = s.toCharArray(); 

 String str = String.valueOf(arr[0]); 

 longSub = 1; 

 for(int i=1;i s.length();i++){ 

 int pos = str.indexOf(arr[i]); 

 if (pos !=-1) { 

 str = str.substring(pos+1)+arr[i]; 

 }else{ 

 str+=arr[i]; 

 if(str.length() longSub) longSub = str.length(); 

 return longSub; 

}

php

class Solution { 

 /** 

 * @param String $s 

 * @return Integer 

 function lengthOfLongestSubstring($s) { 

 $len = strlen($s); 

 if($len==0) return 0; 

 $str = $s[0]; 

 $longSub = 1; 

 for ($i = 1; $i $len; $i++) { 

 $pos = strpos($str, $s[$i]); 

 if ($pos === false) { 

 $str .= $s[$i]; 

 } else { 

 $str = substr($str, $pos + 1) . $s[$i]; 

 $tmp = strlen($str); 

 if ($longSub $tmp) { 

 $longSub = $tmp; 

 return $longSub; 

}

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/20361.html