数组中k个数的最大偶数和

2020-05-26 | algorithm

题目

长度为m的数组,是否存在k个数的和为偶数,且和为最大和。
example:

1
2
3
4
5
6
7
8
input: [123,12,424,32,43,25,46] 4;
output: 636;

input:[1000] 2;
output:-1

input: [1,3,5,7,9] 3;
output: -1

分析过程

首先判断数组M的长度是否小于k,如果小于k,则直接返回-1。
如果数组长度不小于k,则对现有数组进行排序,取排序结果N的前k位的和。判断当前k个数的和是否是偶数,如果是,返回当前和。如果不是,则循环判断排序N-K~N位置中是否存在一个数,使得结果成立。
ps:这里只判断是否存在一个数是因为,当最大和存在,但不为偶数的情况成立,则k mod 2 ≠ 0且构成N的数都为奇数。

排序方式

将数组的第Q项作为基准项(基准项为base。这里将Q取为0,但事实上,用任意一项都可以)。判断M[i](0<=i<M)是否大于base,如果大于,则替换base与M[i]值的位置,调换之后,遍历i-1~0(M的子数组subM,该数组已经是有序数组),将M[i]的值插入到subM中。如果小于等于,base=M[i]。

逻辑结构

排序的过程是按照中序遍历创建一颗二叉树,只要树的最左子树的节点个数等于k,则这个子树就是数组的最大和。如果最大和不是偶数,则按照中序遍历的规则,顺序寻找上层子树的节点是否存在可以满足的值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const result = (test, k) => {
let base = test[0];
let sum = 0;
let tempK = 0;
let sort = 0;
let tempOutside = 0;
let tempInside = 0;
let baseIndex = 0;
if (k > test.length) {
return -1;
}
for (let index = 1; index < test.length; index++) {
const element = test[index];
if (element > base) {
tempOutside = test[index];
test[index] = base;
test[baseIndex] = tempOutside;
for (let j = index - 1; j >= 0; j--) {
if (element > test[j]) {
tempInside = test[j];
test[j] = test[j + 1];
test[j + 1] = tempInside;
}
}
} else {
base = test[index];
}
baseIndex++;
}
while (tempK < k) {
sum += test[sort];
if (tempK === k - 1 && sum % 2 !== 0) {
sum -= test[tempK];
tempK--;
}
tempK++;
sort++;
}
return sum;
};

阅读更多

project review

2020-02-09

阅读更多

在TS中使用字符串作为索引访问对象

2020-01-04 | typescript

场景 & 问题

在访问对象的成员变量时,经常会用到使用字符串作为索引。在JS中,这样的用法是可以的。但是在TS中,当被访问的对象被赋予类型之后,这样的操作将会抛出异常,示例如下:

JS中

1
2
3
4
5
6
7
8
9
10
11
12
const testObj = {
key1: 1,
key2:2
};

// 获得存有当前对象所有Key(浅层)的一个数组 ["key1","key2"]
const tempKeys = Object.keys(testObj);
tempKeys.forEach((item)=>{

// 正常输出testObj中的值
console.log(testObj[key]);
});

上述代码将输出我们预期的结果。

TS中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
interface TestObjType {
key1:number;
key2:number;
}
const testObj:TestObjType = {
key1:1,
key2:2
}
type tempKeysType = keyof TestObjType

// 获得存有当前对象所有Key(浅层)的一个数组 ["key1","key2"]
const tempKeys = Object.keys(testObj) as Array <keyof TestObjType>;

//这里将会有一个报错,提示 :
//参数“item”和“value” 的类型不兼容。`不能将类型“string”分配给类型“"key1" | "key2"”.
//这表明了,即使tempKeysType是通过keyof 从TestObjType中获取到的,但是forEach的callback的参数类型,仍然无法通过TS的类型兼容性检查。
tempKeys.forEach((item:tempKeysType)=>{

//这里也会有一个报错:Element implicitly has an 'any' type because expression of type 'any' can't be used to index type 'TestObjType'。
// TS的类型推断,表示item存在隐式的any类型,而any类型在TS中无法作为obj的索引。同样这也表示了在进行对象的遍历时(在当前代码片段中),不能将any作为item的类型,去访问对象
console.log(testObj[key]);
});

tempKeys.forEach((item:string)=>{

//这里会有同样报错
console.log(testObj[key]);
});

解决思路

对于这一问题的出现,猜测可能是由于在

1
const tempKeys = Object.keys(testObj) as Array <keyof TestObjType>;

但此时可以看到,tempKeys的类型已经变成了

1
("key1"|"key2")[]

所以问题很可能是由 Object.keys的默认值导致的。
由此可得如下解决方案

解决方案

对于此问题,需要封装一个新的 keys 函数来解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 新的keys函数,使用O继承object
function keys<O extends object>(obj: O): Array<keyof O> {
return Object.keys(obj) as Array<keyof O>;
}

interface TestObjType {
key1:number;
key2:number;
}
const testObj:TestObjType = {
key1:1,
key2:2
}
type tempKeysType = keyof TestObjType

// 使用新的keys获得存有当前对象所有Key(浅层)的一个数组 ["key1","key2"]
const tempKeys = keys(testObj) ;

tempKeys.forEach((item:tempKeysType)=>{
console.log(testObj[key]);
});

上述代码将输出我们预期的结果。

阅读更多