力扣Day1

没有对象可以自己new一个

今天下午2h+晚上近3h刷了14道，5道easy+8道medium+1道hard，算复健吧，记录下一些收获(不一定对大多数人适用！)

力扣是真逆天，byd很多时候定义全局数组，他运行的时候好像是循环运行，所以每次使用前记得memset，太tmSB了

(easy)88. 合并两个有序数组

亮点：好像没啥亮点 其实就是一个简单的数组插入，不过逆向指针倒是一个不错的思路(指从尾部开始，比较两个数组哪个更大，更大的就放最后)，代码如下(丑，无所谓码风了):

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int num1 = m - 1;
        int num2 = n - 1;
        int nowpos = m + n - 1;
        while(nowpos >= 0)
        {
            if(num1 < 0)
            {
                if(num2 >= 0)
                {
                    nums1[nowpos] = nums2[num2];
                    nowpos = nowpos - 1;
                    num2 = num2 - 1;
                }
            }
            else if(num2 < 0)
            {
                if(num1 >= 0)
                {
                    nums1[nowpos] = nums1[num1];
                    nowpos = nowpos - 1;
                    num1 = num1 - 1;
                }
            }
            else if(nums1[num1] > nums2[num2])
            {
                nums1[nowpos] = nums1[num1];
                num1 = num1 - 1;
                nowpos = nowpos - 1;
            }
            else
            {
                nums1[nowpos] = nums2[num2];
                num2 = num2 - 1;
                nowpos = nowpos - 1;
            }
        }
    }
};

(easy)27. 移除元素

亮点：初始思路就是当!=val的时候存到新数组里面完事，但要求了必须仅使用 O(1) 额外空间并 原地 修改输入数组 , 那就得重新思考新思路了；后面想到新数组不一定需要真建立，只需要记录位置，然后替换掉旧的。也算是个双指针？先用一个start1变量记录当前被替换位置，初始值为0；然后从0开始循环查找!=val的值，查到一个就存到start1，然后start1前进一位。代码如下：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int start1 = 0;
        for (int end1 = 0; end1 < n; end1++) {
            if (nums[end1] != val) {
                nums[start1] = nums[end1];
                start1++;
            }
        }
        return start1;
    }
};

(easy)26. 删除有序数组中的重复项

原理同上题，只不过需要每次更新val的值罢了。代码如下：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        int left = 0;
        int dup = -10001;
        for(int right = 0; right < n; right++)
        {
            if(nums[right] != dup)
            {
                dup = nums[right];
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
};

(medium)80. 删除有序数组中的重复项 II

原理也同上，只不过还要记录重复出现的次数，小于等于2次才管，大于直接不管。代码如下：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        int start1 = 0;
        int dup = -10001;
        int dup_num = 0;
        int num = 0;
        for(int i=0;i<n;i++)
        {
            if(nums[i] != dup)
            {
                dup = nums[i];
                nums[start1] = nums[i];
                dup_num = 1;
                start1++;
            }
            else
            {
                if(dup_num < 2)
                {
                    nums[start1] = nums[i];
                    dup_num++;
                    start1++;
                }
            }
        }
        return start1;
    }
};

(easy)169. 多数元素

我的思路就是先排序然后找，找到一个出现次数＞[n/2]的就直接输出，因为是[n/2]，只可能有一个。普通代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        int k = n/2;
        sort(nums.begin(), nums.end());
        int dup = -1e9-1;
        int cnt = 0;
        for(int i=0;i<n;i++)
        {
            if(nums[i] == dup)
            {
                cnt++;
            }
            else
            {
                dup = nums[i];
                cnt = 1;
            }
            if(cnt > k)
                return dup;
        }
        return dup;
    }
};

