Mar 14 | Datawhale 01~04 打卡 | Leetcode面试下

第一阶段主要就是学习字符串的处理和二叉树的遍历。前一段时间学习了二叉树的遍历，记忆还比较深刻，这几个题还是比较轻松的做出来了；但是像Longest Palindromic Substring这样的题除了简单的字符串处理（回文判断），还要使用动态规划之类的算法，很久以前简单学习了一下动态规划，但一段时间不用很快就忘记了。这一题我尝试用暴力来解，但很容易就超时了。周末找个时间重新好好学习一下dp！

⚠️ 注：代码我都是用js写的，不是python！

DAY 1

3. Longest Substring Without Repeating Characters (medium)

String | Sliding Window + Hash Table

/*** @param {string} s* @return {number}*/
var lengthOfLongestSubstring = function(s) {let start = 0; // Start of the current windowlet maxLength = 0; // Maximum length of substring found so farconst map = {}; // Map to store the last index of each characterfor(let end = 0; end < s.length; end++) {const currentChar = s[end];// If the character is found in the map and is within the current window,// move the start to the next position after the last occurrence of currentCharif (map[currentChar] >= start) {start = map[currentChar] + 1;}// Update the last index of the current charactermap[currentChar] = end;// Update maxLength if the current window size is largermaxLength = Math.max(maxLength, end - start + 1);}return maxLength;
};

5. Longest Palindromic Substring (medium)

勉强通过的brute-force

/*** @param {string} s* @return {string}*/const isPalindrome = (s, l, r) => {for (let i = l, j = r; i < j; i++, j--) {if(s[i] !== s[j]) return false;}return true;
}
var longestPalindrome = function(s) {let longest = '';for (let start = 0; start < s.length; start++) {for (let end = start; end < s.length; end++) {let substr = s.substring(start, end + 1); if (isPalindrome(s, start, end) && substr.length > longest.length) {longest = substr;}}}return longest;
};

8. String to Integer (atoi) (medium)

晕 @_@ 好难cover所有testcase！

/*** @param {string} s* @return {number}*/
var myAtoi = function(s) {let i = 0, sign = 1, result = 0, INT_MAX = 2**31 - 1, INT_MIN = -(2**31);// Ignore leading whitespacewhile (s[i] === ' ') i++;// Handle signif (s[i] === '+' || s[i] === '-') {sign = s[i] === '+' ? 1 : -1;i++;}// Convert number and avoid non-digit characterswhile (i < s.length && s[i] >= '0' && s[i] <= '9') {result = result * 10 + (s[i] - '0');i++;}// Apply signresult *= sign;// Clamp to 32-bit signed integer rangeif (result < INT_MIN) return INT_MIN;if (result > INT_MAX) return INT_MAX;return result;
};

DAY 2

151. Reverse Words in a String (medium)

43. Multiply Strings (medium)

额(⊙﹏⊙)，说实话没明白这题是啥意思。
不过题目说，Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
之后再仔细研究一下这题！

var multiply = function(num1, num2) {return (BigInt(num1) * BigInt(num2)).toString();
};

14. Longest Common Prefix (easy)

/*** @param {string[]} strs* @return {string}*/
var longestCommonPrefix = function(strs) {if (strs.length === 0) return "";for (let i = 0; i < strs[0].length; i++) {let c = strs[0][i];for (let j = 1; j < strs.length; j++) {if (strs[j].length <= i || strs[j][i] !== c) {return strs[0].slice(0, i);// return strs[0].substring(0, i);}}}return strs[0];
};

一点优化：先将strs 排序，然后直接选取第一个和最后一个比较。
时间复杂度：O($m\ast n$) --> O($nlo{g}_n+m$)

var longestCommonPrefix = function(strs) {if (strs.length === 0) return "";strs.sort();for (let i = 0; i < strs[0].length; i++) {let c = strs[0][i];if(strs[0][i] !== strs[strs.length-1][i]) {return strs[0].substring(0, i);}}return strs[0];
};

DAY 3

144. Binary Tree Preorder Traversal (easy)

const traversal = function (root, res) {if (root === null) return ;res.push(root.val);traversal(root.left, res);traversal(root.right, res);
};var preorderTraversal = function (root) {let res = [];traversal(root, res);return res;
};

94. Binary Tree Inorder Traversal (easy)

var inorderTraversal = function(root) {let res = [];traversal(root, res);return res;
};const traversal = function (root, res) {if (root === null) return;traversal(root.left, res);res.push(root.val);traversal(root.right, res);
};

102. Binary Tree Level Order Traversal (medium)

用队列，先进先出

const levelOrderTraversal = function(root, res, queue) {if(root === null) return [];queue.push(root);while(queue.length !== 0) {const length = queue.length; // the length of root array: 7let level = []; // store each level arrayfor(let i = 0; i< length; i++) {let node = queue.shift(); // take the first num, i.e. the root nodelevel.push(node.val); if(node.left) {queue.push(node.left);} if(node.right) {queue.push(node.right);}}res.push(level);}return res;
}var levelOrder = function(root) {let res = [], queue = [];levelOrderTraversal(root, res, queue);return res;
};

DAY 4

103. Binary Tree Zigzag Level Order Traversal (medium)

用层序遍历，然后隔一行翻转

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

236. Lowest Common Ancestor of a Binary Tree (medium)

自底向上查找 -> 回溯 -> 后序遍历（左右中）

var lowestCommonAncestor = function(root, p, q) {function dfs(root, q, p) {if (root === q || root === p || root === null) return root;let left = dfs(root.left, q, p)let right = dfs(root.right, q, p)if(left !== null && right !== null) return root;else if(left !== null && right === null) return left;else if(left === null && right !== null) return right;else return null;}return dfs(root, q, p);
};

104. Maximum Depth of Binary Tree (easy)

层序遍历求层数，用dfs应该也能做…

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