avatar
对角线Sum 螺旋(线)# JobHunting - 待字闺中
p*n
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
avatar
n*e
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

avatar
p*n
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();
}
}
}
avatar
p*2
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))
avatar
l*n
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

avatar
D*d
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;
}
avatar
n*e
7
能展开说说如何利用等腰三角形吗?

【在 l*n 的大作中提到】
: 21=(25+17)/2;
: 7=(9+5)/2;
: 1=(1+1)/2;
: 3=(5*2-7);
: 13=(17*2-21);
: 就是利用很多等腰三角形,画画看就知道了。

avatar
b*7
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

avatar
p*n
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.
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。