valid sudoku

题目描述

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.The Sudoku board could be partially filled, where empty cells are filled with the character'.'.

题目解析

数独具有以下规则:

  • 每一行所有元素不能重复(1~9);
  • 每一列所有元素不能重复(1~9);
  • 由第3i~3(i)+2行和第3i~3(i)+2列组成的九宫格内元素不能重复(其中0<=i<n/3-1,元素仍为1~9)。

想到重复问题,自然而然我们想到了设置Flag的方法,由此我们可以设置3个n×n大小的矩阵来作为标志位:

  • 第一个矩阵命名为fRow,作为判断每一行的数字是否重复的矩阵,因为元素只能为1~9,所以正好每行9个格子合适。
  • 第二个矩阵命名为fCol,作为判断每一行列的数字是否重复的矩阵,因为元素只能为1~9,所以正好每行9个格子合适。
  • 第三个矩阵命名为fMat,作为判断每个九宫格的数字是否重复的矩阵。

本题的特殊之处在于允许有空格的格子,且空格的地方以字符.表示,且所存储的数字都是char类型,因此首先要进行一个类型转换才能判断:

若检测到该行出现这个数字,则设置该行这个位置为true,当又遍历到这个数字的时候,若检查发现这个位置已经设置为true了,则返回false。当然在实现代码的时候,要把判断放在前面,把设置标志位放在后面。

该方法的时间复杂度为O(n2),空间复杂度为O(n2)。

代码实现

largest rectangle in histogram

题目描述

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

For example,Given height =[2,1,5,6,2,3],return10.

题目解析

我们以[2,1,5,6,2,3]为例来思考这个题目的思想。观察如图所示。

7ca37b3c6aa82f235c77db4e0ebd8239.png

代码实现

pascals-triangle-ii

题目描述

Given an index k, return the k th row of the Pascal's triangle.For example, given k = 3,
Return[1,3,3,1].

题目解析

代码实现

Construct binary tree from preorder and inorder traversal

题目描述

Given preorder and inorder traversal of a tree, construct the binary tree.
Note: 
You may assume that duplicates do not exist in the tree.

思路

关于根据前序和中序如何得到二叉树的结构的计算方式,我就不重复了,之前的程序里面也有,这里就只说说代码里几个参数的思路。
**一定要做边界条件的判断!***

对于左子树处理来说,中序遍历所要处理的位置就是根节点左侧的所有数字,所以自然起始位置就是istart,结束位置就是i-1;对于前序遍历来说表示就麻烦一些,起始位置还好,是pstart+1,结束位置是pstart+(i-istart),其中i-istart是左子树的元素数。
对于右子树处理来说,中序遍历所要处理的位置就是根节点右侧的所有数字,所以自然起始位置就是i+1,结束位置就是iend;对于前序遍历来说,就是从左侧子树最后一个元素后面那个数字到最后一个,所以起始位置是pstart + i - istart + 1,结束位置是pend

代码实现