958. 二叉树的完全性检验

给定一个二叉树的 root ,确定它是否是一个 完全二叉树 。

在一个 完全二叉树 中,除了最后一个关卡外,所有关卡都是完全被填满的,并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。

class Solution {
public:
    int maxIndex=0,n=0;
    bool isCompleteTree(TreeNode* root) {
        if(dfs(root,1)==false) return  false;
        return n==maxIndex;
    }

    bool dfs(TreeNode*root,int k)
    {
        if(root==nullptr) return true;
        if(k>1000) return false;
        maxIndex=max(maxIndex,k);
        n++;
        return dfs(root->left,2*k)&&dfs(root->right,2*k+1);
    }
};
  • k为当前节点数,n为总结点数,maxIndex为最大节点数
  • 如果总结点数n与最大节点数相同,则是完全二叉树,否则不是

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i=0;i<nums.size();i++)
        {
            while(nums[i]>0&&nums[i]<=nums.size()&&nums[nums[i]-1]!=nums[i])
            {
                swap(nums[i],nums[nums[i]-1]);
            }
        }

        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]!=i+1) return i+1;
        }
        return nums.size()+1;
    }
};
  • 置换法
  • 把num[i]和num[num[i]-1]交换,遍历数组当前元素不再对应下标位置的即为答案
  • 若都在下标位置则为连续数组,及返回数组最大值的下一个元素

918. 环形子数组的最大和

给定一个长度为 n 的环形整数数组 nums ,返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上, nums[i] 的下一个元素是 nums[(i + 1) % n] , nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上,对于子数组 nums[i], nums[i + 1], …, nums[j] ,不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int sum=0;
        int maxv=nums[0],minv=nums[0],curmax=0,curmin=0;
        for(auto &i:nums)
        {
            curmax=max(curmax+i,i);
            maxv=max(maxv,curmax);
            curmin=min(curmin+i,i);
            minv=min(minv,curmin);
            sum+=i;
        }
        if(maxv>0) return max(maxv,sum-minv);
        return maxv;
    }
};

1114. 按序打印

三个不同的线程 A、B、C 将会共用一个 Foo 实例。

线程 A 将会调用 first() 方法
线程 B 将会调用 second() 方法
线程 C 将会调用 third() 方法
请设计修改程序,以确保 second() 方法在 first() 方法之后被执行,third() 方法在 second() 方法之后被执行。

class Foo {
public:
    pthread_mutex_t mutex1,mutex2;
    Foo() {
        pthread_mutex_init(&mutex1,nullptr);	//初始化互斥锁
        pthread_mutex_init(&mutex2,nullptr);

        pthread_mutex_lock(&mutex1);		//给2和3加锁
        pthread_mutex_lock(&mutex2);
    }

    void first(function<void()> printFirst) {
        
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        pthread_mutex_unlock(&mutex1);	//1执行完给2解锁
    }

    void second(function<void()> printSecond) {
        
        // printSecond() outputs "second". Do not change or remove this line.
        pthread_mutex_lock(&mutex1);      
        printSecond();
        pthread_mutex_unlock(&mutex2);	//2执行完给3解锁
        
    }

    void third(function<void()> printThird) {
        
        // printThird() outputs "third". Do not change or remove this line.
        pthread_mutex_lock(&mutex2);
        printThird();
    }
};
  • 互斥锁
class Foo {
public:
    pthread_mutex_t mutex1,mutex2;
    pthread_cond_t cond1,cond2;
    int k=1;	//条件
    Foo() {
        pthread_mutex_init(&mutex1,nullptr);	//初始化条件变量和互斥锁
        pthread_mutex_init(&mutex2,nullptr);
        pthread_cond_init(&cond1,nullptr);
        pthread_cond_init(&cond2,nullptr);

        pthread_mutex_lock(&mutex1);		//	加锁
        pthread_mutex_lock(&mutex2);
    }

    void first(function<void()> printFirst) {
        
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        k++;		
        pthread_mutex_unlock(&mutex1);	//给2解锁
    }

    void second(function<void()> printSecond) {
        
        // printSecond() outputs "second". Do not change or remove this line.
        pthread_mutex_lock(&mutex1);      
        while(k!=2) pthread_cond_wait(&cond1, &mutex1);		//如果k不等于2,则阻塞直到满足条件
        printSecond();
        k++;
        pthread_mutex_unlock(&mutex2);		//给3解锁
        
    }

    void third(function<void()> printThird) {
        
        // printThird() outputs "third". Do not change or remove this line.
        pthread_mutex_lock(&mutex2);
        while(k!=3) pthread_cond_wait(&cond2, &mutex2);//如果k不等于3,则阻塞直到满足条件
        printThird();
    }
};
  • 互斥锁+条件变量

1115. 交替打印 FooBar

两个不同的线程将会共用一个 FooBar 实例:

线程 A 将会调用 foo() 方法,而
线程 B 将会调用 bar() 方法
请设计修改程序,以确保 “foobar” 被输出 n 次。

class FooBar {
private:
    int n;
    pthread_mutex_t mutex1,mutex2;
public:
    FooBar(int n) {
        this->n = n;
        pthread_mutex_init(&mutex1, nullptr);
        pthread_mutex_init(&mutex2, nullptr);


        pthread_mutex_lock(&mutex2);

    
    }

