刷題0901

劍指 Offer 03. 數(shù)組中重復的數(shù)字

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzktv1/

在一個長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復的置谦，但不知道有幾個數(shù)字重復了伴逸，也不知道每個數(shù)字重復了幾次凄杯。請找出數(shù)組中任意一個重復的數(shù)字。

  • 思路 1 使用庫函數(shù)申請額外空間
    使用 HashSet 來進行處理岩调，因為 HashSet 本身不允許出現(xiàn)重復元素莱坎，所以當添加元素失敗或已經(jīng)包含該數(shù)字時倔撞，則表示出現(xiàn)了重復元素帚屉，將其返回即可谜诫。
    時間復雜度：O(n)，空間復雜度：O(n)
var findRepeatNumber = function(nums) {
    var numsSet = new Set();
    for(var num of nums){
        if(numsSet.has(num)){
            return num;
        }else{
            numsSet.add(num)
        }
    }
    return false
};
  • 思路 2 數(shù)組本身做哈希表攻旦，達到了節(jié)省空間的目的
    時間復雜度：O(n)喻旷，空間復雜度：O(1)
var findRepeatNumber = function(nums) {
    for(var i = 0; i<nums.length ; i++){
        while(nums[i] != i){
            if(nums[i] == nums[nums[i]]){
                return nums[i]
            } 
            var tmp = nums[i];
            nums[i] =nums[tmp];
            nums[tmp] = tmp;
        }
    }
    return false
};

劍指 Offer 04. 二維數(shù)組中的查找

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz2hh7/

var findNumberIn2DArray = function(matrix, target) {
    let col = matrix.length;
    if(!col) return false
    let row = matrix[0].length;
    let i=col-1, j=0;
    while(i>=0 && j<row){
        if(matrix[i][j] == target){
               return true;
           }else if(matrix[i][j] > target){
              i--;
           }else{
              j++;
         }
    }
    return false;
};

劍指 Offer 05. 替換空格

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz2cf5/

var replaceSpace = function(s) {
 return s.split(' ').join('%20')
};

//數(shù)組
var replaceSpace = function(s) {
    var res ='';
    for(i = 0; i<s.length; i++){
        if(s[i] == " "){
            res += '%20';
        } else{
            res += s[i]
        }
    }
    return res
};

劍指 Offer 06. 從尾到頭打印鏈表

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xs92sh/

  • 方法一：reverse()
var reversePrint = function(head) {
    var stack = [];
    while(head != null){
        stack.push(head.val);
        head = head.next
    }
    //return stack.reverse()
};
  • 方法二：棧（先進后出，push+pop）
var reversePrint = function(head) {
    var stack = [];
    while(head != null){
        stack.push(head.val);
        head = head.next;
    }
    var res = [];
    const len = stack.length; //需要初始stack的長度
    for(var i = 0; i< len; i++){
        res.push(stack.pop()); //stack長度會不斷變化
    }
    return res;
};

劍指 Offer 09. 用兩個棧實現(xiàn)隊列

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz8cid/

var CQueue = function() {
    this.stack1=[];
    this.stack2 = [];
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.stack1.push(value)
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    if(this.stack2.length==0){
        while(this.stack1.length != 0){
            this.stack2.push(this.stack1.pop())
        }
    }
    if(this.stack2.length==0){
        return -1
    }else {
        return this.stack2.pop()
    }
};

劍指 Offer 10- I. 斐波那契數(shù)列

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xslxpr/
寫一個函數(shù)牢屋，輸入 n 且预，求斐波那契（Fibonacci）數(shù)列的第 n 項。斐波那契數(shù)列的定義如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數(shù)列由 0 和 1 開始烙无，之后的斐波那契數(shù)就是由之前的兩數(shù)相加而得出锋谐。
答案需要取模 1e9+7（1000000007），如計算初始結(jié)果為：1000000008截酷，請返回 1涮拗。

var fib = function(n) {
    let f0 = 0, f1 = 1, fn;
    if(n<2){
        return n
    }
    for(let i = 2; i<=n ;i++){
        fn = (f0 + f1) % 1000000007;
        f0 = f1;
        f1 = fn;
    }
    return fn
};

劍指 Offer 17. 打印從 1 到最大的 n 位數(shù)

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzvgc2/

var printNumbers = function(n) {
    if(n==0){
        return false;
    }
    let all = Math.pow(10,n);
    // let all=1
    // for(var i=0;i<n;i++){
    //    all = 10*all   
    // }
    let arr = [];
    for(var i=1;i<all;i++){
        arr.push(i)
    }
return arr;
};

