Skip to content

Instantly share code, notes, and snippets.

View yangpeng-chn's full-sized avatar

Peng Yang yangpeng-chn

  • SmartNews
  • Tokyo, Japan
View GitHub Profile
int longestSubstringKDistinct(string str, int k){
int start = 0, res = 0;
unordered_map<char, int> um;
for (int i = 0; i < str.size(); ++i)
{
um[str[i]]++;
while(um.size() > k){
char left = str[start];
if(--um[left] == 0)
um.erase(left);
@yangpeng-chn
yangpeng-chn / sortedSquares.cpp
Created June 14, 2019 15:12
Two Pointers or Iterators
vector<int> sortedSquares(vector<int>& A) {
vector<int> res(A.size());
int left = 0, right = 0;
/*for(int i = 0; i < A.size(); i++){
if(A[i] < 0){
}
if(A[i] >= 0){
right = i; //
@yangpeng-chn
yangpeng-chn / threeSum.cpp
Last active June 28, 2019 15:35
Two Pointers or Iterators
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
if(nums.size() < 3) return res;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size()-2; i++){
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i+1;
int r = nums.size()-1;
int val = -nums[i];
while(l < r){
@yangpeng-chn
yangpeng-chn / hasCycle.cpp
Last active June 29, 2019 16:12
Fast and Slow pointers
// start with different position
bool hasCycle(ListNode *head) {
if(!head) return false;
ListNode *slow = head;
ListNode *fast = head->next;
while(fast && fast->next){
if(slow == fast) return true;
slow = slow->next;
fast = fast->next->next;
}
vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<vector<int>> res{intervals[0]};
for (int i = 1; i < intervals.size(); ++i) {
if (res.back()[1] < intervals[i][0]) { //doesn't overlap, push current interval
res.push_back(intervals[i]);
} else {
res.back()[1] = max(res.back()[1], intervals[i][1]); //overlap, update end
}
@yangpeng-chn
yangpeng-chn / reverseList.cpp
Last active July 4, 2019 17:58
In-place reversal of linked list
// iteration
ListNode* reverseList(ListNode* head) {
ListNode *pre = nullptr;
ListNode *cur = head;
while(cur){
ListNode *tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
// Iteration
vector<vector<int> > levelOrderBottom(TreeNode* root) {
if (!root) return {};
vector<vector<int>> res;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
vector<int> oneLevel;
for (int i = q.size(); i > 0; --i) { //init i with q.size(), it runs well even if we change the size of q in loop
TreeNode *t = q.front();
q.pop();
// Iteration
bool hasPathSum(TreeNode* root, int sum) {
if(!root) return false;
stack<TreeNode*>s{{root}};
while(!s.empty()){
TreeNode* tmp = s.top();
s.pop();
if(!tmp->left && !tmp->right && tmp->val == sum)
return true;
if(tmp->left){
void helper(TreeNode* root, vector<vector<int>> &res, vector<int>&vec, int sum){
if(!root)return;
vec.push_back(root->val);
if(!root->left && !root->right && root->val==sum)
res.push_back(vec);
helper(root->left, res, vec, sum-root->val);
helper(root->right, res, vec, sum-root->val);
vec.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
@yangpeng-chn
yangpeng-chn / subsets.cpp
Last active December 9, 2019 16:08
Subsets
// Iteration
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> vv;
vv.push_back(vector<int>());
for(int i = 0; i < nums.size(); i++){
int n = vv.size();
for(int j = 0; j < n; j++){
vector<int> v(vv[j]);
v.push_back(nums[i]);
vv.push_back(v);