4.29LeetCode
leetcode
6 分钟 读完 (大约 856 个字)

4.29LeetCode

说一下，今天开始代码尽量准备用java写了，感觉好不习惯。。

198. House Robber

  1. 打家劫舍
    比较简单的动态规划题目。
    dp[i]=max(dp[i-1],dp[i-2]+nums[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// dp[i]表示前n户并且抢劫过第n家的max，感觉自己想复杂了。。。也可以通过。
// class Solution {
// public:
//     int rob(vector<int>& nums) {
//         if(nums.empty()) return 0;
//         if(nums.size()==1) return nums[0];
//         if(nums.size()==2) return max(nums[0],nums[1]);
//         vector<int> dp;
//         dp.resize(nums.size());
//         dp[0]=nums[0]; dp[1]=nums[1]; dp[2]=nums[0]+nums[2];
//         for(int i=3;i<nums.size();i++)
//             dp[i]=max(dp[i-2]+nums[i],dp[i-3]+nums[i]);
//         return max(dp[nums.size()-1],dp[nums.size()-2]);
//     }
// };


class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        if(nums.size()==1) return nums[0];
        vector<int> dp;
        dp.resize(nums.size());
        dp[0]=nums[0]; dp[1]=max(nums[0],nums[1]);
        for(int i=2;i<nums.size();i++)
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        return dp[nums.size()-1];
    }
};

384. Shuffle an Array

  1. 打乱数组
    第一次写java，感觉好难啊。。踩了好多坑，数组的深浅拷贝和伪随机函数等等.. 慢慢学吧 注释的是评论区大佬的答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    int[] Arr;
    int[] Nature;
    public Solution(int[] nums) {
        Arr=nums;
        Nature= Arrays.copyOf(Arr, Arr.length);
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        for(int i=0;i<Arr.length;i++)
            Arr[i]=Nature[i];
        return Arrays.copyOf(Arr, Arr.length);
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        for(int i=Arr.length-1;i>0;i--){
            Random rand=new Random();
            int t=rand.nextInt(i+1); //随机数生成范围要注意
            int temp=Arr[t];
            Arr[t]=Arr[i];
            Arr[i]=temp;
        }
        return Arr;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */


// class Solution {
//     int[] nums;

//     public Solution(int[] nums) {
//         this.nums = nums;
//     }
    
//     /** Resets the array to its original configuration and return it. */
//     public int[] reset() {
//         return nums;
//     }
    
//     /** Returns a random shuffling of the array. */
//     public int[] shuffle() {
//         int[] result = Arrays.copyOf(nums, nums.length);
//         Random rand=new Random();
//         for(int i = nums.length - 1; i > 0; i--) {
//             int n = rand.nextInt(i + 1);
//             // swap n and i 
//             int tmp = result[n];
//             result[n] = result[i];
//             result[i] = tmp;
//         }
//         return result;
//     }
// }

412. Fizz Buzz

java:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> res=new ArrayList<String>();
        for(int i=1;i<=n;i++){
            if(i%3==0&&i%5==0)
                res.add("FizzBuzz");
            else if(i%3==0&&i%5!=0) res.add("Fizz");
            else if(i%5==0&&i%3!=0) res.add("Buzz");
            else res.add(Integer.toString(i));
        }
        return res;
    }
}

204. Count Primes

计数质数
一开始的想法就是判断从1-n的每个数是否为质数，时间复杂度O(n^2)
最简单的方法当然通过不了，参考了某大佬的一篇博客进行剪枝
附连接：判断一个数是不是质数(素数)，3种方式介绍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int countPrimes(int n) {
        int res=0;
        for(int i=1;i<n;i++)
            if(isPrime(i)) res++;
        return res;
        
    }
    public static boolean isPrime(int num) {
        if (num <= 3) {
            return num > 1;
        }
        // 不在6的倍数两侧的一定不是质数
        if (num % 6 != 1 && num % 6 != 5) {
            return false;
        }
        int sqrt = (int) Math.sqrt(num);
        for (int i = 5; i <= sqrt; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

}

然后根据题目下面的提示，了解了埃拉托色尼筛选法（质数问题）。唯一疑惑就是明明应该可以从i*i开始覆盖，不知道为什么总会报错说数组越界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countPrimes(int n) {
        if(n<3) return 0; 
        int res=0;
        int[] temp=new int[n];
        for(int i=0;i<n;i++)
            temp[i]=i;
        for(int i=2;i<n;i++){
            if(temp[i]==i){
                res++;
                for(int j=2;j*i<n;j++)
                    temp[j*i]=i;
            }
        }
        return res;
        
    }
}

