lc189 旋转数组&LC1785&LC6
2021-03-15 本文已影响0人
锦绣拾年
lc189
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 2 * 104
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法1，其实新数组位置已经定了，所以完全可以新建一个数组，把这些信息放进去。
方法2，reverse旧数组。
向右移动k步，刚好后k个元素挪到数组头了。
所以翻转全部数组元素，然后后k个就到头部了。
然后再翻转头部k个，
再翻转后面的
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if(nums.size()==0||k==0)
return;
k=k%nums.size();
reverse(nums.begin(),nums.end());
reverse(nums.begin(),nums.begin()+k);
reverse(nums.begin()+k,nums.end());
return;
}
};
lc1785
给你一个整数数组 nums ，和两个整数 limit 与 goal 。数组 nums 有一条重要属性：abs(nums[i]) <= limit 。
返回使数组元素总和等于 goal 所需要向数组中添加的 最少元素数量 ，添加元素 不应改变 数组中 abs(nums[i]) <= limit 这一属性。
注意，如果 x >= 0 ，那么 abs(x) 等于 x ；否则，等于 -x 。
示例 1：
输入：nums = [1,-1,1], limit = 3, goal = -4
输出：2
解释：可以将 -2 和 -3 添加到数组中，数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4 。
示例 2：
输入：nums = [1,-10,9,1], limit = 100, goal = 0
输出：1
提示：
1 <= nums.length <= 105
1 <= limit <= 106
-limit <= nums[i] <= limit
-109 <= goal <= 109
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-elements-to-add-to-form-a-given-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一个简单的计算问题
class Solution {
public:
int minElements(vector<int>& nums, int limit, int goal) {
long long anum =0;
for(int i=0;i<nums.size();i++){
anum+=nums[i];
}
long long minus = goal-anum;
if(minus<0){
minus=-minus;
}
// cout<<limit<<minus<<endl;
if(minus==0)
return 0;
if(limit>minus)
return 1;
// cout<<1%99<<99%1<<endl;
if(minus%limit==0)
return minus/limit;
else
return minus/limit+1;
}
};
lc6 Z字变换
个人感觉这种题就是找规律然后编程，推规律比较烦人。
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P I N
A L S I G
Y A H R
P I
示例 3：
输入：s = "A", numRows = 1
输出："A"
提示：
1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
string convert(string s, int numRows) {
//0 隔三个 n-1+..+(n-2)
//1 隔1个
//2 隔3个
//4 n-1+..+(n-2)
if(numRows==0)
return "";
if(numRows==1||s.length()==0)
return s;
if(numRows==2){
string s1="";
string s2="";
for(int i=0;i<s.length();i++){
// cout<<s1<<" "<<s2<<endl;
if(i%2==0){
s1+=s[i];
}else{
s2+=s[i];
}
}
return s1+s2;
}
string res = "";
// vector<string> resarr(5);
string resarr[numRows];//用vector初始化貌似有问题，vector合适的初始化
fill(resarr,resarr+numRows,"");
// fill(resarr.begin(),resarr.end(),"");//vector这样不可，但是数组可。
for(int i=0;i<numRows;i++){
int index = i;
int op=0;
int lastindex=-1;
while(index<s.length()){
if(lastindex!=index){
resarr[i]+=s[index];
lastindex=index;
}
if(op==0){
index += 2*numRows-2*i-2;
op=1;
}else if(op==1){
index += 2*i;
op=0;
}
}
}
for(int i=0;i<numRows;i++){
res+=resarr[i];
// cout<<res<<endl;
}
return res;
}
};
