0707学习 agile Posted on Jul 7 2023 面试 leetcode学习 - 剑指 Offer 12. 矩阵中的路径 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。  ---  --- ```C# private int __row; private int __column; private int[][] __filled; private char[][] __board; private string __word; public bool Exist(char[][] board, string word) { __row = board.Length; __column = board[0].Length; __filled = new int[__row][]; __board = board; __word = word; for (var i = 0; i < __row; i++) { __filled[i] = new int[__column]; } for (var i = 0; i < __row; i++) { for (var j = 0; j < __column; j++) { __ResetFill(); if (__Help(i, j, 0)) { return true; } } } return false; } private bool __Help(int i, int j, int index) { if (i < 0 || j < 0 || i >= __row || j >= __column || __filled[i][j] > 0) { return false; } if (__board[i][j] == __word[index]) { if (++index == __word.Length) { return true; } __SetFill(i, j, 1); return __HelpFill(i + 1, j, index) || __HelpFill(i, j + 1, index) || __HelpFill(i - 1, j, index) || __HelpFill(i, j - 1, index); } return false; } private bool __HelpFill(int i, int j, int index) { if (i < 0 || j < 0 || i >= __row || j >= __column) { return false; } if (__filled[i][j] > 0) { return false; } if (__Help(i, j, index)) { return true; } __SetFill(i, j, 0); return false; } private void __ResetFill() { for (var i = 0; i < __row; i++) { Array.Fill(__filled[i], 0); } } private void __SetFill(int i, int j, int v) { if (i < 0 || j < 0 || i >= __row || j >= __column) { return; } __filled[i][j] = v; } // public bool Exist2(char[][] board, string word) { __row = board.Length; __column = board[0].Length; __board = board; __word = word; for (var i = 0; i < __row; i++) { for (var j = 0; j < __column; j++) { if (__Help2(i, j, 0)) { return true; } } } return false; } private bool __Help2(int i, int j, int index) { if (i < 0 || i >= __row || j < 0 || j >= __column || __board[i][j] != __word[index]) { return false; } if (__word.Length == index + 1) { return true; } __board[i][j] = '\0'; var res = __Help2(i, j + 1, index + 1) || __Help2(i, j - 1, index + 1) || __Help2(i + 1, j, index + 1) || __Help2(i - 1, j, index + 1); __board[i][j] = __word[index]; return res; } ``` - 剑指 Offer 13. 机器人的运动范围 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？ ---  --- ```C# private int __row; private int __column; private int __boundaryNum; private int[][] __hasReach; private bool[][] __hasReachFlag; public int MovingCount(int m, int n, int k) { __row = m; __column = n; __boundaryNum = k; __hasReach = new int[m][]; for (int i = 0; i < m; i++) { __hasReach[i] = new int[__column]; Array.Fill(__hasReach[i], -1); } return Moving(0, 0); } private int Moving(int i, int j) { if (i < 0 || i >= __row || j < 0 || j >= __column || __hasReach[i][j] >= 0) { return 0; } var t = __Sum(i, j); __hasReach[i][j] = t; if (t > __boundaryNum) { return 0; } var moveNum = 1; moveNum += Moving(i, j + 1) + Moving(i + 1, j); return moveNum; } private int __Sum(int m, int n) { return __SplitNum(m) + __SplitNum(n); } private int __SplitNum(int num) { var sum = 0; while (num != 0) { sum += num % 10; num = num / 10; } return sum; } //(m+n)%10=0 =>s(i+1)=s(i)-8 //(m+n)%10!=0=>s(i+1)=s(i)+1 public int MovingCount2(int m, int n, int k) { __row = m; __column = n; __boundaryNum = k; __hasReachFlag = new bool[m][]; for (int i = 0; i < m; i++) { __hasReachFlag[i] = new bool[__column]; } return __Moving(0, 0, 0, 0); } private int __Moving(int i, int j, int si, int sj) { if (i < 0 || i >= __row || j < 0 || j >= __column || __hasReachFlag[i][j]) { return 0; } __hasReachFlag[i][j] = true; if (si + sj > __boundaryNum) { return 0; } var res = 1; res += __Moving(i, j + 1, si, __Sum2(j + 1, sj)) + __Moving(i + 1, j, __Sum2(i + 1, si), sj); return res; } private int __Sum2(int i, int sum) { return i % 10 == 0 ? sum - 8 : sum + 1; } ``` --- - 剑指 Offer 34. 二叉树中和为某一值的路径 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 --- ```C# private List<IList<int>> __pathes; public IList<IList<int>> PathSum(TreeNode root, int target) { __pathes = new List<IList<int>>(); if (root == null) { return __pathes; } var s = new List<int>(); __Help(root, s, target); return __pathes; } private void __Help(TreeNode node, List<int> s, int target) { if (node == null) { return; } s.Add(node.val); var temp = target - node.val; __Help(node.left, s, temp); __Help(node.right, s, temp); if (node.left == null && node.right == null && temp == 0) { __pathes.Add(new List<int>(s)); } s.RemoveAt(s.Count - 1); } ``` - 剑指 Offer 36. 二叉搜索树与双向链表 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例：  我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。  特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 ---  --- ```C# private Node __head; private Node __pre; public Node TreeToDoublyList(Node root) { if (root == null) { return root; } __head = new TreeNode(0); __pre = __head; __DFS(root); __head.right.left = __pre; __pre.right = __head.right; return __head.right; } private void __DFS(Node node) { if (node.left != null) { __DFS(node.left); } __pre.right = node; node.left = __pre; __pre = node; if (node.right != null) { __DFS(node.right); } } ``` --- 0709学习 0705学习