326. Power of Three

递归解法很常规

1
2
3
4
5
6
7
class Solution {
    public boolean isPowerOfThree(int n) {
        if(n==1) return true;
        else if(n%3!=0||n==0) return false;
        else return isPowerOfThree(n/3);
    }
}

评论区大佬的两种解法：

1
2
3
4
5
6
7
class Solution {
    public boolean isPowerOfThree(int n) {
        String str=Integer.toString(n,3); //将n由十进制转化为3进制(java进制转换的写法，学到了)
        boolean result = str.matches("^10*$");//^表示正则开始，$表示正则结束,意思为匹配1开头中间可以无数个0的字符
        return result;
    }
}
1
2
3
4
5
class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467%n == 0;
    }
}

13. Roman to Integer

写得太丑陋了。。不忍直视。。。有空一定重新用switch写下。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
    public int romanToInt(String s) {
        int res=0;
        int i=0;
        while(i<s.length()){
            if(s.charAt(i)=='M') {
                res+=1000;
                i++;
                continue;
            }
            if(s.charAt(i)=='D'){
                res+=500;
                i++;
                continue;
            }
            if(s.charAt(i)=='C'){
                if(i+1<s.length()&&s.charAt(i+1)=='D'){
                    res+=400;
                    i+=2;
                }
                else if(i+1<s.length()&&s.charAt(i+1)=='M'){
                    res+=900;
                    i+=2;
                }
                else {
                    res+=100;
                    i++;
                }
                continue;
            }
            if(s.charAt(i)=='L'){
                res+=50;
                i++;
                continue;
            }
            if(s.charAt(i)=='X'){
                if(i+1<s.length()&&s.charAt(i+1)=='L'){
                    res+=40;
                    i+=2;
                }
                else if(i+1<s.length()&&s.charAt(i+1)=='C'){
                    res+=90;
                    i+=2;
                }
                else {
                    res+=10;
                    i++;
                }   
                continue;
            }
            if(s.charAt(i)=='V'){
                res+=5;
                i++;
                continue;
            }
            if(s.charAt(i)=='I'){
                if(i+1<s.length()&&s.charAt(i+1)=='V'){
                    res+=4;
                    i+=2;
                }
                else if(i+1<s.length()&&s.charAt(i+1)=='X'){
                    res+=9;
                    i+=2;
                }
                else {
                    res+=1;
                    i++;
                }       
                continue;
            }
        }
        return res;
    }
}

191. Number of 1 Bits

为什么java里面没有unsignedint啊？？？？？？
学了了评论区大佬的解法，体会了下n=n&(n-1)的妙用(每次可以消掉一个1).

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
         int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}
4.28LeetCode
leetcode
4 分钟 读完 (大约 544 个字)

4.28LeetCode

38. Count and Say

  1. 报数
    emmmmm.题目比较难读懂，读懂很简单啦。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    string countAndSay(int n) {
        string res="1";
        for(int i=1;i<n;i++)
            res=next(res);
        return res;
    }
    string next(string n) {
        int i=0;
        string res;
        while(i<n.length()){
            char temp=n[i];
            int num=1;
            while(1){
                if(i+1!=n.length()&&n[i+1]==n[i])
                {
                    num++; 
                    i++;
                }
                else break;
            }
            res+=to_string(num);
            res+=temp;
            i++;
        }
        return res;
    }
};

237. Delete Node in a Linked List

  1. 删除链表中的节点
    感觉还是思路被桎梏了哈哈，说到删除节点第一时间想的永远是让被删除的前一个结点next指向被删除的next，为什么不换个思路去重新生成从被删除开始之后的整个链表呢
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* p=node;
        while(p->next){
            p->val=p->next->val;
            p=p->next;
        } 
        while(node->next!=p)
            node=node->next;
        node->next=nullptr;
        return;
    }
};

