【leetcode-php】2021-05-4

1、删除有序数组中的重复项

给你一个有序数组 nums ,请你** 原地** 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

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

示例 1:

1
2
3
输入:nums = [1,1,2]
输出:2, nums = [1,2]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* @param Integer[] $nums
* @return Integer
*/
// 方法一
function removeDuplicates(&$nums) {
$nums = array_keys(array_flip($nums));
return count($nums);
}

// 方法二
function removeDuplicates(&$nums) {
$len = count($nums);
$num = 0;
if(empty($nums)){
return 0;
}
for($i = 0; $i < $len; $i++){
if($i == $len - 1){
$num++;
break;
}
if($nums[$i] == $nums[$i+1]){
unset($nums[$i]);
continue;
}
$num++;
}

}

2、移除元素

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

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组

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

Solution

1
2
3
4
5
6
7
8
9
10
function removeElement(&$nums, $val) {
if(empty($nums)) return $nums;
$count = count($nums);
for($i = 0;$i < $count; $i++){
if($nums[$i] == $val){
unset($nums[$i]);
}
}
return count($nums);
}

实现 strStr()

给你两个字符串 haystackneedle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回 -1

说明:

needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1:

1
2
输入:haystack = "hello", needle = "ll"
输出:2

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function strStr($haystack, $needle) {
if(empty($needle) || $haystack == $needle) return 0;
$arr = str_split($haystack);
$len = strlen($needle);
$count = count($arr);
if($len == $count && $haystack != $needle) return -1;
if($len > $count) return -1;
for($i = 0; $i < $count; $i++){
$s = join('',array_slice($arr,$i,$len));
if($s == $needle){
return $i;
}
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function strStr($haystack, $needle) {
if($needle == '') return 0;
$len = strlen($haystack);
$length = strlen($needle);

$i = 0;$j = 0;
while($i<$len && $j < $length){
if($haystack[$i] == $needle[$j]){
$i++;
$j++;
}else{
$i = $i - $j + 1;
$j = 0;
}
if($j == $length){
return $i-$j;
}
}
return -1;
}

3、搜索插入位置

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

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

示例 1:

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer
*/
function searchInsert($nums, $target) {
$count = count($nums);
if($target > $nums[$count-1]) return $count;
for($i = 0; $i < $count; $i++){
if($nums[$i] >= $target){
return $i;
}else{
continue;
}
}
}
}

4、最大子序和

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例 1:

1
2
3
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

1
2
输入:nums = [1]
输出:1

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 贪心算法
function maxSubArray($nums) {
$max_num = max($nums);
if($max_num <= 0) return $max_num;
$sum = $max = $nums[0];
$count = count($nums);
for($i = 1; $i < $count; $i++){
if($sum < 0){
$sum = $nums[$i];
}else{
$sum += $nums[$i];
}
$max = max($max,$sum);
}
return $max;
}
// 动态规划
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function maxSubArray($nums) {
$count = count($nums);
for($i = 1; $i < $count; $i++){
if($nums[$i - 1] > 0){
$nums[$i] += $nums[$i - 1];
}
}
return max($nums);
}
}

5、最长公共前缀

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

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

示例 1:

1
2
输入:strs = ["flower","flow","flight"]
输出:"fl"

示例 2:

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

提示:

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

/**
* @param String[] $strs
* @return String
*/
function longestCommonPrefix($strs) {
$pre = '';
if (empty($strs)) return $pre;
if (! isset($strs[1])) return $strs[0];
rsort($strs, SORT_STRING);
$first = array_shift($strs);
$last = array_pop($strs);
$len = strlen($first);
for ($i = 0; $i < $len; ++$i)
{
if ($first[$i] != $last[$i]) break;
$pre .= $first[$i];
}
return $pre;
}
}

6、有效括号

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

示例 1:

1
2
输入:s = "()"
输出:true

示例 2:

1
2
输入:s = "()[]{}"
输出:true

示例 3:

1
2
输入:s = "(]"
输出:false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {

/**
* @param String $s
* @return Boolean
*/
function isValid($s) {
$strArr = [
')' => '(',
'}' => '{',
']' => '[',
];
if(strlen($s) % 2 != 0) return false;
$arr = str_split($s);
$stack = [];
foreach($arr as $str){
if(in_array($str,$strArr)){
array_push($stack,$str);
}else{
if(!empty($stack) && $strArr[$str] == $stack[count($stack) - 1] ){
array_pop($stack);
}else{
return false;
}
}

}
return empty($stack) ? true : false;
}
}
作者

Fahsa

发布于

2021-05-31

更新于

2021-06-02

许可协议

评论