题目详情

Given a binary array, find the maximum number of consecutive 1s in this array.

就是求数组中连续1的个数最大是多少

Example:

Input: [1,1,0,1,1,1]

Output: 3

思路

  • 用一个对象记录最大值和当前连续的值

具体代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var findMaxConsecutiveOnes = function(nums) {
  6.     let num = { max:0, other:0 };
  7.     let len = nums.length;
  8.     for(var i = 0; i < len; i++) {
  9.         if(nums[i] === 1) {
  10.             num.other ++
  11.         } else if (nums[i] === 0) {
  12.             num.other = 0
  13.         }
  14.         num.max = Math.max(num.max, num.other)
  15.     }
  16.     return num.max
  17. };

leetcode 695. Max Area of Island

题目详情

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

给一个二维数组只有数组中0和1元素，求1的最大面积

Example:

Input: [
[1,1,0,0,0],
[1,1,0,0,0],
[0,0,0,1,1],
[0,0,0,1,1]
]

Output: 4

思路

  • DFS（深度优先搜索）
  • 遍历2d array，遇到1的时候，就利用dfs把这个岛的区域大小找全。
  • 在递归dfs之前，要把当前元素设为0，是为了避免dfs又往回走

具体代码

/**
 * @param {number[][]} grid
 * @return {number}
 */

var maxAreaOfIsland = function(grid) {
    var h = grid.length;
    var w = grid[0].length;
    var max = 0;

    function dfs(i, j) {
        if(i >= 0 && i < h && j >= 0 && j < w) {
            if(grid[i][j] === 1) {
                grid[i][j] = 0
                return
                1 + 
                dfs( i + 1, j) + 
                dfs( i, j + 1) + 
                dfs( i - 1, j) + 
                dfs( i, j - 1)
            }
        }
        return 0
    }

    for(var i = 0; i < h; i++) {
        for(var j = 0; j < w; j++) {
            if(grid[i][j] === 1) {
                max = Math.max(max, dfs(i, j))
            }
        }
    }
    return max
};

leetCode 448. Find All Numbers Disappeared in an Array

题目详情

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

用标志位的方法去做，把原数组中出现的数其应该所在的位置上置为负值，然后重新遍历如果大于0，则表示从未出现过

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

思路

  • 首先第一次遍历，把出现了的元素对应的索引位置设为负值
  • 第一遍历完之后数组是这样的[-4,-3,-2,-7,8,2,-3,-1]
  • 只有第5个和第6个是正数，第二次遍历把大于0的下标+1添加进返回出去的数组

具体代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDisappearedNumbers = function(nums) {
    let ret = []
    let len = nums.length
    for(let i = 0; i < len; i++) {
        let val = Math.abs(nums[i]) - 1
        if(nums[val] > 0) {
            nums[val] = -nums[val]
        }
    }
    for(let i = 0; i < len; i++) {
        if(nums[i] > 0) {
            ret.push(i + 1)
        }
    }
    return ret
};

2018.4.18 - End