进阶思路：因为是[n/2]次，那么将n分为两部分，众数a在第一堆里的个数是k1个，在第二堆里的个数是k2个，k1+k2>[n/2]，所以k1>[n/2]-k2，即k1必定为第一堆的众数；那么按照这个思路一直向下递归，直到长度为1的数堆，然后每堆比较自己左右两堆的众数哪个是自己的众数即可。因为每次分两份，然后每个众数都要和该数堆进行比较，所以效率为n logn，好像也不符合要求(坏)；想不出来所以去看题解了，看到:如果一个数组有大于一半的数相同，那么任意删去两个不同的数字，新数组还是会有相同的性质。 恍然大悟，正确性是因为删去两个不同数t1 t2，如果t2是众数，那么等于t2和不等于t2的数都少了1个，t2占整个的比例从t2/n变为(t2-1)/(n-2)，由于t2/n>1/2即2*t2>n，则2*t2-2>n-2即(t2-1)/(n-2)>1/2，正确性证明成功。那么这样就可以出现一个思路：先记录一个值作为删去的t1，然后记录t1出现次数的cnt值赋为1，如果顺序遍历到相同值则计数值cnt加1，遍历到不同的t2则减1，表示删去一个t1和t2；而当cnt为0时，表示需要一个新的t1，则把当前遍历的值作为t1，同时cnt重新置为1；最后剩下的t1则为众数，因为如果cnt为0则表示有出现同样次数的其他值，这与众数是不符的，即若cnt为0，则该数不可能为众数，代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        int k = n/2;
        int cnt = 0;
        int t1 = nums[0];
        for(int i=0; i<n ; i++)
        {
            if(nums[i] == t1)
            {
                cnt++;
            }
            else
            {
                if(!cnt)
                {
                    cnt = 1;
                    t1 = nums[i];
                }
                else
                    cnt--;
            }
        }
        return t1;
};

(medium)189. 轮转数组

最开始看标题以为是矩阵旋转，还在纸上算；后面看数据是一个数组，那就直接pos[i]=(i+k)%n就完事了。下标是从0开始所以记得+1.代码如下：

int after[100010];
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        for(int i=0;i<n;i++)
        {
            //pos[i]=(i+k)%n;
            after[(i+k+1)%n] = nums[i];
        }
        for(int i=0;i<n;i++)
            nums[i] = after[i+1];
        nums[n-1] = after[0];
    }
};

(easy)121. 买卖股票的最佳时机

很简单的思路，区间最大-最小。唯一需要注意点的就是当更新最小值时由于最大值不能在最小值前出现，所以要更新为当前值。代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minn = prices[0];
        int maxx = prices[0];
        int minn_date = 0;
        int maxx_date = 0;
        int profit = 0;
        int n = prices.size();
        for(int i=0;i<n;i++)
        {
            if(prices[i] >= maxx)
            {
                maxx_date = i;
                maxx = prices[i];
                if(maxx_date > minn_date)
                    profit = max(profit, (maxx - minn));
            }
            if(prices[i] <= minn)
            {
                minn_date = i;
                minn = prices[i];
                maxx = prices[i];
                maxx_date = i;
                if(maxx_date > minn_date)
                    profit = max(profit, (maxx - minn));
            }
        }
        return profit;
    }
};

(medium)122. 买卖股票的最佳时机 II

思路类似，只不过由于是利润总量最高，需要在检测到下跌的时候在之前的区间最高值抛出，仅此而已。（后面看题解发现收集所有上坡值确实是更简单的做法，但懒得改了）代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minn = prices[0];
        int maxx = prices[0];
        int minn_date = 0;
        int maxx_date = 0;
        int profit = 0;
        int n = prices.size();
        for(int i=0;i<n;i++)
        {
            if(prices[i] >= maxx)
            {
                maxx_date = i;
                maxx = prices[i];
                
            }
            else if(prices[i] < maxx)
            {
                if(maxx_date > minn_date)
                    profit += maxx - minn;
                minn_date = i;
                minn = prices[i];
                maxx = prices[i];
                maxx_date = i;
            }
            if(prices[i] <= minn)
            {
                minn_date = i;
                minn = prices[i];
            }
        }
        if(maxx_date > minn_date)
             profit += maxx - minn;
        return profit;
    }
};

(medium)55. 跳跃游戏

也是一道需要稍微思考下的题目，最开始我考虑深搜，直接记忆化跳到每个点之后能不能跳到终点的结果就行(1,0,-1)，但懒得写了(其实是觉得力扣这B平台不能自己处理输入很烦，我如果搜索每次还得把num数组传进来)。后面想动规，即dp[i]表示到第i个点之前所能跳至的最远距离；而当dp[i]<i时，表示永远无法跳至i点，那肯定失败了。代码如下：

int dp[10001];
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (i > dp[i])
                return 0;
            dp[i+1] = max(dp[i], i + nums[i]);
        }
        return 1;
    }
};

(medium)45. 跳跃游戏 II

思路同上，也是dp，dp[i]表示跳到i点所需要的最小次数，代码如下：

