Jackson.tmm

LeetCode 1770 - Maximum Score from Performing Multiplication Operations

You are given two integer arrays nums and multipliers of size n and m respectively, where n >= m. The arrays are 1-indexed.

You begin with a score of 0. You want to perform exactly m operations. On the ith operation (1-indexed), you will:

• Choose one integer x from either the start or the end of the array nums.
• Add multipliers[i] * x` to your score.
• Remove x from the array nums. Return the maximum score after performing m operations. example

1
2
3
4
5
6
7

Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14
Explanation: An optimal solution is as follows:
- Choose from the end, [1,2,3], adding 3 * 3 = 9 to the score.
- Choose from the end, [1,2], adding 2 * 2 = 4 to the score.
- Choose from the end, [1], adding 1 * 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.

1
2
3
4
5
6
7
8
9

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102
Explanation: An optimal solution is as follows:
- Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
- Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
- Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
- Choose from the end, [-2,7,1], adding 1 * 4 = 4 to the score.
- Choose from the end, [-2,7], adding 7 * 6 = 42 to the score. 
The total score is 50 + 15 - 9 + 4 + 42 = 102.

How can we solve this problem?

這題最主要的重點是對於每個multipliers[i],它只能挑選最左邊或者最右邊的值。所有，我們需要知道multipliers[i]拿最左邊的值最後的結果比較大，還是拿最右邊後的結果比較大。為了避免重複計算而超時，所以我們需要使用dp來幫助我們記錄當前最優解。注:因multipliers最多為m個，所有最多只能從nums拿m個數字

LeetCode 969 - Pancake Sorting

Given an array of integers arr, sort the array by performing a series of pancake flips.

In one pancake flip we do the following steps:

• Choose an integer k where 1 <= k <= arr.length.
• Reverse the sub-array arr[0...k-1] (0-indexed). For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3.

Return an array of the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct. example

LeetCode 2007 - Find Original Array From Doubled Array

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order. example

LeetCode 1457 - Pseudo-Palindromic Paths in a Binary Tree

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes. example

1
2
3

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

1
2
3

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

1
2

Input: root = [9]
Output: 1

How can we solve this problem?

這一題簡單的來說就是讓我們從Binary Tree中找到有幾條path是一個Palindromic(Pseudo-Palindromic)偽迴文串。 也就是說從root到leaft的path是一個Palindromic。 (我們只需要知道path是否能組成Palindromic即可)

LeetCode 393 - UTF-8 Validation

Given an integer array data representing the data, return whether it is a valid UTF-8 encoding (i.e. it translates to a sequence of valid UTF-8 encoded characters).

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

1. For a 1-byte character, the first bit is a 0, followed by its Unicode code.
2. For an n-bytes character, the first n bits are all one’s, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

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

1
2

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

1
2

Input: root = []
Output: []

1
2

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

How can we solve this problem?

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

Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * 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

1
2
3

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)"

1
2
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

1
2

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

1
2

Input: nums = [1]
Output: []

How can we solve this problem?

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