LeetCode hot-100 简单and中等难度，91-100._输入:x = 1, y = 4 输出:2

461. 汉明距离

难度简单307收藏分享切换为英文关注反馈

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int ans=0;
        int res=x^y;
        //异或操作
        while(res!=0){
            // ans++;
            ans += (res&1);//res中1的位数之和
            res >>= 1;
        }
        return ans;
    }
};

494. 目标和

难度中等349收藏分享切换为英文关注反馈

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

 

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

把所有符号为正的数总和设为一个背包的容量，容量为x；把所有符号为负的数总和设为一个背包的容量，容量为y。在给定的数组中，有多少种选择方法让背包装满。令sum为数组的总和，则x+y = sum。而两个背包的差为S,则x-y=S。从而求得x=(S+sum)/2。
基于上述分析，题目转换为背包问题：给定一个数组和一个容量为x的背包，求有多少种方式让背包装满。

作者：inkblack
链接：https://leetcode-cn.com/problems/target-sum/solution/huan-yi-xia-jiao-du-ke-yi-zhuan-huan-wei-dian-xing/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 // 虽然测试用例都能过但是会显示超时。
    // unordered_map<string,int> mp;
    // int get(int sum,int s,vector<int> nums,int index){
    //     if(index==nums.size()){
    //         if(sum==s) 
    //         return 1;
    //         else return 0;
    //     }
    //     string a=to_string(index)+","+to_string(sum);
    //     if(mp.count(a)) return mp[a];
    //     int result=get(sum+nums[index],s,nums,index+1)+
    //     get(sum-nums[index],s,nums,index+1);
    //     mp[a]=result;
    //     return result;
    // }
    // int findTargetSumWays(vector<int>& nums, int S) {
    //     int ans=get(0,S,nums,0);
    //     return ans;
    // }
    int findTargetSumWays(vector<int>& nums,int S){
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0]==abs(S)?1:0;
        int sum=0;
        for(int num:nums) sum+=num;
        if(S>sum) return 0;
        if((S+sum)%2!=0) return 0;
        //开始动态规划
        //二维的和一维的
        int dpl = (S+sum)/2;
        int n=nums.size();
        vector<vector<int>> dp(n+1,vector<int>(dpl+1,0));
        // 其实这里挺困惑的，为啥啊？0不行吗？weishenmeshi 1ne???
        // 正确的是dp[0][0]=1,dp[0][1:]=0
        // for (int i = 0; i <= n; i++) {
        //     dp[i][0] = 1;
        // }
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=dpl;j++){
                if(j>=nums[i-1])
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];
                else dp[i][j]=dp[i-1][j];
            }
        }
        return dp[n][dpl];
 
        // vector<int> dp(dpl+1);
        // dp[0]=1;
        // for(int i=1;i<=n;i++)
        //     for(int j=dpl;j>=0;j--)
        //         if(j>=nums[i-1])
        //             dp[j]=dp[j]+dp[j-nums[i-1]];
        // return dp[dpl];
    }

538. 把二叉搜索树转换为累加树

难度简单299收藏分享切换为英文关注反馈

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

 

例如：

输入: 原始二叉搜索树:
              5
            /   \
           2     13

输出: 转换为累加树:
             18
            /   \
          20     13

class Solution {
public:
//反向中序遍历
    int sum=0;
    TreeNode* convertBST(TreeNode* root) {
        // vector<int> v;
        if(root != NULL){
            convertBST(root->right);
            sum = sum + root->val;
            root->val = sum;
            convertBST(root->left);
        }
        return root;
    }
};

543. 二叉树的直径

难度简单436收藏分享切换为英文关注反馈

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

 

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

 

注意：两结点之间的路径长度是以它们之间边的数目表示。

 
class Solution {
public:
    int length = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return length;
    }
 
    int depth(TreeNode* root) {
        if (!root) return 0;
        int lret = depth(root->left);
        int rret = depth(root->right);
        length = max(length, lret+rret);
        return max(lret, rret) + 1;
    }

560. 和为K的子数组

难度中等545收藏分享切换为英文关注反馈

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

