Leetcode 198. House Robber

原题链接:198. House Robber

  一句话理解题意,有个偷马贼晚上要偷尽可能值钱的马,但连续两头马被偷会触发报警,问他如何在不触发报警(不偷连续的两匹马)的情况下偷到总价值最高马,返回最高总价值。
  看到maximum,就应该想到这是应该求解最优的问题,一想到求解最优,一般除了暴力就是动态规划了。

Continue reading

Leetcode 347.Top K Frequent Elements

Top K Frequent Elements
  一句话理解题意:输出数组中出现次数对多的k个数。
  在如果用C语言来写这个题目,思路就是先按数的大小排序,然后再用一个结构体数组保存每个数的出现次次数。 因为数组已经有序了,所以只需要遍历一次数组就可以获得每个数的出现次数了。 结构体如下

strut node 
{
    int num;       //保存数组中的数
    int count;     //这个数出现的次数
}

Continue reading

Leetcode 331.Verify Preorder Serialization of a Binary Tree

Verify Preorder Serialization of a Binary Tree不算一道特别复杂的题目。 题意大概是这样的:给你一个字符数组,让你判断这个数组中的值是不是一棵二叉树的先序遍历结果,其中’#’节点是空节点,无左右字节点。 原文中举了一个例子。 "9,3,4,#,#,1,#,#,2,#,6,#,#" 就是下面这棵二叉树的先序遍历结果。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

Continue reading

Leetcode Find Minimum in Rotated Sorted Array 题解

Leetcode Find Minimum in Rotated Sorted Array

题目大意:

     对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。

     毫无疑问,遍历一次肯定可以找到,但这样时间复杂度是O(n),如果你在面试的时候遇到这样的问题,你这样回答面试官肯定不会满意的,我们接下来讨论有没有什么更快的方法。O(nlogn)??

Continue reading