|
|
|
|
|
s********u
发帖数: 1109 | 6 Phone interview，美国人，说话很清楚。不过太健谈了，导致他每次描述问题，说一
大堆，还各种打比方，要搞清楚whole picture真是太费劲了。。
不过人比较nice，希望好运吧。
1.他说warm up一下，说了一大堆，我才搞明白他的意思是，电影里经常有人拿报纸剪
下很多字母，然后拼成一句话去给别人发威胁message之类。（他一上来就说kidnap小
女孩之类，把我吓坏了，以为要写个绑匪和cops的design题。。。。）
然后让我实现一个function，看看能不能拼成一个message。
因为时间过了挺久，我就有点着急，赶紧写了一个hashtable的方法。然后他问我如果
这个message有重复单词怎么办，我才发现自己的bug（只是考虑newspaper里有没有这
个字母，而没有考虑字母的数量），改了一下。
bool compose( string msg, string newspaper){
unordered_map ccnt;
for(auto it = newspaper.begin(); it != newspa... 阅读全帖 |
|
a******e
发帖数: 710 | 7 2.他说他也是听说来的这道题，又是讨论描述了N久才搞明白，还跟我扯你知道为啥美
国分成这48个州么。。。比如给一个矩阵
1 2 2 3 (5)
3 2 3 (4) (4)
2 4 (5) 3 1 Atlantic
(6) (7) 1 4 5
(5) 1 1 2 4
#####请问括号里面的数字是什么意思？
每个数字代表该地区的海拔，然后西边是太平洋，东边是大西洋，让我返回所有path，
每个path能连通大西洋和太平洋，水只能从高处往低处走。
我到最后才发现他这个例子好像有点不对（他说他也不是很清楚，别人给他的。。汗）
，我觉得真正的意思应该是水流是单向的，否则岂不是随便怎么走都能连通？？
#####若问这里提到的backtracking和recursion有何不同？ 我一直不太了解
backtracking
我就用backtracking的方法，有点类似boggle game那题，从西海岸的点出发，往8个方
向走，如果没超出边界或者没用过，就走下去，直到到达东海岸，把这个路径存下来。
电面结束我才发现我有个bug，就是说，到达东海岸的时候不应该return，... 阅读全帖 |
|
s********u
发帖数: 1109 | 8 Phone interview，美国人，说话很清楚。不过太健谈了，导致他每次描述问题，说一
大堆，还各种打比方，要搞清楚whole picture真是太费劲了。。
不过人比较nice，希望好运吧。
1.他说warm up一下，说了一大堆，我才搞明白他的意思是，电影里经常有人拿报纸剪
下很多字母，然后拼成一句话去给别人发威胁message之类。（他一上来就说kidnap小
女孩之类，把我吓坏了，以为要写个绑匪和cops的design题。。。。）
然后让我实现一个function，看看能不能拼成一个message。
因为时间过了挺久，我就有点着急，赶紧写了一个hashtable的方法。然后他问我如果
这个message有重复单词怎么办，我才发现自己的bug（只是考虑newspaper里有没有这
个字母，而没有考虑字母的数量），改了一下。
bool compose( string msg, string newspaper){
unordered_map ccnt;
for(auto it = newspaper.begin(); it != newspa... 阅读全帖 |
|
a******e
发帖数: 710 | 9 2.他说他也是听说来的这道题，又是讨论描述了N久才搞明白，还跟我扯你知道为啥美
国分成这48个州么。。。比如给一个矩阵
1 2 2 3 (5)
3 2 3 (4) (4)
2 4 (5) 3 1 Atlantic
(6) (7) 1 4 5
(5) 1 1 2 4
#####请问括号里面的数字是什么意思？
每个数字代表该地区的海拔，然后西边是太平洋，东边是大西洋，让我返回所有path，
每个path能连通大西洋和太平洋，水只能从高处往低处走。
我到最后才发现他这个例子好像有点不对（他说他也不是很清楚，别人给他的。。汗）
，我觉得真正的意思应该是水流是单向的，否则岂不是随便怎么走都能连通？？
#####若问这里提到的backtracking和recursion有何不同？ 我一直不太了解
backtracking
我就用backtracking的方法，有点类似boggle game那题，从西海岸的点出发，往8个方
向走，如果没超出边界或者没用过，就走下去，直到到达东海岸，把这个路径存下来。
电面结束我才发现我有个bug，就是说，到达东海岸的时候不应该return，... 阅读全帖 |
|
R*****i
发帖数: 2126 | 10 CSDN上的编程挑战题。
http://hero.csdn.net/Question/Details?ID=610&ExamID=605
我的算法貌似不对，请问正确算法是神马？
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
namespace GridWalk
{
class Program
{
static void Main(string[] args)
{
List nlist = new List();
string line = Console.ReadLine();
while (!string.IsNullOrEmpty(line))
{
nlist.Add(int.Parse(line));
... 阅读全帖 |
|
d****n
发帖数: 1637 | 11 okay,没代码没真相。
here is my shabby codes and I want to share with you all.
output and analysis will be post soon
//file name matrix_op.c
#include
#include
#include
#include
#include
#include
#define _MX_INIT(type_t, row, col) ({ int i;\
type_t ** ret;\
ret=(type_t ** )malloc( row *sizeof(type_t*));\
for(i=0;i
(ret);\
})
#defin... 阅读全帖 |
|
t******e
发帖数: 98 | 12 来自主题: JobHunting版 - 要去面试了 这是我当年考过的面试题，可以负责的告诉你这题面试中不会再考到了，不过拿来练
coding还是很好的，topcoder上面也考过类似的问题。解法如下：
Let the input matrix be x[n][n]. The idea is to calculate two auxiliary
matrices a[n][n], where a[i][j] records the length of the all 1 horizontal
edge to the right of a[i][j], and b[n][n], where b[i][j] records the length
of the all 1 vertical edge above a[i][j]. Then the size of the largest all 1
boundary sub-square whose left bottom corner is a[i][j] is t = max{0≤t≤
min(a[i][j], b[i][j])|a[i-t+1][j]≥t and b[i][j+t-1]≥t... 阅读全帖 |
|
f*******5
发帖数: 52 | 13
有个思路是时间空间都是O(v^2) v是点的个数，比如这个图:
0 - 1 2
| |
3 - 4 - 5
v就是5。思路是DP，先预处理，建一个数组p[v][v]，p[i][j]为true 表示从i 到 j 这
条线上没有间断,并且i和j在一行或一列，在一行的话p[i][j]为true if i 到 j左边的
点为true并且j左边的点到j有边，在一列的话同理。预处理这一步是O(v^2)。
然后遍历每个点，在每个点的时候测试每个长度是否组成正方形，这一步也是O(v^2)。
下面是代码
void preprocess(vector >& arr, vector >& temp, int
row, int col){
int v = row*col;
for(int len = 1; len
for(int from = 0; from
if(from/col-len >=0){
... 阅读全帖 |
|
k*******3
发帖数: 1909 | 14 下面这个程序来自Data structures and algorithms in C++ by Adam Drozdek
第四章的迷宫（maze）程序。
我的疑问是最后几行main函数里面的Maze().exitMaze();怎么解释，我想不通语法是怎
么样的。
Maze()是调用哪个函数呢？如果是Maze class的Maze() constructor,难道不用先定义
一个Maze 对象吗？
谢谢。
#include
#include
#include
using namespace std;
template
class Stack : public stack {
public:
T pop() {
T tmp = top();
stack::pop();
return tmp;
}
};
class Cell {
public:
Cell(int i = 0, int j = 0) {
x = i; y... 阅读全帖 |
|
l******6
发帖数: 340 | 15 问一道题～
2D knapsack
class rect{
public:
int width;
int height;
int area;
};
input: vector source , int canvasWidth , int canvasHeight
no overlap allowed , no rotate allowed, each rect int source and be used as
many times as
possible (area = width * height , setting area as another val will be a
similar problem)
compute the max coverage of canvas using the rects int the source
a dp solution
maxCover[row][col] = max (maxCover[subRow][col] + maxCover... 阅读全帖 |
|
p********m
发帖数: 325 | 16 In case anybody curious about pathology departments ranking in the US, here is one from B"LUE RIDGE INSTITUTE for MEDICAL RESEARCH. The last column may be the research fundings received by that pathology department
Rank Institution City State Pathology
1 UNIV OF PENNSYLVANIA SCH OF MEDICINE PHILADELPHIA PENNSYLVANIA $38,661,181
2 UNIVERSITY OF WASHINGTON SCH OF MEDICINE SEATTLE WASHINGTON $34,202,524
3 JOHNS HOPKINS UNIVERSITY SCH OF MEDICINE ... 阅读全帖 |
|
p********m
发帖数: 325 | 17 In case anybody curious about pathology departments ranking in the US, here is one from B"LUE RIDGE INSTITUTE for MEDICAL RESEARCH. The last column may be the research fundings received by that pathology department
Rank Institution City State Pathology
1 UNIV OF PENNSYLVANIA SCH OF MEDICINE PHILADELPHIA PENNSYLVANIA $38,661,181
2 UNIVERSITY OF WASHINGTON SCH OF MEDICINE SEATTLE WASHINGTON $34,202,524
3 JOHNS HOPKINS UNIVERSITY SCH OF MEDICINE ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 18 我写的 boggle 游戏算法，DFS + trie.
一秒以内给出所有 5x5 的答案。
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Trie {
bool end;
Trie *children[26];
Trie() {
end = false;
memset(children, NULL, sizeof(children));
}
void insert(const char *word) {
const char *s = word;
Trie *p = this;
while (*s) {
int j = *s-'A';
assert(0 <= j && j < 26);
if (!p->childre... 阅读全帖 |
|
d********m
发帖数: 101 | 19 思路是从4个边界分别检测，如果是O就替换为T。最后在整体遍历一次，把O的改为X，T
改为O。
过不去的那个test case超级长，自己测不了。麻烦各位大侠给看看代码。
谢谢先～
class Solution {
public:
void turn (int row, int col, vector> &board) {
if (row < 0 || row >= board.size() || col < 0 || col >= board[0].
size() || board[row][col] != 'O' ) {
return;
}
board[row][col] = 'T';
turn(row + 1, col, board);
turn(row - 1, col, board);
turn(row, col + 1, board);
turn(row, col - 1, board);
... 阅读全帖 |
|
r*****e
发帖数: 792 | 20 和下面说的思想一样，但是要注意一点，code有注释，否则所有entry都变成0了。
for (row=0; row
for (col=0; col
if (mat[row][col]==0) {
if (!foundZero) {
foundZero=true;
therow=row;
thecol=col;
} else {
mat[therow][col]=0;
mat[row][thecol]=0;
}
}
}
}
if (!foundZero) return;//do nothing
for (col=0; col
if (mat[therow][col]==0 && col!=thecol) {//col!=thecol is meant to ... 阅读全帖 |
|
j****i
发帖数: 68152 | 21 笑掉大牙。工资真高啊
UM_DEARBORN Tsui,Louis Y ASSOC PROFESSOR Dbn Col of Eng-Computer &
Info 84,568.00
UM_DEARBORN Elenbogen,Bruce S ASSOC PROFESSOR Dbn Col of Eng-
Computer & Info 88,880.00
UM_DEARBORN Maxim,Bruce R ASSOC PROFESSOR Dbn Col of Eng-Computer &
Info 89,225.00
UM_DEARBORN Yoon,David Hwa ASSOC PROFESSOR Dbn Col of Eng-Computer
& Info 92,978.00
UM_DEARBORN Guo,Jinhua ASSOC PROFESSOR Dbn Col of Eng-Computer &
Info 102,275.00
UM_DEARBORN... 阅读全帖 |
|
j****i
发帖数: 68152 | 22 计算机系的副教授，跟码公码农哪个高？
UM_DEARBORN Tsui,Louis Y ASSOC PROFESSOR Dbn Col of Eng-Computer &
Info 84,568.00
UM_DEARBORN Elenbogen,Bruce S ASSOC PROFESSOR Dbn Col of Eng-
Computer & Info 88,880.00
UM_DEARBORN Maxim,Bruce R ASSOC PROFESSOR Dbn Col of Eng-Computer &
Info 89,225.00
UM_DEARBORN Yoon,David Hwa ASSOC PROFESSOR Dbn Col of Eng-Computer
& Info 92,978.00
UM_DEARBORN Guo,Jinhua ASSOC PROFESSOR Dbn Col of Eng-Computer &
Info 102,275.00
UM_... 阅读全帖 |
|
s******o
发帖数: 2233 | 23 是不是正解不知道，不过pass了OJ的large case:
bool validate(int col, const vector& cols) {
int row = cols.size();
for (int i = 0; i < row; ++i) {
if (col == cols[i] || (row - i == abs(col - cols[i]))) {
return false;
}
}
return true;
}
int Helper(int n, vector& cols) {
if (cols.size() == n) {
return 1;
}
int sum = 0;
for (int i = 0; i < n; ++i) {
if (validate(i, cols)) {
cols.push_back(i);
sum += Helper(n, cols);
cols.pop_back();
}
}
ret... 阅读全帖 |
|
T****s
发帖数: 915 | 24 用python 实现，可是不知道问题出在哪里，结果显示output 和 input 一模一样。
请教大家。
谢谢。
~~~~~~~~~~~~~~~~~
class Solution:
# @param board, a 9x9 2D array
# Solve the Sudoku by modifying the input board in-place.
# Do not return any value.
class _State:
def __init__(self, board, row, col, rowsum, colsum, blocksum):
# board --- the board at the current state
# whichRow and whichCol --- row and col indices that need to
work
on (unfilled)
# rowStat, colStat and blockStat... 阅读全帖 |
|
w****x
发帖数: 2483 | 25 一直认为面试出这么难得题真是过分啊！！
================= kth element in young tablet (M+N)log(numeric range)
solution ===========
const int M = 4;
const int N = 4;
int getOrder(int A[M][N], int tg)
{
int c = 0;
int i = 0;
int j = N-1;
while (i < M && j >= 0)
{
if (A[i][j] >= tg)
j--;
else
{
c += j+1;
i++;
}
}
return c+1;
}
int getKthMin(int A[M][N], int k)
{
if (k <= 0 || k > M*N)
return INT_MIN;
int nBe... 阅读全帖 |
|
r**********d
发帖数: 510 | 26 我请教一个问题。
我想把 http://q.stock.sohu.com/app2/rpsholder.up?code=&sd=2013-7-13&ed=&type=date&dir=1&p=1
上的数据用 php DOM parse， 然后写道数据库中。 但
sohu encoding是gbk, php dom parse 后的encoding是ascii, 我 百度的很多， 试了
一些方法，都不能显示。
我现在只希望能在mysql 用utf8 ecoding 里显示中文。 然后我用 csmar数据做一些分
析。
各位大牛请指点迷津。我叮当包子相报。
$con = mysql_connect($host, $user, $pass);
if (!$con) {
echo "Could not connect to server\n";
trigger_error(mysql_error(), E_USER_ERROR);
} else {
echo "Connection established\n";
}
$ok = mysql_select_d... 阅读全帖 |
|
c**t
发帖数: 2744 | 27 in oracle, join table a and b on col, which is a nullable column
a.col = b.col doesn't match all
( a.col is null and b.col is null )
OR
( a.col is not null and b.col is not null and a.col = b.col )
does
nvl(a.col, 'N/A') = nvl( b.col, 'N/A') seems work, but if a.col is null and
b.col is 'N/A', then it will fail.
What's the best way to compare them? |
|
r**********d
发帖数: 510 | 28 【 以下文字转载自 BuildingWeb 讨论区 】
发信人: rslgreencard (IS), 信区: BuildingWeb
标 题: php DOM parse 中文乱码问题
发信站: BBS 未名空间站 (Mon Jan 13 23:20:10 2014, 美东)
我请教一个问题。
我想把 http://q.stock.sohu.com/app2/rpsholder.up?code=&sd=2013-7-13&ed=&type=date&dir=1&p=1
上的数据用 php DOM parse， 然后写道数据库中。 但
sohu encoding是gbk, php dom parse 后的encoding是ascii, 我 百度的很多， 试了
一些方法，都不能显示。
我现在只希望能在mysql 用utf8 ecoding 里显示中文。 然后我用 csmar数据做一些分
析。
各位大牛请指点迷津。我叮当包子相报。
$con = mysql_connect($host, $user, $pass);
if (!$con) {
echo "Could n... 阅读全帖 |
|
i**********e
发帖数: 1145 | 29 这是用矩阵来储存，利用 spiral 的形式填满矩阵，最后再一行一行打印。
感觉面试时利用这方法比较直观，不容易出错。
#include
#include
using namespace std;
const int N_MAX = 100;
void fill(int row, int col, int dx, int dy, int startVal, int numToFill, int
mat[][N_MAX]) {
int currVal = startVal;
int endVal = startVal + numToFill - 1;
for (int r = row, c = col; currVal <= endVal; r += dy, c += dx) {
mat[r][c] = currVal;
currVal++;
}
}
void generateMatrix(int n, int mat[][N_MAX]) {
if (n <= 0) return;
int row = ... 阅读全帖 |
|
r*c
发帖数: 167 | 30 using System;
using System.Collections.Generic;
namespace WinningGame
{
class Program
{
static void Main(string[] args)
{
int nCount = 0;
int nTotalGames = 1000;
for (int i = 0; i < nTotalGames; i++)
{
Board bd = new Board();
//bd.PrintBoard();
bool bResult = bd.IsWinner();
if (bResult)
{
nCount++;
bd.Print... 阅读全帖 |
|
a**********0
发帖数: 422 | 31 为什么一定要用DFS 不是类似surrounded reigions 吗 可以用 BFS
只不过要设一个variable用于记录cluster的数目
而且BFS过后的要label一下表示不能继续使用 我试着贴一下代码
private void bfs(char[][] board, int i, int j) {
int row = board.length;
int col = board[0].length;
ArrayList queue = new ArrayList();
queue.add(i * col + j);
board[i][j] = 'P';
while (!queue.isEmpty()) {
int cur = queue.get(0);
queue.remove(0);
int x = cur / col;... 阅读全帖 |
|
a**********0
发帖数: 422 | 32 为什么一定要用DFS 不是类似surrounded reigions 吗 可以用 BFS
只不过要设一个variable用于记录cluster的数目
而且BFS过后的要label一下表示不能继续使用 我试着贴一下代码
private void bfs(char[][] board, int i, int j) {
int row = board.length;
int col = board[0].length;
ArrayList queue = new ArrayList();
queue.add(i * col + j);
board[i][j] = 'P';
while (!queue.isEmpty()) {
int cur = queue.get(0);
queue.remove(0);
int x = cur / col;... 阅读全帖 |
|
a********e
发帖数: 53 | 33 这种用dfs的时间复杂度，总是绕不清楚。
code如下，
分析时间复杂度哪种比较对？
一种是dfs一共执行了n！次，每次有n^2, 所以总共是O(n!n^2).
另一种是T(n)= nT(n-1) + n^2, 所以是? 我也不知道了。
////////////////////////////////////
bool PosOK(int col[], int idx){
for ( int i=0; i< idx; i++){
if (col[i]== col[idx] || (idx-i)== abs(col[idx] - col[i] ) )
return false;
}
return true;
}
void dfs2(int col[], int idx, vvs & res, int n){
//when there is a solution
if (idx==n){
string s(n, '.');
vs tmp(n, s);
for (int i=0; i< n; i++)
tmp[i][co... 阅读全帖 |
|
y******d
发帖数: 65 | 34 graph on the left
plot(1,1,type="n",xlim=c(1,5),ylim=c(1,5))
lines(c(2:4),c(4:2),lty=1,col="red")
points(2,4,pch=21,col="blue")
points(4,2,pch=21,col="blue")
graph on the right
plot(1,1,type="n",xlim=c(1,5),ylim=c(1,5))
lines(c(1:2),rep(2,length(c(1:2))),lty=1,col="red")
lines(c(2:3),rep(3,length(c(1:2))),lty=1,col="red")
lines(c(3:4),rep(4,length(c(1:2))),lty=1,col="red")
points(1,2,pch=21,col="blue")
points(2,2,pch=19,col="blue")
points(2,3,pch=21,col="blue")
points(3,3,pch=19,col="blue")
poin... 阅读全帖 |
|
i**********e
发帖数: 1145 | 35 I think you need to do DFS from all possible starting points in the grid, not just the top left point.
My code below for reference (does not return the path but return if the word is in the grid or not, should be easy to modify to return the path) :
#include
#include
using namespace std;
const int MAX_ROWS = 100;
const int MAX_COLS = 100;
bool dfs(char grid[][MAX_COLS], int row, int col, int m, int n,
int charIndex, string target, bool visited[][MAX_COLS]) {
if (ro... 阅读全帖 |
|
g**********y
发帖数: 14569 | 36 这是书上的答案，它把isSquare()当成O(1)的operation.
1 public static Subsquare findSquare(int[][] matrix){
2 assert(matrix.length > 0);
3 for (int row = 0; row < matrix.length; row++){
4 assert(matrix[row].length == matrix.length);
5 }
6
7 int N = matrix.length;
8
9 int currentMaxSize = 0;
10 Subsquare sq = null;
11 int col = 0;
12
13 // Iterate through each column from left to right
14 while (N - col > currentMaxSize) { // See step 4 above
15 for (int row = 0; row < matrix.length; row++){
16 // starting from ... 阅读全帖 |
|
w****x
发帖数: 2483 | 37 careercup上的一道题：
Imagine you have a square matrix, where each cell is filled with either
black or white. Design an algorithm to find the maximum subsquare such that
all four borders are filled with black pixels.
Assumption: Square is of size NxN.
This algorithm does the following:
1. Iterate through every (full) column from left to right.
2. At each (full) column (call this currentColumn), look at the subcolumns (
from biggest to smallest).
3. At each subcolumn, see if you can form a square with ... 阅读全帖 |
|
d*********g
发帖数: 38 | 38 可以过80%的test cases，一个很大的grid结果总是差1。哪位高人看看下面code逻辑有
什么问题吗？不超时。刚才上eclipse跑，数1数的眼睛都快瞎了。
public int numIslands(char[][] grid) {
if(grid==null || grid.length==0 || grid[0].length==0)
return 0;
int row=grid.length, col=grid[0].length;
int res=0;
for(int i=0; i
for(int j=0; j
if(grid[i][j]=='1'){
bfs(i, j, grid);
res++;
}
}
}
... 阅读全帖 |
|
j****i
发帖数: 68152 | 39 计算机系助理教授，跟小硕码农比很有优势吗？
UM_DEARBORN Ma,Di ASST PROFESSOR Dbn Col of Eng-Computer & Info
88,334.00
UM_DEARBORN Xu,Zhiwei ASST PROFESSOR Dbn Col of Eng-Computer & Info
88,701.00
UM_DEARBORN Zeng,Kai ASST PROFESSOR Dbn Col of Eng-Computer & Info
90,000.00
UM_DEARBORN Wang,Shengquan ASST PROFESSOR Dbn Col of Eng-Computer &
Info 94,637.00
UM_DEARBORN Hossain,Afzal Asst Professor Dbn Col of Eng-Electric &
Comp 0.00
UM_DEARBORN Malik,Hafiz M... 阅读全帖 |
|
a***e
发帖数: 413 | 40 这样是不是 O(N^N)的复杂度?
class Solution {
public:
int maximalRectangle(vector > &matrix) {
int row=matrix.size();
if (row==0) return 0;
int col=matrix[0].size();
if (col==0) return 0;
//find all disjoint rectangles
vector> flag(row, vector(col,false));
int maxArea=INT_MIN;
for (int r=0; r
for (int c=0; c
{
int area=0;
if (matrix[... 阅读全帖 |
|
i**********e
发帖数: 1145 | 41 来自主题: Programming版 - 编程题一道 Thanks LZ for sharing this interesting question.
Nice solution!
I agree with thrust that there's no need to store a 2d-array, but I think it
doesn't hurt to ask the interviewer which approach he/she wants.
Basically, you need to make an observation that the grid can be divided into
four areas: upper, lower, left, and right.
The equation for the number in the grid's corner is easy to derived.
Then, you can obtain the actual number by adding the difference either in x
or y coordinate relative to t... 阅读全帖 |
|
r*c
发帖数: 167 | 42 //矩阵求连接图
#include
#include
#include
#include
#include
using namespace std;
enum ColorEnum{White, Black};
struct Cell
{
int row;
int col;
Cell(int r, int c): row(r), col(c){}
};
struct Cluster{
bool visited;
vector vec;
Cluster(int i, int j) : visited(false) {
vec.push_back(Cell( i, j));
}
bool isWithinRange(const Cell& a, const Cell& b){
return abs(a.row - b.row) <= 1 ... 阅读全帖 | |
|
r*c
发帖数: 167 | 43 //矩阵求连接图
#include
#include
#include
#include
#include
using namespace std;
enum ColorEnum{White, Black};
struct Cell
{
int row;
int col;
Cell(int r, int c): row(r), col(c){}
};
struct Cluster{
bool visited;
vector vec;
Cluster(int i, int j) : visited(false) {
vec.push_back(Cell( i, j));
}
bool isWithinRange(const Cell& a, const Cell& b){
return abs(a.row - b.row) <= 1 ... 阅读全帖 | |
|
s*****b
发帖数: 8 | 44 我来贴一个。
Rocket fule (Software Engineer - Machine Learning Scientist ) 技术电面后code
test. code通过了所有test cases. 人家看过code 后就拒了。问题在哪里呢？请各位
牛人不吝赐教。题目本版以前贴过
You are standing in a rectangular room and are about to fire a laser toward
the east wall. Inside the room a certain number of prisms have been placed.
They will alter the direction of the laser beam if it hits them. There
are north-facing, east-facing, west-facing, and south-facing prisms. If the
laser beam strikes an east-facing prism, its cours... 阅读全帖 |
|
f**********t
发帖数: 1001 | 45 来自主题: JobHunting版 - 面试题讨论 #include "common.h"
void CS_(const vector &vs, size_t up, size_t down, size_t col,
map> &graph) {
size_t uu = up;
while (uu < down && vs[uu].size() <= col) {
++uu;
}
if (uu + 1 >= down) {
return;
}
char pre = vs[uu][col];
for (size_t dd = uu + 1; dd < down; ++dd) {
if (vs[dd].size() <= col) {
continue;
}
if (pre != vs[dd][col]) {
graph[pre].insert(vs[dd][col]);
if (uu + 1 < dd) {
CS_(vs, uu, dd... 阅读全帖 |
|
j******8
发帖数: 105 | 46 最后有问题，
q.offer((px+1)*col+py);
q.offer((px-1)*col+py);
q.offer(px*col+py+1);
q.offer(px*col+py-1);//px=1, py=0 will still give valid n
here which is wrong
改成这样
if(px+1
if(px-1>=0) q.add((px-1)*col+py);
if(py+1
if(py-1>=0) q.add(px*col+py-1);
算法本身就是错的，过了的cases是运气 |
|
k******k
发帖数: 6800 | 47 广泛而大量的：
Xiushui River
Date : March, 1939
Place : Nanchang, China
Opponent : Chinese Army
Artillery Unit
Commander
Artillery
6th Field Heavy Artillery Brigade HQ
Major Gen. Sumita
13th Field Heavy Artillery Regiment
Lt. Col. Okoshi
24 Type 4 15cm Howitzers
14th Field Heavy Artillery Regiment
Lt. Col. Maruyama
24 Type 4 15cm Howitzers
10th Field Heavy Artillery Regiment
Lt. Col. Nagaya
24 Type 4 15cm Howitzers
15th Independent Field Heavy Art... 阅读全帖 |
|
j******s
发帖数: 48 | 48 public ArrayList> permuteUnique(int[] num) {
Arrays.sort(num);
ArrayList> output
= new ArrayList>();
ArrayList list = new ArrayList();
boolean col[] = new boolean[num.length];
permute(output,list,col,num,0);
return output;
}
public void permute(ArrayList> output,
ArrayList list,boolean col[]... 阅读全帖 |
|
d**********x
发帖数: 4083 | 49 这个优化之后用的时间大概是顶楼解法的一半(leetcode, 1020ms vs 530ms)
为了清晰起见我就没用bitarray，这个解法的额外空间还是比较多。。
#include
#include
using namespace std;
class Solution {
public:
int totalNQueens(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
n_ = n;
principal_diagonal_.resize(2 * n - 1);
principal_diagonal_.assign(2 * n - 1, 0);
minor_diagonal_.resize(2 * n - 1);
minor_diagonal_.assign(2 * n - 1, 0);
... 阅读全帖 |
|
a********g
发帖数: 36 | 50 用动态规划.
开个m*n的额外空间.
每个cell有个row和col值
if arr[i][j] != 0
row[i][j] 和 col [i][j]
有三个候选项:
1) row[i][j] = row[i-1][j] +1; col[i][j] = 1;
2) col[i][j] = col[i][j-1]; row[i][j] = 1;
3) row[i][j] = min(row[i-1][j], row[i][j-1]) +1 ; col[i][j] = min(col[i-1][j
], col[i][j-1])+1;
取 row[i[j]]*co[i][]j最大的那一个候选项.
这个需要画个图就比较容易想清楚,说明白. |
|
