1.Move Zeroes 移动零
Given an array nums
, write a function to move all 0
's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12]
, after calling your function, nums
should be [1, 3, 12, 0, 0]
.
Note:
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int k = 0; // nums中, [0...k)的元素均为非0元素
// 遍历到第i个元素后,保证[0...i]中所有非0元素
// 都按照顺序排列在[0...k)中
for(int i = 0 ; i < nums.size() ; i ++)
if(nums[i])
nums[k++] = nums[i];
// 将nums剩余的位置放置为0
for(int i = k ; i < nums.size() ; i ++)
nums[i] = 0;
}
};
2.Expression Add Operators 表达式增加操作符
Given a string that contains only digits 0-9
and a target value, return all possibilities to add operators +
, -
, or *
between the digits so they evaluate to the target value.
Examples:
"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []
Credits:
Special thanks to @davidtan1890 for adding this problem and creating all test cases.
这道题给了我们一个只由数字组成的字符串,让我们再其中添加+,-或*号来形成一个表达式,该表达式的计算和为给定了target值,让我们找出所有符合要求的表达式来。题目中给的几个例子其实并不好,很容易让人误以为是必须拆成个位数字,其实不是的,比如"123", 15能返回"12+3",说明连着的数字也可以。如果非要在过往的题中找一道相似的题,我觉得跟Combination Sum II 组合之和之二,Target Sum 目标和很类似。不过这道题要更复杂麻烦一些。还是用递归来解题,我们需要两个变量diff和curNum,一个用来记录将要变化的值,另一个是当前运算后的值,而且它们都需要用long long型的,因为字符串转为int型很容易溢出,所以我们用长整型。对于加和减,diff就是即将要加上的数和即将要减去的数的负值,而对于乘来说稍有些复杂,此时的diff应该是上一次的变化的diff乘以即将要乘上的数,有点不好理解,那我们来举个例子,比如2+3*2,即将要运算到乘以2的时候,上次循环的curNum = 5, diff = 3, 而如果我们要算这个乘2的时候,新的变化值diff应为3*2=6,而我们要把之前+3操作的结果去掉,再加上新的diff,即(5-3)+6=8,即为新表达式2+3*2的值,有点难理解,大家自己一步一步推算吧。
class Solution {
public:
vector<string> addOperators(string num, int target) {
vector<string> res;
addOperatorsDFS(num, target, 0, 0, "", res);
return res;
}
void addOperatorsDFS(string num, int target, long long diff, long long curNum, string out, vector<string> &res) {
if (num.size() == 0 && curNum == target) {
res.push_back(out);
}
for (int i = 1; i <= num.size(); ++i) {
string cur = num.substr(0, i);
if (cur.size() > 1 && cur[0] == '0') return;
string next = num.substr(i);
if (out.size() > 0) {
addOperatorsDFS(next, target, stoll(cur), curNum + stoll(cur), out + "+" + cur, res);
addOperatorsDFS(next, target, -stoll(cur), curNum - stoll(cur), out + "-" + cur, res);
addOperatorsDFS(next, target, diff * stoll(cur), (curNum - diff) + diff * stoll(cur), out + "*" + cur, res);
} else {
addOperatorsDFS(next, target, stoll(cur), stoll(cur), cur, res);
}
}
}
};
标签:Zeroes,cur,nums,res,Operators,Move,stoll,diff,target From: https://blog.51cto.com/u_16147764/6400757