劍指 Offer 18. 刪除鏈表的節(jié)點

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz4mp2/
時間復雜度：O(n)，空間復雜度：O(1)

var deleteNode = function(head, val) {
    if(head == null){
        return null;
    }
    if(head.val == val){
        return head.next;
    }
    var left = head;
    var cur = left.next
    while(cur.val != val && cur.next!= null){
        left=cur;
        cur=cur.next;
    }
    if(cur != null){
        left.next=cur.next
    }
    return head
};

劍指 Offer 21. 調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

var exchange = function(nums) {
  var a = [];
    var b = [];
    for(var i=0;i<nums.length;i++){
        if (nums[i]%2==1){
            a.push(nums[i])
        }else{
            b.push(nums[i])
        }
    }
    return a.concat(b)
};

雙指針

var exchange = function(nums) {
    let right = nums.length-1;
    let left = 0;
    let tmp;
    while(left<right){
       if(left<right &&(nums[right]%2)  == 0 ){
            right--;
        }
       if(left<right &&(nums[left]%2) == 1){
            left++;
        }
    tmp = nums[left]
    nums[left] = nums[right]
    nums[right] = tmp 
    }
  return nums  
};

劍指 Offer 22. 鏈表中倒數(shù)第 k 個節(jié)點

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzy5ei/
時間復雜度：O(n)迂苛，空間復雜度：O(1)

var getKthFromEnd = function(head, k) {
    var cur = head;
    var post= head;
    for(var i=0; i<k; i++){
        cur = cur.next;
    }
    while(cur!=null){
        cur = cur.next;
        post = post.next
    }
    return post
};

劍指 Offer 24. 反轉(zhuǎn)鏈表

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzccxg/
時間復雜度：O(n)三热，空間復雜度：O(1)

var reverseList = function(head) {
    var cur = null;
    var pre = head;
    while(pre!=null){
       var tmp = pre.next;
        pre.next = cur;
        cur = pre;
        pre = tmp;
    }
    return cur
};

劍指 Offer 25. 合并兩個排序的鏈表

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzjkjj/
輸入兩個遞增排序的鏈表，合并這兩個鏈表并使新鏈表中的節(jié)點仍然是遞增排序的灾部。O(m+n)

var mergeTwoLists = function(l1, l2) {
    if(l2==null){
        return l1
  }
    if(l1==null){
        return l2
  }
    if(l1.val>l2.val){
        l2.next = mergeTwoLists(l1,l2.next);
        return l2
    }else{
        l1.next = mergeTwoLists(l2,l1.next);
        return l1
    }
};

劍指 Offer 27. 二叉樹的鏡像

例如輸入：
      4
  2      7
1   3  6   9

鏡像輸出：
     4
  7     2
9   6  3   1

輸入：root = [4,2,7,1,3,6,9]
輸出：[4,7,2,9,6,3,1]

var mirrorTree = function(root) {
    let res = null;
    if(root != null){
        res =new TreeNode(root.val);
        res.left = mirrorTree(root.right);
        res.right = mirrorTree(root.left);
    }
    return res 
};

劍指 Offer 28. 對稱的二叉樹

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsrxq1/

  • 時間復雜度：O(n)
var isSymmetric = function(root) {
    if(root==null){
        return true;
    }
    return dfs(root.left,root.right)
};
var dfs = function(t1, t2){
    if(t1==null && t2==null) {return true}
    if(t1==null|| t2==null) {return false}
    if(t1.val != t2.val){return false}
    return dfs(t1.left,t2.right) && dfs(t1.right,t2.left)
}

