C++ write your own Smart Pointer
Complete code can be foound here: (https://github.com/Interstellarss/mystl/tree/main/include/ptr) Smart PointerSmart pointers are a type of pointer that automatically manage the memory of the object they point to. They are used to prevent memory leaks and other memory-related errors. There are three types of smart pointers: std::unique_ptr std::shared_ptr std::weak_ptr unique_ptrunique_ptr is a smart pointer that owns and manages another object through a pointer and disposes of that object ...
LeetCode 127 Word Ladder
题目描述Word Ladder [HARD] A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that: Every adjacent pair of words differs by a single letter. Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. sk == endWord Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest tr...
CF 817 D - Imbalanced Array
题目描述Imbalanced Array[1900] You are given an array a consisting of n elements. The imbalance value of some subsegment of this array is the difference between the maximum and minimum element from this segment. The imbalance value of the array is the sum of imbalance values of all subsegments of this array. For example, the imbalance value of array [1, 4, 1] is 9, because there are 6 different subsegments of this array: [1] (from index 1 to index 1), imbalance value is 0; [1, 4] (from index 1 to...
C++ write your own STL - HashTable
HashTablehash table 实现： 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168#ifndef MY_HASH_TABLE#define MY_HASH_TABLE#include "my_allocator.h"...
C++ write your own STL - Map & Set
my set: 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#ifndef MY_SET_H#define MY_SET_H#include "my_rbtree.h"#include "my_utility.h"namespace mystl{template <typename Key, typename Compare = std::less<Key>, typename Alloc = mystl::MyAllocator<mystl::RBTreeNode<Key>>>class MySet{private: using tree_type = mystl::MyRBTree<Key, Key, mystl::identity<Key>, Compare, Alloc>; tre...
LeetCode 79 - Word Search
题目描述[Medium] Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. Example 1: 12Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","...
LeetCode 78 - Subsets
题目描述[MEDIUM] Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Example 1: 12Input: nums = [1,2,3]Output: [[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[[]] Example 2: 12Input: nums = [0]Output: [[0]] Constraints: 1 <= nums.length <= 10-10 <= nums[i] <= 10All the numbers of nums are unique. 思路We can use backtracking (DFS) to generate all p...
LeetCode 198 - House Robber
题目描述[MEDIUM] You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alertin...
LeetCode 77 - Combinations
题目描述[MEDIUM] Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order. Example 1: 1234Input: n = 4, k = 2Output: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]Explanation: There are 4 choose 2 = 6 total combinations.Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination. Example 2: 123Input: n = 1, k = 1Output: [[1]]Explanation: There is 1 choose 1 = 1 total combination...
LeetCode 46 - Permutations
题目描述[MEDIUM] Given a collection of distinct integers, return all possible permutations. Example 1: 12Input: [1,2,3]Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Example 2: 12Input: [0,1]Output: [[0,1],[1,0]] Example 3: 12Input: [1]Output: [[1]] 思路递归回溯 （backtracking）题目要求输出所有不重复的排列。我们可以使用 回溯（Backtracking）： 用一个数组 path 来保存当前的排列。 用一个布尔数组 used 标记哪些数字已经被使用。 当 path 的长度等于 nums.size() 时，将当前排列加入结果集。 否则，遍历所有数字： 若该数字未被使用，则加入路径； 递归调用； 回溯（撤销选择）。 代码1234567891011121314151617181920212...