这个帖子sequence /39870/留着以后写
这样写的时候就是几十天之后的沉贴,太机智了, 偷偷

15日前不更新这一篇了，就发在题解好了，避免太长

Explore Card大作战： Version: 0.8August全勤Challenge
$1.$ Detect Capital #LC.520

return word[1:]==word[1:].lower() or word==word.upper() #python

bool detectCapitalUse(string word) { //bool返回(即判断)True/False #c++
    for(int i = 1; i < word.size(); i++){
        if(isupper(word[1]) != isupper(word[i]) || 
           islower(word[0]) && isupper(word[i])) return false;
    }        
    return true;
}

$2.$ Design HashSet #LC.705

• add(value): Insert a value into the HashSet.
• contains(value) : Return whether the value exists in the HashSet or not.
• remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Solution

class MyHashSet:

    def __init__(self):
        self.arr = [None] * 8
        self.capacity = 8
        self.size = 0
        self.thres = 2 / 3

    def hash(self, key): return key % self.capacity

    def rehash(self, key): return (5 * key + 1) % self.capacity

    def insertPos(self, key):
        pos = self.hash(key)
        #using -1 to represent the "removed" item
        while self.arr[pos] is not None:
            if self.arr[pos] == key: return -1
            #here is the small bug, the following item may contain the key
            if self.arr[pos] == -1: break
            pos = self.rehash(pos)
        return pos

    def safeAdd(self, key):
        pos = self.insertPos(key)
        #already in, 
        if pos == -1: return 
        self.arr[pos] = key
        self.size += 1

    def safeAddArr(self, arr):
        for val in arr: 
            if val is not None: self.safeAdd(val)

    def add(self, key: int) -> None:
        def preAdd(self):
            if self.size / self.capacity <= self.thres: return 
            self.capacity <<= 1
            oldArr, self.arr = copy.deepcopy(self.arr), [None] * self.capacity
            self.safeAddArr(oldArr)

        preAdd(self)
        #fix the small bug by precheck before add
        if self.contains(key): return
        self.safeAdd(key)

    def remove(self, key: int) -> None:
        pos = self.hash(key)
        while self.arr[pos] is not None:
            if self.arr[pos] == key: 
                #you cannot assign None, because you will lose track of continuous items
                self.arr[pos] = -1
                self.size -= 1
                return
            pos = self.rehash(pos)
        return

    def contains(self, key: int) -> bool:
        pos = self.hash(key)
        while self.arr[pos] is not None:
            if self.arr[pos] == key: return True
            pos = self.rehash(pos)
        return False
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)

$3.$ LC114. 二叉树展开为链表
给定一个二叉树，原地将它展开为一个单链表。#注:要记得把左子树置空 (避免环)

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if(root == None): return
        self.flatten(root.left)
        self.flatten(root.right)
        tmp = root.right
        root.right = root.left
        root.left = None
        while(root.right != None): root = root.right
        root.right = tmp

注释#先把左右子树捋直 (可删)
        self.flatten(root.left)
        self.flatten(root.right)
        tmp = root.right #把捋直的右子树备份一下
        root.right = root.left #把捋直的左子树放到右边
        root.left = None #记得把左子树置空
        while(root.right): #找到现在右子树的最后一个node
            root = root.right
        root.right = tmp #把捋直的原来的右子树接上去

c++版一样 都是递归，不过self不需要 直接flatten(root.left).. etc.

$4. $Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Input: "A man, a plan, a canal: Panama" Output: true
c++Solution

class Solution {
public:
    bool isPalindrome(string s) {
    for (int i = 0, j = s.size() - 1; i < j; i++, j--) { // Move 2 pointers from each end until they collide
        while (isalnum(s[i]) == false && i < j) i++; // Increment left pointer if not alphanumeric
        while (isalnum(s[j]) == false && i < j) j--; // Decrement right pointer if no alphanumeric
        if (toupper(s[i]) != toupper(s[j])) return false; // Exit and return error if not match
    }

    return true;
}
};

$6.$ LC.442.Find All Duplicates in an Array
Rearragnge number重排列 O(n) time/O(1) space

class Solution(object):
    def findDuplicates(self, nums):
        for i in range(len(nums)):
            while i != nums[i] - 1 and nums[i] != nums[nums[i]-1]:
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]

        return [nums[it] for it in range(len(nums)) if it != nums[it] - 1]

1. Iterator for Combination 字母组合迭代器 迭代排列组合
   位运算 Bit manipulation

set<string>GenaretallComb(string s,int len){
    int mask = 1<<s.length();
    set<string>hold;
    string comString = "";
    for(int no=1;no<mask;no++){
        int num = no,i = 0;
        while(num){
            if(num&1)comString = comString + s[i];
            i++,num>>=1;
        }
        if(comString.length()==len)hold.insert(comString);
        comString = "";
    }
    return hold;
}

