1.盛水最多的容器
思路：双指针，一个最左，一个最右，由于容器的高度由最矮的边决定，因此当左面高于右面时，右面往左移；否则左面往右移，用一个res记录最大值，与每次的面积做对比。
class Solution {
public:
int maxArea(vector<int>& height) {
int len=height.size();
if(len<2) return 0;
int left=0;
int right=len-1;//双指针
int res=min(height[right],height[left])*(right-left);
while(left<right)
{
if(height[left]<height[right])
{
left++;
}
else
{
right--;
}
res=max(res,min(height[right],height[left])*(right-left));
}
return res;
}
};2.删除排序数组中的重复项
思路：从头到尾遍历，设一个指针，如果重复，指针不移动，如果不重复，指针移动，记录下不重复的数字。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int len=nums.size();
if(len<2) return len;
int i=0;
int j=1;
for(i=1;i<len;i++)
{
if(nums[i]!=nums[i-1])
{
nums[j++]=nums[i];
}
}
return j;
}
};3.三数之和（重点）
思路：先对数组进行排序，从头开始遍历，依次选择一个数，然后利用双指针，一个指针指向所选择数的后一位，另一个指向数组的最后一位，如果相加等于0，那么记录下来，小于0，left++，大于0，right--。此问题要注意去重：如果某数与前一个数相同，则直接跳过，当符合条件时，看left++与right--是否与left和right相同。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
vector<int> cur;
int len=nums.size();
if(len<3) return res;//小于三不符合条件
sort(nums.begin(),nums.end());
for(int i=0;i<len-2;i++)
{
if(nums[i]>0) break;
if(i>0&&nums[i]==nums[i-1]) continue;//注意这个判断条件，是后和前比，不是前和后(-1,-1,2)说明不能前和后
int left=i+1;
int right=len-1;
while(left<right)
{
int sum=nums[i]+nums[left]+nums[right];
if(sum==0)
{
cur.push_back(nums[i]);
cur.push_back(nums[left]);
cur.push_back(nums[right]);
res.push_back(cur);
cur.clear();
while(left<right&&nums[left]==nums[left+1]) left++;//去重
while(left<right&&nums[right]==nums[right]-1) right--;//去重
left++;
right--;
}
else if(sum<0)
{
left++;
}
else
{
right--;
}
}
}
return res;
}
};4.移动0
思路：引入一个指针，从头到尾开始遍历，如果不为0，指针记录次数，后移一位，最后剩下的位置都补0.
class Solution {
public:
void moveZeroes(vector<int>& nums) {
if(nums.size()<=0) return;
int j=0;
for(int i=0;i<nums.size();i++)
{
if(nums[i]!=0)
{
nums[j++]=nums[i];
}
}
for(int k=j;k<nums.size();k++)
{
nums[k]=0;
}
}
};5.爬楼梯
思路：一个循环一个递归。
class Solution {
public:
int climbStairs(int n) {
//循环代替递归
if(n==1) return 1;
if(n==2) return 2;
int a=1;
int b=2;
int c;
for(int i=3;i<=n;i++)
{
c=a+b;
a=b;
b=c;
}
return c;
}
};6.合并两个有序链表
思路：一个循环一个递归，见程序。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
/*递归
if(l1==nullptr) return l2;
if(l2==nullptr) return l1;
ListNode *p=nullptr;
if(l1->val<l2->val)
{
p=l1;
p->next=mergeTwoLists(l1->next,l2);
}
else
{
p=l2;
p->next=mergeTwoLists(l1,l2->next);
}
return p;*/
ListNode *Head=new ListNode(-1);
ListNode *p=Head;
while(l1!=nullptr&&l2!=nullptr)
{
if(l1->val<=l2->val)
{
p->next=l1;
l1=l1->next;
}
else
{
p->next=l2;
l2=l2->next;
}
p=p->next;
}
if(l1==nullptr)
p->next=l2;
else
p->next=l1;
return Head->next;
}
};7.旋转数组
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len=nums.size();
k%=len;//重要一步，过长度轮会产生一个循环
reverse(nums,0,len-1);//整体翻转
reverse(nums,0,k-1);//前k个数翻转
reverse(nums,k,len-1);//剩下的数翻转
}
void reverse(vector<int>& nums,int begin,int end)
{
while(begin<end)
{
int temp=nums[begin];
nums[begin]=nums[end];
nums[end]=temp;
begin++;
end--;
}
}
};8.合并两个有序数组
思路：尾结点的双指针。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
//尾部双指针
int tail=m+n-1;
int tail1=m-1;
int tail2=n-1;
while(tail1!=tail)//如果第一个数组遍历完了，就把第二个数组剩余的数字全都依次放在前面
{
if(tail1>=0&&nums1[tail1]>nums2[tail2])
{
nums1[tail--]=nums1[tail1--];//从尾开始对比，如果1大于2，就把1放在最末尾
}
else
{
nums1[tail--]=nums2[tail2--];
}
}
}
};9.两两交换链表中的节点
思路：注意新建两个节点，一个用来当前做改变，另一个保持不动用来返回。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution
{
public:
ListNode* swapPairs(ListNode* head)
{
//新建一个空结点，用来指向头节点
ListNode* p = new ListNode(0);
p->next = head;
//新建和p相同一个curr节点，两个相同的节点一个是当前做改变的节点，一个是保持不动用来返回的节点
ListNode* curr = p;
//循环条件为当前节点为NULL或当前的下一个节点为NULL，分别对应偶数和奇数个节点的终止标志
while(head != NULL && head->next != NULL)
{
//为了清晰明了，我们新建两个节点，一节点和二节点
ListNode* firstNode = head;
ListNode* secondNode = head->next;
///把一和二进行交换，并连接前后
//当前curr节点指向二节点
curr->next = secondNode;
//一节点指向二节点此时的下一节点
firstNode->next = secondNode->next;
//二节点指向一节点，即交换位置成功
secondNode->next = firstNode;
//由于每次循环curr节点都指向每次循环的一节点，所以要再次把curr节点指向一节点
curr = firstNode;
//每次移动都是由head节点来赋值操作，所以head应向右移动两格，即新循环的一节点
head = firstNode->next;
}
//返回p的下一个节点即对应整个操作后的链表
return p->next;
}
};10.链表形式的两数相加
思路：利用栈来存储逆序的计算，注意进位标志的保存，以及链表从尾到头生成。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//逆序想到用栈
stack<int> s1, s2;
while (l1) {
s1.push(l1 -> val);
l1 = l1 -> next;
}
while (l2) {
s2.push(l2 -> val);
l2 = l2 -> next;
}
int carry = 0;
ListNode* ans = nullptr;
while (!s1.empty() || !s2.empty() || carry != 0) {
int a = s1.empty() ? 0 : s1.top();
int b = s2.empty() ? 0 : s2.top();
if (!s1.empty()) s1.pop();
if (!s2.empty()) s2.pop();
int cur = a + b + carry;
carry = cur / 10;//进位
cur %= 10;
auto curnode = new ListNode(cur);
curnode -> next = ans;
ans = curnode;//倒着往回走
}
return ans;
}
};
京公网安备 11010502036488号