leetcode-每日一题

每日一题

336.回文对

题目比较简单，上来可以先判断两个拼接好的字符串是否符合，然后遍历判断。

class Solution {
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        int len=words.size();
        vector<vector<int>> all;
        for(int i=0;i<len;i++)
        {
            for(int j=0;j<len;j++)
            {
                if(i!=j&&Judge(words[i],words[j]))
                {
                    vector<int> temp;
                    temp.push_back(i);
                    temp.push_back(j);
                    all.push_back(temp);
                }
            }
            
        }
        return all;


    }
    bool Judge(string& w1,string& w2)
    {
        string str = w1+w2;
        int len = str.size();
        for(int i=0;i<len;i++)
        {
            if(str[i]!=str[len-1-i])
                return false;
        }
        return true;
    }
};

提交结果，有一半能够通过，其他的超出了时间限制。看到题解说不能直接用str = w1+w2;，移动指针会快一些。

bool Judge(string& w1,string& w2)
{
    int len1 = w1.size();
    int len2 = w2.size();
    int len = len1 +len2;
    int i;
    
    for(i=0;i<len/2;i++)
    {
        if(len1>len2)
        {
            if(i<len2)
            {
                if(w1[i]!=w2[len2-1-i])
                return false;
            }
            else
            {
                if(w1[i]!=w1[len-1-i])
                return false;
            }
        }
        else
        {
            if(i<len1)
            {
                if(w1[i]!=w2[len2-1-i])
                return false;
            }
            else
            {
                if(w2[i-len1]!=w2[len2-1-i])
                return false;
            }
        }
            
    }
    return true;
}

执行结果：通过
执行用时：1528 ms, 在所有 C++ 提交中击败了7.14%的用户。
内存消耗：21.6 MB, 在所有 C++ 提交中击败了100.00%的用户。

另一个方法使用 manacher算法，竞赛难度就算了。只能做人下人了，哈哈。

后面评论实在太逗了。

100. 相同的树

很简单的一道题，直接递归调用判断就行

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p!=nullptr&& q!=nullptr)
        {
            return p->val==q->val&&isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);             
        }
        else if(p==nullptr && q== nullptr)
            return true;
        else 
            return false; 
    }
};

226. 翻转二叉树

easy 递归交换左右节点。

344. 反转字符串

遍历头尾交换。

142. 环形链表 II

1. 暴力搜索 O($n^2$)
2. hash表
3. 利用快慢指针，快指针每次走两步，慢指针每次走一步。

416. 分割等和子集

• 美好的一天从每日一题结束
• 动态规划，可以转化为0-1背包问题。
• 对每一个数，都可以选择取和取。
• 转移方程
  $dp[i][j]=\begin{cases} dp[i-1][j]|dp[i-1][j-nums[i]],&{if}&{j}≥{nums[i]}\\ dp[i-1][j],&{if}&{j}<{nums[i]} \end{cases}$
  dp[i][j] 表示从数组的[0,i] 下标范围内选取若干个正整数（可以是0个），是否存在一种选取方案使得被选取的正整数的和等于j。

0-1 背包问题

给定 n 种物品和一个容量为 C 的背包，物品 i 的重量是 wi，其价值为 vi 。
问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？

• 声明一个 大小为 m[n][c] 的二维数组，m[ i ][ j ] 表示 在面对第 i 件物品，且背包容量为 j 时所能获得的最大价值
• 状态转移方程：
  $m[i][j]=\begin{cases} max(m[i-1][j],m[i-1][j-w[i]]+v[i]),&{if}&{j}≥{w[i]}\\ m[i][j]=m[i-1][j],&{if}&{j}<{w[i]} \end{cases}$

530. 二叉搜索树的最小绝对差

中序遍历可以得到二叉搜索树值的有序序列，元素的最小绝对差一定是相邻两个元素之间的。last记录上次的值，与本次的值求绝对差，边遍历边更新最小绝对差，

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        {
            MidTra(root);
            return _min;
        }

    }
