标签： LeetCode

leetcode 3. 无重复字符的最长子串

第一种：也是我写的，弱智写法，两个for不断循环累积子串判断有没有重复

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if (s =='') return 0
    let count = 1,max = 1
    for(let i = 0; i< s.length; i++) {
        let tmp = new Map()
        tmp.set(s[i],1)
        for (let j = i+1; j < s.length; j++) {
            if(!tmp.has(s[j])) {
                tmp.set(s[j],1)
                count ++
            }
            else {
                count = 1
                break
            }
            if(count>max) max = count
            if(j ==  s.length-1) count =1
        }
    }
    return max
};

时间复杂度为O(n^3)

第二种，通过迭代字符串然后slice截取字符串再用indexof找到重复的字符串，遇到重复的就把startnum重置，最后找到最长子串

var lengthOfLongestSubstring = function(s) {
    let startNum = 0;
    let maxNum = 0;
    s.split('').forEach((v, i) => {
        const index = s.slice(startNum, i).indexOf(v);
        if(index === -1) {
            // 无重复字符
            maxNum = Math.max(maxNum, i - startNum + 1);
        } else {
            // 重复字符
            startNum = index + startNum + 1;
        }
    });
    return maxNum;
};

leetcode 896. 单调数列

我自己的写法：很容易理解，出现递增就让z为true，出现递减就让j为true，当索引>0且z和j都为true时，就不是单调数组了

/**
 * @param {number[]} A
 * @return {boolean}
 */
var isMonotonic = function(A) {
    let z = j = false
    for(let i = 0; i<A.length; i++) {
        if(A[i] < A[i+1]) z = true 
        if(A[i] > A[i+1]) j = true 
        if (i>0 && z && j ) return false 
    }
    return true
};

题目

如果数组是单调递增或单调递减的，那么它是单调的。

如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。

当给定的数组 A 是单调数组时返回 true，否则返回 false。

leetcode 217. 存在重复元素

弱智写法：两个循环

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    if (nums.length == 1) return false
    for (let i = 0; i<nums.length; i++) {
        for (let j = 0; j<nums.length; j++) {
            if (i == j) continue
            if (nums[i] == nums[j]) {
                return true
            }
        }
    }
    return false
};
弱智写法

排序然后比较两个相邻的元素，但是用到 sort() 函数 不推荐

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort()
    for(let i = 0; i < nums.length; i++) {
        if (nums[i] == nums[i+1]) return true
    }
    return false
};

第三种方法：set方法

set对象用于储存唯一值，如果nums有重复的值，会自动去掉，然后再比较长度就行了

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    return new Set(nums).size < nums.length
};

但是感觉用到此类高级方法，算法题就变得没意思了

方法四：将值全部储存在map，然后有遇到重复的就返回true

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (map.has(nums[i])) {
            return true;
        } else {
            map.set(nums[i], 1);
        }
    }
    return false;
};

map对象学习： http://es6.ruanyifeng.com/#docs/set-map#Map

leetcode 169. 多数元素 JavaScript

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

特别注意题目的 大于 二字，这里的思路是先把数组的第一个元素存起来，然后在第一次循环的时候 count 就会+1，然后遇到不同的 -1，当count==0的时候 将下一个元素赋给tmp，绝对要是下一个元素，这样才能在下一个循环的时候 保证count为正数

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let tmp = nums[0], i =0, count = 0
    for(; i< nums.length; i++) {
        if (tmp !== nums[i]) {
            count -- 
        } else {
            count ++
        }
        if (count == 0)  tmp = nums[i+1]
        console.log(count)
    }
    
    return tmp
};

leetcode 905. 按奇偶排序数组 JavaScript

第一种办法是声明一个新数组，然后遍历原数组将偶数放入新数组的前面，奇数放到新数组的后面

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParity = function(A) {
    let s =0,j=A.length-1,b = []
    for(let i =0; i< A.length; i++) {
        if(A[i]%2 == 0) {
            b[s] = A[i]
            s++
        } else {
            b[j] = A[i]
            j--
        }
    }
    return b
};

第二种是原地算法，用两个指针从数组前后同时遍历，遇到前奇后偶的就叫唤一下

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParity = function(A) {
    let i=0;j=A.length-1
    while (i <j) {
        if(A[i]%2 >A[j]%2) {
            let tmp = A[j]
            A[j] = A[i]
            A[i] = tmp
        }
        if (A[i]%2==0) i++
        if (A[j]%2==1) j--
    }
    return A
};

题目

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。

leetcode 485.最大连续1的个数 JavaScript

