周常
五道算法題 java 實(shí)現(xiàn)
1.二維數(shù)組搜索
2.二分查找最小值
3.從尾到頭打印鏈表
4.用棧表示隊(duì)列
5.重建二叉樹koa-bodyparser 源碼解析
async / await 原理解析
算法題
二維數(shù)組中查找
輸入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
輸出: true
---
輸入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
輸出: false
解題思路
- 此二維數(shù)組是按順序排列
- 每一行數(shù)組的最后一位都是此行數(shù)組的最大值
- target 如果比當(dāng)前數(shù)組最后一位大篙骡，那 target 肯定在下面的幾行數(shù)組內(nèi)
- target 如果比當(dāng)前數(shù)組最后一位小稽坤，那 target 可能在當(dāng)前數(shù)組內(nèi)
-
用 target 與二維數(shù)組內(nèi)的每個(gè)數(shù)組最后一位比較，在最后一位比 target 大的那一行數(shù)組內(nèi)進(jìn)行 target 查找
代碼實(shí)現(xiàn)
public class SearchMatrix {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0)
return false;
int i = 0; // 第一行
int j = matrix[0].length - 1; // 最后一個(gè)點(diǎn)
while (i < matrix.length && j >= 0) {
if (matrix[i][j] == target) // 第一排最后一個(gè)
return true;
else if (matrix[i][j] < target) // 如果小糯俗，就移動(dòng)到下一排最后一個(gè)
i++;
else // matrix[i][j] > target // 如果大尿褪，i 就是當(dāng)前排，在當(dāng)前排搜索
j--;
}
return false;
}
}
尋找旋轉(zhuǎn)排序數(shù)組中的最小值
假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)得湘。
( 例如杖玲，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。
請(qǐng)找出其中最小的元素淘正。
你可以假設(shè)數(shù)組中不存在重復(fù)元素摆马。
解題思路
- 查找某個(gè)值比較合適的解法是二分搜索
- 此題數(shù)組已經(jīng)是排序數(shù)組，變化后有以下幾個(gè)結(jié)果,
[1,2,3,4,5] // 順序不變鸿吆，直接取數(shù)組 arr[0]
// 中值 arr[mid] 是數(shù)組最大值或最小值
[3,4,5,1,2] // arr[mid] 是 5 arr[mid] > arr[mid+1] 最小值是 arr[mid+1]
[4,5,1,2,3] // arr[mid] 是 1 arr[mid-1] > arr[mid] 最小值是 arr[mid]
// 中值 arr[mid] 是數(shù)組最大值或最小值以外的值
[2,3,4,5,1] // arr[mid] 是 4 最小值在數(shù)組右側(cè)囤采，left = mid + 1 繼續(xù)查找
[5,1,2,3,4] // arr[mid] 是 2 最小值在數(shù)組左側(cè)，right = mid - 1 繼續(xù)查找
代碼實(shí)現(xiàn)
public class BinarySearch {
/**
* 找到最小數(shù)
* nums [3,4,5,1,2], 一定是按順序排列的數(shù)組惩淳，只是進(jìn)行了旋轉(zhuǎn)
* 旋轉(zhuǎn)后=[3,4,5,1,2]蕉毯， 原數(shù)組=[1,2,3,4,5]
*/
public int findMin(int[] nums) {
// 一個(gè)數(shù)
if (nums.length == 1)
return nums[0];
int left = 0, right = nums.length - 1;
// [1,2,3,4,5] 為沒旋轉(zhuǎn)的原數(shù)組
if (nums[right] > nums[0])
return nums[0];
// 進(jìn)行二分搜索
while (right >= left) {
// 找到中點(diǎn)防止溢出
int mid = left + ((right - left) >> 1);
// [3,4,5,1,2] midVal = 5
if (nums[mid] > nums[mid + 1])
return nums[mid + 1];
// [4,5,1,2,3] midVal = 1
if (nums[mid - 1] > nums[mid])
return nums[mid];
// [2,3,4,5,1]
if (nums[mid] > nums[0])
left = mid + 1;
// [5,1,2,3,4]
else // nums[mid] < nums[0]
right = mid - 1;
}
return -1;
}
}
使用棧實(shí)現(xiàn)隊(duì)列
解題思路
- 隊(duì)列有 push 添加元素， pop 刪除并返回隊(duì)列頭元素，peek 查看隊(duì)列頭的元素, empty 是否為空
-
實(shí)現(xiàn) Queue 的 push 可以直接使用 Stack 的 push代虾，而隊(duì)列的頭部元素可以用 Front 變量來保存进肯。
- 實(shí)現(xiàn) Queue 的 pop 需要?jiǎng)h除掉 隊(duì)列的頭元素并返回，而 Stack 的 pop 只能返回最后進(jìn)入的元素棉磨，這時(shí)候需要 Stack2 協(xié)助完成
-
Stack1 的元素 pop() 出來 push() 到 Stack2 中江掩，這時(shí) Stack2.pop() 出的就是 隊(duì)列的頭部元素
- 實(shí)現(xiàn)隊(duì)列 peek 方法要考慮兩種情況
-
Stack2 是空的，此時(shí) Queue 隊(duì)列還沒進(jìn)行 pop() 操作或者 Stack2 已經(jīng)排空含蓉，只有 Stack1 有元素, 此時(shí) front 變量就是 peek() 出的元素
-
Stack2 有元素频敛，此時(shí) Queue 隊(duì)列已經(jīng)進(jìn)行 pop() 操作，Stack2 的棧頂就是隊(duì)列頭馅扣，只需要進(jìn)行 Stack2.peek() 就行了斟赚。
-
Stack2 是空的，此時(shí) Queue 隊(duì)列還沒進(jìn)行 pop() 操作或者 Stack2 已經(jīng)排空含蓉，只有 Stack1 有元素, 此時(shí) front 變量就是 peek() 出的元素
代碼實(shí)現(xiàn)
public class ImplementQueueUsingStacks {
private int front;
private Stack<Integer> s1 = new Stack<>();
private Stack<Integer> s2 = new Stack<>();
/** Initialize your data structure here. */
public MyQueue() {}
/** Push element x to the back of queue. */
public void push(int x) {
if (s1.isEmpty())
front = x;
s1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
while (s2.isEmpty()) {
if (!s1.isEmpty())
s2.push(s1.pop());
}
return s2.pop();
}
/** Get the front element. */
public int peek() {
if (!s2.isEmpty())
return s2.peek();
return front;
}
/** Returns whether the queue is empty. */
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
從尾到頭打印鏈表的值
// 鏈表節(jié)點(diǎn)結(jié)構(gòu)
private class ListNode {
int val;
ListNode next;
}
實(shí)現(xiàn)思路
- 使用 Stack 保存所有鏈表的值
-
再使用 List 保存 Stack.pop() 出來的值
代碼實(shí)現(xiàn)
public class PrintListFromTailToHead {
public List<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> arrayList = new ArrayList<>();
while (!stack.isEmpty()) {
arrayList.add(stack.pop());
}
return arrayList;
}
}
根據(jù)中序排列、前序排列重建二叉樹
實(shí)現(xiàn)思路
- 前序遍歷順序?yàn)?[ 根 左 右 ]
// 前序遍歷的序號(hào)順序
0
/ \
1 9
/ \ / \
2 6 10 13
/ \ / \ / \ / \
3 5 7 8 11 12 14 15
/
4
- 中序遍歷順序?yàn)?[ 左 根 右 ]
// 中序遍歷的序號(hào)順序
8
/ \
4 12
/ \ / \
2 6 10 14
/ \ / \ / \ / \
1 3 5 7 9 11 13 15
/
0
- 使用一個(gè)函數(shù)遞歸重建二叉樹
- 函數(shù)中先確定重建的當(dāng)前節(jié)點(diǎn)樹的根節(jié)點(diǎn)差油，前序遍歷的第一位 preStart 就是當(dāng)前樹結(jié)構(gòu)的根節(jié)點(diǎn) root = preorder[preStart]
- 確定 root.left 的位置拗军，root.left 為 root 節(jié)點(diǎn)的 在前序遍歷的位置 preStart + 1 的位置
- 確定 root.right 的位置, root.right 為 root 節(jié)點(diǎn)在前序遍歷中 preStart + (所有左子樹元素個(gè)數(shù)) + 1 的位置。
- 確定 root.right 的位置需要知道 root 所有左子樹元素個(gè)數(shù)蓄喇，這時(shí)只依靠前序遍歷的結(jié)果是無法得到的发侵，而中序遍歷的結(jié)果順序?yàn)?[ 左 根 右 ], 我們已經(jīng)根據(jù)前序遍歷 preorder[preStart] 確定了 根 root 的值，找到 root 在中序遍歷結(jié)果中的位置后妆偏，此位置在中序遍歷中的所有左側(cè)元素就是我們要的結(jié)果刃鳄。
- 查找當(dāng)前 root 節(jié)點(diǎn)在 inorder 中的位置，已知 root钱骂，需要提供此段節(jié)點(diǎn) inStart, inEnd 的位置叔锐。這時(shí)我們的函數(shù) 可寫為
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {} - 找到 root 在 inorder 中的位置 inIndex，inIndex - inStart 為 root 節(jié)點(diǎn)所有左子樹元素個(gè)數(shù)见秽， root.right 的 preStart 就為 preStart + inIndex - inStart + 1
- 在遞歸函數(shù)參數(shù)中愉烙，通過 inIndex 再來確定 root.left、root.right 的 inStart 和 inEnd
代碼實(shí)現(xiàn)
public class ReConstructBinaryTreeBak2 {
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public TreeNode buildTree(int [] preorder, int [] inorder) {
return helper(0, 0, inorder.length - 1, preorder, inorder);
}
public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd)
return null;
TreeNode root = new TreeNode(preorder[preStart]);
int inIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (root.val == inorder[i])
inIndex = i;
}
root.left = helper(preStart + 1, inStart, inIndex - 1, preorder, inorder);
root.right = helper(preStart + (inIndex - inStart + 1), inIndex + 1, inEnd, preorder, inorder);
return root;
}
}
koa-bodyparser 源碼解析
作用
將 http POST 請(qǐng)求的數(shù)據(jù)解析成對(duì)象掛載到 ctx.request.body 對(duì)象上進(jìn)行使用解取。
koa-bodyparser 中間件默認(rèn)支持表單格式 application/x-www-form-urlencoded 和 JSON 格式 application/json
源碼
bodyParser 中間件把請(qǐng)求的使用 parseBody(ctx) 解析成對(duì)象進(jìn)行掛載
return async function bodyParser(ctx, next) {
if (ctx.request.body !== undefined) return await next();
if (ctx.disableBodyParser) return await next();
try {
const res = await parseBody(ctx); // 解析 ctx 數(shù)據(jù)步责，默認(rèn) from json 兩種格式
ctx.request.body = 'parsed' in res ? res.parsed : {}; // 解析成功把結(jié)果掛載到 ctx.request.body 上
if (ctx.request.rawBody === undefined) ctx.request.rawBody = res.raw;
} catch (err) {
if (onerror) {
onerror(err, ctx);
} else {
throw err;
}
}
await next();
};
parseBody 函數(shù)使用 co-body 模塊進(jìn)行解析。
var parse = require('co-body');
// ...
async function parseBody(ctx) {
if (enableJson && ((detectJSON && detectJSON(ctx)) || ctx.request.is(jsonTypes))) {
return await parse.json(ctx, jsonOpts); // 解析 json 類型
}
if (enableForm && ctx.request.is(formTypes)) {
return await parse.form(ctx, formOpts); // 解析表單類型
}
if (enableText && ctx.request.is(textTypes)) {
return await parse.text(ctx, textOpts) || ''; // 解析文本類型
}
return {};
}
};
co-body 模塊解析 json, 把請(qǐng)求解析成字符串后進(jìn)行 JSON.parse(str) 然后返回
const raw = require('raw-body');
const inflate = require('inflation');
module.exports = async function(req, opts) {
req = req.req || req;
opts = utils.clone(opts);
// ...
const str = await raw(inflate(req), opts);
try {
const parsed = parse(str); // JSON.parse
return opts.returnRawBody ? { parsed, raw: str } : parsed;
} catch (err) {
err.status = 400;
err.body = str;
throw err;
}
co-body 模塊解析 from, 把表單請(qǐng)求解析成字符串后使用 qs.parse 解析后返回
const raw = require('raw-body');
const inflate = require('inflation');
module.exports = async function(req, opts) {
req = req.req || req;
opts = utils.clone(opts);
const queryString = opts.queryString || {};
// ...
const str = await raw(inflate(req), opts);
try {
const parsed = opts.qs.parse(str, queryString); // 使用 qs.parse 解析
return opts.returnRawBody ? { parsed, raw: str } : parsed;
} catch (err) {
err.status = 400;
err.body = str;
throw err;
}
};
nodejs 的 http 模塊接收的 post 請(qǐng)求為可讀流內(nèi)容禀苦，co-body 通過使用 raw-body 來解析成 str 供 co-body 來生成返回對(duì)象蔓肯。
var inflate = require('inflation')
var raw = require('raw-body')
const str = await raw(inflate(req), opts);
這里使用了 inflate 庫，庫里返回 http 可讀流的解壓后 Stream伦忠， stream.pip(zip.Unzip(opts)) 省核，作為參數(shù)傳給 raw-body 來解析
var zlib = require('zlib')
function inflate(stream, options) {
// ...
switch (encoding) {
case 'gzip':
case 'deflate':
break
case 'identity':
return stream
default:
var err = new Error('Unsupported Content-Encoding: ' + encoding)
err.status = 415
throw err
}
// no not pass-through encoding
delete options.encoding
return stream.pipe(zlib.Unzip(options))
}
raw-body 模塊通過 readStream 方法返回解析出來的 buf 字符串?dāng)?shù)據(jù)
function getRawBody (stream, options, callback) {
// ...
return new Promise(function executor (resolve, reject) {
readStream(stream, encoding, length, limit, function onRead (err, buf) {
if (err) return reject(err)
resolve(buf)
})
})
}
readStream 方法注冊 http stream 的事件進(jìn)行處理，onData 來處理 POST 請(qǐng)求的 Stream 數(shù)據(jù)昆码， onEnd 用 done 函數(shù)處理事件結(jié)束气忠。
function readStream (stream, encoding, length, limit, callback) {
// ...
var buffer = decoder
? ''
: []
stream.on('aborted', onAborted)
stream.on('close', cleanup)
stream.on('data', onData)
stream.on('end', onEnd)
stream.on('error', onEnd)
// ...
function onData (chunk) {
if (complete) return
received += chunk.length
if (limit !== null && received > limit) {
done(createError(413, 'request entity too large', {
limit: limit,
received: received,
type: 'entity.too.large'
}))
} else if (decoder) {
buffer += decoder.write(chunk)
} else {
buffer.push(chunk)
}
}
function onEnd (err) {
if (complete) return
if (err) return done(err)
if (length !== null && received !== length) {
done(createError(400, 'request size did not match content length', {
expected: length,
length: length,
received: received,
type: 'request.size.invalid'
}))
} else {
var string = decoder
? buffer + (decoder.end() || '')
: Buffer.concat(buffer)
done(null, string)
}
}
}
body-parser 總結(jié)
koa-bodyparser 通過使用 raw-body 模塊解析 http 請(qǐng)求的 stream buffer 數(shù)據(jù)成字符串格式邻储，再根據(jù)請(qǐng)求頭中的 MIME 來解析字符串成對(duì)應(yīng)的對(duì)象，最后掛載到 ctx.request.body 對(duì)象上旧噪。
async / await 方法解析
async function async1() {
console.log('async1 start');
await async2();
console.log('async1 end');
}
async function async2() {
console.log('async2');
}
async 函數(shù)通過 babel 后為一個(gè)自執(zhí)行函數(shù)吨娜，返回另一個(gè)函數(shù), 而原 async 函數(shù)里所要執(zhí)行的內(nèi)容將由 function*() { // 執(zhí)行內(nèi)容 } 包裹傳入 _asyncToGenerator 里
let async1 = (() => {
var _ref = _asyncToGenerator(function*() {
console.log("async1 start");
yield async2();
console.log("async1 end");
});
return function async1() {
return _ref.apply(this, arguments);
};
})();
let async2 = (() => {
var _ref2 = _asyncToGenerator(function*() {
console.log("async2");
});
return function async2() {
return _ref2.apply(this, arguments);
};
})();
解析 _asyncToGenerator
- _asyncToGenerator 的執(zhí)行
1.會(huì)先執(zhí)行傳入的 generator 函數(shù)
2.然后返回一個(gè) new Promise()
3.在 new Promise 里執(zhí)行 step("next") 來檢查當(dāng)前函數(shù)是否 有 yield 可執(zhí)行
4.有 yield 可執(zhí)行就通過 Promise.resolve(value).then(// 繼續(xù)執(zhí)行 step('"next", value))
5.一直到當(dāng)前 generator 函數(shù)執(zhí)行完畢，next() 返回 done 為 true 時(shí)才最終返回 resolve(value) 并把執(zhí)行的結(jié)果帶出淘钟，也就是 await 出來的值宦赠。
function _asyncToGenerator(fn) {
return function() {
var gen = fn.apply(this, arguments); // 先執(zhí)行傳入 generator 函數(shù)
return new Promise(function(resolve, reject) {
function step(key, arg) {
try {
var info = gen[key](arg);
var value = info.value;
} catch (error) {
reject(error);
return;
}
if (info.done) {
resolve(value);
} else {
return Promise.resolve(value).then(
function(value) {
step("next", value);
},
function(err) {
step("throw", err);
}
);
}
}
return step("next");
});
};
}
async / await 總結(jié)
當(dāng) async 函數(shù)執(zhí)行時(shí)，經(jīng)過內(nèi)部自執(zhí)行函數(shù)的將會(huì)把需要執(zhí)行的內(nèi)容直接傳入 _asyncToGenerator 中執(zhí)行米母，同時(shí)直接返回的 new Promise(// .. step("next")), 而返回的 new Promise 回調(diào)中 step("next") 函數(shù)會(huì)一直執(zhí)行直到 resolve(value) 帶出 await 后的執(zhí)行結(jié)果