劍指 Offer 30. 包含 min 函數(shù)的棧

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzqg03/

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack1 = [];
    this.stack2 = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack1.push(x);
    if(this.stack2.length == 0 || this.stack2[this.stack2.length - 1] >= x) {
        this.stack2.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    if(this.stack1.pop() == this.stack2[this.stack2.length - 1]) {
        this.stack2.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack1[this.stack1.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
    return this.stack2[this.stack2.length - 1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

劍指 Offer 32 - I. 從上到下打印二叉樹

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsnu0i/
例如:
給定二叉樹: [3,9,20,null,null,15,7],
返回：[3,9,20,15,7]

var levelOrder = function(root) {
    if(root == null){
        return [];
    }
    let queue = [root];
    let res = [];
    while(queue.length != 0){
        let node = queue.shift();
        res.push(node.val);
        if(node.left){
            queue.push(node.left);
        }
        if(node.right){
            queue.push(node.right);
        }
    }
    return res
};

劍指 Offer 32 - II. 從上到下打印二叉樹 II

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xswwvg/
從上到下按層打印二叉樹惯退，同一層的節(jié)點按從左到右的順序打印赌髓，每一層打印到一行。
給定二叉樹: [3,9,20,null,null,15,7],
返回其層次遍歷結(jié)果：[[3],[9,20], [15,7]]

var levelOrder = function(root) {
  if(root == null){
        return [];
    }
    let queue = [root];
    let res = [];
    while(queue.length != 0){
        let level = [];
        let len = queue.length;
        for(let i = 0; i < len; i++){
            let node = queue.shift();
            level.push(node.val);
            if(node.left){
                queue.push(node.left);
            }
            if(node.right){
                queue.push(node.right);
            }
        }
        res.push(level)
    }
    return res
};

劍指 Offer 32 - III. 從上到下打印二叉樹 III

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xs0paj/
請實現(xiàn)一個函數(shù)按照之字形順序打印二叉樹催跪，即第一行按照從左到右的順序打印锁蠕，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印懊蒸，其他行以此類推荣倾。

例如:
給定二叉樹: [3,9,20,null,null,15,7],
返回其層次遍歷結(jié)果：[[3],[20,9], [15,7]]

var levelOrder = function(root) {
     if(root == null){
        return [];
    }
    let queue = [root];
    let res = [];
    let flag = 1;
    while(queue.length != 0){
        let level = [];
        let len = queue.length;
        for(let i = 0; i < len; i++){
             let node = queue.shift();
            if(flag==1){  
                level.push(node.val);
            }else{
                level.unshift(node.val);
            };
            if(node.left){
                queue.push(node.left);
                }
            if(node.right){
                queue.push(node.right);
                }
        }
        flag = -flag; 
        res.push(level)
    }
    return res
};

BFS 翻轉(zhuǎn)二叉樹（附）

var mirrorTree = function(root) {
    if(root == null){
        return []
    }
    let res = [];
    let queue = [root];
    while(queue.length != 0 ){
        let node = queue.shift();
        res.push(node.val);
        if(node.right){
            queue.push(node.right)
        }
        if(node.left){
            queue.push(node.left)
        }
    }
    return res
};

劍指 Offer 39. 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz7dgg/

方法一：數(shù)組排序：首先將 nums 排序，由于該數(shù)字超過數(shù)組長度的一半骑丸，所以數(shù)組的中間元素就是答案舌仍，時間復雜度為 O(nlogn)

var majorityElement = function(nums) {
    nums.sort((a,b) => a-b)
    return nums[parseInt(nums.length / 2 )]  
}

方法一：哈希計數(shù)：遍歷 nums 數(shù)組，將數(shù)字存在 HashMap 中通危，統(tǒng)計數(shù)字出現(xiàn)次數(shù)铸豁，統(tǒng)計完成后再遍歷一次 HashMap，找到超過一半計數(shù)的數(shù)字菊碟，時間復雜度為 O(n)

摩爾投票：遍歷 nums 數(shù)組节芥，使用 count 進行計數(shù)，記錄當前出現(xiàn)的數(shù)字為 cur，如果遍歷到的 num 與 cur 相等头镊，則 count 自增蚣驼，否則自減，當其減為 0 時則將 cur 修改為當前遍歷的 num相艇，通過增減抵消的方式颖杏，最終達到剩下的數(shù)字是結(jié)果的效果，時間復雜度為 O(n)

  • 摩爾投票是最優(yōu)解法厂捞，時間復雜度：O(n)输玷，空間復雜度：O(1)
var majorityElement = function(nums) {
    let cur ,count=0;
    for(let i = 0; i<nums.length; i++){
        if(count == 0){
            cur = nums[i];  
        }
        if(nums[i]  == cur){
            count++;
        }else{
            count--
        }
    }
    return cur
}

劍指 Offer 40. 最小的k個數(shù)

  • 題目：輸入整數(shù)數(shù)組 arr ，找出其中最小的 k 個數(shù)靡馁。例如欲鹏，輸入4、5臭墨、1赔嚎、6、2胧弛、7尤误、3、8這8個數(shù)字结缚，則最小的4個數(shù)字是1损晤、2、3红竭、4尤勋。

解法 1: 直接排序

思路和算法:對原數(shù)組從小到大排序后取出前 k個數(shù)即可。

var getLeastNumbers = function(arr, k) {
    arr.sort((a,b)=>a-b)
    var min=[]
    for(var i=0;i<k;i++){
        min.push(arr[i]);
    }
    return min
};

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/chao-quan-3chong-jie-fa-zhi-jie-pai-xu-zui-da-dui-/

解法 2: 最大堆

解法 3: 基于快速排序的 partition

劍指 Offer 42. 連續(xù)子數(shù)組的最大和

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsiyed/
輸入一個整型數(shù)組茵宪，數(shù)組里有正數(shù)也有負數(shù)最冰。數(shù)組中的一個或連續(xù)多個整數(shù)組成一個子數(shù)組。求所有子數(shù)組的和的最大值稀火。要求時間復雜度為O(n)暖哨。

var maxSubArray = function(nums) {
    let res = nums[0]
    for(let i = 1; i<nums.length ;i++){
        if(nums[i-1]>0){
            nums[i] += nums[i-1]
        }else{
            nums[i] = nums[i] 
        }
        res = Math.max(res,nums[i])
    }
    return res
};

劍指 Offer 47. 禮物的最大價值

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xstkx3/
在一個 m*n 的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0）凰狞。你可以從棋盤的左上角開始拿格子里的禮物篇裁，并每次向右或者向下移動一格、直到到達棋盤的右下角赡若。給定一個棋盤及其上面的禮物的價值达布，請計算你最多能拿到多少價值的禮物？

var maxValue = function(grid) {
    let col = grid.length;
    let row = grid[0].length;
     for(let i = 0; i<col ;i++){
        for(let j = 0; j<row ; j++){
            if(i >= 1 && j >= 1){
                grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
            }else if(i >= 1){
                grid[i][j] += grid[i-1][j];
            }else if(j >= 1){
                grid[i][j] += grid[i][j-1];
            }
        }
    }
    return grid[col-1][row-1];
};

var maxValue = function(grid) {
    let col = grid.length;
    let row = grid[0].length;
       for(let i = 0; i<col ;i++){
        for(let j = 0; j<row ; j++){
             if(i == 0 && j==0){
                continue;
            }else if(i == 0){
                grid[i][j] += grid[i][j-1];
            }else if(j==0){
                grid[i][j] += grid[i-1][j];
            }else {
                grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
            }
        }
    }
    return grid[col-1][row-1];
};

劍指 Offer 50. 第一個只出現(xiàn)一次的字符

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzzd25/

在字符串 s 中找出第一個只出現(xiàn)一次的字符斩熊。如果沒有往枣，返回一個單空格。 s 只包含小寫字母。
示例: s = "abaccdeff" 分冈，返回 "b"圾另；
示例: s = "" ， 返回 " "

  • 思路: 首先遍歷字符串將每個字符串映射到固定的位置雕沉，并且該位置存儲字符串的出現(xiàn)次數(shù)集乔，然后再遍歷一次字符串，找到第一個只出現(xiàn)一次的字符
    時間復雜度：O(n)坡椒，空間復雜度：O(1)
var firstUniqChar = function(s) {
    var maps = new Map();
    for(var num of s){
        maps.set(num, maps.has(num))
    }
     for(var num of s){
         if(maps.get(num)==0){
             return num;
         }
     }
    return " "
};

劍指 Offer 52. 兩個鏈表的第一個公共節(jié)點

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xshucr/
使用兩個指針 node1扰路，node2 分別指向兩個鏈表 headA，headB 的頭結(jié)點倔叼，然后同時分別逐結(jié)點遍歷汗唱，
當 node1 到達鏈表 headA 的末尾時，重新定位到鏈表 headB 的頭結(jié)點丈攒；
當 node2 到達鏈表 headB 的末尾時哩罪，重新定位到鏈表 headA 的頭結(jié)點。
這樣巡验，當它們相遇時际插，所指向的結(jié)點就是第一個公共結(jié)點。

  • 時間復雜度：O(M+N)显设。
  • 空間復雜度：O(1)O(1)框弛。
//（雙指針法）
var getIntersectionNode = function(headA, headB) {
    let curA = headA;
    let curB = headB;
    while (curA != curB) {
        curA = curA != null ? curA.next : headB;
        curB = curB != null ? curB.next : headA;
    }
    return curA;
};

劍指 Offer 53 - II. 0～n-1中缺失的數(shù)字

解法 1: 遍歷

var missingNumber = function(nums) {  
    if(nums[i]==0){
        return 1
    }
    for(var i=0;i<nums.length;i++){
        if(nums[i]!=i){
            return i
        }
    }
    return nums.length
};

解法 2: 二分查找（有序數(shù)組都應該想到二分查找）

var missingNumber = function(nums) {
    let i = 0;
    let j = nums.length-1;
    while(i <= j){
        let mid =parseInt((i + j) / 2)
        if(nums[mid] == mid){
            i = mid + 1;
        }else{
            j = mid - 1
        }   
    }
    return i
};

劍指 Offer 54. 二叉搜索樹的第 k 大節(jié)點

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xspy85/

  • 時間復雜度：O(n)，空間復雜度：O(1)
  • 二叉搜索樹：根節(jié)點的值大于其左子樹中任意一個節(jié)點的值，小于其右節(jié)點中任意一節(jié)點的值，這一規(guī)則適用于二叉查找樹中的每一個節(jié)點。
  • 二叉搜索樹的【中序遍歷】為 【遞增序列】，易得二叉搜索樹的 【中序遍歷倒序】 為 【遞減序列】 劣欢。
    因此，求 “二叉搜索樹第 k大的節(jié)點” 可轉(zhuǎn)化為求 “此樹的【中序遍歷倒序】的第 k 個節(jié)點”砸捏。 中序遍歷 為 “左竟闪、根、右” 順序溅呢，倒序就是“右澡屡、根、左” 咐旧。
    時間復雜度：O(n)驶鹉，空間復雜度：O(1)
var nums;
var res;
var kthLargest = function(root, k) {
    nums = k
    dfs(root);
    return res;
};
var dfs = function(root){
    if(root == null){
        return;
    }
    dfs(root.right);
    if(nums == 0){
        return
    }
    nums --;
    if(nums==0){
        res = root.val
    }
    dfs(root.left)
}

劍指 Offer 55 - I. 二叉樹的深度

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsaki2/

  • 時間復雜度：O(n)，空間復雜度：O(1)
var maxDepth = function(root) {
    if(root == null){
        return 0
    }
    return Math.max(maxDepth(root.left),maxDepth(root.right))+1
};

劍指 Offer 57. 和為 s 的兩個數(shù)字

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzimqj/
輸入一個遞增排序的數(shù)組和一個數(shù)字s铣墨，在數(shù)組中查找兩個數(shù)室埋，使得它們的和正好是s。如果有多對數(shù)字的和等于s，則輸出任意一對即可姚淆。
思路：有序數(shù)組孕蝉，雙指針

var twoSum = function(nums, target) {
    var len = nums.length;
    var left = 0;
    var right = len-1;
    var arr = []
    for(var i = 0; i<len ;i++){
        if(nums[left]+nums[right] == target){
            //  arr.push(nums[left]);
            // arr.push(nums[right]) 
            return  [nums[left],nums[right]]
        };
        if(nums[left]+nums[right] > target){
            right--
        }
        if(nums[left]+nums[right] < target){
            left++
        }
    }
};

劍指 Offer 57 - II. 和為s的連續(xù)正數(shù)序列

  • 題目描述：輸入一個正整數(shù) target ，輸出所有和為 target 的連續(xù)正整數(shù)序列（至少含有兩個數(shù)）腌逢。
    序列內(nèi)的數(shù)字由小到大排列降淮，不同序列按照首個數(shù)字從小到大排列。
    示例：輸入：target = 9;輸出：[[2,3,4],[4,5]]

  • 題解

方法：滑動窗口

var findContinuousSequence = function(target) {
    var i=1;
    var j=1;
    var sum = 0;
    var res =[];
    while(i<=parseInt(target/2)){
        if (sum<target){
           sum+=j;
           j++;
        }else if(sum>target){
            sum -=i;
            i++;
        }else{
            let arr =[];
            for(let k=i;k<j;k++){
                arr.push(k);
            }
            res.push(arr)
            sum -=i;
            i++;
        }
    }
    return res;
};

劍指 Offer 61. 撲克牌中的順子

  • 題目：從撲克牌中隨機抽5張牌搏讶，判斷是不是一個順子佳鳖，即這5張牌是不是連續(xù)的。2～10為數(shù)字本身媒惕，A為1系吩，J為11，Q為12妒蔚，K為13淑玫，而大、小王為 0 面睛，可以看成任意數(shù)字絮蒿。A 不能視為 14。
  • 方法：排序 + 遍歷
  • 思路：最大值-最小值<5叁鉴，且沒有重復的數(shù)字土涝。
var isStraight = function(nums) {
    nums.sort((a,b) => a-b);
    var len = nums.length;
    var joker = 0;//判斷0的個數(shù)
    for(var i = 0; i<len ;i++){
        if(nums[i] === 0){
            joker++
        }else if(nums[i] == nums[i+1]){
            return false
        }
    }
    return (nums[len-1]-nums[joker] < 5) ? true :false // 最大值-最小值 <5
 };

劍指 Offer 62. 圓圈中最后剩下的數(shù)字

1哩盲、遞歸
遞推公式：f(N,M) = ( f(N?1,M) + M ) % N

var lastRemaining = function(n, m) {
    if(n==1){
        return 0;
    }
    var res = lastRemaining(n-1,m)
    return (res+m)%n
};

2前方、迭代實現(xiàn)
時間復雜度：O(n)狈醉，需要求解的函數(shù)值有 n 個。
空間復雜度：O(1)惠险，只使用常數(shù)個變量舔糖。

var lastRemaining = function(n, m) {
    if (n === 1) {
        return 0;
    }
    var res = 0
    for(var i=2;i<=n;i++){
        res = (res+m)%i;
    }
    return res 
};
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個濱河市莺匠，隨后出現(xiàn)的幾起案子金吗，更是在濱河造成了極大的恐慌，老刑警劉巖趣竣，帶你破解...
    沈念sama閱讀 222,946評論 6贊 518
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件摇庙，死亡現(xiàn)場離奇詭異，居然都是意外死亡遥缕，警方通過查閱死者的電腦和手機卫袒，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3贊 399
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來单匣，“玉大人夕凝，你說我怎么就攤上這事』С樱” “怎么了码秉？”我有些...
    開封第一講書人閱讀 169,716評論 0贊 364
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長鸡号。 經(jīng)常有香客問我转砖，道長，這世上最難降的妖魔是什么鲸伴？ 我笑而不...
    開封第一講書人閱讀 60,222評論 1贊 300
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任府蔗，我火速辦了婚禮，結(jié)果婚禮上汞窗，老公的妹妹穿的比我還像新娘姓赤。我一直安慰自己，他們只是感情好仲吏，可當我...
    茶點故事閱讀 69,223評論 6贊 398
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布不铆。 她就那樣靜靜地躺著，像睡著了一般蜘矢。 火紅的嫁衣襯著肌膚如雪狂男。 梳的紋絲不亂的頭發(fā)上综看，一...
    開封第一講書人閱讀 52,807評論 1贊 314
  • 城市分裂傳說
    那天品腹，我揣著相機與錄音，去河邊找鬼红碑。 笑死舞吭，一個胖子當著我的面吹牛泡垃，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播羡鸥，決...
    沈念sama閱讀 41,235評論 3贊 424
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼蔑穴，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了惧浴？” 一聲冷哼從身側(cè)響起存和，我...
    開封第一講書人閱讀 40,189評論 0贊 277
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎衷旅，沒想到半個月后捐腿，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 46,712評論 1贊 320
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡柿顶，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,775評論 3贊 343
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年茄袖，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片嘁锯。...
    茶點故事閱讀 40,926評論 1贊 353
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡宪祥，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出家乘，到底是詐尸還是另有隱情蝗羊，我是刑警寧澤，帶...
    沈念sama閱讀 36,580評論 5贊 351
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布仁锯，位于F島的核電站肘交，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏扑馁。R本人自食惡果不足惜涯呻，卻給世界環(huán)境...
    茶點故事閱讀 42,259評論 3贊 336
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望腻要。 院中可真熱鬧复罐，春花似錦、人聲如沸雄家。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0贊 25
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽趟济。三九已至乱投，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間顷编，已是汗流浹背戚炫。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1贊 274
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留媳纬，地道東北人双肤。 一個月前我還...
    沈念sama閱讀 49,368評論 3贊 379
  • 代替公主和親
    正文 我出身青樓施掏，卻偏偏與公主長得像，于是被迫代替她去往敵國和親茅糜。 傳聞我的和親對象是個殘疾皇子七芭，可洞房花燭夜當晚...
    茶點故事閱讀 45,930評論 2贊 361