一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 1639|回复: 62
收起左侧

刷题记录帖子

[复制链接] |试试Instant~ |leetcode, 刷题
我的人缘0

分享帖子到朋友圈
Myron2017 | 显示全部楼层 |阅读模式
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   92% (124)
 
 
7% (10)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
自己开一个帖子, 激励自己,刷题记录。

今天准备明天的报告,只刷了一题, LC 299 Bulls and Cows。

比较简单,说白了就是通过一次遍历,这个时候你一定是位置 match 的,因为你之检测一个位置。所以现在,内容 Match 的就是 Bulls,如果内容不 Match 那么你就记录下来,用一个【0~9】的数组,因为后面只需要比较这里的【0,9】各自在两个数组出现了多少次,然后取每个数字少的那个,当然初始话要都是 0.
时间复杂度 O(n) + 9 其实就是 O(n) 遍历数组的时间,空间复杂度,不算原来的数组,其实只要 O(1)两个长度为 10 的数组记录各相同位置不同内容数字的总体出现次数。

上一篇:公共卫生的CPH考试有人考过吗?求经验!
下一篇:打卡开始
我的人缘0
 楼主| Myron2017 2020-3-28 00:09:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (124)
 
 
7% (10)    👎
补下昨天的,104 Maximum Depth of Binary Tree

出现了低级失误,居然没做出来。

其实很简单就是递归,先看root,再 left, 再 right,最后对于该节点做一个归纳,决定怎么输出。

List all scenarios of what a binary tree could be like:

1. when a binary tree is null, simply return maximum depth as 0
2. when a binary tree just have a root node, return maximum depth as 1
3. when a binary tree has a root node and child nodes, maximum depth would be the depth of the bigger side between left and right subtrees plus 1.

回复

使用道具 举报

我的人缘0
 楼主| Myron2017 2020-3-28 00:38:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (124)
 
 
7% (10)    👎
本帖最后由 Myron2017 于 2020-3-28 00:52 编辑

LC 442 Find All Duplicates in an Array

The idea is we do a linear pass using the input array itself as a hash to store which numbers have been seen before. We do this by making elements at certain indexes negative.
[Python] 纯文本查看 复制代码
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        # HashMap is an obvious solution, we will not check it
        # Try to solve it in O(n) time without extra space
        # so we must use space in the array itself
        # Then we will cancel each other if possible
        res = []
        for item in nums:
            if nums[abs(item) - 1] < 0:
                res.append( abs(item) )
            else:
                nums[abs(item) - 1] *= -1
        return res


回复

使用道具 举报

我的人缘0
 楼主| Myron2017 2020-3-28 02:09:52 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (124)
 
 
7% (10)    👎
LC 806. Number of Lines To Write String

还是很简单的题目,其实可以很容易看懂思路,设置两个变量然后不断检查当前的字符。
回复

使用道具 举报

我的人缘0
jf2891 2020-3-28 03:01:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (3)
 
 
0% (0)    👎
赞一个,楼主讲解的很详细!加油!
回复

使用道具 举报

我的人缘0
 楼主| Myron2017 2020-3-28 12:36:56 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (124)
 
 
7% (10)    👎
1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

这个题目其实我不知道为什么要给 old tree 完全是冗余条件,但是其实就是纯粹的traverse tree 然后你比较 value 并且记录当前的 treeNode。
回复

使用道具 举报

我的人缘0
 楼主| Myron2017 2020-3-29 02:49:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (124)
 
 
7% (10)    👎
今天复习 双指针 topic, 参照这个 Github 帖子, 双指针

167. Two Sum II - Input array is sorted 非常直接双指针使用,直接两头夹逼出答案

633. Sum of Square Numbers 需要注意的是,这个是从 0 开始的,换句话说 0**2 + 2**2 == 4 是符合平方和要求的。

345. Reverse Vowels of a String 首先是如何从 Python String 转 List,其次是从 List 转回 String,因为 String 在 Python 中不可变。 其次是需要考虑字符串的大小写问题。最后是其实写判断条件的时候,时刻注意两个 Pointer 的范围,越界是比较讨厌的问题。同时双指针满足条件,交换了内容之后别忘记更新指针。
回复

使用道具 举报

我的人缘0
 楼主| Myron2017 2020-3-29 11:52:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (124)
 
 
7% (10)    👎
1108       
Defanging an IP Address     太简单,就是简单的字符串操作练习,没啥提高。
回复

使用道具 举报

我的人缘0
 楼主| Myron2017 2020-3-31 04:42:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (124)
 
 
7% (10)    👎
本帖最后由 Myron2017 于 2020-3-31 05:03 编辑

LC 1395. Count Number of Teams 周六比赛的时候暴力求解,现在看到花花的视频,还可以用压缩解法,对于 O(n^3) 的算法,肯定确实是如果超过300就不太暴力做了。
学习了,其实就是变第二趟遍历的时候,可以统计出可能的状态数,这样简单乘法计算即可,而不用一个个检测。代码快了接近 30 倍。

[Python] 纯文本查看 复制代码
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        totalN = len(rating)
        """
        This time we use the j th ratings to cut the array into two parts
        then i is choosen from the left part,
             j is choosen from the right part,
             so i < j < k
        Since unique rating values in ratings
        Then (1) for rating[i] < rating[j] < rating[k]
             we can count how many elements in j left part is smaller than j which is the possible value of i saying it is numL
             (2) for rating[i] > rating[j] > rating[k]
             total number of all elements in j th left part is j, so the number of elements that is larger than j th is ( j - numL )
        """

        res = 0
        for j in range(1,totalN-1):
            # Both numL and numR are for smaller cases
            numL = 0
            numR = 0
            for i in range(0, j):
                if rating[i] < rating[j]:
                    numL += 1
            for k in range(j+1,totalN):
                if rating[j] < rating[k]:
                    numR += 1
            # print("%d , %d"%(numL, numR))
            res = res + numL * numR + (j - numL) * (totalN - j - numR - 1)
            # print(res)
        return res
            
            






本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
回复

使用道具 举报

我的人缘0
 楼主| Myron2017 2020-4-1 10:53:22 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (124)
 
 
7% (10)    👎
1295. Find Numbers with Even Number of Digits 把数字转换成字符串再用字符串长度 %2 计算。 其实可以用位运算。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-6-4 19:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表