最近在学习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<r+1;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; } }