LeetCode
66. 加一(模板题)
给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1:
输入:digits = [1,2,3]
输出:[1,2,4]
解释:输入数组表示数字 123。
示例 2:
输入:digits = [4,3,2,1]
输出:[4,3,2,2]
解释:输入数组表示数字 4321。
示例 3:
输入:digits = [0]
输出:[1]
提示:
1 <= digits.length <= 100
0 <= digits[i] <= 9
解题思路
1. 位数上加1有两种情况,9加1,和不是9加1
不是9加1,return
是9加1,进位,循环到上一位,重复判断
2. 如果循环走完了,说明都产生的进位,需要在最前面补1
完整代码
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
for(let i=digits.length-1;i>=0;i--){
digits[i]++
digits[i]=digits[i]%10
if(digits[i]!==0){
return digits
}
}
// 走到这里,说明全部发生了进位
// 前补1
digits.unshift(1)
return digits
};
25. K 个一组翻转链表
给你链表的头节点 head
,每 k
个节点一组进行翻转,请你返回修改后的链表。
k
是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k
的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
示例 1:
输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]
示例 2:
输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]
提示:
- 链表中的节点数目为
n
1 <= k <= n <= 5000
0 <= Node.val <= 1000
进阶:你可以设计一个只用 O(1)
额外内存空间的算法解决此问题吗?
解题思路
1. k个一组翻转转换为单链表的翻转
2. 单链表翻转添加限制条件,走k步一个翻转
3. 每次翻转前,需要记录原来的头部(oldHead),翻转后的头部(newHead),以及原来链表k步后下一个节点的指针(temp),pre指针(最初在保护节点,每次翻转变为翻转后的头部)
4. 翻转完成后 pre.next=翻转后的头部 pre=原来的头部(即翻转的尾部)
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var reverseKGroup = function(head, k) {
// 解题思路
// k个一组翻转链表
// 转换为单链表翻转
// 每k步翻转一次单链表
// 单链表翻转
const resloveList=(head,k)=>{
if(!head){
return null
}
let pre=null
let p=head
let step=0
while(p!=null&&step<k){
step++
let temp=p.next
p.next=pre
pre=p
p=temp
}
return pre
}
// k步一个翻转
// 保护节点
let secureNode=new ListNode(-1)
secureNode.next=head
// 保护节点
let p=head
let step=0
// 原来链表的头部
let oldHead=head
let pre=secureNode
// let old
while(p){
p=p.next
step++
if(step===k){
let temp=p
// 翻转
let newHead=resloveList(oldHead,k)
step=0
pre.next=newHead
pre=oldHead
oldHead=temp
// console.log(oldHead,'oldHead')
p=temp
}
}
pre.next=oldHead
return secureNode.next
};
标签:digits,head,return,队列,链表,数组,节点,翻转
From: https://www.cnblogs.com/lingxin1123/p/17087578.html