private:
    int last = -1;
    int _min = INT_MAX;
    void MidTra(TreeNode* root)
    {
        if(root!=NULL)
        {
            MidTra(root->left);
            if(last!=-1)
            {
                _min=min(_min,root->val-last);
                last=root->val;
            }
            else
            {
                last = root->val;
            }
            MidTra(root->right);
        }
    } 
};

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

easy难度，就是简单的链表节点交换问题。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
            return head;
        ListNode *first = head,*second = head->next,*ret = head->next,*last =nullptr;
        while(first && second)
        {
            ListNode *temp = second->next;
            second->next = first;
            first->next =nullptr;
            if(last!=nullptr)
                last->next = second;
            last = first;
            first = temp;
            if(first!=nullptr)
            {
                second = first->next;
                if(second==nullptr)
                    last->next = first;
            }
            else
                break;
        }
        return ret;  
    }
};

1002. 查找常用字符

• 设置一个长度26的vector存储每个字符串中各个字符的计数。
• 遍历整个字符串向量，分别每个字符串中的字符个数进行计数。
• 取所有vector的交集（对于字符计数不同的，取此字符较小的计数）

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        if(A.size()==0)
            return vector<string>();
        vector<int> cnt(26,0); 
        for(auto ch :A[0])
             cnt[ch-'a']++;
        for(int i=1;i<A.size();i++)
        {
            vector<int> ths(26,0);
            for(auto ch :A[i])
            {
                ths[ch-'a']++;
            }
            for(int i=0;i<26;i++)
                if(cnt[i]!=ths[i])
                    cnt[i]=min(cnt[i],ths[i]); 
        }
        vector<string> ret;
        for(int i=0;i<26;i++)
        {
            while(cnt[i])
            {
                ret.push_back(string(1,'a'+i));
                cnt[i]--;
            }
        }
        return ret;
    }
};

116. 填充每个节点的下一个右侧节点指针

• 可以采取先序遍历的思想

• 对于每个节点root，如果有左子节点 root->left，那么左子节点的next是右子节点，root->left->next = root->right

• 如果有右子节点（有左定有有）root->right，右子节点的next是

  • 若root的next节点不为空，右子节点的next是root->next的左子节点，root->right->next = root->next->left
  • 若root的next节点为空，右子节点的next是NULL,root->right->next = NULL

• 本题很容易想到使用额外的队列进行树的层次遍历，在此我们可以省略掉这个额外的队列进行循环的层次遍历。

• next的赋值操作和上一个递归的一致

• 对于每一层，我们进行下一层的next的赋值操作。我们利用上层对本层完成的next的赋值从左到右对每个节点进行遍历，完成对每个节点的子节点的next的赋值操作，完成全部子节点后进入下一层。继续进行。

class Solution {
public:
    Node* connect(Node* root) {
        Pre(root);
        return root;
        
    }
    void Pre(Node *root)
    {
        if(root)
        {
            if(root->left)
                root->left->next = root->right;
            if(root->right)
            {
                if(root->next)
                    root->right->next = root->next->left;
                else
                    root->right->next = NULL;
            }
            Pre(root->left);
            Pre(root->right); 
        }
    }
};

977. 有序数组的平方

easy

19. 删除链表的倒数第N个节点

快慢指针，第一个指针先前进N个节点，然后两个指针一起前进，知道第一个指针到达链表的尾部。

844. 比较含退格的字符串

• 第一次遍历，将需要退格的字符换成’#’, 第二次遍历，判断连个字符串是否相同。
• 利用栈，遍历对于字符，将字符压入栈中，对于退格符，将栈顶的字符从栈中取出，完成之后，再比较两个栈中的内容。

143. 重排链表

• 用递归做思路不难，结束条件有点麻烦。
• 先到达链表的最后一个，将其插入到相应的位置后返回，再到前一个判断后插入，持续如此，到达结束条件之后，直接返回。

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head)
            return;
        cur = head;
        ret = false;
        inser(head->next);
    }
    ListNode *cur=nullptr;
    bool ret;
    void inser(ListNode *node)
    {
        if(!node)
        {
            return;
        }
        inser(node->next);
        if(ret)
            return;
        if(node->next==nullptr)
        {
            if(cur->next!=node)
                node->next = cur->next;
            cur->next = node;
        }
        else if(node->next == cur->next)
        {
            cur = cur->next->next;

            if(cur==node||cur->next == node)
            {
                node->next=nullptr;
                ret = true;
            }
            else
            {
                node->next = cur->next;
                cur->next = node;
            }
        }
    }
};

