算法练习之合并两个有序链表, 删除排序数组中的重复项,移除元素,实现strStr(),搜索插入位置
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法练习之合并两个有序链表, 删除排序数组中的重复项,移除元素,实现strStr(),搜索插入位置，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4982字，纯文字阅读大概需要8分钟。
内容图文
最近在学习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;
}
}
内容总结
以上是互联网集市为您收集整理的算法练习之合并两个有序链表, 删除排序数组中的重复项,移除元素,实现strStr(),搜索插入位置全部内容，希望文章能够帮你解决算法练习之合并两个有序链表, 删除排序数组中的重复项,移除元素,实现strStr(),搜索插入位置所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。