剑指 Offer 59 - I. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> vec;
        for(int i=0;i<nums.size();i++)
        {
            if(i-k==dq.front()) dq.pop_front();     //如果首元素超过滑动窗口,弹出
            while(!dq.empty()&&nums[i]>nums[dq.back()]) //构造单调递减队列
            {
                dq.pop_back();
            }
            dq.push_back(i);
            if(i>=k-1) vec.push_back(nums[dq.front()]); //在滑动窗口内每次都要添加最大值
        }
        return vec;
    }
};
  • 构造单调递减队列,使最大元素为队首,然后滑动窗口

剑指 Offer 59 - II. 队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空,pop_front 和 max_value 需要返回 -1

class MaxQueue {
public:
    deque<int> dq;
    queue<int> q;
    MaxQueue() {
    }
    
    int max_value() {
        if(dq.empty())  return -1;
        return dq.front();
    }
    
    void push_back(int value) {
        while(!dq.empty()&&value>dq.back())
        {
            dq.pop_back();
        }
        q.push(value);
        dq.push_back(value);
    }
    
    int pop_front() {
        if(dq.empty()) return -1;
        int t=q.front();
        q.pop();
        if(t==dq.front())
        {
            dq.pop_front();
        }
        return t;
    }
};
  • 维护单调递减的双端队列

剑指 Offer 61. 扑克牌中的顺子

从若干副扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。

class Solution {
public:
    bool isStraight(vector<int>& nums) {
        int n=0;
        int minv=INT_MAX,maxv=INT_MIN;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]==0)    continue;
            if(i<nums.size()-1)
            {
                if(nums[i]==nums[i+1]) return false;
            }
            if(nums[i]>maxv)    maxv=nums[i];
            if(nums[i]<minv)    minv=nums[i];
        }
        if(maxv-minv<=4) return true;
        return false;  
    }
};
  • 排序
  • 判断是否有重复值和判断最大值最小值差值是否小于5

剑指 Offer 62. 圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。

例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。

class Solution {
public:
    int lastRemaining(int n, int m) {
        int x=0;
        for(int i=2;i<=n;i++)
        {
           x=(x+m)%i;
        }
        return x;
    }
};
  • 约瑟夫环问题

剑指 Offer 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        int minV=prices[0];
        int pre=INT_MIN;
        for(int i=-0;i<prices.size();i++)
        {
            if(prices[i]<minV)  minV=prices[i];
            pre=max(pre,prices[i]-minV);
        }
        return pre;     
    }
};
  • dp
  • 优化空间

剑指 Offer 64. 求1+2+…+n

求 1+2+…+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

class Solution {
public:
    int sumNums(int n) {
        n&&(n+=sumNums(n-1));
        return n;
    }
};
  • A&&B 当A为假时,不执行B
  • A||B 当A为真时,不执行B
  • 由此可以当终止条件

剑指 Offer 66. 构建乘积数组

给定一个数组 A[0,1,…,n-1],请构建一个数组 B[0,1,…,n-1],其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        vector<int> vec; 
        vector<int> left,right;
        left.push_back(1);
        int sum=1;
        for(int i=1;i<a.size();i++)
        {
            sum*=a[i-1];
            left.push_back(sum);
        }
        sum=1;
        right.push_back(1);
        for(int i=a.size()-1;i>0;i--)
        {
            sum*=a[i];
            right.push_back(sum);
        }      
        reverse(right.begin(),right.end());
        for(int i=0;i<a.size();i++)
        {
            vec.push_back(left[i]*right[i]);
        }
        return vec;
    }
};
  • 遍历两次记录每个元素左右元素乘积
  • 然后左右元素相乘即可

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root!=nullptr)
        {
            if(p->val>root->val&&q->val>root->val)  root=root->right;
            else if(p->val<root->val&&q->val<root->val)  root=root->left;
            else break;
        }
        return root;

    }
};