• 可以先找链表中点，使用快慢指针，慢指针走一步，快指针走两步。slow = slow->next, fast = fast->next->next;
• 将后半部分链表逆序排序
• 合并两个链表

925. 长按键入

• 使用两个指针，分别指向两个字符串，然后就很显然了。。。。

763. 划分字母区间

• 遍历字符串，进行分段。设置一个位置P用作新段的开始，一个栈S用作记录分段
• 找到当前位置 i 的字符出现在字符串中的最后一次出现的位置 E，
  • 如果当前字符是一个新段的开始，压入 E-i+1 然后 P = E+1
  • 否则，判断这个位置E和新段开始P的大小，如果大于或等于P，将栈顶的分段大小加上 E-P+1 然后 P=E+1

1. 第二步中找字符出现的字符串中的最后一次出现的位置 E 时，可以用字典或HASH表遍历一遍字符串提前记录下来。 这样时间复杂度就是$O(n)$,而不是$O(n^2)$
2. 可以使用双指针代替使用栈。

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int len = S.size();
        int start = 0;
        int dict[26]={0};
        stack<int> sta;
        for(int i=len-1;i>=0;i--)
        {
            dict[S[i]-'a'] = dict[S[i]-'a']>0?dict[S[i]-'a']:i;
        }
        for(int i=0;i<len;i++)
        {
            int j=dict[S[i]-'a'];
            if(i==start)
            {
                sta.push(j-start+1);
                start = j+1;
            }
            else
            {
                if(j>=start)
                {
                    int pre = sta.top();
                    sta.pop();
                    sta.push(pre + j-start+1);
                    start = j+1;
                }
            }
        }
        vector<int> v(sta.size());
        for(auto &vi:v)
        {
            vi = sta.top();
            sta.pop();
        }
        reverse(v.begin(),v.end());
        return v;  
    }
};

第一次medium运行时间0ms,超过100%还是挺开心的。

234. 回文链表

• 首先快慢指针找到链表中间节点。
• 反转其中一半链表
• 比较

其中第一步和第二步可以合并，在寻找链表中间节点的时候可以将前半部分的链表反转，之后就可以直接比较了。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow = head,*fast = head;
        ListNode *tail = NULL;
        while(fast&&fast->next)
        {
            ListNode *temp = slow;
            slow = slow->next;
            fast = fast->next->next;
            temp->next = tail;
            tail = temp;
        }
        if(fast)
            slow = slow->next;
        while(tail && slow)
        {
            if(tail->val!=slow->val)
                return false;
            tail = tail->next;
            slow  = slow->next;
        }
        return true;
    }
};

1024. 视频拼接 （2020-1024？）

• 可使用贪心算法或动态规划,本题使用贪心算法最优
• 动规：$dp[j] = min(dp[j],dp[i]+1)$
• 动规和贪心前半部分结合

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        vector<int> dt(T,0);
        vector<int> dp(T+1,-1);
        for(auto c :clips)
        {
            if(c[0]<T&&c[1]>dt[c[0]])
                dt[c[0]] = c[1];
        }
        for(int i=0;i<=dt[0]&&i<=T;i++)
            dp[i] = 1;
        for(int i=1;i<T;i++)
        {
            if(dp[i]<0)
                return -1;
            if(dt[i]>i)
            {
                for(int j=i+1;j<=dt[i] &&j<=T;j++)
                {
                    if(dp[j]>0)
                        dp[j] = min(dp[j],dp[i]+1);
                    else
                        dp[j] = dp[i]+1;
                }
            }
        }
        return dp[T];
    }
};

• 贪心：先记录每个位置能到达的最远点。遍历，记录当前能到达的最远点far，和当前使用段的结束点ed。进行判断，结束或记录所使用的最少段cnt

for (int i = 0; i < T; i++) 
{
    far = max(far, dt[i]);
    if (i == far) 
        return -1;
    if (i == ed) 
    {
        cnt++;
        ed = far;
    }
}

