每日两题 T35

合一大师

发布于 2020-07-20 09:52:19

7510

发布于 2020-07-20 09:52:19

文章被收录于专栏：JavaScript全栈JavaScript全栈

算法

LeetCode T33. 搜索旋转排序数组[1]

描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例1 :

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

分析

使用二分法即可完成，当然JavaScript中的数组方法 index 已实现该功能，见代码二。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
  let l = 0
  let r = nums.length - 1
  while(l <= r){
    let mid = l + ((r - l) >> 1)         // 取中间索引
    if(nums[mid] === target) return mid  // 找到了 直接返回

    if(nums[l] <= nums[mid]){            // 如果第一个元素 小于等于 中间元素 表示 左边的是增序的 如[4,5,6,7,0,1,2]

      // 如果target 小于 中间元素, 大于第一个元素 ,说明target处于 [l, mid]间
      if(nums[mid] > target && nums[l] <= target){  
        r = mid - 1
      } else {  // 否则处于 [mid + 1, r]中
        l = mid + 1
      }

    } else {                            // 否则 右边是增序的 如[6,7,0,1,2,4,5]

      // 如果target 大于中间元素 小于最后元素, 说明处于[mid + 1, r]中
      if(nums[mid] < target && nums[r] >= target){   
        l = mid + 1
      } else {  // 否则处于[l, mid - 1]中
        r = mid - 1
      }

    }
  }
  // 没找到
  return -1
};

代码二

var search = function (nums, target) {
  return nums.indexOf(target);
};

前端

为什么要用redux-saga？看过dva源码吗？

redux

redux是 JavaScript 状态容器，提供可预测化的状态管理。

应用中所有的 state 都以一个对象树的形式储存在一个单一的 store 中。惟一改变 state 的办法是触发 action，一个描述发生什么的对象。为了描述 action 如何改变 state 树，你需要编写 reducers。

你应该把要做的修改变成一个普通对象，这个对象被叫做 action，而不是直接修改 state。然后编写专门的函数来决定每个 action 如何改变应用的 state，这个函数被叫做 reducer。

redux 有且仅有一个 store 和一个根级的 reduce 函数（reducer）。随着应用不断变大，你应该把根级的 reducer 拆成多个小的 reducers，分别独立地操作 state 树的不同部分，而不是添加新的 stores。这就像一个 React 应用只有一个根级的组件，这个根组件又由很多小组件构成。

redux-saga

redux-saga 是一个用于管理应用程序 Side Effect（副作用，例如异步获取数据，访问浏览器缓存等）的 library，它的目标是让副作用管理更容易，执行更高效，测试更简单，在处理故障时更容易。

可以想像为，一个 saga 就像是应用程序中一个单独的线程，它独自负责处理副作用。redux-saga 是一个 redux 中间件，意味着这个线程可以通过正常的 redux action 从主应用程序启动，暂停和取消，它能访问完整的 redux state，也可以 dispatch redux action。

redux-saga 使用了 ES6 的 Generator 功能，让异步的流程更易于读取，写入和测试。（如果你还不熟悉的话，这里有一些介绍性的链接）通过这样的方式，这些异步的流程看起来就像是标准同步的 Javascript 代码。（有点像 async/await，但 Generator 还有一些更棒而且我们也需要的功能）。

你可能已经用了 redux-thunk 来处理数据的读取。不同于 redux thunk，你不会再遇到回调地狱了，你可以很容易地测试异步流程并保持你的 action 是干净的。