Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 367. Valid Perfect Square

题目大意:判断一个数是否是平方数。不能使用开根号函数。

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Example 2:

Idea:

Binary search

Solution:

C++

Time complexity: O(log(num))

Space complexity: O(1)

 

花花酱 LeetCode 653. Two Sum IV – Input is a BST

题目大意:给你一棵二叉搜索树,返回树中是否存在两个节点的和等于给定的目标值。

Problem:

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Example 2:

Solution:

C++

 

花花酱 LeetCode 748. Largest Number At Least Twice of Others

题目大意:给你一个数组,问你其中最大的数是不是比剩下的数大2倍以上,返回这样的数的索引。如果不存在,返回-1.

Problem:

In a given integer array nums, there is always exactly one largest element.

Find whether the largest element in the array is at least twice as much as every other number in the array.

If it is, return the index of the largest element, otherwise return -1.

Example 1:

Example 2:

Note:

  1. nums will have a length in the range [1, 50].
  2. Every nums[i] will be an integer in the range [0, 99].

Solution:

C++

 

花花酱 LeetCode 17. Letter Combinations of a Phone Number

题目大意:给你一串电话号码,输出可以由这串电话号码打出的所有字符串。

Problem:

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Solution 1: DFS

C++

Java

Python3

Solution 2:  BFS

C++

Java

Python

 

花花酱 LeetCode Input Size V.S. Time Complexity SP2

本期节目介绍了输入数据规模和时间复杂度上限的关系,可以通过数据规模推算使用算法的类型。

 

  • < 10: O(n!) permutation
  • < 15: O(2^n) combination
  • < 50: O(n^4) DP
  • < 200: O(n^3) DP, all pairs shortest path
  • < 1,000: O(n^2) DP, all pairs, dense graph
  • < 1,000,000: O(nlogn), sorting-based (greedy), heap, divide & conquer
  • < 1,000,000: O(n), DP, graph traversal / topological sorting (V+E), tree traversal
  • < INT_MAX: O(sqrt(n)), prime, square sum
  • < INT_MAX: O(logn), binary search
  • < INT_MAX: O(1) Math