Given a list of points that form a polygon when joined sequentially, find if this polygon is convex (Convex polygon definition).[[0,0],[0,1],[1,1],[1,0]]Answer: True[[0,0],[0,10],[10,10],[10,0],[5,5]]Answer: False思路：这题问的是给一系列polygon的点，判断其是否是convex的。一个比较好的判断方法是看所有点是否是按照同一个顺序排列的，比如所有点都是依次顺时针，逆时针或者是同一条线排列。这里判断方向的方法...
题目：Given a linked list, swap every two adjacent nodes and return its head.For example,Given 1->2->3->4, you should return the list as 2->1->4->3.Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. 代码：oj 测试通过 Runtime: 42 ms 1# Definition for singly-linked list. 2# class ListNode: 3# def __init__(self, x): 4# ...
题目：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。思路：自己想的方法类似于接雨水的问题，但是计算量在有的例子的时候太大，超时了，参考的别人的方法，就是使用栈和哨兵的思路，这个思路的程序设计的很巧妙。程序1：class Solution: def largestRectangleArea(self, heights: List[int]) -> int: length = len(heights) ...
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例 1:输入: 123输出: 321 示例 2:输入: -123输出: -321示例 3:输入: 120输出: 21注意:假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [?231, 231 ? 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。 这道题可以用到python的字符串反转[::-1]，非常方便，只要处理一下溢出以及负数即可class Solution:def reverse(self, x: int) -> ...
Given a 2d grid map of ‘1‘s (land) and ‘0‘s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.Example 1:11110110101100000000Answer: 1Example 2:11000110000010000011Answer: 3 思路 = dfs（四叉树，上下左右） +剪枝剪枝是剪掉遍历过的结点cl...
# -*- coding: utf8 -*-‘‘‘__author__ = ‘dabay.wang@gmail.com‘56: Merge Intervalshttps://oj.leetcode.com/problems/merge-intervals/Given a collection of intervals, merge all overlapping intervals.For example,Given [1,3],[2,6],[8,10],[15,18],return [1,6],[8,10],[15,18].===Comments by Dabay===这道题想起来比较简单，实现的时候恼火。技巧在与，不是一个个地插入到已有的序列，而是把已有的序列插入到一个标...
Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions.Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).Credits: Special thanks to @Freezen for adding this problem and creating all test cases. Based on Dynamic ...
题目：Given two sorted integer arrays A and B, merge B into A as one sorted array.Note:You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and nrespectively. 代码：oj测试通过 Runtime: 58 ms 1class Solution:2# @param A a list of integers 3# @param m an integer, length of A 4# @param...
The set [1,2,3,…,n] contains a total of n! uniquepermutations. 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. I post two methods.. the first one is brute force. which is N! time. the second one is linear time. input fac = (n-1)! k = k -1 1. get the value from...
LeetCode 0093. Restore IP Addresses复原IP地址【Medium】【Python】【回溯】【DFS】【暴力】ProblemLeetCodeGiven a string containing only digits, restore it by returning all possible valid IP address combinations.Example:Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"]问题力扣给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。示例:输入: "25525511135" 输出: ["255.255.11.13...
You are given a data structure of employee information, which includes the employee‘s unique id, his importance value and his direct subordinates‘ id.For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. They have importance value 15, 10 and 5, respectively. Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and emp...
题目：罗马数字转整数：罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。字符 数值I 1V 5X 10L 50C 100D 500M 1000例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数...
#Given a sorted array and a target value, return the index if the target is found. If #not, return the index where it would be if it were inserted in order.#You may assume no duplicates in the array.#Here are few examples. #[1,3,5,6], 5 → 2 #[1,3,5,6], 2 → 1 #[1,3,5,6], 7 → 4 #[1,3,5,6], 0 → 0class Solution(object):def searchInsert(self, nums, target):""":type nums: List[int]:type target: int:...
题目: 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。示例 1:输入: "A man, a plan, a canal: Panama"输出: true示例 2:输入: "race a car"输出: false来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-palindrome 本题需要注意的是, 在python2.7中filter函数直接返回列表,而python3中的filter返回的是迭代器对象,需要用...
99. 恢复二叉搜索树题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/recover-binary-search-tree题目二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。示例 1:输入: [1,3,null,null,2]1/32输出: [3,1,null,null,2]3/12 示例 2:输入: [3,1,4,null,null,2]3/ 1 4/2输出: [2,1,4,null,null,3]2/ 1 4/3 进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案...