手撕代码记录贴

才发现牛客网发帖子是可以编辑的T……T

春招接近尾声，自己尚有很多很多的不足，尤其是现场代码能力方面需要加强。

接下来一段时间会整理各路大佬的手撕代码题目和题解，希望大家多多发自己面试遇到的题目啦～

因为是自己写的，不一定是最优解，欢迎小伙伴们来讨论哇～～

（自己只熟悉Python，所以。。。，还是好好学习C++吧)

自己遇到的：

1. 剑指offer 判断节点环（快慢指针求解）

2. 翻转数组

b[j*col+i]=a[i*row+j]

3. 有序数组二分查找目标值

4. Leetcode 69. Sqrt(x) 求平方根

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """        
        start=0
        end=(x+1)/2
        while(start<end):
            mid=start+(end-start)/2
            tmp=mid*mid
            if(tmp==x):
                return mid
            elif tmp<x:
                start=mid+1
            else:
                end=mid-1
        tmp=end*end
        if(tmp>x):
            return end-1
        else:
            return end

5. Leetcode 4. Median of Two Sorted Arrays 有序数组的中位数

思路：分治

class Solution(object):
    def findDigit(self,nums1,nums2,idx):
        if len(nums1)>len(nums2):
            return self.findDigit(nums2,nums1,idx)
        if len(nums1) == 0:
            return nums2[idx-1]
        if idx == 1:
            return min(nums1[0],nums2[0])
        l1_mid = min(idx/2,len(nums1))
        l2_mid = idx-l1_mid
        if nums1[l1_mid-1] <= nums2[l2_mid-1]:
            return self.findDigit(nums1[l1_mid:],nums2,l2_mid)
        else:
            return self.findDigit(nums1,nums2[l2_mid:],l1_mid)
    def findMedianSortedArrays(self,nums1,nums2):
        '''
        :param nums1: List[int]
        :param nums2: List[int]
        :return: float
        '''
        total_length = len(nums1) + len(nums2)
        if total_length%2 == 1:
            return self.findDigit(nums1,nums2,total_length/2+1)
        else:
            return (self.findDigit(nums1,nums2,total_length/2)+self.findDigit(nums1,nums2,total_length/2+1))*0.5

========别人面试遇到的题目=======

1. Leetcode 85. Maximal Rectangle (头条、腾讯）

思路：转化Leetcode 84 求直方图中的最大面积问题，单调栈求解

class Solution(object):
    def maximalRectangle(self,matrix1):
        m = len(matrix1)
        if m == 0: return 0
        n,maxValue = len(matrix1[0]),0
        dp = [[0 for i in range(n)] for j in range(m)]
        for i in range(m):
            for j in range(n):
                if i==0 and matrix1[i][j] == '1':
                    dp[i][j] = 1
                if i>0 and matrix1[i][j]=='1':
                    dp[i][j] = dp[i-1][j]+1
        for col in range(m):
             maxValue=max(maxValue,self.largestRectangleArea(dp[col]))
        return maxValue
    
    def largestRectangleArea(self, heights):
        heights.append(0)
        stack = []
        area = 0
        for i,h in enumerate(heights):
            if stack == [] or heights[stack[-1]]<=h:
                stack.append(i)
            else:
                while(stack and heights[stack[-1]]>h):
                    idx = stack.pop()
                    left = stack[-1] if stack else -1
                    area = max((i-left-1)*heights[idx],area)
                stack.append(i)
        return area

全部评论

推荐最新楼层

江沢直树

杭州电子科技大学安卓

好多…我只撕过三个代码，一个快排就不说了，还有哈夫曼树创建和最长公共连续子序列

点赞回复分享

发布于 2018-04-25 11:15

尹斗俊喊你去学习

楼主

上海戏剧学院算法工程师

https://www.nowcoder.com/discuss/71505?type=2&order=0&pos=22&page=1 题目来源头条一面编程题翻转二叉树 Leetcode 226. Invert Binary Tree class Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if root: root.left, root.right = self.invertTree(root.right), self.invertTree(root.left) return root 最大连续子串和 Leetcode 53. Maximum Subarray class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ if nums == []: return 0 dp = ret= nums[0] for i in range(1,len(nums)): dp = max(dp+nums[i],nums[i]) ret = max(ret,dp) return ret 二面编程题给一棵边权树树找到最大路径可以先考虑不带权值的 Leetcode 543. Diameter of Binary Tree 最大路径实际上可以转化为求叶子节点之间的最长距离 class Solution(object): def diameterOfBinaryTree(self, root): self.diameter = 0 self.depth(root) return self.diameter def depth(self,root): if not root: return 0 left = self.depth(root.left) right = self.depth(root.right) self.diameter = max(self.diameter,left+right) return max(left,right)+1 其实带权值和不带权值的区别在于不带权值的树其实权值为1 需要修改的点在 self.diameter = max(self.diameter,left+right+root.lweight+root.rweight) return max(left+root.lweight,right+root.rweight) 三面编程题给一个字符串和单词列表，判断字符串能不能由这些单词组成 Leetcode 139 Word Break 思路是用数组dp，dp[i] 表示字符串 s[:i+1] 能否由单词列表中的单词组成那么可以得到 dp[i] = dp[j] and (s[j:i+1] in wordlist) for j in j in range(i) class Solution(object): def wordBreak(self, s, wordDict): """ :type s: str :type wordDict: List[str] :rtype: bool """ worddict = {} for word in wordDict: worddict[word] = True dp = [True]+[False for i in s] for i in range(len(s)): for j in range(i+1): if s[j:i+1] in worddict and dp[j]==True: dp[i+1] = True break return dp[-1] 股票买卖问题可以参见 https://blog.csdn.net/tinkle181129/article/details/79506010 Leetcode 121. Best Time to Buy and Sell Stock 贪心思想 class Solution(object): def maxProfit(self, prices): if prices == []: return 0 minNum,ret = prices[0],0 for p in prices: minNum = min(minNum,p) ret = max(ret,p-minNum) return ret

点赞回复分享

发布于 2018-04-26 10:53

offer点击就送哦

华为_华为云计算公司_java开发工程师