Majority Element Given an array of size n, find the majority element. The majority element is the element that appears more than ? n/2 ? times.You may assume that the array is non-empty and the majority element always exist in the array. python code：class Solution: # @param {integer[]} nums # @return {integer} def majorityElement(self, nums): b={} for eachnum in num...
题目来源： https://leetcode.com/problems/powx-n/ 题意分析： 实现一个整型的幂运算。 题目思路： 幂运算可以利用二分的方法来做。也就是x^n = x ^ (n /2) * x ^(n / 2) (n %2 == 0)或者x^n = x ^ (n /2) * x ^(n / 2) * x(n %2 == 1)。要注意的时候，当n < 0 的时候，x ^ n =1 / （x ^(-n))。 代码（python）：class Solution(object):def myPow(self, x, n):""":type x: float:type n: int:rtype: float"""if n < 0:...
题目来源： https://leetcode.com/problems/trapping-rain-water/ 题意分析： 输入一组数组，代表一个宽度为1的高度地图。问，这个地图在雨后可以收集多少水。例如，输入一个数组[0,1,0,2,1,0,1,3,2,1,2,1]，返回的是6.如图所示： 题目思路： 这道题目虽然说是hard难度的题目，但是其实不是很难。不难发现，水都是从最高那个数起和第二高数之间。那么这题可以分成两部。①找到数组的最大值。②计算最大值左边和右边分别可...
题目：给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。思路：本题较简单程序：class Solution: def generate(self, numRows: int) -> List[List[int]]: result = [] if numRows <= 0: return result for index1 in range(1, numRows + 1): data = [] if index1 == 1: data.append(1) elif index1 == 2: data.append...
98. 验证二叉搜索树题目来源：https://leetcode-cn.com/problems/validate-binary-search-tree题目给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。示例 1:输入:2/ 1 3 输出: true 示例 2:输入:5/ 1 4/ 3 6 输出: false 解释: 输入为: [5,1,4,null,null...
题目：假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 注意数组中可能存在重复的元素。 说明：这道题是 寻找旋转排序数组中的最小值 的延伸题目。允许重复会影响算法的时间复杂度吗？会如何影响，为什么？思路：仍然使用二分法，考虑到会存在重复元素的情况，因此当判断到有重复数字时(nums[middle] == nums[tail]）时，使用tail...
# -*- coding: utf8 -*-‘‘‘https://oj.leetcode.com/problems/median-of-two-sorted-arrays/There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.The overall run time complexity should be O(log (m+n)).===Comments by Dabay===先计算中位数在合并后数组中的什么坐标为medium_pos。同时考虑到，合并后数组的元素总数是奇数偶数的不同情况，用一个变量last来记录寻...
原题地址：https://oj.leetcode.com/problems/text-justification/题意：Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly L characters.Extr...
Problem: Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would haveexactly one solution. For example, given array S = {-1 2 1 -4}, and target = 1.The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).Solution:此题与15题基本类似，甚至更简单一些，只需要比较和...
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.Example 1:Input: cost = [10, 15, 20] Output: 15 Explanation: Cheapest is start on cost[1], pay that cost and go t...
问题描述：Given a binary tree, return the bottom-up level order traversal of its nodes‘ values. (ie, from left to right, level by level from leaf to root).For example:Given binary tree [3,9,20,null,null,15,7], 3/ 9 20/ 15 7return its bottom-up level order traversal as:[[15,7],[9,20],[3] ]注意是每一层的所有数字放入同一个list内思路：二叉树问题，考虑使用递归算法，计算出每一层的所有元素值...
原题地址：https://oj.leetcode.com/problems/candy/题意：There are N children standing in a line. Each child is assigned a rating value.You are giving candies to these children subjected to the following requirements:Each child must have at least one candy.Children with a higher rating get more candies than their neighbors.What is the minimum candies you must give?解题思路：求最少的蛋糕数。先从前到...
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4.Credits: Special thanks to @amrsaqr for adding this problem and creating all test cases. code is as follow:class Solution:# @param m, an integer# @param n, an integer# @return an integerdef rangeBitwiseAnd(self, m, n):i = 0wh...
# -*- coding: utf8 -*-‘‘‘__author__ = ‘dabay.wang@gmail.com‘50: Pow(x, n)https://leetcode.com/problems/powx-n/Implement pow(x, n).=== Comments by Dabay===技巧在于用x的平方来让n减半。同时注意n为负数的情况，以及n为奇数的情况。‘‘‘class Solution: # @param x, a float # @param n, a integer # @return a float def pow(self, x, n): if x == 0: return 0 elif n < 0:...
题目来源https://leetcode.com/problems/permutation-sequence/The set [1,2,3,…,n] contains a total of n! unique permutations.By listing and labeling all of the permutations in order,We get the following sequence (ie, for n = 3):"123""132""213""231""312""321" Given n and k, return the kth permutation sequence.题意分析Input: n, kOutput: the kth permutation in permutations based on nConditions: 返回第n...