数组
1删除排序数组中的重复项 快慢指针
2买卖股票的最佳时机 II 最简单的贪心算法
3旋转数组 分多次旋转
旋转数组
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k=k%nums.size();
reverse(nums,0,nums.size()-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.size()-1);
}
void reverse(vector<int>& nums,int begin,int end){
for(int i=0;i<(end-begin+1)/2;i++){
int a=nums[begin+i];
nums[begin+i]=nums[end-i];
nums[end-i]=a;
}
}
};4存在重复元素 常规：哈希表 ，set
5只出现一次的数字 异或运算
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result=0;
for(int i=0;i<nums.size();i++){
result ^= nums[i];
}
return result;
}
};6两个数组的交集 II 排序后双指针/map
7加一 循环，挪位
8移动零 快慢指针
9两数之和 哈希表
10有效的数独 循环
11旋转图像 循环
字符串
1反转字符串 同数组反转
2整数反转 注意溢出检测方法
public int reverse(int x) {
int res = 0;
while (x != 0) {
int t = x % 10;
int newRes = res * 10 + t;
//如果数字溢出，直接返回0
if ((newRes - t) / 10 != res)
return 0;
res = newRes;
x = x / 10;
}
return res;
}3字符串中的第一个唯一字符 hashmap，也许数组效率更高
4有效的字母异位词 hashmap或数组
5验证回文串 双指针
6字符串转整数
7strStr() 逐个判断/KMP算法
8外观数列9最长公共前缀 没啥说的
链表
1删除链表中的节点
class Solution {
public:
void deleteNode(ListNode* node) {
ListNode *next1 = node->next;
node->val = next1->val;
node->next = next1->next;
delete next1;
next1=nullptr;
}
};2删除链表倒数第N个
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head->next==nullptr)
return nullptr;
int *time = new int;
*time = n;
remove(head,time);
if(*time==0)
return head->next;
else
return head;
}
void remove(ListNode* head, int* times){
if(head->next!=nullptr)
remove(head->next,times);
if(*times!=0)
*times = *times - 1;
else{
ListNode *temp = head->next;
head->next=temp->next;
delete temp;
*times = *times - 1;
}
}
};3反转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr || head->next==nullptr)
return head;
ListNode* head1 = reverseList(head->next);
head->next->next=head;
head->next = nullptr;
return head1;
}
};4合并两个有序链表
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1==nullptr)
return list2;
if(list2==nullptr)
return list1;
ListNode *l1;ListNode *l2;
if(list1->val<=list2->val){
l1=list1;l2=list2;
}
else{
l1=list2;l2=list1;
}
digui(l1,l1->next,l2);
return l1;
}
void digui(ListNode* begin,ListNode* l1,ListNode* l2){
if(l1==nullptr){
begin->next=l2;
return;
}
if(l2==nullptr){
begin->next=l1;
return;
}
if(l1->val<=l2->val){
begin->next=l1;
digui(l1,l1->next,l2);
}
else{
begin->next=l2;
digui(l2,l1,l2->next);
}
}
};5回文链表 快慢指针与反转链表
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode *slow,*fast;
slow=fast=head;
while(fast->next!=nullptr && fast->next->next!=nullptr){
slow=slow->next;
fast=fast->next->next;
}
if(slow->next==nullptr)
return true;
slow->next=reverse(slow->next);
slow=slow->next;
while(slow!=nullptr){
if(head->val!=slow->val)
return false;
slow=slow->next;
head=head->next;
}
return true;
}
ListNode* reverse(ListNode *head){
ListNode* prev = nullptr;
ListNode* next = nullptr;
while(head!=nullptr){
next=head->next;
head->next=prev;
prev=head;
head=next;
}
return prev;
}
};6环形链表 快慢指针
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==nullptr)
return false;
ListNode *slow, *fast;
slow=fast=head;
while(slow!=nullptr){
if(fast->next==nullptr || fast->next->next==nullptr)
return false;
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
return true;
}
return false;
}
};树
1二叉树的最大深度 递归
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==nullptr)
return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};2验证二叉搜索树 递归
class Solution {
public:
bool isValidBST(TreeNode* root) {
return fanwei(root,LONG_MIN,LONG_MAX);
}
bool fanwei(TreeNode* root,long left,long right){
if(root==nullptr)
return true;
long val = long(root->val);
if(val<=left||val>=right)
return false;
return (fanwei(root->left,left,min(right,val)) && fanwei(root->right,max(left,val),right));
}
};3对称二叉树
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root==nullptr)
return true;
return duicheng(root->left,root->right);
}
bool duicheng(TreeNode* left,TreeNode* right){
if(left==nullptr&&right==nullptr)
return true;
if(left==nullptr||right==nullptr)
return false;
if(left->val!=right->val)
return false;
return duicheng(left->left,right->right)&&duicheng(left->right,right->left);
}
};4二叉树的层序遍历 使用队列记录node
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> answer;
if(root==nullptr)
return answer;
queue<TreeNode*> nodequeue;
int num=1;
nodequeue.push(root);
while(num!=0){
vector<int> temp;
for(int i=0;i<num;i++){
TreeNode* current = nodequeue.front();
temp.push_back(current->val);
nodequeue.pop();
if(current->left!=nullptr)
nodequeue.push(current->left);
if(current->right!=nullptr)
nodequeue.push(current->right);
}
answer.push_back(temp);
num=nodequeue.size();
}
return answer;
}
};5将有序数组转化成为二叉搜索树
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
int size = nums.size();
TreeNode *top = new TreeNode(nums[size/2]);
top->left = digui(nums,0,size/2 - 1);
top->right = digui(nums,size/2 + 1,size - 1);
return top;
}
TreeNode* digui(vector<int>& nums,int left,int right){
if(left>right)
return nullptr;
int size = right-left+1;
TreeNode *top = new TreeNode(nums[left+size/2]);
if(size>=2)
top->left = digui(nums,left,left + size/2-1);
if(size>=3)
top->right = digui(nums,left + size/2+1,right);
return top;
}
};排序和搜索
1合并两个有序数组 从后向前排
2第一个错误版本 二分查找
class Solution {
public:
int firstBadVersion(int n) {
int left=1;int right=n;
while(left<right){
int mid=left/2+right/2;
if(isBadVersion(mid)==true){
left = left;right=mid;
}
else{
left=mid + 1;right=right;
}
}
return left;
}
};动态规划
1爬楼梯
class Solution {
public:
int climbStairs(int n) {
if(n==1)
return 1;
if(n==2)
return 2;
int a=1;int b=2;
for(int i=2;i<n;i++){
if(i%2==0){
a=a+b;
}
else{
b=a+b;
}
}
return a>b?a:b;
}
};2买卖股票的最佳时机 动态规划/快慢指针/单调栈
3最大子序和 动态规划
4打家劫舍 动态规划，【2，length】记录是否打劫情况下的最大利润
Comments NOTHING