Welcome to LeaCoder's Blog!

持之以恒终有收获，自律自强方至成功

LeetCode-169-求众数(-Majority-Element)

2019-03-28

leacoder

Algorithm

Algorithm Leetcode

求众数
Python3 实现

求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

Python3 实现

排序法

# @author:leacoder
# @des:  排序法 求众数  时间复杂度 O（nlg(n)）

class Solution:
    def majorityElement(self, nums: List[int]) -> int: 
        nums.sort()
        return nums[int(len(nums)/2)]  #条件>n/2，所以排序后，中间元素一定是众数

dic计数

# @author:leacoder
# @des:  dic 求众数

class Solution:
    def majorityElement(self, nums: List[int]) -> int: 
        dic = {}
        for num in nums:
            if num in dic:
                dic[num] = dic[num]+1
            else:
                dic[num] = 1
        length = len(nums)
        for num in dic:
            if dic[num]>int(length/2):
                return num

摩尔投票法

# @author:leacoder
# @des:  摩尔投票法 求众数

class Solution:
    def majorityElement(self, nums: List[int]) -> int: 
        moore = 0
        count = 0
        for num in nums:  #由于给定的数组总是存在众数。 众数 与 非众数 抵消后最后 count必然>0
            if count == 0:
                moore = num #最终 moore 存放的就是众数
            if num == moore:
                count +=1  #重复一次 +1
            else:
                count -=1 #出现其他数据 -1
        return moore

GitHub链接： https://github.com/lichangke/LeetCode

知乎个人首页： https://www.zhihu.com/people/lichangke/

简书个人首页： https://www.jianshu.com/u/3e95c7555dc7

个人Blog: https://lichangke.github.io/

欢迎大家来一起交流学习

Read All

LeetCode-50--Pow(x,-n)

2019-03-27

leacoder

Algorithm

Algorithm Leetcode

Pow(x, n)
Python3实现
- 非递归移位
- 递归

Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2(-2) = 1/2(2) = 1/4 = 0.25

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2(31), 2(31) − 1] 。

Python3实现

非递归移位

每次对半计算，先每次算n/2 n/2的值,由两值可得n 注意每次对半计算时 n为偶数还是计算

# @author:leacoder
# @des:  非递归  移位法 Pow(x, n)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n<0:
            x = 1/x
            n = -n
        pow = 1
        while n:
            if n&1: # n 为奇数
                pow *= x
            
            x *=x #偶数   x = x*x  n=n>>1 (右移1 n减半)   即为 x(n) = (x*x)(n/2)
            n >>=1 #移位 左移1 n减半
            
        return pow

递归

每次对半计算，先每次算n/2 n/2的值,由两值可得n 注意每次对半计算时 n为偶数还是计算

# @author:leacoder
# @des:  递归  Pow(x, n)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0: #递归终止条件
            return 1
        if n<0: #n<0的情况
            return 1/self.myPow(x,-n)
        if n%2 == 0: # n为偶数
            return self.myPow(x*x,n/2) # x(n/2) * x(n/2) = (x * x)(n/2)
        else:#n为奇数
            return x*self.myPow(x,n-1) # x * x((n-1)/2) * x((n-1)/2) = x * (x*x)((n-1)/2) = x* x(n-1)
            # return x*self.myPow(x*x,(n-1)/2)

GitHub链接： https://github.com/lichangke/LeetCode

知乎个人首页： https://www.zhihu.com/people/lichangke/

简书个人首页： https://www.jianshu.com/u/3e95c7555dc7

个人Blog: https://lichangke.github.io/

欢迎大家来一起交流学习

Read All

From-Medium

2019-03-26

leacoder

Medium

Medium
- From Medium:
Medium – a place to read and write big ideas and important stories

