Week1题目重刷
peach2580
帮助1人
- 今天把week1的题目都重新刷了一遍，明天开始week2的内容~
704.二分查找
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1, m;
while (l <= r) {
m = (l r) >>> 1;
if (nums[m] < target) {
l = m 1;
} else if (nums[m] > target) {
r = m - 1;
} else {
return m;
}
}
return -1;
}
}
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length, m;
while (l < r) {
m = (l r) >>> 1;
if (nums[m] < target) {
l = m 1;
} else if (nums[m] > target) {
r = m;
} else {
return m;
}
}
return -1;
}
}
35.搜索插入位置
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length - 1, m;
while (l <= r) {
m = (l r) >>> 1;
if (nums[m] < target) {
l = m 1;
} else if (nums[m] > target) {
r = m - 1;
} else {
return m;
}
}
return l;
}
}
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0, r = nums.length, m;
while (l < r) {
m = (l r) >>> 1;
if (nums[m] < target) {
l = m 1;
} else if (nums[m] > target) {
r = m;
} else {
return m;
}
}
return l;
}
}
27.移除元素
class Solution {
public int removeElement(int[] nums, int val) {
int s = 0;
for (int f = 0; f < nums.length; f ) {
if (nums[f] != val) {
nums[s] = nums[f];
s ;
}
}
return s;
}
}
26. 删除有序数组中的重复项
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 1) return 1;
int s = 0;
for (int f = 1; f < nums.length; f ) {
if (nums[f] != nums[s]) {
s ;
nums[s] = nums[f];
}
}
return s;
}
}
283. 移动零
class Solution {
public void moveZeroes(int[] nums) {
int s = 0;
for (int f = 0; f < nums.length; f ) {
if (nums[f] != 0) {
nums[s] = nums[f];
s ;
}
}
while (s < nums.length) {
nums[s] = 0;
s ;
}
}
}
class Solution {
public void moveZeroes(int[] nums) {
int s = 0;
for (int f = 0; f < nums.length; f ) {
if (nums[f] != 0) {
int t = nums[f];
nums[f] = nums[s];
nums[s] = t;
s ;
}
}
}
}
844. 比较含退格的字符串
class Solution {
public boolean backspaceCompare(String s, String t) {
return removeBackspace(s).equals(removeBackspace(t));
}
private String removeBackspace(String str) {
Deque<Character> quene = new ArrayDeque();
for (char c : str.toCharArray()) {
if (c != '#') {
quene.addFirst(c);
} else {
if (!quene.isEmpty()) quene.removeFirst();
}
}
String res = new String();
while (!quene.isEmpty()) {
res = quene.removeLast();
}
return res;
}
}
class Solution {
public boolean backspaceCompare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1, skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) { // 只有两个字符串都遍历结束，大循环才结束，长度不一样内部处理
while (i >= 0) { // 对s进行循环
if (s.charAt(i) == '#') { // 找到#，把skipS 1
skipS ;
i--;
}
else if (skipS > 0) { // 不是# 但skipS > 0 这个字符应该被删除
skipS--;
i--;
}
else break; // 找到了一个要比较的字符
} // 这个循环结束，要么找到了要比较的字符，要么 i < 0
while (j >= 0) {
if (t.charAt(j) == '#') {
skipT ;
j--;
}
else if (skipT > 0) {
skipT--;
j--;
}
else break;
} // j 也一样
if (i < 0 && j < 0) return true; // 如果都小于零，说明都变成了空串。返回true
if (i < 0 || j < 0) return false; // 有一个大于零，说明长度不一样，返回false
if (s.charAt(i) != t.charAt(j)) return false; // 都大于零，比较一下这两个字符
i--; // 别忘了比较之后移动位置
j--;
}
return true; // 大循环结束，说明两个字符串都遍历完了，长度一样，对应字符一样，返回true
}
}
977.有序数组的平方
class Solution {
public int[] sortedSquares(int[] nums) {
int l = 0, r = nums.length - 1;
int[] res = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[l] * nums[l] > nums[r] * nums[r]) {
res[i] = nums[l] * nums[l];
l ;
} else {
res[i] = nums[r] * nums[r];
r--;
}
}
return res;
}
}
209. 长度最小的子数组
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0, j = 0, res = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i ) {
sum = nums[i];
while (sum >= target) {
res = Math.min(res, i - j 1);
sum -= nums[j];
j ;
}
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
904. 水果成篮
class Solution {
public int totalFruit(int[] fruits) {
int left = 0, res = 0;
Map<Integer, Integer> map = new HashMap(); // 哈希表，记录元素出现次数
for (int right = 0; right < fruits.length; right ) { // 快指针遍历数组
map.put(fruits[right], map.getOrDefault(fruits[right], 0) 1); // 每遍历一个元素，把它在map中的v 1
while (map.size() > 2) { // 一旦size>2 说明种类超过了两个，应该开始从左边开始删除元素
map.put(fruits[left], map.get(fruits[left]) - 1); // 从左边开始删除元素，这里一定能get到
if (map.get(fruits[left]) == 0) { // 因为一旦元素v为0，就remove
map.remove(fruits[left]);
}
left ; // 删除完别忘了移动慢指针
}
res = Math.max(res, right - left 1); // 外层循环每进行一次，都要更新一下res
}
return res; // 最后返回res
}
}
76. 最小覆盖子串
class Solution {
public String minWindow(String s, String t) {
int left = 0, res = Integer.MAX_VALUE, start = 0;
int[] countS = new int[128]; // 创建两个数组作为哈希表
int[] countT = new int[128];
for (char c : t.toCharArray()) {
countT[c] ; // 遍历T数组，得到哈希数组
}
for (int right = 0; right < s.length(); right ) {
countS[s.charAt(right)] ; // 快指针走一步，数组更新一次
while (check(countS, countT)) { // 一旦check成功，说明s这部分包含了t，可能要更新res，进入内层循环
if (right - left 1 < res) {
res = right - left 1;
start = left; // 更新的时候记录start位置
}
countS[s.charAt(left)]--; // 更新完left指针移动
left ;
}
}
return res == Integer.MAX_VALUE ? "" : s.substring(start, start res);
}
// check函数的逻辑，一旦发现countT某个位置元素比S大，就返回false，要么比你多要么你没有
private boolean check(int[] countS, int[] countT) {
for (int i = 0; i < 128; i ) {
if (countS[i] < countT[i]) {
return false;
}
}
return true;
}
}
59.螺旋矩阵II
class Solution {
public int[][] generateMatrix(int n) {
int l = 0, r = n - 1, b = 0, t = n - 1, num = 1;
int[][] res = new int[n][n];
while (num <= n * n) {
for (int i = l; i <= r; i ) {
res[b][i] = num ;
}
b ;
for (int i = b; i <= t; i ) {
res[i][r] = num ;
}
r--;
for (int i = r; i >= l; i--) {
res[t][i] = num ;
}
t--;
for (int i = t; i >= b; i--) {
res[i][l] = num ;
}
l ;
}
return res;
}
}
203. 移除链表元素
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
while (pre.next != null) {
if (pre.next.val == val) {
pre.next = pre.next.next;
} else {
pre = pre.next;
}
}
return dummy.next;
}
}
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) return null;
head.next = removeElements(head.next, val);
if (head.val == val) head = head.next;
return head;
}
}
707.设计链表
class MyLinkedList {
private ListNode head;
private int size;
public MyLinkedList() {
head = new ListNode(-1);
size = 0;
}
public int get(int index) {
if (index < 0 || index >= size) return -1;
ListNode cur = head;
while (index-- >= 0) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if (index > size) return;
ListNode pre = head;
while (index-- > 0) {
pre = pre.next;
}
ListNode node = new ListNode(val, pre.next);
pre.next = node;
size ;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
ListNode pre = head;
while (index-- > 0) {
pre = pre.next;
}
pre.next = pre.next.next;
size--;
}
}
class ListNode {
int val;
ListNode next;
public ListNode(){};
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
public ListNode(int val) {
this.val = val;
}
}
/**
* 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);
*/
206.反转链表
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return head;
ListNode pre = head;
ListNode cur = pre.next;
ListNode temp;
while (cur != null) {
temp = cur.next;
cur.next = pre;
if (pre == head) pre.next = null;
pre = cur;
cur = temp;
}
return pre;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
24.两两交换链表中的节点
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode reHead = swapPairs(head.next.next);
ListNode res = head.next;
head.next.next = head;
head.next = reHead;
return res;
}
}
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
ListNode cur = head;
ListNode temp;
while (cur != null && cur.next != null) {
temp = cur.next;
pre.next = temp;
cur.next = temp.next;
temp.next = cur;
pre = cur;
cur = pre.next;
}
return dummy.next;
}
}
19.删除链表的倒数第N个节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode temp = dummy;
ListNode s = dummy;
while (n-- > 0) {
temp = temp.next;
}
while (temp.next != null) {
temp = temp.next;
s = s.next;
}
s.next = s.next.next;
return dummy.next;
}
}
面试题 02.07. 链表相交
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode tA = headA;
ListNode tB = headB;
while (tA != tB) {
tA = tA == null ? headB : tA.next;
tB = tB == null ? headA : tB.next;
}
return tA;
}
}
142.环形链表Ⅱ
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode f = head, s = head;
while (f != null && f.next != null) {
f = f.next.next;
s = s.next;
if (f == s) {
f = head;
while (f != s) {
f = f.next;
s = s.next;
}
return f;
}
}
return null;
}
}
这篇好文章是转载于：学新通技术网
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 学新通技术网
- 本文地址： /boutique/detail/tanhgekkah
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01