    void foo(function<void()> printFoo) {
        
        for (int i = 0; i < n; i++) {
            
        	// printFoo() outputs "foo". Do not change or remove this line.
            pthread_mutex_lock(&mutex1);
        	printFoo();
            //pthread_mutex_lock(&mutex1);
            pthread_mutex_unlock(&mutex2);
        }
    }

    void bar(function<void()> printBar) {
        
        for (int i = 0; i < n; i++) {
            
        	// printBar() outputs "bar". Do not change or remove this line.
            pthread_mutex_lock(&mutex2);
        	printBar();
            //pthread_mutex_lock(&mutex2);
            pthread_mutex_unlock(&mutex1);
        }
    }
};

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {

        int ans=0;
        vector<vector<int>> memo(matrix.size(),vector<int>(matrix[0].size()));//记忆数组
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                int maxl=dfs(matrix,i,j,-1,memo);
                ans=max(ans,maxl);
            }
        }
        return ans;
    }
    int dfs(vector<vector<int> >& matrix,int x,int y,int pre,vector<vector<int>>& memo)
    {
        int maxl=0;
        if(x<0||x>=matrix.size()||y<0||y>=matrix[0].size()||matrix[x][y]<=pre)
        {
            return 0;
        }

        if(memo[x][y]!=0)	//已经遍历过了直接返回之前的结果
        {
            return memo[x][y];
        }   
        maxl=max(maxl,dfs(matrix,x-1,y,matrix[x][y],memo));
        maxl=max(maxl,dfs(matrix,x+1,y,matrix[x][y],memo));
        maxl=max(maxl,dfs(matrix,x,y-1,matrix[x][y],memo));
        maxl=max(maxl,dfs(matrix,x,y+1,matrix[x][y],memo));
        memo[x][y]=maxl+1;	//没有遍历过则加入到数组中,要max+1,长度需要+1
        return maxl+1;
    }
};
  • dfs+记忆化搜索

7. 整数反转

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

class Solution {
public:
    int reverse(int x) {
        int ans=0;
        while(x!=0)	     
        {
            if(ans<INT_MIN/10||ans>INT_MAX/10) return 0;
            int t=x%10;
            x/=10;
            ans=ans*10+t;
        }
        return ans;
    }
};

24. 两两交换链表中的节点

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy=new ListNode(-1);
        dummy->next=head;
        ListNode* cur=dummy;
        while(cur->next!=nullptr&&cur->next->next!=nullptr)
        {
            ListNode* t=cur->next;
            cur->next=t->next;
            t->next=t->next->next;
            cur->next->next=t;
            cur=cur->next->next;
        }
        return dummy->next;
    }
};

1143. 最长公共子序列

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1));
        for(int i=1;i<=text1.size();i++)
        {
            for(int j=1;j<=text2.size();j++)
            {
                if(text1[i-1]==text2[j-1])  dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

最长公共子串

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        int maxL=0,lastIndex=0;
        vector<vector<int>> dp(str1.size()+1,vector<int>(str2.size()+1));
        for(int i=1;i<=str1.size();i++)
        {
            for(int j=1;j<=str2.size();j++)
            {
                if(str1[i-1]==str2[j-1])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                    if(maxL<dp[i-1][j-1])    
                    {
                        maxL=dp[i-1][j-1];
                        lastIndex=i;
                    }
                }
                else
                    dp[i][j]=0;
            }
        }
        return str1.substr(lastIndex-maxL-1,maxL+1);
    }
};
  • dp记录最长子串长度和最长下标
  • 截取字符串

5. 最长回文子串

给你一个字符串 s,找到 s 中最长的回文子串。

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size()==0) return "";
        int l=0,r=0;
        int maxStart,maxL=0;
        int len=1;
        for(int i=0;i<s.size();i++)
        {
            l=i-1,r=i+1;
            while(l>=0&&s[i]==s[l])
            {
                len++;
                l--;
            }
            while(r<s.size()&&s[i]==s[r])
            {
                len++;
                r++;
            }
            while(l>=0&&r<s.size()&&s[l]==s[r])
            {
                len+=2;
                r++;
                l--;
            }
            if(len>maxL)
            {
                maxL=len;
                maxStart=l;		//如果求最大长度去掉这行,返回maxL即可
            }
            len=1;
        }
        return s.substr(maxStart+1,maxL);
    }
};
  • 中心拓展法

179. 最大数

给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> vec;
        for(int i=0;i<nums.size();i++)
        {
            vec.push_back(to_string(nums[i]));
        }
        sort(vec.begin(),vec.end(),[](string &a,string &b){return a+b>b+a;});
        string s;
        for(auto &a:vec)
        {
            s+=a;
        }
        if(s[0]=='0') return "0";
        return s;
    }
};
  • 自定义比较函数

129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字:

例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。

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

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root,0);
    }

    int dfs(TreeNode *root,int sum)
    {
        if(root==nullptr) return 0;
        int s=sum*10+root->val;
        if(root->left==nullptr&&root->right==nullptr)    
        {
            return s;
        }
        return dfs(root->left,s)+dfs(root->right,s);
    }
};

206. 反转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        ListNode *node=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        return node;
    }
};
  • 递归

102. 二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> vec;
    vector<vector<int>> levelOrder(TreeNode* root) {
        dfs(root,0);
        return vec;
    }

    void dfs(TreeNode* root,int level)
    {
        if(root==nullptr) return;
        if(level>=vec.size()) vec.push_back({});	//防止后续元素无法加入进去
        vec[level].push_back(root->val);
        dfs(root->left,level+1);
        dfs(root->right,level+1);
    }
};
  • 递归

Q.E.D.