class CombinationIterator {
public:
    set<string>st;
    set <string> :: iterator cur;
    CombinationIterator(string characters, int combinationLength) {
        this->st = GenaretallComb(characters,combinationLength);
        this->cur = begin(st);
    }

    string next() {
        return !(cur==end(st))?*cur++:"";
    }

    bool hasNext() {
        return !(cur==end(st));
    }
};

python版

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.characters = characters
        self.n = len(characters)
        self.combinations = gen_combinations(self.n, combinationLength)
        self.ind = len(self.combinations) - 1

    def next(self) -> str:
        s = ""
        for i in range(self.n):
            if self.combinations[self.ind][i] != "0":
                s += self.characters[i]
        self.ind -= 1
        return s

    def hasNext(self) -> bool:
        return self.ind > -1 

def gen_combinations(l, n):
    end = int("1" * l, 2)
    ans = []
    for i in range(end + 1):
        b = bin(i)[2:]
        if b.count('1') == n:
            ans.append(b.zfill(l))
    return ans

$17.$ 买卖股票的最佳时机 III
【$\color{#66ccff}{记忆化}$递归】
-挺万能的方法。具体可根据递归代码来理解变化过程

class Solution:
    def maxProfit(self, prices):
        n = len(prices)
        if n < 2:
            return 0
        dp1 = [0 for _ in range(n)]
        dp2 = [0 for _ in range(n)]
        minval = prices[0]
        maxval = prices[-1]
        #前向   
        for i in range(1,n):
            dp1[i] = max(dp1[i-1], prices[i] - minval)
            minval = min(minval, prices[i])
        #后向    
        for i in range(n-2,-1,-1):
            dp2[i] = max(dp2[i+1], maxval - prices[i])
            maxval = max(maxval, prices[i])

        dp = [dp1[i] + dp2[i] for i in range(n)]
        return max(dp)

c++版递归

TLE

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        return f(prices, 0, 0, 0);
    }

    /**
     *
     * @param prices
     * @param i 当前考虑第几天
     * @param hasStock 是否有股票在手
     * @param counts 已经交易的次数（每买一次股票就加一）
     * @return
     */
private:
    int f(vector<int>& prices, int i, int hasStock, int counts) {
        // 如果已经买了两次股票，并且手里已经没有股票了，那么后面的天数不需要考虑
        if(i >= prices.size() || (counts >= 2 && hasStock < 1))
            return 0;
        // 如果手里有股票，我可以选择卖或者不卖
        if(hasStock > 0)
            return  max(prices[i] + f(prices, i+1, 0, counts), f(prices, i+1, 1, counts));
        // 如果没有股票，我可以选择买或者不买
        return max(-prices[i] + f(prices, i+1, 1, counts+1), f(prices, i+1, 0, counts));
    }   
};

自己修改的c++版 52 ms 5.89%

class Solution {
public: int maxProfit(vector<int> prices) {
        int m = prices.size();
        vector<vector<vector<int>>> dp(m+1, vector<vector<int>>(2+1, vector<int>(2,0)));
        dp[0][2][1] = dp[0][1][1] = -1e8;
        dp[0][2][1] = dp[0][1][1] = -1e8;
        for(int i = 1; i<=m; i++)
            for(int k=1; k<=2; k++){  //表示用了k次交易
                dp[i][k][0] = max(dp[i-1][k][1] + prices[i-1], dp[i-1][k][0]);
                dp[i][k][1] = max(dp[i-1][k-1][0] - prices[i-1], dp[i-1][k][1]);
            }
        return max(dp[m][1][0], dp[m][2][0]);
    }
};

java版

public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0) return 0;
        int k = 2;
        int[][][] dp = new int[len][k+1][2];

        for(int i = 0; i < len; i ++){
            for(int j = k; j > 0; j --){
                if (i == 0){
                    //第i天，还有j次，手里没有股票，当i=0，手里没股票，最大利润为0
                    dp[i][j][0] = 0;
                    //当i=0，手里有股票，因为还没有盈利，最大利润为 负prices[i]
                    dp[i][j][1] = -prices[i];
                    continue;
                }
                //今天手里没股票，比较MAX（前一天可能没股票，前一天有股票但是今天卖出去了，卖出去就有利润，所以+ prices[i]）
                dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                //今天手里有股票，比较MAX（前一天可能有股票，前一天没股票但是今天买了，买了就有成本，所以- prices[i]）
                dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
            }
        }
        return dp[len-1][k][0];
    }