From Medium:
- The SQL vs NoSQL Difference: MySQL vs MongoDB
介绍了什么是SQL什么是NoSQL，从可扩展性和结构两方面比较了SQL和NoSQL。并具体介绍比较了SQL代表MySQL 的好处和优势以及 NOSQL代表MongoDB的好处和优势。就哪个数据库适合您的业务给出了建议
- An A-Z of useful Python tricks
这篇文章对python使用者有很大的启迪和帮助，作者在文中介绍了26类（按字母A到Z排列）实用的Python技巧，推荐收藏并根据作者在文中扩展的进一步了解。
- What exactly can you do with Python? Here are Python’s 3 main applications.
作者在文中介绍了python的3个主要应用方向：Web开发、数据科学（包括机器学习，数据分析以及数据可视化）、脚本。 Web开发: 作者说明了我们为什么需要web框架，对比了基于python的web框架Django 和 Flask，推荐了文章 Flask vs. Django: Why Flask Might Be Better 数据科学: 首先回顾了什么是机器学习，介绍了python流行的机器学习库和框架，并给出了如何学习机器学习的建议。接着介绍了数据分析和数据可视化，以及实用的python库脚本: 作者简单介绍了下什么是脚本
- Learn the fundamentals of a good developer mindset in 15 minutes
作者在文章中介绍了自己25个关于良好开发人员思维方式的基础知识的要点，了解并遵循这些要点会让你减少很多软件开发中烦恼并避免开发很多人员都经常犯的错。
- A Smart Programmer Understands The Problems Worth Fixing
作者以Peter解决订单系统的故事引出自己的观点，聪明的程序员不是解决所有问题的人，而是理解值得解决的问题的人。
- SOLID Principles every Developer Should Know
每个开发人员都应知道的 SOLID 原则。作者通过简单代码示例，介绍了SLOID原则。面向对象的编程并不能防止难以理解或不可维护的程序。因此，Robert C. Martin 制定了五项指导原则，使开发人员很容易创建出可读性强且可维护的程序。这五项原则被称为 S.O.L.I.D 原则（这种缩写是由 Michael Feathers 提出的）：S: Single Responsibility Principle（单一责任原则） O: Open-Closed Principle（开闭原则）L: Liskov Substitution Principle（里式替换原则）I: Interface Segregation Principle（接口隔离原则）D: Dependency Inversion Principle（依赖倒置原则） https://www.jianshu.com/p/d3080383451f
- What I learned from doing 1000 code reviews
作者根据工作经验给出了3+1项代码审查建议，建议1：出现问题时抛出异常不要试图返回一个空对象或者其他东西。建议2：尽可能使用最具体的类型这会让你避免一堆bug也是选择强类型语言的基本原因。建议3：使用Optionals而不是nulls Optional类代表可合理存在或不存在的实体，允许您从程序中完全避免空指针异常（NPE），但是你得正确使用它。额外建议：尽可能使用“非提升”(Unlift)方法
- How to Become a Better Software Developer
如何成为更好的软件开发人员，作者从多个方面提出了自己的意见。软件开发不只与编码有关，需要理解软件端到端的开发全过程，需要了解客户的真实需求，为工作选择合适的工具和流程，需要进行安全试验，可以站在巨人的肩上开发，可以通过重新实现来学习，研究你的工作方式并改进提高它，消除开发中的不利因素，专注于基础知识，要懂得分享知识，出现问题不要责怪自己或他人要专注于导致问题的事情，弄清楚它为什么会发生，不要成为令人讨厌的混蛋
- All you need to know about “Big O Notation” to crack your next coding interview
作者以排序算法引出Big O的作用，用于衡量算法的效率。并给出了常用排序算法在最佳平均最坏情况的 Big O表格。研究Big O让我们关注程序的效率，在大的数据面前一点算法效率的提升，会很明显体现出来
- Which Programming Language Should You Learn Next?
作者首先简介了2017到2018编程语言的趋势，然后对初学者，中级以及专家级开发人员推荐了相应的编程语言学习，当然学习的编程语言也要尊重你的职业兴趣与愿望。
- Cookies vs. LocalStorage: What’s the difference?
介绍了Cookies 和LocalStorage是什么，以及异同点
- The top data structures you should know for your next coding interview
介绍了面试中常常遇到的数据结构，并罗列了一些面试问题。建议自己也回答下，如果答不上来 google
- Goodbye, Object Oriented Programming
作者是一个使用面向对象编程几十年的超级老鸟=_=，罗列了他所遇到的属于面向对象编程三大支柱的相关问题，吐槽了其背后的坑。前人踩了坑，我们踩着他就行了，在我们进行面向对象编程时随时注意 https://www.jianshu.com/p/de374f075d80

GitHub链接： https://github.com/lichangke/LeetCode

知乎个人首页： https://www.zhihu.com/people/lichangke/

简书个人首页： https://www.jianshu.com/u/3e95c7555dc7

个人Blog: https://lichangke.github.io/

欢迎大家来一起交流学习
Read All

LeetCode-98--验证二叉搜索树(Validate-Binary-Search-Tree)

2019-03-25

leacoder

Algorithm

Algorithm Leetcode

验证二叉搜索树
Python3 实现
Java实现
- 递归比较min max

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
    2
   / \
  1   3
输出: true
示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

Python3 实现

中序遍历

