2019-05-03

leetcode

9 分钟读完 (大约 1361 个字)

5.3LeetCode

前两天放假，就没更新，每天也做不了几题，今天集中更新下。

步入五月，感觉生活正在逐渐变得紧凑，这学期的课程都还没咋学，还有三门实验课要应付，再加上最近开始看java了，所以以后刷题量可能会减少点，但肯定不会停下！
还有个问题就是，初级算法卡片刷完了，现在开始刷中级算法了，感觉好难啊！。。头秃。

15.3Sum

15.三数之和
C++.感觉好难啊！一开始不知道为什么总想着用map做，试了半天总是无法解决漏解的问题。。
看了答案才会做。
第一个是三指针的处理方式，将复杂度从O(n^3)降到了O(n^2)。学习了。
第二个是重复解的剔除，不需要通过set就可以实现。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        std::sort(nums.begin(),nums.end());
        vector<vector<int>> res; 
        int n=nums.size();
        for(int k=n-1;k>1;k--){
            int i=0,j=k-1;
            while(i<j){
                if(nums[i]+nums[j]+nums[k]>0) j--;
                else if(nums[i]+nums[j]+nums[k]<0) i++;
                else{
                    vector<int> temp={nums[i],nums[j],nums[k]};
                    res.push_back(temp);
                    while(i+1<n&&nums[i+1]==nums[i]) i++;
                    i++;
                    while(j-1>=0&&nums[j-1]==nums[j]) j--;
                    j--;
                }
            }
            while(k-1>=0&&nums[k-1]==nums[k]) k--;
        }
        return res;
    }
};

73. Set Matrix Zeroes

73.矩阵置零
之前看过这道题，大概知道不用额外空间思路，但是自己写起来又犯蠢了。。
用来做标志位的首行和首列不能先乱动(不然就全部变成0了)，，
解决方案是用两个bool去存是否要把首行首列变0

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean row=false,coloum=false;
        for(int j=0;j<matrix[0].length;j++)
            if(matrix[0][j]==0){
                row=true; break;
            }
        for(int i=0;i<matrix.length;i++)
            if(matrix[i][0]==0){
                coloum=true; break;
            }
        
        for(int i=0;i<matrix.length;i++)
            for(int j=0;j<matrix[0].length;j++)
                if(matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
        for(int i=1;i<matrix.length;i++)
            for(int j=1;j<matrix[0].length;j++)
                if(matrix[i][0]==0||matrix[0][j]==0)
                    matrix[i][j]=0;
        
        if(row)
            for(int j=0;j<matrix[0].length;j++)
                matrix[0][j]=0;
        if(coloum)
            for(int i=0;i<matrix.length;i++)
                matrix[i][0]=0;
        
    }
}

5. Longest Palindromic Substring

最长回文子串
这道题简直是剧毒。。做得我头都大了。昨天晚上做了俩小时，今天下午又看了俩小时做了三种方法，dp，中心拓展，马拉车算法

解法1：动态规划
二维动态规划，不看答案根本想不到。bobo

class Solution {
    public String longestPalindrome(String s) {
        String res=new String();
        int n=s.length();
        boolean[][] dp=new boolean[n][n];
        for(int i=0;i<n;i++)
            dp[i][i]=true;
        for(int i=0;i<n-1;i++){
            if(s.charAt(i)==s.charAt(i+1))
                dp[i][i+1]=true;
            else dp[i][i+1]=false;
        }
        for(int k=2;k<n;k++){
            for(int i=0;i<n-k;i++){
                if(dp[i+1][k+i-1]==true && s.charAt(i)==s.charAt(k+i))
                    dp[i][k+i]=true;
                else dp[i][k+i]=false;
            }
        }
        int flag=0;
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<n-i;j++)
                if(dp[j][i+j]==true){
                    flag=1;
                    res=s.substring(j,i+j+1);
                    break;
                }
            if(flag==1) break;
        }

        return res;
    }
}

解法2：中心拓展算法
比较容易理解，但是没想到当时。

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

解法3：马拉车算法
网上博客都看不太懂，说得都不是人话。。找了篇漫画感觉讲的还挺形象的，附上链接：
点击查看漫画

然后照着源码写了下java版本的，第一次用StringBuffer. sb哈哈哈。
感慨On复杂度确实比On^2快了好多……

