485 最大连续一的个数

DAV%$A0V@84~20UTF}9QC%X.png

思路

设置计数器,结果存储器
当读到1的时候计数器就开始计数,且计数器的数值比结果存储器大时,将计数器的数值赋值给存储器
读到0时清空计数器
接着继续往下重复操作,每结束一次计数,就将当前的数和变量中的数做一个对比,保留最大值

遇到过的问题

1.思路错误
一开始的计划是读到0的时候就认为计数结束,但是这个结束条件会导致当数组的最后一位数为1时,无法触发计数器和结果存储器的数值大小对比,导致数据丢失

2.if nums[i] ==”1”
题目中明确给出的条件表示num[i]的类型为int型,不能此处条件写成了string类型,导致计数器无法正常工作

3.把if count > result: 改为result = max(count,result)
result = count
导致运行时间增加了50%,由此可见函数的使用应该考虑到对程序的时间或空间上的成本

而运行时间增长的原因为:
因为max涉及函数名称的字典查找，然后是函数调用，而直接<运算符则没有。
max 当你有更多的元素时，它开始变得有趣。

4虽然本题不需要考虑这个情况,但确实是缺乏减枝的意识
即 当nums 为null或nums的长度为0时,直接return 0
python中:
数组为空和 数组长度为0是等价的

java中:
nums是一个数组，可以看到他们的区别。
intarray = null;数组为空，此时array不指向任何对象;
int[array = new array[O];定义一个长度为0的数组;
int[ array = new array[2];定义一个长度为2的数组，此时如果数组没有被初始化，默认的值为null;
一般先判断nums 是否为空，然后再判断长度是否为0，因为可能报空指针异常。
所以如果在一行代码中要同时判断的时候需要这样写:
if(array == null || array.length =-= o)
因为Ⅱ是短路或，前面的符合了后面的就不考虑了。

python代码

  1. #!/usr/bin/env python 
  2. # -*- coding:utf-8 -*-
  3. __author__ = 'C2TR'
  4. def findMaxConsecutiveOnes(nums):
  5.     count = 0
  6.     result = 0
  7.     for i in range(len(nums)):
  8.         if nums[i] == 1 :
  9.             count += 1
  10.             if count > result:
  11.                 result = count
  13.             else:
  14.                 count = 0
  15.                 return result
  16.             nums = [1,1,0,1,1,1]
  17. print(findMaxConsecutiveOnes(nums))

java代码

  1. class Solution {
  2.     public int findMaxConsecutiveOnes(int[] nums) {
  3.         int count = 0;
  4.         int result = 0;
  5.         int len_nums  = nums.length;
  6.         for(int i = 0;i<len_nums;i++){
  7.             if (nums[i] == 1){
  8.                 count++;
  9.                 if (count > result){
  10.                     result = count;
  11.                 }
  12.             }else{
  13.                 count = 0;
  14.             }
  16.         }
  17.         return result;
  19.     }
  20. }

滑动窗口思想

  1. class Solution {
  2.     public int findMaxConsecutiveOnes(int[] nums) {
  3.         int length = nums.length;
  4.         int left = 0;
  5.         int right = 0;
  6.         int maxSize = 0;
  8.         while(right < length){
  9.             //当窗口中所有元素为 1 时，右指针向右移，扩大窗口。
  10.             if (nums[right++] == 0){
  11.                 //当窗口中存在 0 时，计算连续序列长度，左指针指向右指针。
  12.                 maxSize = Math.max(maxSize, right - left - 1);
  13.                 left = right;
  14.             }
  15.         }
  16.         // 因为最后一次连续序列在循环中无法比较，所以在循环外进行比较
  17.         return Math.max(maxSize, right - left);
  18.     }
  19. }

心得总结

想解题思路的时候,应当动笔并着重在题目给出的例子上进行分析
正确的思路应该是 先按给出的输入做一个计算
[1,1,0,1,1,1]
首先可以分为
1,1 长度为2
0
1,1,1 长度为3
其中[1,1]的部分以1开头,以0结束
而[1,1,1]的部分以1开头,以数组的末尾为结束
因此共同的规律落在1的判定上,而不能使用0为计数结束的判定

283 移动零

![JWAIKLL9$FYSX{@%6CO~2J.png

思路:

识别到0就把它给丢出去没然后在尾部加一个零

定义一个指针记录0的位置,再定义一个指针标记非零的位置,找到一个为零一个为非零时就直接进行交换

定义一个指针从0开始.从头到尾遍历,一直找到第一个不为零的元素为止,把不为零的元素放到指针里,指针自增1,重复操作,遍历结束时把指针后的所有元素全部改为零

python代码:

  1. def moveZeroes(self, nums: List[int]) -> None:
  2.         """
  3.         Do not return anything, modify nums in-place instead.
  4.         """
  5.         # for i in nums:
  6.         #     if i == 0:#如果当前元素为0
  7.         #         nums.remove(0)
  8.         #         nums.append(0)#在尾部加0    
  11.         #fast,slow=0,0
  12.         #while fast<len(nums):
  13.         #    if nums[fast]!=0:
  14.         #        nums[fast],nums[slow]=nums[slow],nums[fast]
  15.         #        slow+=1
  16.         #    fast+=1
  18.         index = 0
  19.         for i in range(len(nums)):
  20.             if nums[i] != 0:
  21.                 nums[index] = nums[i]
  22.                 index += 1
  23.         for j in range of (index,len(nums)):
  24.             nums[j] = 0

java代码:

  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.         int index = 0;
  4.         for(int i = 0;i<nums.lenth;i++){
  5.             if (nums[i] != 0){
  6.                 nums[index] = nums[i];
  7.                 index++;
  8.             }
  9.         }
  10.         for(int j = index;j<nums.length;j++){
  11.             nums[j] = 0;
  12.         }
  13.     }
  14. }

27移除元素

根据题意将数组分成「前后」两段：
前半段是有效部分，存储的是不等于 val 的元素。
后半段是无效部分，存储的是等于 val 的元素。
最终答案返回有效部分的结尾下标。

总结:对于诸如「相同元素最多保留 k 位元素」或者「移除特定元素」的问题，更好的做法是从题目本身性质出发，利用题目给定的要求提炼出具体的「保留逻辑」，将「保留逻辑」应用到遍历到的每一个位置。

python

  1. class Solution:
  2.     def removeElement(self, nums: List[int], val: int) -> int:
  3.         a = 0
  4.         b = 0
  6.         while a < len(nums):
  7.             if nums[a] != val:
  8.                 nums[b] = nums[a]
  9.                 b += 1
  10.             a += 1
  12.         return b

java

  1. class Solution {
  2.     public int removeElement(int[] nums, int val) {
  3.         int j = nums.length - 1;
  4.         for (int i = 0; i <= j; i++) {
  5.             if (nums[i] == val) {
  6.                 swap(nums, i--, j--);
  7.             }
  8.         }
  9.         return j + 1;
  10.     }
  11.     void swap(int[] nums, int i, int j) {
  12.         int tmp = nums[i];
  13.         nums[i] = nums[j];
  14.         nums[j] = tmp;
  15.     }
  16. }