算法学习——LeetCode力扣补充篇14
179. 最大数
描述
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例
示例 1：
输入：nums = [10,2]
输出：“210”
示例 2：
输入：nums = [3,30,34,5,9]
输出：“9534330”
提示
1 <= nums.length <= 100
0 <= nums[i] <= 109
代码解析
class Solution {
public:
static bool cmp( string &s1 , string &s2 )
{
string tmp1 , tmp2;
tmp1 = s1 + s2;
tmp2 = s2 + s1;
return tmp1 > tmp2;
}
string largestNumber(vector<int>& nums) {
vector<string> tmpStr;
string result;
for(int i=0 ; i<nums.size() ; i++)
{
string tmp = to_string(nums[i]);
tmpStr.push_back(tmp);
}
sort(tmpStr.begin() , tmpStr.end() , cmp);
for(int i=0 ; i<tmpStr.size() ; i++)
{
result += tmpStr[i];
}
if(result[0] == '0') return "0";
return result;
}
};
43. 字符串相乘
描述
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例
示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”
示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”
提示
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。
代码解析
class Solution {
public:
string multiply(string num1, string num2) {
if(num1 == "0" || num2 == "0") return "0";
vector<vector<int>> tmp_nums;
vector<int> path;
int add = 0, num_0 = 0 , cur_num = 0;
int max_bit = 0;
for(int i=num1.size()-1 ; i>=0 ; i--)
{
path.clear();
add = 0;
num_0 = num1.size()-1 - i;
while(num_0--) path.push_back(0);
for(int j=num2.size()-1 ; j>=0 ; j--)
{
cur_num = (num1[i] - '0') * (num2[j] - '0') + add;
path.push_back(cur_num %10);
add = cur_num/10;
}
if(add != 0 ) path.push_back(add);
if(path.size() > max_bit) max_bit = path.size();
tmp_nums.push_back(path);
}
string result;
add = 0;
for(int i=0 ; i<max_bit ; i++)
{
cur_num = 0;
for(int j=0 ; j<tmp_nums.size();j++)
{
if(tmp_nums[j].size() > i)
{
cur_num += tmp_nums[j][i];
}
}
cur_num += add;
result += (cur_num )%10 + '0';
add = (cur_num )/10;
}
if(add != 0) result += add + '0';
reverse(result.begin() , result.end());
return result;
}
};
32. 最长有效括号
描述
给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号
子串
的长度。
示例
示例 1：
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：
输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：
输入：s = “”
输出：0
提示
0 <= s.length <= 3 * 104
s[i] 为 ‘(’ 或 ‘)’
代码解析
class Solution {
public:
int longestValidParentheses(string s)
{
int maxans = 0;
stack<int> stk;
stk.push(-1); //栈底最后一个没有被匹配的右括号的下标
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '(')
{
stk.push(i);
}
else if (s[i] == ')')
{
stk.pop();
if (stk.empty()) stk.push(i);
else maxans = max(maxans, i - stk.top());
}
}
return maxans;
}
};
543. 二叉树的直径
描述
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
输入：root = [1,2]
输出：1
提示
树中节点数目在范围 [1, 104] 内
-100 <= Node.val <= 100
代码解析
/**
* 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:
int result = 0;
int track_back(TreeNode* cur )
{
if(cur == nullptr) return 0;
int left_hight = track_back(cur->left) ;
int right_hight = track_back(cur->right) ;
result = max(result , left_hight + right_hight + 1);
return max(left_hight , right_hight ) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
track_back(root);
return result-1 ;
}
};
113. 路径总和 II
描述
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
提示
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
代码解析
/**
* 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<vector<int>> result;
vector<int> path;
int sum = 0;
void track_back(TreeNode* cur , int &targetSum)
{
if(cur == nullptr) return;
path.push_back(cur->val);
sum += cur->val;
if( sum == targetSum && cur->left == nullptr && cur->right == nullptr)
{
result.push_back(path);
}
track_back(cur->left , targetSum);
track_back(cur->right , targetSum);
sum -= cur->val;
path.pop_back();
return;
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum)
{
track_back(root,targetSum);
return result;
}
};