class Solution {
    public String preHandle(String s){
        StringBuffer sb=new StringBuffer();
        sb.append('#');
        for(int i=0;i<s.length();i++){
            sb.append(s.charAt(i));
            sb.append('#');
        }
        return sb.toString();
    }
    public String longestPalindrome(String s) {
        String str=preHandle(s);
        int rightboard=0;
        int rightcenter=0;
        int[] halflen = new int[str.length()];
        int center=0;
        int maxlen=0;
        for(int i=0;i<str.length();i++){
            boolean needSearch=true;
            if(i<rightboard){
                int left=2*rightcenter-i;
                halflen[i]=halflen[left];
                if(i+halflen[i]>rightboard)
                    halflen[i]=rightboard-i;
                if(i+halflen[i]<rightboard)
                    needSearch=false;
            }
            if(needSearch){
                while(i-halflen[i]-1>=0 &&i+halflen[i]+1<str.length()){
                    if(str.charAt(i-halflen[i]-1)==str.charAt(i+halflen[i]+1)){
                        halflen[i]++;
                    }
                    else break;
                }
                rightboard=i+halflen[i];
                rightcenter=i;
                if(halflen[i]>maxlen){
                    center=i;
                    maxlen=halflen[i];
                }
            }

        }
        StringBuffer sb=new StringBuffer();
        for(int i = center - maxlen + 1; i <= center + maxlen; i += 2) {
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }
}

334. Increasing Triplet Subsequence

递增的三元子序列
挺有意思的一道题，想清楚就好了，只要记录当前最小值和某个子序列里第二大的数就可以了。

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums.length<3) return false;
        int low=Integer.MAX_VALUE, mid=Integer.MAX_VALUE;
        int i=0;
        while(i<nums.length){
            if(nums[i]<=low)
                low=nums[i];
            else if(nums[i]<mid)
                mid=nums[i];
            else if(nums[i]>mid) return true;
            i++;
        }
        return false;
    }
}

103. Binary Tree Zigzag Level Order Traversal

二叉树的锯齿形层次遍历
层次遍历的变种，没啥难度。

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res= new ArrayList<>();
        Stack<TreeNode> left=new Stack<>();
        Stack<TreeNode> right=new Stack<>();
        if(root==null) return res;
        right.push(root);
        boolean flag=true;
        while(!left.isEmpty() ||!right.isEmpty()){
            List<Integer> l=new ArrayList<>();
            if(flag){
                while(!right.isEmpty()){
                    TreeNode temp=right.pop();
                    l.add(temp.val);
                    if(temp.left!=null) left.push(temp.left);
                    if(temp.right!=null) left.push(temp.right);
                }
            }
            else
                while(!left.isEmpty()){
                    TreeNode temp=left.pop();
                    l.add(temp.val);
                    if(temp.right!=null) right.push(temp.right);
                    if(temp.left!=null) right.push(temp.left);
                }
            res.add(l);
            flag=!flag;
        }
        return res;
    }
}

230. Kth Smallest Element in a BST

二叉搜索树中第K小的元素
中序遍历即可。

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> list=new ArrayList<>();
        help(root,list,k);
        return (int)list.get(k-1);
        
    }
    public void help(TreeNode p,List<Integer> list,int k){
        if(p==null||k==0) return;
        help(p.left,list,k);
        k--;
        list.add(p.val);
        help(p.right,list,k);
    }
}

17. Letter Combinations of a Phone Number

电话号码的字母组合
发现之前好久没接触过回溯的题目了。。第一个想法就是for循环，但是不知道String的长度
偷看了评论区答案，用递归去写。。。没有必要记录步长、。

class Solution {
    public List<String> letterCombinations(String digits) {
        int n=digits.length();
        String s=new String();
        List<String> res=new ArrayList<>();
        if(n==0) return res;
        help(res,"",digits);
        return res;
    }
    private void help(List<String> list,String s,String digits){
        String[] reps={"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        if(s.length()==digits.length()){
            list.add(s); 
            return;
        }
        int n=s.length();
        String rep=reps[digits.charAt(n)-50];
        for(int i=0;i<rep.length();i++)
        {
            help(list,s+rep.charAt(i),digits);
        }
    }
}

22. Generate Parentheses

22.括号生成

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res=new ArrayList<>();
        if(n==0) return res;
        help(res,0,0,n,"");
        return res;
    }
    public void help(List<String> list, int left, int right,int n, String s){
        if(left==right&&left==n) {
            list.add(s);
            return;
        }
        if(left<n) help(list,left+1,right,n,s+'(');
        if(right<left) help(list,left,right+1,n,s+')');
        return;
    }
}

终于贴完了，收工！

2019-04-27

leetcode

6 分钟读完 (大约 835 个字)

4.27LeetCode

26. Remove Duplicates from Sorted Array

从排序数组中删除重复项
双指针法解决。当数值不同且不指向同一个时替换。写的有点丑陋，可以利用nums[i]的值去替代temp

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()) return 0; 
        int i=j=0;
        int temp=nums[i];
        int res=1;
        while(j<nums.size()){
            if(temp<nums[j]){
                res++;                
                if(i!=j)
                {
                    i++;
                    nums[i]=nums[j];
                }  
                temp=nums[j];
            }
            j++;
        }
        return res;
    }
};

121. Best Time to Buy and Sell Stock

买卖股票的最佳时机
动态规划前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        vector<int> dp;
        dp.resize(prices.size());
        dp[0]=0;
        int minp=prices[0];
        for(int i=1;i<prices.size();i++){
            if(prices[i]<=prices[i-1])
                dp[i]=dp[i-1];
            else if(prices[i]-minp>dp[i-1])
                dp[i]=prices[i]-minp;
            else dp[i]=dp[i-1];
            minp=min(minp,prices[i]);
        }
        return dp[prices.size()-1];
    }
};

