p****n 发帖数: 4 | 1 一道面试题 for a big company in java , the efficiency solution?
25 24 23 22 21
10 9 8 7 20
11 2 1 6 19
12 3 4 5 18
13 14 15 16 17
Starting with the number 1 and moving to the right in a counter-clockwise
direction a 5 by 5 螺旋 is as above, sum the 对角线:
for example 21 + 7 + 1 + 3 + 13 | n****e 发帖数: 678 | 2 不太明白题目,能再说说吗?
【在 p****n 的大作中提到】 : 一道面试题 for a big company in java , the efficiency solution? : 25 24 23 22 21 : 10 9 8 7 20 : 11 2 1 6 19 : 12 3 4 5 18 : 13 14 15 16 17 : Starting with the number 1 and moving to the right in a counter-clockwise : direction a 5 by 5 螺旋 is as above, sum the 对角线: : for example 21 + 7 + 1 + 3 + 13
| p****n 发帖数: 4 | 3 Get the Sum of 对角线 of 螺旋(线) in n X n
Starting with the number 1 and moving to the right in a counter-clockwise
direction a 5 by 5 .
The issue is that the 1 is in the middle.
Normally:
for example :螺旋(线) (3X3)
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
[leetcode]Spiral Matrix II
(2013-03-12 15:14:57)
转载▼
标签:
分类: leetcode
Given an integer n, generate a square matrix filled with elements from 1 to
n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
class Solution {
public:
vector > generateMatrix(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > matrix;
int pi = 0;
int w = n;
int cur = 1;
vector tmp;
for(int i = 0;i < n;i++)
tmp.push_back(0);
for(int i = 0;i < n;i++)
matrix.push_back(tmp);
while(w >= 0)
{
dealWithRect(pi,w,cur,matrix);
w -= 2;
pi += 1;
}
return matrix;
}
void dealWithRect(int pi,int w,int & cur,vector > &matrix)
{
if(w == 0)
return;
if(w == 1)
{
for(int i = 0; i < w;i++)
matrix[pi+i][pi] = cur++;
return;
}
for(int i = 0; i < w;i++)
matrix[pi][pi+i] = cur++;
for(int i = 1; i < w-1;i++)
matrix[pi+i][pi+w-1] = cur++;
for(int i = w-1; i >= 0;i--)
matrix[pi+w-1][pi+i] = cur++;
for(int i = w-2; i >= 1;i--)
matrix[pi+i][pi] = cur++;
}
};
one solution:
using System;
using System.Collections;
using System.Text;
namespace Test
{
class Diagsum
{
static void Main(string[] args)
{
Console.WriteLine(sumdiagprimes(5));
Console.WriteLine(sumdiagprimes(75));
}
public static string sumdiagprimes(int size)
{
long startTime = DateTime.Now.Ticks;
int j = 2;
ArrayList primes = new ArrayList();
while (primes.Count < Math.Pow(size, 2))
{
if (isprime(j))
{
primes.Add(j);
}
j++;
}
primes.Reverse();
int p = size - 1;
int q = 0;
int iter = 0;
ArrayList result = new ArrayList();
while(q<=primes.Count-1 && p>0)
{
for(int i=1; i<=5; i++)
{
iter++;
if (q <= primes.Count - 1)
{
//Console.WriteLine("p="+p+" q="+q);
if (result.Count==0 || (result[result.Count - 1] !=
primes[q]))
{
result.Add(primes[q]);
}
q = q + p;
}
else
{
break;
}
}
//Console.WriteLine("old q=" + q);
q = q - p;
//Console.WriteLine("new q="+q);
p=p-2;
}
if((size % 2) != 0)
{
result.Add(result[result.Count-1]);
}
Int64 resultsum = 0;
for (int i = 0; i <= result.Count-1; i++)
{
resultsum = resultsum + Convert.ToInt64(result[i]);
}
//PrintValues(result);
long endTime = DateTime.Now.Ticks;
TimeSpan timeTaken = new TimeSpan(endTime - startTime);
return "size: "+size+"\r\niter: "+iter+"\r\ntime: "+timeTaken.
ToString()+"\r\n sum: "+resultsum+"\r\n\r\n";
}
public static bool isprime(int number)
{
int i = 0;
if (number < 2)
{
return false;
}
else
{
for (i = 2; i <= (number / 2); i++)
{
if (number % i == 0)
{
return false;
}
}
return true;
}
}
public static void PrintValues(IEnumerable myList)
{
foreach (Object obj in myList)
Console.Write("{0},", obj);
Console.WriteLine();
}
}
} | p*****2 发帖数: 21240 | 4 (defn f [n]
(defn dfs [i pre sum]
(cond
(= i n) sum
:default
(let [curr (+ pre (* 2 i))]
(dfs (inc i) curr (+ sum curr)))))
(dfs 1 1 1)) | l*n 发帖数: 529 | 5 21=(25+17)/2;
7=(9+5)/2;
1=(1+1)/2;
3=(5*2-7);
13=(17*2-21);
就是利用很多等腰三角形,画画看就知道了。
【在 p****n 的大作中提到】 : 一道面试题 for a big company in java , the efficiency solution? : 25 24 23 22 21 : 10 9 8 7 20 : 11 2 1 6 19 : 12 3 4 5 18 : 13 14 15 16 17 : Starting with the number 1 and moving to the right in a counter-clockwise : direction a 5 by 5 螺旋 is as above, sum the 对角线: : for example 21 + 7 + 1 + 3 + 13
| D**********d 发帖数: 849 | 6 int CounterDiagSum(int n){
if(n < 1) return 0;
int Cur = (n-1)*n + 1;
int Sum = Cur;
while(--n > 0){
Cur -= (n + n);
Sum += Cur;
}
return Sum;
} | n****e 发帖数: 678 | 7 能展开说说如何利用等腰三角形吗?
【在 l*n 的大作中提到】 : 21=(25+17)/2; : 7=(9+5)/2; : 1=(1+1)/2; : 3=(5*2-7); : 13=(17*2-21); : 就是利用很多等腰三角形,画画看就知道了。
| b******7 发帖数: 92 | 8 整个n*n矩阵可以看成n/2个正方形组成,第i个正方形边长为n-2*i,从(n-2*i)*(n-2*i
)的值开始递减
右上角值为(n-2*i) * (n-2*i) - (n-2*i) + 1
左下角值为(n-2*i)*(n-2*i) - 3(n-2*i - 1)
int sum(int n)
{
if(n < 1){
return 0;
}
int sum = 1;
for(int i = 1; i < n/2; i++){
int a = n-2*i;
sum += a*a - (a -1);
sum += a*a - 3*(a-1);
}
return sum;
}
【在 p****n 的大作中提到】 : 一道面试题 for a big company in java , the efficiency solution? : 25 24 23 22 21 : 10 9 8 7 20 : 11 2 1 6 19 : 12 3 4 5 18 : 13 14 15 16 17 : Starting with the number 1 and moving to the right in a counter-clockwise : direction a 5 by 5 螺旋 is as above, sum the 对角线: : for example 21 + 7 + 1 + 3 + 13
| p****n 发帖数: 4 | 9 The answer(5X5) should be 45.
10 X 10 should be 340.
螺旋矩阵(由内向外, This question also check the way to generate a 螺旋矩阵
(由内向外), move the "point" in related directions and then calculate one
of the 对角线 sum. |
|