#@author:leacoder
#@des:  中序遍历  验证二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        inorderlist = self.inorder(root) #中序遍历后 如果是二叉搜索树 那么 结果必然是递增有序的 
        return inorderlist == list(sorted(set(inorderlist))) #set 集合用于去重  有重复的数那么必然不是二叉搜索树
        
    def inorder(self,root): #中序遍历 形成 左 根 右形式
        if root is None:
            return []
        return self.inorder(root.left) + [root.val] + self.inorder(root.right)
    
    
    '''
    sort() 对list本身进行排序,改变list的值。sort()只能对list排序。
    sorted() 产生一个新的list，不改变list的值。sorted()可以对iterable对象排序
    集合（set）是一个无序的不重复元素序列。
    可以使用大括号 { } 或者 set() 函数创建集合，注意：创建一个空集合必须用 set() 而不是 { }，因为 { } 是用来创建一个空字典。

中序遍历优化

#@author:leacoder
#@des:  中序遍历 优化  验证二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.prev = None
        return self.helper(root)
    
    def helper(self,root): #中序遍历 但是不全返回， 比较前节点是否比后节点小 小:二叉搜索树 大：非二叉搜索树
        if root is None:
            return True
        if not self.helper(root.left): #先判断左子树
            return False
        #前节点 与 后节点比  
        if self.prev and self.prev.val >= root.val:  #左子树:left 与root比    右子树：root与right比
            return False
        
        self.prev = root  #右子树将prev 设为 root
        #程序向后走（判断右叶子） 将前节点（root）与后节点（right）比较
        return self.helper(root.right) #再判断右子树
        
        '''
        对每个  left root right 判断 是否  left <root< right
        '''

递归比较min max

#@author:leacoder
#@des:  递归 min max,  验证二叉搜索树
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        min = max = None
        return self.isValid(root,min,max)
    
    def isValid(self,root,min,max):
        if root is None:
            return True
        # 当前root节点值 必须在 min 和 max之间
        if min is not None and root.val <=min:
            return False
        if max is not None and root.val >=max:
            return False
        # 分别递归检测   root的左子树（min下界不关心，其上界必须是root的值） 与 root右子树（max上界不关心，其下界必须是root的值）
        if self.isValid(root.left,min,root.val) and self.isValid(root.right,root.val,max):
            return True
        else:
            return False
    

Java实现

递归比较min max

/*
 *@author:leacoder
 *@des:  递归比较min max,  验证二叉搜索树
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        Integer min = null;
        Integer max = null;
        
        return isValid(root,min,max);
    }
    public boolean isValid(TreeNode root,Integer min,Integer max){ //min 下界   max上界
        if(root == null) return true;
        if(min!=null && root.val <=min) return false; 
        if(max!=null && root.val >=max) return false;  //当前root节点值 必须在 min 和 max之间
        
        //注意下边函数式子     分别递归检测   root的左子树（min下界不关心，其上界必须是root的值） 与 root右子树（max上界不关心，其下界界必须是root的值）
        return isValid(root.left,min,root.val)&&isValid(root.right,root.val,max);
    }
}

GitHub链接： https://github.com/lichangke/LeetCode

知乎个人首页： https://www.zhihu.com/people/lichangke/

简书个人首页： https://www.jianshu.com/u/3e95c7555dc7

个人Blog: https://lichangke.github.io/

欢迎大家来一起交流学习

Read All

LeetCode-703--数据流中的第K大元素(Kth-Largest-Element-in-a-Stream)

2019-03-24

leacoder

Algorithm

Algorithm Leetcode

Java 实现
- 优先队列

数据流中的第K大元素

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

示例:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8
说明: 
你可以假设 nums 的长度≥ k-1 且k ≥ 1。

Java 实现

优先队列

/*
 *@author:leacoder
 *@des:  优先队列 数据流中的第K大元素
 */

class KthLargest {
    final PriorityQueue<Integer> myqueue;
    final int kMax;

    public KthLargest(int k, int[] nums) {
        myqueue = new PriorityQueue<>(k);  //指定初始容量k的优先队列
        kMax = k;
        for(int n:nums){
            add(n); //将数据加入到 优先队列中
        }
    }
    
    public int add(int val) {
        if(myqueue.size()<kMax){
            myqueue.offer(val); //队列还未填满 直接入队
        }
        else if(myqueue.peek()<val){//队列顶 小于加入的val 说明第k大变为val，原来的变为k+1大
            myqueue.poll();
            myqueue.offer(val);  //移除顶端 数据 加入新数据
        }
        
        return myqueue.peek(); 
            
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

GitHub链接： https://github.com/lichangke/LeetCode

知乎个人首页： https://www.zhihu.com/people/lichangke/

简书个人首页： https://www.jianshu.com/u/3e95c7555dc7

个人Blog: https://lichangke.github.io/

欢迎大家来一起交流学习

Read All

LeetCode-15--三数之和(3Sum)

2019-03-24

leacoder

Algorithm

Algorithm Leetcode

三数之和
Python3实现
- 借助两数之和
- 一层枚举左右两指针形式
C++实现
- 一层枚举左右两指针形式

三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Python3实现

借助两数之和

# @author:leacoder
# @des:   借助两数之和  三数之和

class Solution(object):
    def threeSum(self, nums):
        nums.sort() #排序 方便去重
        res = []
        for i, num in enumerate(nums): #一层循环
            if i > 0 and nums[i] == nums[i-1]: # 避免重复
                continue
                
            new_nums = nums[i+1:] #剔除 一层循环后的数 
            two_sums = self.twoSum(new_nums, -num) #由于何为0  两数之和要为 -num
            for two_sum in two_sums:
                res.append([num, new_nums[two_sum[0]], new_nums[two_sum[1]]])
                         
        return res
            
        
    def twoSum(self, nums, target):
        d = {}
        res = []
        hit = False
        for i, num in enumerate(nums):
            if i > 1 and nums[i] == nums[i-1] and hit:
                continue
            if num in d:
                res.append([d[num], i])
                hit = True
            else:
                d[target - num] = i
                hit = False
        return res

一层枚举左右两指针形式

# @author:leacoder
# @des:   一层枚举 左右两指针形式  三数之和 

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for index1,value in enumerate(nums[:-2]): #一层循环
            if index1>0 and nums[index1] == nums[index1-1]: #不可以包含重复的三元组
                continue
            left,right = index1+1,len(nums)-1  #左右指针形式  左：一层数据右侧开始  右:数据最右端开始
            while left<right: #循环条件  依据实际大小情况，选择左或右指针向中间移动  但右必定大于左
                sumtmp = nums[index1] + nums[left] + nums[right] #三数和
                if sumtmp <0: left +=1 # <0 表明和小了，那么左指针向右+1 真大 nums[left]  nums已经排序 右边必定大于 左边
                elif sumtmp >0: right -=1 #同上 
                else: #刚好为0
                    res.append((nums[index1],nums[left],nums[right]))
                    while left < right and nums[left]==nums[left+1]: #不可以包含重复的三元组
                        left +=1
                    while left < right and nums[right]==nums[right-1]:#不可以包含重复的三元组
                        right -=1
                    left +=1;right -=1
        return res
                

C++实现

一层枚举左右两指针形式

/*
 *@author:leacoder
 *@des:   一层枚举 左右两指针形式  三数之和 
 */
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res; //返回值
        if(nums.size()<3){ //输入检查
            return res;
        }
        sort(nums.begin(), nums.end()); //排序
        
        for (int i = 0; i < nums.size()-2; i++) //一层循环
        {
            if(i>0 && nums[i] == nums[i-1])
                continue;
            int target = -nums[i]; //其他两数和
            int l = i + 1, r = nums.size() - 1; //左右指针形式  l 左 r右
            while (l < r)
            {
                if (nums[l] + nums[r] < target) //小于目标 l 增加
                    ++l;
                else if (nums[l] + nums[r] > target) //大于目标 r 减少
                    --r;
                else{ //刚好
                    res.push_back(vector<int>{nums[i], nums[l], nums[r]});
                    while (l < r && nums[l] == nums[l+1])
                        l++;
                    while (l < r && nums[r] == nums[r-1])
                        r--;
                    l++; r--;
                }
            }
            
        }
        return res;
    }
};

GitHub链接： https://github.com/lichangke/LeetCode

知乎个人首页： https://www.zhihu.com/people/lichangke/

简书个人首页： https://www.jianshu.com/u/3e95c7555dc7

个人Blog: https://lichangke.github.io/

欢迎大家来一起交流学习

Read All

9/12

Welcome to LeaCoder's Blog!

Python3 实现

排序法

dic计数

摩尔投票法

Python3实现

非递归移位

递归

From Medium:

Python3 实现

中序遍历

中序遍历 优化

递归比较min max

Java实现

递归比较min max

Java 实现

优先队列

Python3实现

借助两数之和

一层枚举 左右两指针形式

C++实现

一层枚举 左右两指针形式

中序遍历优化

一层枚举左右两指针形式

一层枚举左右两指针形式