59. 螺旋矩阵 II
class Solution {
public int[][] generateMatrix(int n) {
int[][] nums = new int[n][n]; // 定义二维数组用于存储数据
int startX = 0; // 定义每循环一个圈的起始位置
int startY = 0;
int loop = 1; // 定义圈数,最少1圈
int count = 1; // 用来给矩阵中每一个空格赋值
int offset = 1; // 需要控制每一条边遍历的长度,每次循环右边界收缩一位
int i;
int j;
int mid = n/2; // 矩阵中间的位置,例如:n为3, 中间的位置就是(1,1),n为5,中间位置为(2, 2)
// 每次一个转圈会让边长为n的矩阵减少2,那么2*循环次数=n,所以循环次数为n/2
while (loop <= n/2) {
j = startY;
i = startX;
// 下面开始的四个for就是模拟转了一圈
// 模拟填充上行从左到右(左闭右开)
for ( ; j < n - offset; j++) {
nums[i][j] = count++;
}
// 模拟填充右列从上到下(左闭右开)
for ( ; i < n - offset; i++) {
nums[i][j] = count++;
}
// 模拟填充下行从右到左(左闭右开)
for ( ; j > startY; j--) {
nums[i][j] = count++;
}
// 模拟填充左列从下到上(左闭右开)
for ( ; i > startX; i--) {
nums[i][j] = count++;
}
// 第二圈开始的时候,起始位置要各自加1, 例如:第一圈起始位置是(0, 0),第二圈起始位置是(1, 1)
startX++;
startY++;
// offset 控制每一圈里每一条边遍历的长度
offset++;
loop++;
}
// 如果n为奇数的话,需要单独给矩阵最中间的位置赋值
if (n%2 == 1) {
nums[mid][mid] = count;
}
return nums;
}
}
203. 移除链表元素
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
notice:
1.头结点的指向不能改变
2.对链表结点取值前先判空
*/
// 1.不使用虚拟头结点,直接在原链表删除
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode p = head;
// 先判断头结点是否为空
if (head == null) {
return null;
}
// 要删除的节点为头结点
while (head != null && head.val == val) {
head = head.next;
}
// 要删除的节点不为头结点
while (p.next != null) {
if (p.next.val == val) {
p.next = p.next.next;
} else {
p = p.next;
}
}
return head;
}
}
// 2.使用虚拟头结点
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 设置虚拟头结点
ListNode dummyHead = new ListNode();
dummyHead.next = head;
if (head == null) {
return null;
}
ListNode cur = dummyHead;
while (cur.next != null) {
if (cur.next.val == val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
// 避免头结点被删除的情况
return dummyHead.next;
}
}
707. 设计链表
//单链表
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) {
this.val = val;
}
}
/**
插入数据就不要忘了将链表元素的个数+1
删除数据就不要忘了将链表元素的个数-1
*/
class MyLinkedList {
// size存储链表元素的个数
int size;
// 虚拟头结点
ListNode dummyHead;
// 初始化链表
public MyLinkedList() {
size = 0;
dummyHead = new ListNode(0);
}
// 获取第index个节点的数值,注意index是从0开始的,第0个节点就是头结点
public int get(int index) {
// 如果index非法,返回-1
if (index < 0 || index > size-1) {
return -1;
}
ListNode cur = dummyHead;
//包含一个虚拟头节点,所以查找第 index+1 个节点
for (int i = 0; i <= index; i++) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
ListNode newNode = new ListNode(val);
newNode.next = dummyHead.next;
dummyHead.next = newNode;
size++; //不要忘了将链表元素的个数+1
}
public void addAtTail(int val) {
ListNode newNode = new ListNode(val);
ListNode cur = dummyHead;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
size++;
}
// 在第 index 个节点之前插入一个新节点,例如index为0,那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度,则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度,则返回空
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
if (index < 0) {
index = 0;
}
// 找到要插入节点的前驱
ListNode pre = dummyHead;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
ListNode newNode = new ListNode(val);
newNode.next = pre.next;
pre.next = newNode;
size++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
//因为有虚拟头节点,所以不用对Index=0的情况进行特殊处理
ListNode pre = dummyHead;
for (int i = 0; i < index ; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
size--;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/