简单的插入排序，总是超时，暂且放在这记录一下。class Solution:# @param head, a ListNode# @return a ListNodedef insertionSortList(self, head):if head == None or head.next == None:return headpsuhead = ListNode(-1)while head:tail = psuheadheadnext = head.nextwhile tail.next and tail.next.val < head.val:tail = tail.nexthead.next = tail.nexttail.next = headhead = headnextreturn psuhead.next
Last execute...
# -*- coding: utf8 -*-‘‘‘__author__ = ‘dabay.wang@gmail.com‘54: Spiral Matrixhttps://leetcode.com/problems/spiral-matrix/Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.For example,Given the following matrix:[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ]]You should return [1,2,3,6,9,8,7,4,5].=== Comments by Dabay===一圈一圈的处理，一共处理n/2圈...
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character ‘.‘.
You may assume that there will be only one unique solution.
A sudoku puzzle...
This problem is M^9 complexity m is the number of empty slots.
we can use DFS to solve this problem with backtracking.class Solution:# @param board, a 9x9 2D array# Solve the Sudoku by modifying the inp...
# -*- coding: utf8 -*-‘‘‘__author__ = ‘dabay.wang@gmail.com‘39: Combination Sumhttps://oj.leetcode.com/problems/combination-sum/Given a set of candidate numbers (C) and a target number (T),find all unique combinations in C where the candidate numbers sums to T.The same repeated number may be chosen from C unlimited number of times.Note:All numbers (including target) will be positive integers....
# -*- coding: utf8 -*-‘‘‘__author__ = ‘dabay.wang@gmail.com‘37: Sudoku Solverhttps://oj.leetcode.com/problems/sudoku-solver/Write a program to solve a Sudoku puzzle by filling the empty cells.Empty cells are indicated by the character ‘.‘.You may assume that there will be only one unique solution.===Comments by Dabay===逐行扫描，当遇到“.”的时候，尝试每一个可能的valid_num。如果能DFS到底，就...
Problem:
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2...
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
generally we can have two methods to do this problem, the first one is based on finding pivot and then divide the array into two parts, then search.
second one is still based on Binary search.class S...
原题地址：http://www.cnblogs.com/x1957/p/3373994.html题意：Given an array of integers, every element
appears twice except for one. Find that single
one.要求：线性时间复杂度，并且不用额外空间。解题思路：这题考的是位操作。只需要使用异或(xor)操作就可以解决问题。异或操作的定义为：x ^ 0 = x; x ^ x = 0。用在这道题里面就是：y
^ x ^ x = y; x ^ x = 0; 举个例子：序列为：1122334556677。4是那个唯一的数，之...
Python 3class MinStack:def__init__(self):self.stack = []self.min_stack = [math.inf]def push(self, x: int) -> None:self.stack.append(x)self.min_stack.append(min(x, self.min_stack[-1]))def pop(self) -> None:self.stack.pop()self.min_stack.pop()def top(self) -> int:return self.stack[-1]def getMin(self) -> int:return self.min_stack[-1] 原文：https://www.cnblogs.com/vicky2021/p/14897746.html
题目：反转链表 II：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度。示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4输出: 1->4->3->2->5->NULL思路：思路较简单，找到规律就好。程序：# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution:...
题目描述：给定一个由时间字符组成的列表，找出任意两个时间之间最小的差值。思路：把给定的链表排序，并且在排序的同时把60进制的时间转化成十进制整数；遍历排序的数组，求出两个相邻值之间的差值；求出首尾两个值之间的差值。class Solution(object):def findMinDifference(self, timePoints):""" :type timePoints: List[str] :rtype: int """t =sorted(int(t[:2]) *60+int(t[-2:]) for t in timePoints)...
Find the sum of all left leaves in a given binary tree.Example: 3/ 9 20/ 15 7There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def sumOfLeftLeaves(self, ro...
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def minDepth(self, root):""":type root: TreeNode:rtype: int"""if root == None:return 0if root.left == None and root.right != None:return self.minDepth(root.right)+1if root.left != None and root.right == None:...
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.Note: m and n will be at most 100.这题的做法...
题目https://leetcode-cn.com/problems/find-the-kth-smallest-sum-of-a-matrix-with-sorted-rows/给你一个 m?* n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。
你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。示例 1：输入：mat = [[1,3,11],[2,4,6]], k = 5
输出：7解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6...
题目：
排序链表：在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
思路：
看到时间复杂度为?O(n log n) ，想到使用二分法，但是在链表里的二分法还没有想到思路，先使用懒人方法做一下，竟然通过了，哈哈哈，万万没想到，之后再补按照要求的程序。
程序1：这个程序是不符合题目要求的，但是没想到会通过，哈哈哈，这个题目的空间复杂度为O(n)。
#?Definition?for?singly-linked?list.
#?class?ListNode:
#?????def?__init__(self,?x):
#?????????self.val?=?x
#?????????self.next?=?None