845. 数组中的最长山脉

• 今天是中等难度，不过感觉像是简单的题目。
• 从0开始，然后判断就行了。每次在中间记录一下山顶，确定不是只有上坡或者下坡。

class Solution {
public:
    int longestMountain(vector<int>& A) {
        int len = A.size();
        int i=0,start=0,max=0,heil=0;
        while(i<len)
        {
            start = i;
            while(i+1<len &&A[i+1]>A[i]) i++;
            int mid = i;
            while(i+1<len &&A[i+1]<A[i]) i++;
            if(i==start)
            {
                i++;
            }
            else
            {
                if(i>mid&&mid>start&& max<i-start+1)
                    max = i-start+1;
            }    
        }
        return max;

    }
};

1365. 有多少小于当前数字的数字

• 计数排序，然后统计

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        int dict[101]={0};
        for(auto n:nums)
        {
            dict[n]++;
        }
        for(int i=1;i<101;i++)
        {
            dict[i]+=dict[i-1];
        }
        vector<int> ret(nums);
        for(auto &r:ret)
        {
            if(r!=0)
                r=dict[r-1];
        }
        return ret;
    }
};

144. 二叉树的前序遍历

• 非递归遍历，while + stack

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> v;
        while(root||!s.empty())
        {
            if(root)
            {
                v.push_back(root->val);
                s.push(root);
                root = root->left;
            }
            else
            {
                TreeNode *temp = s.top();
                s.pop();
                root = temp->right;
            }
        }
        return v;
    }
};

1207. 独一无二的出现次数

• 对输入数组进行计数
• 对计数的数组进行排序
• 相邻两个数比较，如果有相同的就表明出现次数不是独一无二的

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        vector<int> cnt(2001);
        for(int i=0;i<arr.size();i++)
        {
            if(arr[i]>=0)
                cnt[arr[i]]++;
            else
                cnt[2001+arr[i]]++;
        }
        sort(cnt.begin(),cnt.end());
        for(int i=0;i<2000;i++)
        {
            if(cnt[i]!=0 &&cnt[i]==cnt[i+1])
                return false;
        }
        return true;

    }
};

第二、三步也进行一次计数

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        vector<int> cnt(2001);
        vector<int> dt(1001);
        for(int i=0;i<arr.size();i++)
        {
            if(arr[i]>=0)
                cnt[arr[i]]++;
            else
                cnt[2001+arr[i]]++;
        }
        for(int i=0;i<2001;i++)
        {
            dt[cnt[i]]++;
            if(dt[cnt[i]]>1 &&cnt[i]!=0)
                return false;

        } 
        return true;
    }
};

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

• 递归求和

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return Func(root,0);
    }
private:
    int Func(TreeNode *root,int num)
    {
        if(!root)
            return 0;
        num = num*10 +root->val;
        if(root->left==NULL&&root->right==NULL)
        { 
            return num;
        }
        else 
            return Func(root->left,num)+Func(root->right,num);
    }
};

463. 岛屿的周长

• 从左往右，从上往下遍历即可
• 如果地图是一个岛屿，周长 +4 ，如果这个岛屿左边也是岛屿，周长 -2，如果这个岛屿上方也是岛屿，周长 -2，

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int rows = grid.size();
        if(rows==0)
            return 0;
        int cols = grid[0].size();
        int sum = grid[0][0]*4;
        for(int j=1;j<cols;j++)
        {
            if(grid[0][j]==1)
            {
                sum+=4;
                if(grid[0][j-1]==1)
                    sum-=2;
            }
        }        
        for(int i=1;i<rows;i++)
        {
            if(grid[i][0]==1)
            {
                sum += grid[i][0]*4;
                if(grid[i-1][0]==1)
                    sum-=2;
                
            }
            for(int j=1;j<cols;j++)
            {
                if(grid[i][j]==1)
                {
                    sum+=4;
                    if(grid[i][j-1]==1)
                        sum-=2;
                    if(grid[i-1][j]==1)
                        sum-=2;
                }

            }
        }
        return sum;
    }
};