88. Merge Sorted Array

  1. 合并两个有序数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=0,j=0;
        vector<int> temp;
        while(i<m&&j<n){
            if(nums1[i]<=nums2[j])
            {
                temp.push_back(nums1[i]);
                i++;
            }else{
                temp.push_back(nums2[j]);
                j++;
            }
        }
        if(i!=m){
            while(i!=m){
                temp.push_back(nums1[i]);
                i++;               
            }
        }
        if(j!=n){
            while(j!=n){
                temp.push_back(nums2[j]);
                j++;                
            }
        }
        i=0;
        for(int it:temp){
            nums1[i]=it;
            i++;
        }
        return;
    }
};

70. Climbing Stairs

爬楼梯
斐波那契数列。。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int climbStairs(int n) {
        if(n==1) return 1;
        vector<int> dp;
        dp.resize(n);
        dp[0]=1;dp[1]=2;
        for(int i=2;i<n;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[n-1];
    }
};

53. Maximum Subarray

  1. 最大子序和
    这题实在是太难了。。。想了一上午都没想明白，说到底还是自己太菜了。。。到现在也只是勉强能理解标准答案。
    评论区大佬解答：这道题难度不该是easy 这道题的一开始我想到的是暴力的滑窗去做，复杂度O(n^2)，显然达不到题目中要求的复杂度 这道题根据题目关键词，“最大”“连续”，可以判断是一道动态规划，附上这道题目的wiki链接https://zh.wikipedia.org/wiki/%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E5%88%97%E9%97%AE%E9%A2%98 方法如下：
    1.定义一个函数f(n)，以第n个数为结束点的子数列的最大和，存在一个递推关系f(n) = max(f(n-1) + A[n], A[n]);
    2.将这些最大和保存下来后，取最大的那个就是，最大子数组和。因为最大连续子数组 等价于 最大的以n个数为结束点的子数列和 
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int tempmax,res;
        res=nums[0];
        tempmax=0;
        for(int i=0;i<nums.size();i++){
            tempmax=max(tempmax+nums[i],nums[i]);
            res=max(res,tempmax);
        }
        return res;
    }
};
4.27LeetCode
leetcode
6 分钟 读完 (大约 835 个字)

4.27LeetCode

26. Remove Duplicates from Sorted Array

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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天中的最小价格}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

  1. 买卖股票的最佳时机 II
    贪心没啥思路，偷看了评论区的答案：[7, 1, 5, 6] 第二天买入，第四天卖出，收益最大（6-1），所以一般人可能会想，怎么判断不是第三天就卖出了呢? 这里就把问题复杂化了，根据题目的意思，当天卖出以后，当天还可以买入，所以其实可以第三天卖出，第三天买入，第四天又卖出（（5-1）+ （6-5） === 6 - 1）。所以算法可以直接简化为只要今天比昨天大，就卖出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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题，但是感觉其实也没很难。。想了很久才明白旋转规则。（四个结点旋转）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

  1. 有效的字母异位词
    建立字母表 再比较。 也可以用map去做。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

  1. 验证回文串
    双指针法，感觉贴题目好有成就感。。题目不难，比较繁琐的是大小写的转换以及干扰字符去除的写法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)

  1. 字符串转换整数 (atoi)
    还是属于比较简单的medium主要考察一个细心把。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 我枯了，明明是道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;
    }
};
关注我

链接

分类

标签云

ASR C++ DFS Java N叉树 SR/LID java n叉树 二叉搜索树 位运算 前缀树 动态规划 双指针 合并排序 回溯 字符串 排序搜索 数组 算法 贪心算法 递归迭代 链表 随便写写

最新文章

归档

标签

ASR 1
C++ 3
DFS 1
Java 1
N叉树 1
SR/LID 1
java 1
n叉树 1
二叉搜索树 1
位运算 1
前缀树 1
动态规划 5
双指针 2
合并排序 1
回溯 1
字符串 1
排序搜索 1
数组 3
算法 1
贪心算法 1
递归迭代 1
链表 1
随便写写 2

最新文章

归档

标签

ASR 1
C++ 3
DFS 1
Java 1
N叉树 1
SR/LID 1
java 1
n叉树 1
二叉搜索树 1
位运算 1
前缀树 1
动态规划 5
双指针 2
合并排序 1
回溯 1
字符串 1
排序搜索 1
数组 3
算法 1
贪心算法 1
递归迭代 1
链表 1
随便写写 2
Your browser is out-of-date!

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

×