最近在学习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.无重复字符的最长子串
给定一个字符串，找出其中不含有重复字符的 最长子串 的长度。
示例 : 输入: "abcabcbb"
输出:
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 。
示例 : 输入: "bbbbb"
输出:
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 。
示例 : 输入: "pwwkew"
输出:
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 。
请注意，答案必须是 子串 的长度，"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;
}
}