上下翻转二叉树
给你一个二叉树的根节点 root ，请你将此二叉树上下翻转，并返回新的根节点。
你可以按下面的步骤翻转一棵二叉树：
原来的左子节点变成新的根节点
原来的根节点变成新的右子节点
原来的右子节点变成新的左子节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| var upsideDownBinaryTree = function(root) {
if (root && root.left === null) return root;
return fn(root, null);
};
function fn(node, pre) {
if (node === null) return pre;
if (node.left === null) return pre;
const currNode = {
val: node.left.val,
left: node.right ? generateTree(node.right.val) : null,
right: pre ? pre : generateTree(node.val)
}
return fn(node.left, currNode);
}
function generateTree(val) {
return {
val: val,
left: null,
right: null
}
}
|
链表
链表相加
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
function reverse(head){
if(head===null) return head;
let pre=null;
let cur=head;
let next=null
while(cur){
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
head=pre;
return head;
}
function addInList(head1,head2){
if(head1===null) return head2;
if(head2===null) return head1;
let l1=reverse(head1);
let l2=reverse(head2);
let dum=new ListNode(-1);
let p=dum;
let ca=0;
while(l1||l2){
let sum=ca;
if(l1){
sum+=l1.val;
l1=l1.next;
}
if(l2){
sum+=l2.val;
l2=l2.next;
}
ca=Math.floor(sum/10);
let val=sum%10;
p.next=new ListNode(val);
p=p.next;
}
if(ca>0) p.next=new ListNode(ca);
return reverse(dum.next);
}
module.exports = {
addInList : addInList
};
|
链表排序
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
| function sortInList(head) {
if(head==null || head.next==null) return head;
let slow = head,
fast = head.next;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
let temp = slow.next;
slow.next = null;
let left = sortInList(head);
let right = sortInList(temp);
let empty = {};
let pre = empty;
while(left!=null && right!=null){
if(left.val < right.val){
pre.next = left;
left = left.next;
}else{
pre.next = right;
right = right.next;
}
pre = pre.next;
}
pre.next = left!=null ? left : right;
return empty.next;
}
module.exports = {
sortInList: sortInList,
};
|
题目描述：
一队士兵在操场上排成一列，士兵总数为n，士兵按照队伍从前往后的顺序从1到n依次编号。每个士兵有各自的身高，第i个士兵的身高为ai。
士兵列队完毕后，将军走到队列的最前面。因为身高不一，有些士兵可能被前面身高更高的挡住了，这样将军就看不到他们。将军能看到某个士兵当且仅当他的身高严格大于他前面的所有士兵。
问将军一共能看到多少个士兵。
python示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def count_visible_soldiers(n, heights):
\
visible_count = 0
max_height_so_far = 0
for height in heights:
\
if height > max_height_so_far:
visible_count += 1
max_height_so_far = height
return visible_count
T = int(input().strip())
for _ in range(T):
n = int(input().strip())
heights = list(map(int, input().strip().split()))
print(count_visible_soldiers(n, heights))
|
Java示例代码
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
| import java.io.*;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(reader.readLine());
ArrayList list = new ArrayList<>(count);
for (int i = 0; i < count; i++) {
reader.readLine();
int num = 0;
int max = Integer.MIN_VALUE;
for (String s : reader.readLine().split(" ")) {
if(max < Integer.parseInt(s)) {
num++;
max = Integer.parseInt(s);
}
}
list.add(num);
}
for (int i = 0; i < count; i++) {
System.out.println(list.get(i));
}
}
}
|
C示例代码
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
| #include <stdio.h>
int main() {
int T, n, i;
int *soldiers; // 动态数组存储士兵身高
// 读取测试数据组数
scanf("%d", &T);
while (T--) {
// 读取士兵个数
scanf("%d", &n);
// 动态分配内存以存储士兵身高
soldiers = (int *)malloc(n * sizeof(int));
if (soldiers == NULL) {
printf("Memory allocation failed!\n");
return 1;
}
// 读取士兵身高
for (i = 0; i < n; i++) {
scanf("%d", &soldiers[i]);
}
// 计算并输出将军能看到的士兵数
int visible = 0, maxHeight = 0;
for (i = 0; i < n; i++) {
if (soldiers[i] > maxHeight) {
visible++;
maxHeight = soldiers[i];
}
}
printf("%d\n", visible);
// 释放内存
free(soldiers);
}
return 0;
}
|
JavaScript示例代码
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
41
42
| // process.stdin.on("data", function(data) {
// console.log("hello, " + data);
// });
const readline = require("readline")
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
})
var iter = rl[Symbol.asyncIterator]()
let read = async() => (await iter.next()).value
void async function(){
let num = await read(); // 测试数据的组数
num = parseInt(num);
let res_arr = []
for(let i=0; i<num; i++){
let n = await read(); // 每组数据的士兵个数
let tokens = await read();
let t_arr = tokens.split(" ").map(item=>Number(item))
let res = 0;
let target = 0;
if (t_arr.length>=1){
res = 1;
target = t_arr[0];
for(let j=1; j<t_arr.length; j++) {
if (t_arr[j]>target) {
res += 1;
target = t_arr[j];
}
}
}
res_arr.push(res);
}
res_arr.forEach(element => {
console.log(element)
});
}()
|
输入描述：第一行输入一个整数T（T<=100），表示测试数据的组数。每组数据第一行输入一个数n（1=<n<=10000）表示士兵的个数，第二行n个整数a1,a2,…,an（0=<ai<=1000000000），依次表示每一个士兵的身高。数字之间用空格隔开。
输出描述：对于每组数据，输出一行，将军能看到的士兵数。
输入样例：3 4 1 2 3 4 3 1 1 1 4 1 1 3 2
输出样例：4 1 2
题目描述：
洗牌在生活中十分常见，现在需要写一个程序模拟洗牌的过程。
现在需要洗2n张牌，从上到下依次是第1张，第2张，第3张一直到第2n张。首先，我们把这2n张牌分成两堆，左手拿着第1张到第n张（上半堆），右手拿着第n+1张到第2n张（下半堆）。接着就开始洗牌的过程，先放下右手的最后一张牌，再放下左手的最后一张牌，接着放下右手的倒数第二张牌，再放下左手的倒数第二张牌，直到最后放下左手的第一张牌。接着把牌合并起来就可以了。
例如有6张牌，最开始牌的序列是1,2,3,4,5,6。首先分成两组，左手拿着1,2,3；右手拿着4,5,6。在洗牌过程中按顺序放下了6,3,5,2,4,1。把这六张牌再次合成一组牌之后，我们按照从上往下的顺序看这组牌，就变成了序列1,4,2,5,3,6。
现在给出一个原始牌组，请输出这副牌洗牌k次之后从上往下的序列。
输入描述：第一行一个数T(T<=100)，表示数据组数。对于每组数据，第一行两个数n,k(1<=n,k<=100)，接下来一行有2n个数a1,a2,…,a2n(1<=ai<=1000000000)。表示原始牌组从上到下的序列。
输出描述：对于每组数据，输出一行，最终的序列。数字之间用空格隔开，不要在行末输出多余的空格。
输入样例：3 3 1 1 2 3 4 5 6 3 2 1 2 3 4 5 6 2 2 1 1 1 1
输出样例：1 4 2 5 3 6 1 5 4 3 2 6 1 1 1 1