1. 数组的长度为 [1, 20,000]。
2. 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 其实就是一句sum(i,j)=sum(0,j)-sum(0,i)
//         // 前缀和数组对连续子数组求和问题基本上都能用上。
        int sum = 0, ans = 0;
        unordered_map<int,int> mp;
        mp[0] = 1;
        for(int i: nums){
            sum += i;
            if(mp.find(sum-k) != mp.end()) ans += mp[sum-k];
            mp[sum] ++;
        }
        return ans;
    }
};

581. 最短无序连续子数组

难度简单365收藏分享切换为英文关注反馈

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

示例 1:

输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

说明 :

1. 输入的数组长度范围在 [1, 10,000]。
2. 输入的数组可能包含重复元素 ，所以升序的意思是<=。

通过次数34,240提交次数98,264

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> v=nums;
        sort(v.begin(),v.end());
        int x=-1,y=-2;
        for(int i=0;i<nums.size();i++){
            if(x==-1&&nums[i]!=v[i]) x=i;
            if(nums[i]!=v[i]) y=i;
        }
        // cout<<x<<y;
        return y-x+1;
    }
};

617. 合并二叉树

难度简单435收藏分享切换为英文关注反馈

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==NULL&&t2==NULL) return NULL;
        TreeNode* x= new TreeNode(0);
        if(t1!=NULL&&t2!=NULL){
            x->val=t1->val+t2->val;
            x->left=mergeTrees(t1->left,t2->left);
            x->right=mergeTrees(t1->right,t2->right);
        }else if(t1!=NULL){
            x=t1;
        }else if(t2!=NULL){
            x=t2;
        }
        return x;
    }
};

621. 任务调度器

难度中等337收藏分享切换为英文关注反馈

给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

 

示例 ：

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 

 

提示：

1. 任务的总个数为 [1, 10000]。
2. n 的取值范围为 [0, 100]。

规定 n + 1 个任务为一轮，这样的好处是同一轮中一个任务最多只能被安排一次。在每一轮中，我们将当前的任务按照它们剩余的次数降序排序，并选择剩余次数最多的 n + 1 个任务依次执行。如果任务的种类 t 少于 n + 1 个，就只选择全部的 t 种任务，其余的时间空闲。

作者：LeetCode
链接：https://leetcode-cn.com/problems/task-scheduler/solution/ren-wu-diao-du-qi-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        //不会子，对不起
        vector<int> mp(26);
        for(char c:tasks){
            mp[c-'A']++;
        }
        sort(mp.begin(),mp.end());
        int time=0;
        while(mp[25]>0){
            int i=0;
            while(i<=n){
                if(mp[25]==0) break;
                if(i<26&&mp[25-i]>0) mp[25-i]--;
                time++;
                i++;
            }
            sort(mp.begin(),mp.end());
        }
        return time;
    }
};

647. 回文子串难度中等295收藏分享切换为英文关注反馈给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

示例 2:

输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.length();
        vector<vector<int>> dp(n,vector<int>(n));
        int ans=0;
        for(int i=0;i<n;i++){
            ans++;
            dp[i][i]=1;
            if(i!=n-1&&s[i]==s[i+1]){
                dp[i][i+1]=1;
                ans++;
            }
        }
        for(int l=3;l<=n;l++){
            for(int i=0;i+l-1<n;i++){
                int j=i+l-1;
                if(s[i]==s[j]){
                    dp[i][j]=dp[i+1][j-1];
                }else dp[i][j]=0;
                if(dp[i][j]==1) ans++;
            }
        }
        return ans;
    }
};

739. 每日温度

难度中等464收藏分享切换为英文关注反馈

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        stack<int> s;
        for(int i=0;i<T.size();i++){
            int x=T[i];
            if(s.empty()){
                s.push(i);continue;
            }
            else{
                while(!s.empty()){
                    int y=T[s.top()];
                    if(y>=x){
                        break;
                    }
                    else{
                        T[s.top()]=i-s.top();
                        s.pop();
                    }
                }
                s.push(i);
            }
        }
        while(!s.empty()){
            T[s.top()]=0;s.pop();
        }
        return T;
    }
};