• 第一种:也是我写的,弱智写法,两个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;
    };
    


  • 我自己的写法:很容易理解,出现递增就让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。


  • 弱智写法:两个循环

    /**
     * @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


  • 给定一个大小为 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ 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
    };

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

    /**
     * @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 的所有偶数元素之后跟着所有奇数元素。


  • 这题就很简单了,直接 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中很多有关数组的题目都可以用双指针解决,例如之前做的一道要求在原地(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.

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

    杨辉三角规律就是从第三行开始,除了第一和最后一个值 中间的值都是上一行的行数+行数-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
    };

  • 首先搞懂题目意思,要求原地(in-place)移除数组元素并return长度

    /**
     * @param {number[]} nums
     * @param {number} val
     * @return {number}
     */
    var removeElement = function(nums, val) {
        let s = 0
        for(let i =0; i < nums.length; i++) {
            if(val !== nums[i] ) {
                nums[s] = nums[i]
                s++
            }
        }
    
        return s
    };

    偷偷看了题解…很巧妙的办法