最长无重复子数组
描述
给定一个长度为n的数组arr,返回arr的最长无重复元素子数组的长度,无重复指的是所有数字都不相同。
子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组
数据范围:0\le arr.length \le 10^50≤arr.lengt**h≤105,0 < arr[i] \le 10^50<arr[i]≤105
示例1
输入:
[2,3,4,5]
复制
返回值:
4
说明:
[2,3,4,5]是最长子数组
示例2
输入:
[2,2,3,4,3]
返回值:
3
说明:
[2,3,4]是最长子数组
示例3
输入:
[9]
返回值:
1
示例4
输入:
[1,2,3,1,2,3,2,2]
返回值:
3
说明:
最长子数组为[1,2,3]
示例5
输入:
[2,2,3,4,8,99,3]
返回值:
5
说明:
最长子数组为[2,3,4,8,99]
代码:
/**
*
* @param arr int整型一维数组 the array
* @return int整型
*/
function maxLength( arr ) {
// 方法一
// 创建一个集合
let map=new Map();
// 初始化最大值
let max=-1;
// i用来遍历数组,j用来存储子数组初始下标
let i,j,len=arr.length;
for(i=0,j=0;i<len;i++){
// 判断map中是否重复存在arr[i];
if(map.has(arr[i])){
// 有重复,即判断当前值在map中的下标和之前存储的下标那个大,改变当前下标
j=Math.max(j,map.get(arr[i])+1);
}
// 存储当前值
map.set(arr[i],i);
// 判断当前最大值与当前值的下标减去子数组初始下标加一后那个大
max=Math.max(max,i-j+1);
}
return max;
}
module.exports = {
maxLength : maxLength
};
删除链表的倒数第n个节点
描述
给定一个链表,删除链表的倒数第 n 个节点并返回链表的头指针
例如,
给出的链表为: 1\to 2\to 3\to 4\to 51→2→3→4→5, n= 2n=2.
删除了链表的倒数第 nn 个节点之后,链表变为1\to 2\to 3\to 51→2→3→5.
数据范围: 链表长度 0\le n \le 10000≤n≤1000,链表中任意节点的值满足 0 \le val \le 1000≤val≤100
要求:空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)
备注:
题目保证 nn 一定是有效的
示例1
输入:
{1,2},2
返回值:
{2}
方法一:
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
function removeNthFromEnd( head , n ) {
// write code here
let p1=head,count=0;
while(p1){
count++;
p1=p1.next
}
let sum =count-n-1;
let p2=head;
while(sum>0){
p2=p2.next;
sum--;
}
if(sum==0){
p2.next=p2.next.next;
}else{
head=head.next;
}
return head;
}
module.exports = {
removeNthFromEnd : removeNthFromEnd
};
方法二:
let count=0;
let p=head;
let arr=[]
while(p){
count++;
arr.push(p.val)
p=p.next;
}
let cur=new ListNode(null);
let pre=cur;
let sum=count-n;
for(let i=0;i<arr.length;i++){
if(i==sum){
continue;
}
let node=new ListNode(arr[i]);
pre.next=node;
pre=pre.next;
}
return cur.next;
NC1 大数加法
描述
以字符串的形式读入两个数字,编写一个函数计算它们的和,以字符串形式返回。
数据范围:s.length,t.length \le 100000s.lengt**h,t.lengt**h≤100000,字符串仅由’0’~‘9’构成
要求:时间复杂度 O(n)O(n)
示例1
输入:
"1","99"
返回值:
"100"
说明:
1+99=100
示例2
输入:
"114514",""
返回值:
"114514"
代码:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 计算两个数之和
* @param s string字符串 表示第一个整数
* @param t string字符串 表示第二个整数
* @return string字符串
*/
function solve( s , t ) {
let str="";
let len1=s.length,len2=t.length;
let i,j;
// 使两个数值位数一致
while(len1>len2){
t="0"+t;
len2++;
}
while(len2>len1){
s="0"+s;
len1++;
}
let up=0;//定义进位
// 从后往前相加
for(i=len1-1;i>=0;i--){
// 两位数值相加并加上进位
let temp=Number(s[i])+Number(t[i])+up;
str=str+(temp%10+"");
// 更新进位
up=Math.floor(temp/10);
}
// 判断最后是否还需进位
if(up){
str=str+(up+"");
}
// 将结果反转并拼接
let str1=str.split("").reverse().join("");
return str1;
}
module.exports = {
solve : solve
};
NC14 按之字形顺序打印二叉树
描述
给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)
数据范围:0 \le n \le 15000≤n≤1500,树上每个节点的val满足 |val| <= 1500∣val∣<=1500
要求:空间复杂度:O(n)O(n),时间复杂度:O(n)O(n)
例如:
给定的二叉树是{1,2,3,#,#,4,5}
该二叉树之字形层序遍历的结果是
[
[1],
[3,2],
[4,5]
]
示例1
输入:
{1,2,3,#,#,4,5}
复制
返回值:
[[1],[3,2],[4,5]]
复制
说明:
如题面解释,第一层是根节点,从左到右打印结果,第二层从右到左,第三层从左到右。
示例2
输入:
{8,6,10,5,7,9,11}
返回值:
[[8],[10,6],[5,7,9,11]]
示例3
输入:
{1,2,3,4,5}
返回值:
[[1],[3,2],[4,5]]
方法一:
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Print(pRoot)
{
let res=[];
let p=[];
p.push(pRoot);
let x=1;
if(pRoot==null){
return []
}
while(p.length!=0){
let len=p.length;
res.push([]);
let node;
for(let i=0;i<len;i++){
// 判断节点是奇层还是偶数层
if(x%2!=0){
// 奇数层,节点从数组头部弹出
node=p.shift()
}else{
// 偶数层节点从数组尾部弹出
node=p.pop()
}
// 将节点从头部推入数组中
res[res.length-1].unshift(node.val);
// 判断节点是奇层还是偶数层
if(x%2!=0){
// 奇数层,从右至左判断是否存在左右节点,如果存在则将节点从尾部推入数组
if(node.right)
p.push(node.right);
if(node.left)
p.push(node.left)
// 偶数层,从左至右判断是否存在左右节点,如果存在则将节点从头部推入数组
if(node.left)
p.unshift(node.left);
if(node.right)
p.unshift(node.right);
}
}
x++;
}
return res;
}
module.exports = {
Print : Print
};
方法二:
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Print(pRoot)
{
let res=[];
let p=[];
p.push(pRoot);
let x=1;
if(pRoot==null){
return []
}
let temp=[]
// 判断q当前的长度是否为0,如果为0则层序遍历结束
while(p.length!=0){
// 存储当前q的长度
let currentlength=p.length;
// 给存储数组推入一个空数组
// res.push([]);
temp=[]
// 循环遍历当前层的节点
for(let i=0;i<currentlength;i++){
// 弹出q内的节点
let node=p.shift();
// 将节点值存入res新加入的数组中
temp.push(node.val);
// 判断当前节点是否有左孩子
if(node.left!=null)
// 有则向q推入下层节点
p.push(node.left);
// 同上
if(node.right!=null)
p.push(node.right);
}
// 判断该层是奇数层还是偶数层
if(x%2==0){
// 如果为偶数层则将该层数组反转
res.push(temp.reverse())
}else{
// 如果为偶数层则无需反转
res.push(temp)
}
x++;
}
return res;
}
module.exports = {
Print : Print
};
NC40 链表相加(二)
描述
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。
给定两个这种链表,请生成代表两个整数相加值的结果链表。
数据范围:0 \le n,m \le 10000000≤n,m≤1000000,链表任意值 0 \le val \le 90≤val≤9
要求:空间复杂度 O(n)O(n),时间复杂度 O(n)O(n)
例如:链表 1 为 9->3->7,链表 2 为 6->3,最后生成新的结果链表为 1->0->0->0。
示例1
输入:
[9,3,7],[6,3]
返回值:
{1,0,0,0}
说明:
如题面解释
示例2
输入:
[0],[6,3]
返回值:
{6,3}
备注:
1 \leq n, m \leq 10^61≤n,m≤106
0 \leq a_i, b_i \leq 90≤ai,bi≤9
方法一:
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
function addInList( head1 , head2 ) {
// 方法一
let p1="",p2="",len1=0,len2=0;
let cnt="";
// 将链表中的值取出形成一个字符串
while(head1){
p1+=head1.val;
head1=head1.next;
len1++;
}
while(head2){
p2+=head2.val;
head2=head2.next;
len2++;
}
// 以下操作和大数加法相同
while(len1>len2){
p2="0"+p2;
len2++;
}
while(len2>len1){
p1="0"+p1;
len1++;
}
let temp;
let up=0;
for(let i=len1-1;i>=0;i--){
temp=Number(p1[i])+Number(p2[i])+up;
cnt+=temp%10;
up=Math.floor(temp/10);
}
if(up){
cnt+=up
}
// 新建链表
let p=new ListNode(Number(Number(cnt[cnt.length-1])));
// 定义指向链表的指针
let cur=p;
// 将结果形成新的链表
for(let i=cnt.length-2;i>=0;i--){
cur.next=new ListNode(Number(cnt[i]));
cur=cur.next;
}
// 返回链表
return p;
}
module.exports = {
addInList : addInList
};
方法二:
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
function addInList( head1 , head2 ) {
let p1=null,p2=null;
let cur1=head1,cur2=head2,len1=0,len2=0;
// 反转第一条链表
while(cur1){
let temp=cur1.next;
cur1.next=p1;
p1=cur1;
cur1=temp;
len1++;
}
// 反转第二条链表
while(cur2){
let temp=cur2.next;
cur2.next=p2;
p2=cur2;
cur2=temp;
len2++;
}
// 比较两条链表的长度,cur1指向长的链表,cur2指向短的链表
cur1=len1>=len2?p1:p2;
cur2=len2<=len1?p2:p1;
let up=0;
let x=cur1;
// 循环链表
while(cur1){
// 将链表上的数字相加
let temp =cur1.val+ ((cur2 ? cur2.val : 0) +up)
up=Math.floor(temp/10);
cur1.val=temp%10;
// 另x指向cur1
x=cur1;
cur1 = cur1.next
cur2 = cur2 ? cur2.next : null
}
// 判断是否需要进位
if(up){
x.next=new ListNode(up);
// cur1=x.next;
}
let pre=null,pre2;
// 令cur1指向较长的链表并让其反转
cur1=len1>=len2?p1:p2;
while(cur1){
let temp=cur1.next;
cur1.next=pre;
pre=cur1;
cur1=temp;
}
return pre;
}
module.exports = {
addInList : addInList
};