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.25LeetCode
leetcode
7 分钟 读完 (大约 1114 个字)

4.25LeetCode

总结： 昨天晚上被蚊子咬到睡不着觉，好不容易进入梦乡，恍惚间又听到噗通一声，我当时就料想到是手机掉到床柜后面去了，于是早上七点多钟又爬起来翻箱倒柜找手机关闹钟。
所以意料当中地今天上午下午摸鱼只做了三条题目，都是比较ez的，晚上划水搭建了下博客。

701. Insert into a Binary Search Tree

Given the root node of a binary search tree (BST) and a value to be inserted into the tree, insert the value into the BST. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Note that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

For example,

Given the tree:

    4
   / \
  2   7
 / \
1   3

And the value to insert: 5

You can return this binary search tree:

     4
   /   \
  2     7
 / \   /
1   3 5

This tree is also valid:

     5
   /   \
  2     7
 / \   
1   3
     \
      4

解答:
方案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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) return new TreeNode(val);
        if(val > root->val){
            if(root->right==nullptr)  root->right=new TreeNode(val);
            else  insertIntoBST(root->right,val);            
        }
        else if(val < root->val){
            if(root->left==nullptr)  root->left=new TreeNode(val);
            else insertIntoBST(root->left,val);            
        }
        return root;
    }
};

方案2 迭代求解，用时明显短于递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) return new TreeNode(val);
        TreeNode *p=root;
        while(1){
            if(val<p->val&&p->left)
                p=p->left;
            else if(val>p->val&&p->right)
                p=p->right;
            else break;
        }
        if(p->val <val) p->right=new TreeNode(val);
        else p->left=new TreeNode(val);
        return root;
    }
};

原题中特地强调，可以改变树的结构，但是相对来说比较复杂，翻了翻评论区并没有这么写的解答，我思考了下，感觉与平衡二叉树的删除类似，在找到其应该插入位置后根据是否存在左右子树分类谈论。二叉树实在是太复杂啦！

235. Lowest Common Ancestor of a Binary Search Tree

  1. 二叉搜索树的最近公共祖先
    Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note:

All of the nodes’ values will be unique.
p and q are different and both values will exist in the BST.

解法： 递归实在是太好写啦，主要注意其二叉搜索树的特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return nullptr;
        if(p->val<root->val && q->val>root->val) return root;
        if(p->val>root->val && q->val<root->val) return root;
        if(p==root||q==root) return root;
        if(p->val<root->val && q->val<root->val) return lowestCommonAncestor(root->left,p,q);
        if(p->val>root->val && q->val>root->val) return lowestCommonAncestor(root->right,p,q);
        return root;
    }
};

589. N-ary Tree Preorder Traversal

  1. N叉树的前序遍历

一开始写了个递归版本，发现速度很慢，想写迭代版本，但是感觉和二叉树又不太一样 参考了下评论区大神的思路 豁然开朗 随便写写写下来，
发现时间还是特别高！ 非常生气地拿了80ms的源码来跑，结果虽然比我的好，还是很高。 就有点懵逼了。

感觉这个迭代写法还是可以学习一下，和之前常写的二叉树的前序遍历迭代版本不太相同。（对栈的使用）

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
75
76
77
78
79
80
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
// class Solution {
// public:
//     vector<int> preorder(Node* root) {
//         vector<int> res;
//         help(root,res);
//         return res;
//     }
//     void help(Node* p,vector<int>& res){
//         if(!p) return;
//         res.push_back(p->val);
//         for(auto it:p->children)
//             help(it,res);
//     }
// };

// class Solution {
// public:
//     vector<int> preorder(Node* root) {
//         stack<Node*> stk;
//         vector<int> res;
//         if(!root) return res;
//         Node* p=root;
//         stk.push(p);
//         while(!stk.empty()){
//             p=stk.top();stk.pop();
//             res.push_back(p->val);
//             if(p->children.empty())
//                 continue;
//             else{
//                 for(auto it=p->children.rbegin();it!=p->children.rend();it++)
//                     stk.push(*it);
//             }
//         }
//         return res;

        
//     }
// };



class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> res;
        if(root == nullptr) return res;
        
        stack<Node*> st;
        
        st.push(root);
        
        while(!st.empty())
        {
            Node* t = st.top();
            st.pop();
            res.push_back(t->val);
            for(auto r = t->children.rbegin(); r != t->children.rend(); r++)
            {
                st.push(*r);
            }
        }
        
        return res;
    }
};

关注我

链接

分类

标签云

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

×