LeetCode

tags: LeetCode https://leetcode.com/problems/validate-binary-search-tree/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { if (root == nullptr || (root->left == nullptr && root->right == nullptr)) { return true; } if (root->left !...

tags: LeetCode,backtracking https://leetcode.com/problems/path-sum-ii/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int targetSum) { vector<vector<int>> r; if (root == nullptr) { return r; } if (root->left !...

tags: LeetCode https://leetcode.com/problems/path-sum/ 递归版 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root == nullptr) { return false; } return pathSum(root, 0, targetSum); } bool pathSum(TreeNode* node, int sum, int targetSum) { sum += node->val; if (node->left == nullptr && node->right == nullptr) { if (sum == targetSum) { return true; } } if (node->left !...

tags: LeetCode 79. Word Search class Solution { public: bool exist(vector<vector<char>>& board, string word) { backtracking(board, word, 0, 0); return res; } private: string track; bool res = false; enum Direction { right, down, up, left, }; /** * @param dir: 0: right, 1: down, 2: up, 3: left */ void backtracking(vector<vector<char>>& board, string word, int row, int col) { if (track == word || res) { res = true; return; } for (int i = row; i < board....

tags: LeetCode

tags: LeetCode https://leetcode.com/problems/valid-sudoku/ <- high -- low -> +------------------- wow(row(i):0,col(j):0) 0 -> [ 0010, 0010 ] | 1 -> [ 0000, 0000 ] | 2 -> [ 0000, 0000 ] | | +--------------- wow(row(i):0,col(j):1) 0 -> [ 0010 | 1 = 0011, 0010 ] | | 1 -> [ 0000, 0000 | 1 = 0001 ] | | 2 -> [ 0000, 0000 ] | | | | +----------- wow(row(i):0,col(j):2) 0 -> [ 0011 | 3 = 0100, 0010 ] | | | 1 -> [ 0000, 0001 ] | | | 2 -> [ 0000, 0000 | 3 = 0100 ] +---+---+---+ | 2 | 1 | 3 | +---+---+---+ ----| 3 | 2 | 1 | | +---+---+---+ | | 1 | 3 | 2 | | +---+---+---+ |- wow(row(i):1,col(j):0) 0 -> [0010 | 3 = 0110, 0010] +---------------------+ 1 -> [0000, 0001 | 3 = 0101] 2 -> [0000, 0100] class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { vector<int> wow(9,0); int mux1; int mux2; int mux3; int box_index; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(board[i][j] == '....

tags: LeetCode source: https://leetcode.com/problems/combination-sum-ii/ LeetCode: 39. Combination Sum 的进阶。元素不在唯一且每一个元素只能出现一次。对结果进行排序然后通过 set 对结果进行去重： class Solution { public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtracking(candidates, 0, 0, target); vector<vector<int>> r; for (auto t : res) { r.push_back(t); } return r; } private: set<vector<int>> res; vector<int> track; map<int, bool> visited; void backtracking(vector<int>& condidates, int start, int n, int target) { if (n == target) { res.insert(track); return; } if (n > target) { return; } int c = 0; int sz = condidates....

tags: LeetCode source: https://leetcode.com/problems/combination-sum/ class Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { backtracking(candidates, 0, target); return res; } private: vector<vector<int>> res; vector<int> track; void backtracking(vector<int> & candidates, int n, int target) { if (n == target) { res.push_back(track); return; } // this is new if (n > target) { return; } for (auto c : candidates) { track.push_back(c); backtracking(candidates, n + c, target); track.pop_back(); } } }; 问题：会有不同顺序但是元素相同的数组，如何快速高效的进行过滤？...

tags: LeetCode,backtracking source: https://leetcode.com/problems/n-queens-ii/ 参见：LeetCode: 51. N-Queens

tags: LeetCode,backtracking source: https://leetcode.com/problems/n-queens/ 一旦一个 Queue 被放置，那么横轴、纵轴、对角线都不再允许放置。我们按行进行遍历，所以我们需要跟踪以下位置是否已经放置 Queue： 纵轴（Column）：cols 主对角线（Positive Diagonal）：posDiag 次对角线（Negative Diagonal）：negDiag 纵轴很好记录，但是对角线比较困难，我们先来看一下对角线的特征，假设横轴为 r 纵轴为 c ， r - c 在正对角线是一致的： 斜对角线 r + c 是一致的: class Solution { public: vector<vector<string>> solveNQueens(int n) { for (int r = 0; r < n; r++) { string col = string(n, '.'); track.push_back(col); } backtracking(0, n); return res; } private: set<int> cols; // c set<int> posDiag; // r - c set<int> negDiag; // r + c vector<vector<string>> res; vector<string> track; void backtracking(int r, int n) { if (r == n) { res....

tags: LeetCode,backtracking 视频解析：https://www.youtube.com/watch?v=s7AvT7cGdSo 在 LeetCode: 46. Permutations 的基础上增加重复的元素。感觉不能依赖于 track + map 的去重逻辑回溯。 class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> res; } }; 数据特征： Value: 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, Index: 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { set<vector<int>> res; vector<vector<int>> ret; int n, i; vector<vector<int>> perms; if (nums....

tags: LeetCode,backtracking Keywords backtrack 回溯算法 图解 举例： [1, 2, 3] ，顺着叶子节点和删除的节点就可以还原成全排列。 从上面图可以看出来，叶子节点加上回溯路径上被移除的节点就是结果的一项，从左到右依次是： [3,R:2,R:1] -> [3,2,1] [2,R:3,R:1] -> [2,3,1] … class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> track; backtrack(res, track, nums); return res; } void backtrack(vector<vector<int>> & res, vector<int> & track, vector<int>& nums) { if (track.size() == nums.size()) { res.push_back(track); return; } for (int i = 0; i < nums.size(); i++) { if (visited.find(nums[i]) != visited.end() && visited[nums[i]]) { continue; } track....

tags: LeetCode source: https://leetcode.com/problems/reverse-nodes-in-k-group/ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { deque<ListNode*> dq; ListNode* cur = head; ListNode* top = nullptr; ListNode* tail = nullptr; bool first_k = true; while (cur !...

tags: LeetCode source: https://leetcode.com/problems/reverse-linked-list-ii/ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { stack<int> st; ListNode* cur = head; ListNode* prev_start = nullptr; if (left == 1) { prev_start = new ListNode(0, head); // dummy prev_start point to head } int i = 1; while(cur !...

tags: LeetCode

tags: LeetCode 移除小写字母中重复的字母，让所有字母都只出现一次，并且结果是所有结果中按照字典序排序最小的那个。 Example 1 Input: “bcabc” Output: “abc” Example 2 Input: “cbacdcbc” Output: “acdb” 解法之一: 通过一个数组对每一个出现的字母进行计数 遍历每一个字母放入栈，并将该字母的计数减 1 查看栈底的字母有没有比当前字母大且该字母的计数不为 0 的（有比当前更小的字典序），从栈底弹出该字母 func removeDuplicateLetters(s string) string { var countOfEachLetter [26]int var visited [26]bool stack := make([]byte, 0) stackBottom := 0 bytesArr := []byte(s) for _, c := range bytesArr { countOfEachLetter[getIndex(c)]++ } for _, c := range bytesArr { index := getIndex(c) countOfEachLetter[index]-- if visited[index] { continue } // countOfEachLetter[getIndex(stack[stackBottom])] > 0 后面还有该字符 for len(stack[stackBottom:]) > 0 && stack[stackBottom] > c && countOfEachLetter[getIndex(stack[stackBottom])] > 0 { // 标记为未访问用于后面的字符加入结果 visited[getIndex(stack[stackBottom])] = false // 移动栈底 stackBottom++ } // 加入到结果栈 stack = append(stack, c) visited[index] = true } return string(stack[stackBottom:]) } func getIndex(b byte) int { return int(b - 'a') } 通过上面解法遇到如下错误：...

tags: LeetCode 解法 1 找到中间节点依次往左右扩散： 向左边扩散，如果左边的大于当前元素，那么当前元素即为最小值 向右边扩散，如果右边的小于当前元素，那么右边元素即为最小值 如果以上不成立则第一个元素为最小元素（未旋转），以下是代码 func findMin(nums []int) int { length := len(nums) if length == 1 { return nums[0] } // 从中间开始确定方向 mid := length / 2 - 1 left, right := mid, mid for left - 1 >= 0 || right + 1 < length { if left - 1 >= 0 { if nums[left - 1] > nums[left] { return nums[left]; } left-- } if right + 1 < length { if nums[right] > nums[right + 1] { return nums[right + 1] } right++ } } return nums[0] } 优化 参考答案后可通过二分查找做如下优化，首先判断是否被旋转：...

tags: LeetCode 思路 这个是 LeetCode: 153.Find Minimum in Rotated Sorted Array 扩展，增加了以下几种边界情况： ‘[2, 2, 2, 2, 1]’ ‘[3, 1, 3]’ ‘[1, 1, 1]’ ‘[10, 1, 10, 10, 10]’ 但核心依然是判断最小值是在左边还是右边。假设如下数组： ‘[3, 3, 3, 1, 3]’ left[0]=3, right[4]=3, mid[2]=3, 这时候不确定最小值在哪边但是 right– 是安全的，所以执行 right– left[0]=3, right[3]=1, mid[2]=3, 这时候 mid < right 说明最小值在 mid 的右边，所以调整 left = mid + 1 左右两边索引一致终止循环 实现 func findMin(nums []int) int { length := len(nums) left, right := 0, length - 1 for left < right { mid := (left + right) / 2 if nums[mid] > nums[right] { left = mid + 1 } else if nums[mid] < nums[right] { right = mid } else { right-- } } return nums[right] }

tags: LeetCode 准备 动态规划 实践 字符串 “abcabcbb” 根据索引有如下关系 a b c a b c b b 0 1 2 3 4 5 6 7 \(f(0,1)=f(0,0) + 1\) \(f(0,2)=f(0,1) + 2\) 在所有字符都不重复的情况下有如下公式 \(f(s,e)=f(s,e-1) + e\) 若遇到重复的情况则，3 索引于当前字串 的 0 重复则表明当前字串已经到头，需要记录并偏移 s，s=1： \(f(1,3)=f(1,2)+3\) 假设： s - 开始字符索引 e - 结束字符索引 若遇到当前字符于前面 r 字符重复则： \[ f(r,e)=f(s,e - 1) + e; s=r \] 解法 func lengthOfLongestSubstring(s string) int { if len(s) == 0 { return 0 } appearedIndexes := [256]int{} for i := 0; i < 256; i++{ appearedIndexes[i] = -1 } longest, start, end := 0, 0, 0 b := []byte(s) for cIndex, c := range b { index := int(c) appearedIndex := appearedIndexes[index] end = cIndex // 出现过需要截断 if appearedIndex !...

tags: LeetCode 思路 归并排序 代码 func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { nums := mergeSort(nums1, nums2) length := len(nums) if length % 2 != 0 { return float64(nums[(length - 1) / 2]) } i := length / 2 return (float64(nums[i]) + float64(nums[i - 1])) / 2 } func mergeSort(nums1 []int, nums2 []int) []int { l1 := len(nums1) l2 := len(nums2) result := make([]int, 0, l1 + l2) i, j := 0, 0 for i < l1 && j < l2 { if nums1[i] < nums2[j] { result = append(result, nums1[i]) i++ } else { result = append(result, nums2[j]) j++ } } result = append(result, nums1[i:]....

tags: LeetCode > https://leetcode.com/problems/longest-palindromic-substring/description/ 思路 直接暴力往两边搜索 func longestPalindrome(s string) string { buf := []byte(s) length := len(buf) if length == 0 { return s } start, end := 0, 0 for ci, _ := range buf { i, j := ci, ci // 无法处理 "aaaa" 和 "noon" 这种情况 for i > 0 && j < length - 1 && buf[i - 1] == buf[j + 1] { i-- j++ } // 考虑 "bba" 这种情况 if i == j && ci > 0 && buf[ci] == buf[ci - 1] { i, j = ci-1, ci } // 考虑 "abb" 这种情况 if i == j && ci < length - 1 && buf[ci] == buf[ci + 1] { i, j = ci, ci + 1 } if i !...

tags: LeetCode srouce: https://leetcode.com/problems/zigzag-conversion/description/ 先根据行数计算列数： \(column=length / (row + 2) + bool(length \mod (row + 2))\) 每一行必然有点的位置为： \(i \mod (row - 1)\) 为 0