122. Best Time to Buy and Sell Stock II

买卖股票的最佳时机 II
贪心没啥思路，偷看了评论区的答案：[7, 1, 5, 6] 第二天买入，第四天卖出，收益最大（6-1），所以一般人可能会想，怎么判断不是第三天就卖出了呢? 这里就把问题复杂化了，根据题目的意思，当天卖出以后，当天还可以买入，所以其实可以第三天卖出，第三天买入，第四天又卖出（（5-1）+ （6-5） === 6 - 1）。所以算法可以直接简化为只要今天比昨天大，就卖出。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        int res=0;
        int pricenow=prices[0];  //默认持有价格
        for(int i=1;i<prices.size();i++){   
            if(prices[i]<=pricenow)    //当天价格比你持有的低,直接放弃之前的
                pricenow=prices[i];
            else{
                res+=prices[i]-pricenow;
                pricenow=prices[i];
            }
        }
        return res;
    }
};

48. Rotate Image

旋转图像
虽然是道medium题，但是感觉其实也没很难。。想了很久才明白旋转规则。（四个结点旋转）

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        if(matrix.empty()) return;
        int n=matrix.size();
        for(int i=0;i<n/2;i++){
            for(int j=i;j<n-i-1;j++){
                int temp=matrix[i][j];
                matrix[i][j]=matrix[n-1-j][i];
                matrix[n-1-j][i]=matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j]=matrix[j][n-1-i];
                matrix[j][n-1-i]=temp;
            }
        }
        return;
    }
};

242. Valid Anagram

有效的字母异位词
建立字母表再比较。也可以用map去做。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int a[26]={0};
        int b[26]={0};
        for(int i=0;i<s.length();i++)
            a[s[i]-'a']++;
        for(int i=0;i<t.length();i++)
            b[t[i]-'a']++;
        for(int i=0;i<26;i++)
            if(a[i]!=b[i]) return false;
        return true;
    }
};

125. Valid Palindrome

验证回文串
双指针法，感觉贴题目好有成就感。。题目不难，比较繁琐的是大小写的转换以及干扰字符去除的写法。

class Solution {
public:
    bool isPalindrome(string s) {
        if(s.empty()) return true;
        int i=0,j=s.length()-1;
        while(i<j){
            while(1){
                if((s[i]>='0'&&s[i]<='9')||(s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')||i==j) break;
                i++;
            }
            while(1){
                if((s[j]>='0'&&s[j]<='9')||(s[j]>='a'&&s[j]<='z')||(s[j]>='A'&&s[j]<='Z')||i==j) break;
                j--;
            } 
            if(i==j) break;
            char p=s[i],q=s[j];
            if(p>='A'&&p<='Z') p+=32;
            if(q>='A'&&q<='Z') q+=32;
            if(p!=q) return false;
            i++;
            j--;
        }
        return true;
        
    }
};

8. String to Integer (atoi)

字符串转换整数 (atoi)
还是属于比较简单的medium主要考察一个细心把。。

class Solution {
public:
    int myAtoi(string str) {
        long long res=0;
        if(str.empty()) return 0;
        int i;
        for(i=0;i<str.length();i++)
            if(str[i]!=' ') break;
        if(i==str.length()||(str[i]<'0'&&str[i]!='-'&&str[i]!='+')||str[i]>'9') return 0;
        char temp=str[i];
        if(str[i]=='-'||str[i]=='+') i++;
        while(i<str.length()){
            if(str[i]>='0'&&str[i]<='9')
            {
                if(res>pow(2,31)-1) return temp=='-'?INT_MIN:INT_MAX;
                res=res*10+(int)(str[i]-'0');
                i++;
            }
            else break;
        }
        if(temp=='-') res=res*(-1);
        if(res>pow(2,31)-1) return INT_MAX;
        if(res<pow(2,31)*(-1)) return INT_MIN;
        return res;
    }
};

28. Implement strStr()

实现strStr()

// 我枯了，明明是道ez题，居然随便写写过不了。。。还要剪枝。。

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()) return 0;
        int n1=haystack.length(),n2=needle.length();
        if(n2>n1) return -1;
        int i=0;
        while(i+n2<=haystack.length()){
            int t=i;
            int j=0;
            for( j=0;j<needle.length();j++)
            {
                if(haystack[t]!=needle[j]) break;
                t++;
            }
            if(j==needle.length()) return i;
            i++;
        }
        return -1;
    }
};

Doctor-Do

努力奋斗的江湖小虾米

Kunshan,Jiangsu

文章

17

分类

5

标签

23

2020-01-17

200117

2020-01-16

写在2020的话

2019-05-09

5.9 LeetCode

2019-05-08

5.8 LeetCode

2019-05-07

5.7LeetCode

2020-01-17

200117

2020-01-16

写在2020的话

2019-05-09

5.9 LeetCode

2019-05-08

5.8 LeetCode

2019-05-07

5.7LeetCode

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now