581. 最短無(wú)序連續(xù)子數(shù)組

我也是很疑惑為什么有那么多做法，自己一個(gè)也沒(méi)想起來(lái)

題解思路1

使用sort，第一個(gè)和原數(shù)組不一樣的元素的下標(biāo)為左值，最后一個(gè)為右值。

vector<int> vec(nums);
sort(vec.begin(), vec.end());
int left = nums.size() - 1, right = 0;
for (int i = 0; i < nums.size(); ++i) {
    if (nums[i] != vec[i]) {
        left = min(left, i);
        right = max(right, i);
    }
}
return right - left > 0 ? right - left + 1 : 0;

需要注意的地方。vector的拷貝均為深拷貝,重載了=運(yùn)算符

題解思路2 :超時(shí)

在邊界[i, j]中,如果存在有數(shù)比nums[i]小,則left = i,如果有數(shù)比nums[j]大,則right = j;
n^2遍歷

for (int i = 0; i < nums.size(); ++i) {    
    for (int j = i + 1; j < nums.size(); ++j)        
        //如果只是找左邊界，碰到第一個(gè)num[j] < nums[i],left賦值之后就可以return了
        if (nums[j] < nums[i]) {
            left = min(left, i);
            right = max(right, j);
        }
}

我的思路

按照上面的思路我把左右分開(kāi),沒(méi)有超時(shí)(也接近超時(shí)了)

for (int i = 0; i < nums.size() && flag; ++i) {    
    for (int j = i + 1; j < nums.size(); ++j)        
        //如果只是找左邊界，碰到第一個(gè)num[j] < nums[i],left賦值之后就可以return了
        if (nums[j] < nums[i]) {
            left = min(left, i);
            flag = false;
            break;
        }
}

flag = true;
for (int i = nums.size() - 1; i >= 0 && flag; --i) {    
    for (int j = i - 1; j >= 0; --j)        
        if (nums[j] > nums[i]) {
            right = max(right, i);
            flag = false;
            break;
        }
}

題解思路3

再延伸一下上面的思路,找到逆序?qū)χ凶钚〉闹岛妥畲蟮闹?從左往右第一個(gè)大于min的下標(biāo)為left,從右往左第一個(gè)大于max的下標(biāo)為right

int left = nums.size() - 1, right = 0;
if (nums.size() <= 1)   return 0;
int maxnum = INT_MIN, minnum = INT_MAX;
for (int i = 1; i < nums.size(); ++i) {            
    if (nums[i - 1] > nums[i]) {
        minnum = min(minnum, nums[i]);
        maxnum = max(maxnum, nums[i - 1]);
    }
}

for (left = 0; left < nums.size(); ++left) {
    if (nums[left] > minnum)  break;
}

for (right = nums.size() - 1; right >= 0; --right) {
    if (nums[right] < maxnum) break;
}

return left > right ? 0 : right - left + 1;

617. 合并二叉樹(shù)

題解思路

盡量少對(duì)下一層做判斷，我在root1left連接到root2的left上后，對(duì)root2 -> left的釋放上糾結(jié)了很長(zhǎng)時(shí)間
因?yàn)槭堑降自倩厮莸?所以不用釋放對(duì)后面也沒(méi)有影響,就是這個(gè)節(jié)點(diǎn)會(huì)同時(shí)被root1和root2所指.還是新開(kāi)一個(gè)root吧

if (!root2 && !root1)   return nullptr;
if (!root1) return root2;
if (!root2) return root1;

// TreeNode* root = new TreeNode(root1 -> val + root2 -> val);
root1 -> val += root2 -> val;
root1 -> left = mergeTrees(root1 -> left, root2 -> left);
root1 -> right = mergeTrees(root1 -> right, root2 -> right);
return root1;

621. 任務(wù)調(diào)度器

題解思路

先把最長(zhǎng)的排好，取左邊這種情況和右邊這種情況的最大值

vector<int> chcnt(26, 0);
int maxchcnt = 0;
for (char c : tasks) {
    chcnt[c - 'A'] += 1;
    maxchcnt = max(maxchcnt, chcnt[c - 'A']);
}


int maxcount = 0;
for (int t : chcnt) {
    if (t == maxchcnt) {
        maxcount++;
    }
}

int size = tasks.size();
return max((n + 1) * (maxchcnt - 1) + maxcount, size);

647. 回文子串

題解思路

我不知道怎么處理回文串的中心位置，思路應(yīng)該是確定一個(gè)中心位置，像兩邊擴(kuò)散如果字符相等，ans++

int len = s.size();
int ans = 0;
for (int i = 0; i < len * 2 - 1; ++i) {
    int left = i / 2, right = i / 2 + i % 2;
    while (left >= 0 && right <= len - 1 && s[left] == s[right]) {
        left--;
        right++;
        ans++;
    }
}
return ans;

739. 每日溫度

我的思路

逆序單調(diào)棧，沒(méi)什么毛病的bug-free

stack<int> st;
vector<int> ans(T.size(), 0);
for (int i = T.size() - 1; i >= 0; --i) {
    while (!st.empty() && T[i] >= T[st.top()]) {
        st.pop();
    }
    if (st.empty()) {
        ans[i] = 0;                
    }
    else {
        ans[i] = st.top() - i;
    }
    st.push(i);
}
return ans;

題解思路

順序單調(diào)棧

stack<int> st;
vector<int> ans(T.size(), 0);        
for (int i = 0; i < T.size(); ++i) {
    while (!st.empty() && T[i] > T[st.top()]) {
        ans[st.top()] = i - st.top();
        st.pop();
    }
    st.push(i);
}
return ans;