这题就很简单了，直接 for 循环，判断是 1 就给 temp +1 然后到 0 之后就判断是否是最大 然后 temp 置 0

如果最后一个元素是1的话 是跳不到else里的，所以需要在最后 比较一下 temp 和 ans

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaxConsecutiveOnes = function(nums) {
    if (nums.length===1) return nums[0] === 0 ? 0 : 1 
    let ans = temp = 0 
    for(let i = 0; i < nums.length; i++) {
        if (nums[i] == 1) {
            temp++
        } else {
            if (temp > ans) {
                ans = temp
            }
            temp = 0
        }
    }
    if(temp>ans) ans=temp
    return ans
};

Max Consecutive Ones

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

Example 1:

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

Note:

  • The input array will only contain 0 and 1.
  • The length of input array is a positive integer and will not exceed 10,000

leetcode 283. 移动零 JavaScript双指针

leetcode中很多有关数组的题目都可以用双指针解决，例如之前做的一道要求在原地（in-place）移除元素就是用双指针做的 LeetCode 27. 移除元素 – 昨日当年

使用思路是：在需要进行原地操作的题中 声明两个指针， 一个指针用来作索引正常遍历，另一个指针指向需要做替换操作的元素

就比如这道 Move Zeroes 

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let i = j =0
    for(;i<nums.length; i++) {
        if(nums[i]!==0) {
            nums[j] = nums[i]
            j++
        }
    }
    for(; j<i; j++) {
        nums[j] = 0
    }
};

i 作 index 用来遍历 nums

找到非0元素时 把值赋给 nums[j]

则在 for 循环结束时 nums[0] 至 nums[j] 为非0元素

即数组中存在 j+1 个非0元素 ，然后用原本数组的长度（i+1）减去非0元素 剩下的赋为0就行了

Move Zeroes

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

  1. You must do this in-place without making a copy of the array.
  2. Minimize the total number of operations.

leetcode 268. 缺失数字

首先是我自己乱写的，弱智写法：排序然后不断+1找到没有的那个

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    if(nums.length == 1 && nums[0] == 0) return 1
    if(nums.length == 1) return 0
    nums.sort(function(a,b) { return a-b})
    if (nums[0] != 0) return 0
    for( let i =0; i < nums.length ; i++) {
        if(nums.includes(nums[i]+1) === false) {
            console.log(nums[i]+1)
            return nums[i]+1
        }
    }
};

第二种方法是我看了解析知道的，可以把0…数组长度+1求和减去原本数组的和，就是缺的这个数字了，效率快很多

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let sum = 0
    for(let i = 0; i <nums.length; i++) {
        sum += nums[i]
    }
    return nums.length * (nums.length+1)/2 -sum
};

第三种办法是个骚操作了，异或运算，我也没整明白

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    let res = nums.length
    for(let i = 0; i <nums.length; ++i) {
        res ^= nums[i]
        res ^= i
    }
    return res
};

leetcode 561. 数组拆分1

题目乍一看很复杂的样子，其实就是把数组按增序排序然后把每相邻两个元素之间最小的那个加起来就行了

js：

/**
 * @param {number[]} nums
 * @return {number}
 */
var arrayPairSum = function(nums) {
    nums.sort(function(a,b){return a-b;})
    let answer = 0
    for (let i = 0; i<nums.length;){
        answer = answer + nums[i]
        i = i+2
    }
    return answer
};

java:

class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length;) {
            sum = sum + nums[i];
            i = i+2;
        }
        return sum;
    }
}

leetcode 118. 杨辉三角

好像记得在以前刚学算法，好像是递归的时候学到过这个三角形，所以第一眼看到想用递归做，又感觉好像不对劲，看了看题解发现没人用递归做

杨辉三角规律就是从第三行开始，除了第一和最后一个值 中间的值都是上一行的行数+行数-1 也是 这个值的位数+位数-1

即 answer[i-2][s-1] + answer[i-2][s-2]

i 为当前的行数 上一行-1 索引-1 所以为-2

s为当前行要求的第n个元素 然后因为是索引 -1

说的比较乱，写的也很菜…

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    if (numRows == 0 ) return []
    if (numRows == 1 ) return [[1]]
    let answer = [[1], [1,1]]
    if (numRows == 2 ) return answer
    for (let i = 3; i <= numRows; i++) {
        let newarr = []
        for (let s = 2; s < i; s++) {
            newarr.push(answer[i-2][s-1] + answer[i-2][s-2]) 
        }
        newarr.unshift(1)
        newarr.push(1)
        answer.push(newarr)
    }
    return answer
};

没有更多文章了