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...
罗马数字包含以下七种字符: 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。数字 1 在数字 5 的左边，...
题目：Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.Note:You are not suppose to use the library‘s sort function for this problem.click to show follow up.Follow up:A rather straight...