算法

面试中算法题目

云账户 /** 给定一个包括 '('，')'，'{'，'}'，'['，']' 和'*'干扰字符的字符串，判断字符串是否有效。 例： {**[*()*(**)**]**} 输出true {**[**)**(**]**} 输出false */ 快手 260. 只出现一次的数字 III 腾讯 168. Excel表列名称 72. 编辑距离 字节 package main import "fmt" func calc(x, y int) int { fmt.Println(x, y, x+y) return x + y } func main() { a := 1 b := 2 defer calc(a, calc(a, b)) a = 0 defer calc(a, calc(a, b)) } 200. 岛屿数量 128. 最长连续序列 某部门面试题 //a_0 = [1] //a_1 = [a_0, 2, a_0] = [1,2,1] //a_2 = [a_1, 3, a_1] = [1,2,1,3,1,2,1] //a_n = [a_{n-1}, n+1, a_{n-1}] // //a_n.

预习

第1课 | 数据结构与算法总览，第2课 | 训练准备和复杂度分析

第1周

第一周 第三课|数组、链表、跳表 参考链接 Java 源码分析（ArrayList） Linked List 的标准实现代码 [Linked List 示例代码](http://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/code/LinkedList.java) Java 源码分析（LinkedList） LRU Cache - Linked list： LRU 缓存机制 Redis - Skip List：跳跃表 、为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？ Array 实战题目 11. 盛最多水的容器 //方法一： 暴力求解 双循环 class Solution { /** * @param Integer[] $height * @return Integer */ function maxArea($height) { $max = 0; $len = count($height); for ($i = 0; $i < $len - 1; $i++) { for ($j = $i + 1; $j < $len; $j++) { $area = ($j - $i) * min($height[$i], $height[$j]); $max = $area < $max ?

第1周 数组、链表、跳表

第3课|数组、链表、跳表

第2周

第2周 第4课 | 栈、队列、优先队列、双端队列 参考链接 Java 的 PriorityQueue 文档 Java 的 Stack 源码 Java 的 Queue 源码 Python 的 heapq 高性能的 container 库 预习题目 20. 有效的括号 class Solution { /** * 方法一：栈(spl标准库) * @param String $s * @return Boolean */ function isValid($s) { //构造哈希表 $map = [')'=>'(', ']'=>'[', '}'=>'{']; $stack = new SplStack(); for ($i = 0, $len = strlen($s); $i < $len; $i++) { if (!isset($map[$s[$i]])) { $stack->push($s[$i]); } else if (!$stack->count() || $stack->pop() !

第2周 栈、队列、哈希表

第4课 | 栈、队列、优先队列、双端队列，第5课 | 哈希表、映射、集合

第3周

第3周 第6课 | 树、二叉树、二叉搜索树 1. 树、二叉树、二叉搜索树的实现和特性 参考链接 二叉搜索树 Demo 思考题 树的面试题解法一般都是递归，为什么？ 说明：同学们可以将自己的思考写在课程下方的留言区一起讨论，也可以写在第 2 周的学习总结中。 2. 实战题目解析：二叉树的中序遍历 参考链接 树的遍历 Demo 实战题目 / 课后作业 94. 二叉树的中序遍历 /** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */ class Solution { private $values = []; /** * 方法一：递归 * @param TreeNode $root * @return Integer[] */ function inorderTraversal1($root) { $this->inorder($root); return $this->values; } function inorder($root) { if ($root) { $this->inorder($root->left); $this->values[] = $root->val; $this->inorder($root->right); } } /** * 方法二：迭代 * @param TreeNode $root * @return Integer[] */ function inorderTraversal2($root) { $stack = $res = []; while ($root || $stack) { while ($root) { $stack[] = $root; $root = $root->left; } $root = array_pop($stack); $res[] = $root->val; $root = $root->right; } return $res; } /** * 方法三：颜色标记法 * @param TreeNode $root * @return Integer[] */ function inorderTraversal3($root) { $white = 0; $gray = 1; $stack = [[$white, $root]]; $res = []; while ($stack) { [$color, $node ] = array_pop($stack); if (!

第4周

第4周 第9课 | 深度优先搜索和广度优先搜索 1. 深度优先搜索、广度优先搜索的实现和特性 参考链接 DFS 代码模板（递归写法、非递归写法） 递归写法 visited = set() def dfs(node, visited): if node in visited: # terminator # already visited return visited.add(node) # process current node here. ... for next_node in node.children(): if next_node not in visited: dfs(next_node, visited) 非递归写法 def DFS(self, tree): if tree.root is None: return [] visited, stack = [], [tree.root] while stack: node = stack.pop() visited.add(node) process (node) nodes = generate_related_nodes(node) stack.push(nodes) # other processing work .

第6周

第12课 | 动态规划 1. 动态规划的实现及关键点 参考链接 递归代码模板 # Python 代码模板 def recursion(level, param1, param2, ...): # recursion terminator if level > MAX_LEVEL: process_result return # process logic in current level process(level, data...) # drill down self.recursion(level + 1, p1, ...) # reverse the current level status if needed //Java 代码模板 public void recur(int level, int param) { // terminator if (level > MAX_LEVEL) { // process result return; // process current logic process(level, param); // drill down recur( level: level + 1, newParam); // restore current status } 分治代码模板 def divide_conquer(problem, param1, param2, .

第6周 动态规划

第12课 动态规划

第7周

第7周 第13课 | 字典树和并查集 1. Trie树的基本实现和特性 参考链接 102. 二叉树的层序遍历 /** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */ class Solution { /** * bfs * @param TreeNode $root * @return Integer[][] */ function levelOrder($root) { if (!$root) return []; $queue = [$root]; $res = []; while ($queue) { $count = count($queue); $row = []; while ($count--) { $node = array_shift($queue); $row[] = $node->val; $node->left && $queue[] = $node->left; $node->right && $queue[] = $node->right; } $res[] = $row; } return $res; } // function levelOrder($root) { if (!

第8周

第8周 第16课 | 位运算 1. 位运算基础及实战要点 参考链接 如何从十进制转换为二进制 2. 位运算实战题目解析 参考链接 N 皇后位运算代码示例 def totalNQueens(self, n): if n < 1: return [] self.count = 0 self.DFS(n, 0, 0, 0, 0) return self.count def DFS(self, n, row, cols, pie, na): # recursion terminator if row >= n: self.count += 1 return bits = (~(cols | pie | na)) & ((1 << n) — 1) # 得到当前所有的空位 while bits: p = bits & —bits # 取到最低位的1 bits = bits & (bits — 1) # 表示在p位置上放入皇后 self.

第9周

第9周 第19课 | 高级动态规划 1. 动态规划、状态转移方程串讲 参考链接 70.爬楼梯 class Solution { /** * 动态规划解法 * Binets 方法 和 斐波那契公式 时间复杂度为O(log(N)) * @param Integer $n * @return Integer */ function climbStairs($n) { if ($n <= 2) return $n; $first = 1; $second = 2; for ($i = 3; $i <= $n; $i++) { $tmp = $first + $second; $first = $second; $second = $tmp; } return $second; } } //斐波那契公式 public class Solution { public int climbStairs(int n) { double sqrt5=Math.

第9周 高级动态规划、字符串算法

第19课 | 高级动态规划、第20课 | 字符串算法

第10周 期末串讲、期末考试、毕业刷题路线

期末串讲、期末考试、毕业刷题路线

LeetCode 回文串系列

剑指 Offer II 018. 有效的回文 剑指 Offer II 086. 分割回文子字符串 剑指 Offer II 020. 回文子字符串的个数 336. 回文对 125. 验证回文串 647. 回文子串 680. 验证回文字符串 Ⅱ 409. 最长回文串 131. 分割回文串 https://leetcode-cn.com/submissions/detail/152376203/ 132. 分割回文串 II 1278. 分割回文串 III 1745. 回文串分割 IV 5. 最长回文子串 1616. 分割两个字符串得到回文串 42. 接雨水 268. 丢失的数字 688. 骑士在棋盘上的概率 1005. K 次取反后最大化的数组和 1380. 矩阵中的幸运数

LeetCode每日一题

(03-25) 892. 三维形体的表面积 class Solution { /** * @param Integer[][] $grid * @return Integer */ function surfaceArea($grid) { $n = count($grid); $area = 0; for ($i = 0; $i < $n; $i++) { for ($j = 0; $j < $n; $j++) { $level = $grid[$i][$j]; if ($level > 0) { //贡献的面积 << 2 相当于 * 4 $area += 2 + ($level << 2); //减去重合的面积 << 1 相当于 * 2 $area -= $i > 0 ? min($level, $grid[$i - 1][$j]) << 1 : 0; //减去重合的面积 $area -= $j > 0 ?

2022年02月LeetCode每日一题

20220216 1719. 重构一棵树的方案数 困难 func checkWays(pairs [][]int) int { adj := map[int]map[int]bool{} for _, p := range pairs { x, y := p[0], p[1] if adj[x] == nil { adj[x] = map[int]bool{} } adj[x][y] = true if adj[y] == nil { adj[y] = map[int]bool{} } adj[y][x] = true } // 检测是否存在根节点 root := -1 for node, neighbours := range adj { if len(neighbours) == len(adj)-1 { root = node break } } if root == -1 { return 0 } ans := 1 for node, neighbours := range adj { if node == root { continue } currDegree := len(neighbours) parent := -1 parentDegree := math.

LeetCode

数组和链表 206. 反转链表 24. 两两交换链表中的节点 141. 环形链表 142. 环形链表 II 24. 两两交换链表中的节点 21. 合并两个有序链表 25.K 个一组翻转链表 86.分隔链表 92.反转链表 II /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { int change_len = n - m + 1; ListNode *pre_head = NULL; ListNode *result = head; while (head && --m) { pre_head = head; head = head->next; } ListNode *modify_list_tail = head; ListNode *new_head = NULL; while (head && change_len--) { ListNode *next = head->next; head->next = new_head; new_head = head; head = next; } //连接为翻转部分 modify_list_tail->next = head; if (pre_head) { pre_head->next = new_head; } else { result = new_head; } return result; } }; /** * Definition for a singly-linked list.

第八课动态规划

70. 爬楼梯 class Solution { public: int climbStairs(int n) { std::vector<int> dp(n + 3, 0); dp[1] = 1; dp[2] = 1; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }; 198. 打家劫舍 class Solution { public: int rob(vector<int>& nums) { if (nums.size() == 0) { return 0; } if (nums.size() == 1) { return nums[0]; } //设第一个房间的最优解dp[i] std::vector<int> dp(nums.size(), 0); dp[0] = nums[0]; dp[1] = std::max(nums[0], nums[1]); for (int i = 2; i < nums.