leetcode解题思路分析（六十九）594 - 600 题

向右看齐 2022-11-09 15:29 170阅读 0赞

1.  最长和谐子序列  
    和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

**哈希表遍历一遍即可**

class Solution { 
    public:
        int findLHS(vector<int>& nums) 
        { 
            unordered_map<int, int> mp;
    		int ret = 0;
    
    		for (int i : nums) 
            { 
    			mp[i]++;
                
                if (mp.count(i - 1))
                { 
                    ret = max(ret, mp[i - 1] + mp[i]);
                }
    
                if (mp.count(i + 1))
                { 
                    ret = max(ret, mp[i] + mp[i + 1]);
                }
    		}
    
    		return ret;
        }
    };

1.  大的国家  
    如果一个国家的面积超过 300 万平方公里，或者人口超过 2500 万，那么这个国家就是大国家。编写一个 SQL 查询，输出表中所有大国家的名称、人口和面积。

**使用or或者Union即可**

select 
    	name, population,area 
    from 
    	World
    where 
    	area > 3000000 or population > 25000000;
    
    # Write your MySQL query statement below
    SELECT
        name, population, area
    FROM
        world
    WHERE
        area > 3000000
    
    UNION
    
    SELECT
        name, population, area
    FROM
        world
    WHERE
        population > 25000000
    ;

1.  超过5名学生的课  
    有一个courses 表 ，有: student (学生) 和 class (课程)。请列出所有超过或等于5名学生的课。

**使用group by语句做或者group by + having**

# Write your MySQL query statement below
    select 
        class 
    from 
        (select
            class, COUNT(distinct student) as num
        from
            courses
        group by class) as temp_table
    where 
        num >= 5
    ;
    
    
    # Write your MySQL query statement below
    SELECT
        class
    FROM
        courses
    GROUP BY class
    HAVING COUNT(DISTINCT student) >= 5
    ;

1.  范围求和2

给定一个初始元素全部为 0，大小为 m\*n 的矩阵 M 以及在 M 上的一系列更新操作。

操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b 的数组表示，含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M\[i\]\[j\] 的值都增加 1。

在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。

**因为每次都会覆盖0，0并且包含了Ops为边界的值，因此求Ops的最小值即可**

class Solution { 
    public:
        int maxCount(int m, int n, vector<vector<int>>& ops) 
        { 
            for (auto op: ops) { 
                m = min(m, op[0]);
                n = min(n, op[1]);
            }
            return m * n;  
        }
    };

1.  列表  
    假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。

**用一个哈希表存储第一个列表的索引，第二个链表再遍历一遍即可**

class Solution { 
    public:
        vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) 
        { 
            int index = 0, sum = 0;
            std::vector<string> ret;
            int indexSum = INT_MAX;
            std::unordered_map<string, int> m_cnt;
    
            for (int i = 0; i < list1.size(); i++)
            { 
                m_cnt[list1[i]] = i + 1;
            }
    
            for (int i = 0; i < list2.size(); i++)
            { 
                index = m_cnt[list2[i]];
                if (index > 0)
                { 
                    sum = i + index - 1;
                    if (sum < indexSum)
                    { 
                        indexSum = sum;
                        ret.clear();
                        ret.push_back(list2[i]);
                    }
                    else if (sum == indexSum)
                    { 
                        ret.push_back(list2[i]);
                    }
                }
            }
    
            return ret;
        }
    };

1.  不含连续1的非负整数

**从 numnum 的最高位开始考虑，对于第 ii 个位置遇到的 11 （从低位序号为 0 开始考虑），我们将答案加 f\[i\]f\[i\] ，对每个遇到的 00 ，我们不给答案加任何值。我们还要记录上一个位置的数值为多少，一旦我们发现连续的 1 ，我们将第二个 1 变成 0 的影响考虑后即停止遍历。如果我们没有遇到连续的 1 ，我们一直遍历到最低位并将最终答案加 1 ，表示 numnum 也是合法数字，因为上述过程并没有考虑 numnum 进去。**

class Solution { 
    public:
        int findIntegers(int num) { 
            int f[32];
            f[0] = 1;
            f[1] = 2;
            for (int i = 2; i < 32; i++)
                f[i] = f[i - 1] + f[i - 2];
            int i = 30, sum = 0, prev_bit = 0;
            while (i >= 0) { 
                if ((num & (1 << i)) != 0) { 
                    sum += f[i];
                    if (prev_bit == 1) { 
                        sum--;
                        break;
                    }
                    prev_bit = 1;
                } else
                    prev_bit = 0;
                i--;
            }
            return sum + 1;
        }
    };

1.  体育馆的人流量  
    编写一个 SQL 查询以找出每行的人数大于或等于 100 且 id 连续的三行或更多行记录。

# Write your MySQL query statement below
    select distinct t1.*
    from stadium t1, stadium t2, stadium t3
    where t1.people >= 100 and t2.people >= 100 and t3.people >= 100
    and
    (
    	  (t1.id - t2.id = 1 and t1.id - t3.id = 2 and t2.id - t3.id =1)  -- t1, t2, t3
        or
        (t2.id - t1.id = 1 and t2.id - t3.id = 2 and t1.id - t3.id =1) -- t2, t1, t3
        or
        (t3.id - t2.id = 1 and t2.id - t1.id =1 and t3.id - t1.id = 2) -- t3, t2, t1
    )
    order by t1.id
    ;