code | 嗷嗚

卡特蘭數 & LEETCODE Unique Binary Search Trees

發佈日期: 10 月 13, 201910 月 13, 2019 作者: user

先來看下題目

https://leetcode.com/problems/unique-binary-search-trees/

閱讀全文 “卡特蘭數 & LEETCODE Unique Binary Search Trees” →

[LEETCODE] Longest Substring Without Repeating Characters

發佈日期: 7 月 9, 20197 月 9, 2019 作者: user

https://leetcode.com/problems/longest-substring-without-repeating-characters/

第一版

class Solution {
public:
    string cs;
    
    int lengthOfLongestSubstring(string s) {
        int l = s.length();
        int ans = 0;
        
        cs = s;
        
        for (int i = 0; i < l; i++) {
           ans = max(ans, checkNonDoublealphabets(i-ans,i));
        }       
        
        return ans;
    }
    
    int checkNonDoublealphabets(int s, int e)
    {        
        bool alphabets[256] = {false};        

        
        for (int i = s; i <= e; i++) {
            if(alphabets[static_cast<int>(cs[i])] == true)
                return 0;
            alphabets[static_cast<int>(cs[i])] = true;
        }
        return e-s+1;
    }
};

class Solution {

public:

string cs;

int lengthOfLongestSubstring(string s) {

int l = s.length();

int ans = 0;

cs = s;

for (int i = 0; i < l; i++) {

ans = max(ans, checkNonDoublealphabets(i-ans,i));

}

return ans;

}

int checkNonDoublealphabets(int s, int e)

{

bool alphabets[256] = {false};

for (int i = s; i <= e; i++) {

if(alphabets[static_cast<int>(cs[i])] == true)

return 0;

alphabets[static_cast<int>(cs[i])] = true;

}

return e-s+1;

}

};

先做了一版slide window, length = ans, 每次都往前檢查 window內是不是有重複的字元

有的話就退出，沒有的話就把新的字元吃進來=>長度加一

大概只有50%的ranking…

閱讀全文 “[LEETCODE] Longest Substring Without Repeating Characters” →

[LeetCode] 153. Find Minimum in Rotated Sorted Array

發佈日期: 4 月 5, 20194 月 5, 2019 作者: user

這題前幾年同學去面試Synology的時候有被問到類似

（rotated之後找特定數字）

難易度差不多吧，就是變形的binary search

閱讀全文 “[LeetCode] 153. Find Minimum in Rotated Sorted Array” →

[LeetCode] 155. Min Stack

發佈日期: 4 月 5, 20194 月 5, 2019 作者: user

幾百年沒有更新Blog了

前幾天看到這題就順手寫了一下

用兩個stack的作法好像還蠻簡單的

但只用一個stack做就蠻炫的，discussion上有靠diff的方式只花了一個stack

簡單來說大概就是在遇到更小data push的時候更新min

pop掉的時候在用diff回到先前的 min

class MinStack {
public:
    /** initialize your data structure here. */
    long min;
    stack<long> my_stack;
    
    MinStack() {
    
    }
    
    void push(int x) {
        if(this->my_stack.empty()) {
            min = x;
            my_stack.push(0);
        }
        else
        {
            my_stack.push(x-min);
            if(x<min) min = x;
        }
    }
    
    void pop() {
        if(this->my_stack.top() < 0)
            this->min -= this->my_stack.top();
        this->my_stack.pop();
    }
    
    int top() {
        if(this->my_stack.top() > 0)
            return this->my_stack.top() + this->min;
        else
            return this->min;
    }
    
    int getMin() {
        return this->min;
    }
};