leetcode部分排序类-competivie-cpp:竞争-cpp

  • E4_358073
    了解作者
  • 17.7KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-05-12 03:27
    上传日期
leetcode 部分排序类最大子数组和 INT_MIN , INT_MAX 语法: int x=0, y=0; 库std::array , array<type> = { {...} }; std::array作为未知大小的参数,使用模板, template<std> 最大子数组和的更简单的解决方案 排序和二分查找 makefile :对于 cpp 程序使用CXX而不是CC (类似于CPPFLAGS ) 使用sort 、 .begin() and .end() 对vector进行sort . rbegin() and rend()` 语法: template<typename> void swap(T& x, T& y) 在 C++ 中打印向量不是很方便,需要自己编写函数 std:pair用法, first和second std:get<i>(tuple)获取第i个元素,也适用于pair 外部cmp函数 使用lower_bound作为二分查找 使用upper_bound作为索引 + 1 要获取索引,请使用index - v.begin() 基
competivie-cpp-master.zip
  • competivie-cpp-master
  • data_structures.cpp
    1.9KB
  • counting_subsets.cpp
    811B
  • coin_greedy.cpp
    575B
  • query_range_sum.cpp
    685B
  • cycle_detection.cpp
    1.1KB
  • graph_traversal.cpp
    1.3KB
  • README.md
    6KB
  • longest_increasing_sequence.cpp
    483B
  • permutation.cpp
    701B
  • counting_tilings.cpp
    1.5KB
  • my_macros.h
    164B
  • starter_code.cpp
    133B
  • path_in_a_grid.cpp
    897B
  • .gitignore
    273B
  • maximum_subarray_sum.cpp
    1.4KB
  • backtracking.cpp
    680B
  • knapsack.cpp
    1022B
  • sort_practice.cpp
    1.7KB
  • binary_search_variant.cpp
    917B
  • Makefile
    233B
  • counting_bits.cpp
    549B
  • edit_distance.cpp
    561B
  • binary_search.cpp
    1.1KB
  • coin_dp.cpp
    473B
  • generating_subset.cpp
    647B
  • iterate_permutation_by_subset.cpp
    671B
  • bit_manipulation.cpp
    682B
  • pruning_search_space.cpp
    1.4KB
内容介绍
# maximum subarray sum - `INT_MIN`, `INT_MAX` - syntax: `int x=0, y=0;` - library `std::array`, array<type, size> = { {...} }; - `std::array` as parameter of unknown size, use template, `template<std::size_t SIZE>` - much easier solution for maximum subarray sum # sort and binary search - `makefile`: use `CXX` instead of `CC`for cpp programs (similar for `CPPFLAGS`) - sort `vector` using `sort`, `.begin() and `.end()`. `rbegin()` and `rend()` - syntax: `template<typename T> void swap(T& x, T& y)` - print vector not very handy in C++, needs to write your own function - `std:pair` usage, `first` and `second` - `std:get<i>(tuple)` to get the `i`th element, works also for `pair` - external `cmp` function - use `lower_bound` as binary search - use `upper_bound` as index + 1 - to get the index, use `index - v.begin()` ## 2nd version of binary search based on jump - jump: another method to search (also logarithmic time) - `k`: current position - `b`: stride to try with `k+b`. - if fail, then try smaller stride (`b/=2`) - integer division like Python: `5/2 = 2` - generalization of the jump binary search on finding smallest solution with on arrays like `<F, F, F, F, T, T, T>` # data structures ## vector - `vector<type> a(length, value)` or `vector<type> a(length)` initialized all to zero - `.back` and `.front` method ## string - `substr` and `find` ## set - `set` based on balanced binary tree, `O(log n)` time - `unordered_set` based on hashtable, `O(1)` time main methods: `insert`, `erase`, `count` (can be used as contains) - similarly for `multiset` and `unordered_multiset` ## map - similarly `map` and `unordered_map` - insertion by `m[key]=value` - existence by `m.count(key)` - if a key does not exist but is requested, automatically added with default value - `for(auto p: m)` and `p.first` and `p.second` (`p` is a pair) ## iterators - iterating vector, set, string using `iterators` - an iterator is essentially a pointer - `s.begin()` returns a pointer. so to get the value, use `*` to de-reference ## bitset - `cout << (s1 & s2) << endl;` using *parenthesis* s1 and s2 - `bitset<10> bs(string("0101010"))` - if length is longer, the zeros are *prepended* ## deque - change on *both* ends of the list - `push_{front|back}` and `pop_{front|back}` - comparison to `vector`: `push_front` and `pop_front` not supported ## stack - `push`, `top` and `pop` ## queue - `push`, `front` and `pop` ## `priority_queue` - `push`, `top` and `pop` - sorted from largset to smallest by default - `priority_queue<int> q;` - `priority_queue<int,vector<int>,greater<int>> q;`: from smallest to greatest # complete search ## generating subset - method 1: review of recursive method - method 2: each subset can be represented by a bitset of size `n` - so we iterate through an int varaible `b` from `0` to `(1<<n) - 1` (for example, if `n=3`, then `b` is from `000` to `111` - to check if the `i`th bit is active, use `(1<<i) & b` (neat!) ## permutation - method 1: recursive - selecting the `i`the number a the starting code and recurse on the rest of the sequence - method 2: `next_permutation` ## backtracking a technique featured by: - *incrementally* build a solution - abandons a partial solution if not feasible ("backtrack" means "go back") "queen" problem: solved by recursive approach - a novel way to store which position is possible/impossible - cells in the same column share the same column index - cells in the same left diagonal share the same `x+y` value - similar results for cells in the right diagonal - kinda of "common features" for linked cells - the storage is **linear** instead of quadratic (wow!) # pruning - 2d vector, example: `vector<vector<bool>> m(d, vector<bool>(d, false))` - [print stacktrace](https://stackoverflow.com/questions/18706496/can-one-use-libsegfault-so-to-get-backtraces-for-sigabrt) or [this for C](https://stackoverflow.com/questions/77005/how-to-generate-a-stacktrace-when-my-gcc-c-app-crashes) - tool gdb: `run` and `where` to print stacktrace - one cause for *segmentatio fault*: recursion does not terminate # dynamic programming - use `min/max` function to update - problem: path in a grid, initial state for first row and column - initialize 2d vectors with values: `vector<vector<int>> m {{...}, ..., {...}} - running time of dp for knapsack: `O(nW)` or `O(nS)` - `W` capacity - `S` sum of values of all items - [pseudo-polynomial](https://en.wikipedia.org/wiki/Pseudo-polynomial_time): running time in the *numeric value* of the input (not size) ## string edit distance dynamic programing table index 0 and array index 0 -- different meaning - table index 0: empty string - array index 0: the first character - use `min({num1, ..., numk})` for a list of numbers - `(expr1 opr expr2 ? val1 : val2))` ## count tilings - `string.find` and `string::npos` - `s.find(ss) == string::npos`: `ss` NOT in `s` - `string.substr` vs `string.operator[]`: return `string` and `char` - `utility.h` gives `std::pair` - generating valid cartesian product (with constraints) ## learned from leetcode - sometimes, space complexity can be `O(1)`, for example: - [maximum profit](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/) and [climb stairs](https://leetcode.com/problems/climbing-stairs/description/) ## range sum query [problem statement](https://leetcode.com/problems/range-sum-query-immutable/description/) # cpp class constructor function: private: type1 prop1; type2 prop2; ClassName(type1 param1, type1 param2): prop1(param1), prop2(param2){ .... } note: - initialization using parameter list - order should obey the declaration order, `prop1` before `prop2` # graph ## graph traversal review of `queue` and `stack`: - same: `push`, `pop` - diff: `queue.front`, `stack.pop` ## when setting `z[i]=true` when push `i`, set it to `true`, otherwise, it can be visited multiple times. example: a triangle graph for dfs. ## cycle detection `std:tie(i, j) = some pair`: unpack the value in pair `tie` defined in `tuple`
评论
    相关推荐
    • leetcode c++ 分类高清版 有答案
      leetcode c++ 分类高清版 有答案 leetcode c++ 分类高清版 有答案 leetcode c++ 分类高清版 有答案 leetcode c++ 分类高清版 有答案leetcode c++ 分类高清版 有答案
    • leetcode2sumc-LeetCode:C++11中的LeetCode解决方案
      C++ 11 中的 LeetCode 解决方案。 不。 标题 解决方案 困难 1 简单的 2 中等的 4 难的 5 中等的 20 简单的 21 简单的 35 简单的 43 中等的 53 简单的 63 中等的 64 中等的 92 简单的 121 简单的 129 中等的 144 简单...
    • leetcode本地c++11开发组件
      方便本地开发测试,专注于实现提交函数,初版完善有限见量
    • leetcode答案-leetcode:leetcode-c++answers
      leetcode 答案leetcode leetcode-c++answers leetcode 的答案....更新中
    • leetcode-leetcode:leetcode的最佳C++解决方案
      C++ solutions for the leetcode 这是我自己写的leetcode的题解,目前已经完成了70%左右,后续部分会很快更新 这里放上来的代码都能保证是最优解(复杂度最优) 当然有些题目因为测试数据等原因可能会和统计中最快的...
    • leetcode:leetcodeC++代码
      leetcode 使用C++解决leetcode问题, //oj.leetcode.com/ 简单的介绍 编译标准 ISO C++11
    • leetcode代码200题c++
      leetcode代码200题,语言c++。用了一个月做了下leetode。都是AC代码。
    • LeetCode C++全解
      1. Introduction 2. Array i. Remove Element ii. Remove Duplicates from Sorted Array iii. Plus One iv. Pascal's Triangle v. Merge Sorted Array vi. Sum vii. Find Minimum in ...viii....ix....x....xi....xii....xiii....xiv....
    • leetcodepushfront-leetcode:C++中的leetcode
      C++中的leetcode 重要:15, 74, 105, 200, 236, 39 & 40 & 46, 43, 55, 81, 90, 96, 131 重做:31、33 binary_search 变种:旋转,重复 cp: // string string strNew = str + 'c' string strNew = str + "car" ...