int dp[10010];
class Solution {
public:
    int jump(vector<int>& nums) {
        int num = 1e9;
        int n = nums.size();
        for(int i=0;i<n;i++)
            dp[i] = i;
        for(int i=0;i<n;i++)
        {
            if(dp[i]>num)
                continue;
            else
            {
                int g = dp[i] + 1;
                int end = i+nums[i];
                for(int j=i+1;j<=end && j < n;j++)
                {
                    if(dp[j] == 0)
                        dp[j] = g;
                    else
                        dp[j] = min(dp[j], g);
                }
            }
            num = min(num, dp[n-1]);
        }
        if(n == 1)
            return 0;
        return num;
    }
};

(medium)274. H 指数

看数据范围，data范围小于n的范围，一眼桶排序(最后看题解好像一堆人用二分？)。tong[i]记录的是引用次数≥i的论文数；代码如下：

int tong[1010];
class Solution {
public:
    int hIndex(vector<int>& citations) {
        memset(tong,0,sizeof(tong));
        int n = citations.size();
        int maxn = 0;
        for(int i=0;i<n;i++)
        {
            tong[citations[i]]++;
            maxn = max(maxn, citations[i]);
        }
        int ans = 0;
        for(int i=maxn;i>0;i--)
        {
            tong[i-1]=tong[i-1]+tong[i];
        }
        for(int i=0;i<=maxn;i++)
        {
            if(tong[i]>=i)
                ans = i;
        }
        return ans;
    }
};

(medium)238. 除自身以外数组的乘积

两个数组，分别遍历记录左边乘起来的值和右边乘起来的值，最后结果是左边的值*右边的值。这道题卡我最久的是这个傻逼非得要返回vector数组，搞的我调了半天才发现返回的是vector数组而不是普通数组。代码如下：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> l(n, 0), r(n, 0);
        vector<int> answer(n);
        l[0] = 1;
        r[n-1] = 1;
        for(int i=1;i<n;i++)
        {
            l[i] = nums[i-1] * l[i-1];
            r[n-i-1] = nums[n-i]*r[n-i]; 
        }
        for(int i=0;i<n;i++)
            answer[i] = l[i]*r[i];
        return answer;
    }
};

(medium)134. 加油站

这道题吃饭前做的，老实说没做出来。后面看题解才理解正解做法；主要是我一直是想用dp做，dp[i]表示从i点出发能到达的最远点，dp_spend[i]则表示从i出发到达最远点后剩的油，从后往前推，不知道为啥调炸了，刚好又到恰饭时间就不想调了(

正解则是类似贪心的思路：从头遍历，因为若能从x经过y到达z，则说明x到达y之前的燃料肯定是正的；而若x到达y之前燃料为正，但仍然无法到达z，则说明y肯定也无法到达z，所以下一个最优起点应当是第一个非负点，即若x到达y之前燃料就为负，则说明x过来的旅途是拖累了y，从y出发会更优。代码如下：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start = 0, total_gas = 0, current_gas = 0;
        int n=gas.size();
        for (int i = 0; i < n; ++i)
        {
            current_gas += gas[i] - cost[i];
            total_gas += gas[i] - cost[i];
            if (current_gas < 0)
            {
                //如果当前燃油<0，则从下个站点开始(不是从该站点开始是因为第一次小于0发生那必定表示当前到达站点gas-cost<0，不可能从该站点出发)
                start = i + 1;
                current_gas = 0;
            }
        }
        return total_gas >=0 ? start : -1;
    }
};

(hard)135. 分发糖果

不懂这题为啥会是hard。依然是个左右分开统计的思路，各取满足值，最后再取同时满足左右的最大值，加起来即可。代码如下：

int ans1[20010];
int ans2[20010];
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        for(int i=0;i<n;i++)
        {
            ans1[i] = 1;
            ans2[i] = 1;
        }
        for(int i=1;i<n;i++)
        {
            if(ratings[i] > ratings[i-1])
            {
                ans1[i] = ans1[i-1] + 1;
            }
            if(ratings[n-i-1] > ratings[n-i])
            {
                ans2[n-i-1] = ans2[n-i] + 1;
            }
        }
        int cnt = 0;
        for(int i=0;i<n;i++)
        {
            cnt = cnt + max(ans1[i],ans2[i]);
        }
        return cnt;
    }
};

总结

总体而言今天题难度不大，但有些思路确实忘了，确实得复健(