Jackson.tmm

LeetCode 948 - Bag of Tokens

You have an initial power of power, an initial score of 0, and a bag of tokens where tokens[i] is the value of the i^th token (0-indexed).

Your goal is to maximize your total score by potentially playing each token in one of two ways:

• If your current power is at least tokens[i], you may play the i^th token face up, losing tokens[i]power and gaining 1a score.
• If your current score is at least 1, you may play the i^th token face down, gaining tokens[i] power and losing 1 score. Each token may be played at most once and in any order. You do not have to play all the tokens.

Return the largest possible score you can achieve after playing any number of tokens.

LeetCode 1996 - The Number of Weak Characters in the Game

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the i^th character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character’s attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attack_j attack_i and defense_j > defense_i.

LeetCode 94 - Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

example

Input: root = [1,null,2,3]
Output: [1,3,2]

Input: root = []
Output: []

Input: root = [1]
Output: [1]

How can we solve this problem?

這題很簡單,只要使用中序遍歷即可。

Solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> res;
        inorder(root,res);
        return res;
    }
    
    void inorder(TreeNode* root,vector<int>& res){
        if(!root) return;
        
        inorder(root->left,res);
        res.emplace_back(root->val);
        inorder(root->right,res);
    }
};

LeetCode 606 - Construct String from Binary Tree

Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.

Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree. example

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)"

Input: root = [1,2,3,null,4]
Output: "1(2()(4))(3)"
Explanation: Almost the same as the first example, except we cannot omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output

How can we solve this problem?

這題就是要讓我們講以string的方式輸出Binary Tree。只要注意他的規則就可以解決這題。

LeetCode 442 - Find All Duplicates in an Array

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space. example

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Input: nums = [1]
Output: []

How can we solve this problem?

這題要我們找出所有在Array裡重複出現2次的數字。解法也很簡單, 因為題目也說了數字會出現1次或者2次,哪我們可以透過Map來計數,但當前數字已經出現過1次,也就代表當前數字是重複了2次,加入到結果即可。

LeetCode 2196 - Create Binary Tree From Descriptions

You are given a 2D integer array descriptions where descriptions[i] = [parenti, childi, isLefti] indicates that parenti is the parent of childi in a binary tree of unique values. Furthermore,

• If isLefti == 1, then child_i is the left child of parent_i.
• If isLefti == 0, then child_i is the right child of parent_i. Construct the binary tree described by descriptions and return its root.

The test cases will be generated such that the binary tree is valid. example

LeetCode 814 - Binary Tree Pruning

Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node node is node plus every node that is a descendant of node.

example

Input: root = [1,null,0,0,1]
Output: [1,null,0,null,1]
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Input: root = [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

How can we solve this problem?

這題是要讓我們移除所有不包含1的sub-tree。所以，我們只要透過DFS判斷一下node的left-sub tree 以及 right-sub tree 是否都不包含1: 1. 如果左右子樹都不包含1且當前node為0, 直接返回nullptr 2. 若當前節點為1就返回自身 2. 左子樹不包含1, 當前node的左子樹設成nullptr;同理右子樹不包含1,當前node 的右子數設為nullptr

LeetCode 92 - Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

example

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Input: head = [5], left = 1, right = 1
Output: [5]

How can we solve this problem?

這一題的問題非常的簡單,就是要讓我們在給定的一個list中翻轉(Reverse)[left,right]之間的Node,並返回結果。這題跟Reverse Linked List I解法類似,不同的是多了個翻轉範圍。
首先，我們要做的是在的翻轉的開始的位置。然後再透過recursive來翻轉List,最後返回的node/head再由left位置的Node的前一個Node接起來(如有)就可以了~

這題主要是學習DP思想，做個小記錄

LeetCode 629 - K Inverse Pairs Array

For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].

Given two integersn and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.

LeetCode 338 - Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

example:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

How can we solve this problem?

這題要我們解決的問題是給定一個數字n,回傳0 - n中每個數字包含了多少個為1的bits。例如: n=2 => 00,01,10,回傳的結果便會是[0,1,1]。