剑指 Offer 68 - II. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr) return nullptr;
        if(p==root||q==root) return root;

        TreeNode* left=lowestCommonAncestor(root->left,p, q);   //找到p或q节点,返回
        TreeNode* right=lowestCommonAncestor(root->right,p, q);//找到p或q节点,返回

        if(left!=nullptr&&right!=nullptr) return root;  //如果左和右都非空(两个节点分别在左和右)则公共祖先为root
        else if(left==nullptr) return right;        //如果左无节点,则返回右(题目说pq节点都在书中)
        else if(right==nullptr) return left;    
        return nullptr;     //左右都没有返回空
    }
};

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy=new ListNode(-1);
        dummy->next=head;
        ListNode*pre=dummy,*cur=head;
        for(int i=0;i<left-1;i++)
        {
            pre=pre->next;
            cur=cur->next;
        }
        for(int i=0;i<right-left;i++)
        {
            ListNode *t=cur->next;
            cur->next=cur->next->next;
            t->next=pre->next;
            pre->next=t;
        }
        return dummy->next;
    }
};

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l=0,r=nums.size()-1;
        if(nums.size()==1) return 0;
        while(l<r)
        {
            int mid=l+(r-l)/2;
            if(nums[mid]<nums[mid+1]) l=mid+1;
            else r=mid;
        }
        return r;
    }
};
  • 因为nums[mid]<nums[mid+1],所以mid肯定不是峰值,mid+1可能是峰值,所以要l=mid+1
  • 如果nums[mid]>nums[mid+1] ,mid+1肯定不是峰值,mid可能是峰值,所以r=mid

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

class Solution {
public:
    int n=0;
    void merge(vector<int>&nums,int left,int right)
    {
        int mid=left+((right-left)>>1);
        int index=0,p1=left,p2=mid+1;
        int *aux=new int[right-left+1];
        while(p1<=mid&&p2<=right)
        {
            if(nums[p1]<=nums[p2]) aux[index++]=nums[p1++];
            else 
            {
                aux[index++]=nums[p2++];
                n+=mid-p1+1;	//统计逆序对
            }
        }
        while(p1<=mid) aux[index++]=nums[p1++];
        while(p2<=right) aux[index++]=nums[p2++];
        for(int i=0;i<index;i++)
        {
            nums[i+left]=aux[i];
        }
        delete[] aux;
    }

    void mergeSort(vector<int>&nums,int left,int right)
    {
        if(nums.size()==0||left>=right) return;
        int mid=left+((right-left)>>1);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);
        merge(nums,left,right);
    }

    int reversePairs(vector<int>& nums) {
        mergeSort(nums, 0, nums.size()-1);
        return n;
    }
};
  • 归并排序+一条语句

165. 比较版本号

给你两个版本号 version1 和 version2 ,请你比较它们。

版本号由一个或多个修订号组成,各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成,可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推。例如,2.5.33 和 0.1 都是有效的版本号。

比较版本号时,请按从左到右的顺序依次比较它们的修订号。比较修订号时,只需比较 忽略任何前导零后的整数值 。也就是说,修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号,则该修订号视为 0 。例如,版本 1.0 小于版本 1.1 ,因为它们下标为 0 的修订号相同,而下标为 1 的修订号分别为 0 和 1 ,0 < 1 。

返回规则如下:

如果 version1 > version2 返回 1,
如果 version1 < version2 返回 -1,
除此之外返回 0。

class Solution {
public:
    int compareVersion(string v1, string v2) {
        int i=0,j=0;
        while(i<v1.size()||j<v2.size())
        {
            int num1=0,num2=0;
            while(i<v1.size()&&v1[i]!='.') 
            {
                num1=10*num1+v1[i]-'0';    //把字符串转换为数字
                i++;
            }
            while(j<v2.size()&&v2[j]!='.') 
            {
                num2=10*num2+v2[j]-'0';
                j++;
            }
            if(num1>num2) return 1;
            else if(num1<num2) return -1;
            else i++,j++;
        }
        return 0;
    }
};

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。

叶子节点 是指没有子节点的节点。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return false;
        return dfs(root,targetSum);
    }

    bool dfs(TreeNode* root, int sum)
    {
        if(root==nullptr) return false;
        sum-=root->val;
        if(sum==0&&root->left==nullptr&&root->right==nullptr) return true;
        return dfs(root->left,sum)||dfs(root->right,sum);
    }
};

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

class Solution {
public:
    vector<int> v;
    vector<vector<int>> vec;
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return vec;
        dfs(root,targetSum);
        return vec;
    }
    void  dfs(TreeNode* root, int sum)
    {
        if(root==nullptr)
        {
            return ;
        }
        sum-=root->val;
        v.push_back(root->val);
        if(sum==0&&root->left==nullptr&&root->right==nullptr)
        {
            vec.push_back(v);
        }
        if(root->left!=nullptr) dfs(root->left,sum);
        if(root->right!=nullptr) dfs(root->right,sum);
        v.pop_back();
    }

};

543. 二叉树的直径

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

class Solution {
public:
    int ans=-1;
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }
    
    int dfs(TreeNode* root)
    {
        if(root==nullptr) return 0;
        int l=dfs(root->left);
        int r=dfs(root->right);
        ans=max(ans,l+r);
        return max(l,r)+1;
    }
};

Q.E.D.