判断题库

// bananas: 香蕉的甜度
void findSelectedBananas(vector<int>& bananas, vector<int>& dp) {
    vector<int> selected;
    int i = bananas.size() - 1;
 
    while (i >= 0) {
        if (i == 0) {
            selected.push_back(0);
            break;
        }
 
        if (dp[i] == dp[i-1]) {
            i--;
        } else {
            selected.push_back(i);
            i -= 2;
        }
    }
 
    reverse(selected.begin(), selected.end());
    cout << "小猴子吃了第: ";
    for (int idx : selected)
        cout << idx+1 << " ";
    cout << "个香蕉" << endl;
}
 
int main() {
    vector<int> bananas = {1, 2, 3, 1}; // 每个香蕉的甜
    vector<int> dp(bananas.size());
    dp[0] = bananas[0];
    dp[1] = max(bananas[0], bananas[1]);
    for (int i = 2; i < bananas.size(); i++) {
        dp[i] = max(bananas[i] + dp[i-2], dp[i-1]);
    }
    findSelectedBananas(bananas, dp);
    return 0;
}

int fib_dp(int n) {
    if (n <= 1) return n;
    vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

TreeNode* searchBST(TreeNode* root, int val) {
    while (root && root->val != val) {
        root = (val < root->val) ? root->left : root->right;
    }
    return root;
}

//       1
//      / \
//     2   3
//    / \   \
//   4   5   6
 
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
void inorderIterative(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* curr = root;
 
    while (curr || !st.empty()) {
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top(); st.pop();
        cout << curr->val << " ";
        curr = curr->right;
    }
}