本文是对leetbook《数组和字符串》学习完成后的总结。
字符串匹配算法：KMP
双指针情形一:
指针向中间或两端移动，移动方向始终相对
双指针情形二：
指针向同侧移动，形成前后指针或快慢指针
杨辉三角是以图的形式展示了二项式的性质
按照性质往下打印即可
一个注意点是先打印两边(第0列和第i列），再打印中间（j<i）
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例
1: 输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2:
输入: numRows = 1 输出: [[1]] 提示: 1 <= numRows <= 30
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ret(numRows);//一共numRows行
for (int i = 0; i < numRows; ++i) {
ret[i].resize(i + 1);//第i行有i+1列
ret[i][0] = ret[i][i] = 1;//每一行的首尾都是1
for (int j = 1; j < i; ++j) {//除首尾以外的，每个数等于上面两个数之和
ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
}
}
return ret;
}
};
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0
输出: [1]
示例 3:
输入: rowIndex = 1
输出: [1,1]
提示:0 <= rowIndex <= 33
进阶：你可以优化你的算法到 O(rowIndex) 空间复杂度吗
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + 1);//要遍历到rowIndex行所以设置成rowIndex+1的大小
row[0] = 1;//每行第一个数是1
for (int i = 1; i <= rowIndex; ++i) {
row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;//防止数据溢出，要用long long型的
}
return row;
}
};
时间复杂度：O(rowIndex)。
空间复杂度：O(1)。不考虑返回值的空间占用。
可以再开辟一个数组的空间，也可以原地操作（Java,javascript不适用其string为不可变类型）。
原地操作，向后扫描，遇到空格，调换一个单词的顺序
给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1：
输入：s = “Let’s take LeetCode contest” 输出：“s’teL ekat edoCteeL tsetnoc”
示例 2:
输入： s = “God Ding” 输出：“doG gniD”
提示：
1 <= s.length <= 5 * 104
s 包含可打印的 ASCII 字符。
s 不包含任何开头或结尾空格。
s 里 至少有一个词。 s 中的所有单词都用一个空格隔开。
class Solution {
public:
string reverseWords(string s) {
int length = s.length();
int i=0;
while(i<length){//向后遍历
int start = i;//记录单词初始位置
while(i<length&&s[i]!=' '){//遍历到单词结尾
i++;
}
int left = start,right = i-1;//交换一个单词的首尾
while(left<right){
swap(s[left],s[right]);
left++;
right--;
}
while(i<length && s[i]==' '){//遍历下一个单词，空格位置不动
i++;
}
}
return s;
}
};
二分法
对于数组中最后一个数x，在最小值右侧的元素都小于x,在最小值左侧的值都大于x（旋转到前面的一段比后面的一段大），通过这条性质来收缩查找区间。所以只用比较mid和right的大小
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums =
[0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到
[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n)的算法解决此问题。
示例 1： 输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3次得到输入数组。
示例 2： 输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7]，旋转 4 次得到输入数组。
示例 3： 输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示： n == nums.length 1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同 nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转。
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0;
int right = nums.size()-1;
while(left<right){
int mid = left+(right-left)/2;
if(nums[mid]>nums[right]){//找最小值
left = mid+1;
}
else right = mid;
}
return nums[left];
}
};
双指针。快指针表示遍历数组达到的下标位置，慢指针表示下一个不同的元素要填入的位置。将快指针与其前一个位置所指值比较
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。示例 1
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。 示例 2：输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104 nums 已按 升序 排列
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int fast=1,slow=1;
if(!nums.size()||nums.size()==1)
return nums.size();
for(int i=1;i<nums.size();i++){
if(nums[fast-1]!=nums[fast]){
nums[slow++]=nums[fast];
}
fast++;
}
return slow;
}
};
双指针，快指针遍历到达的下标的位置，慢指针指向需要交换的0的位置，快指针碰到非零数就与慢指针的值进行交换
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
进阶：你能尽量减少完成的操作次数吗？
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int left = 0,right= 0;
while(right<n){//right向前找非零值
if(nums[right]){//找到就将其交换，慢指针向后移动一步
swap(nums[left],nums[right]);
left++;
}
right++;
}
}
};