陣列：記憶體空間連續，資料型別統一，下標從0開始
二分查找
704
class Solution {
public int search(int[] nums, int target) {
// 方法一：暴力解法
// for(int i = 0; i < nums.length; i++){
// if(nums[i] == target){//找到目標值
// return i;
// }
// }
// return -1;
// 方法二：二分查找（元素有序且無重復元素），使用迭代，執行速度快，但是記憶體消耗大
// return binarySearch(nums, target, 0, nums.length-1);
// 方法三：二分查找，統一使用左閉右閉區間
// 上來先處理邊界條件
if(target < nums[0] || target > nums[nums.length - 1]){
return -1;
}
int left = 0;
int right = nums.length - 1;//右閉區間
int mid = (left + right) >> 1;
while(left <= right){//因為取得陣列區間左右都是閉的，所以取等號的時候也能滿足條件，還不需要退出回圈
if(target == nums[mid]){
return mid;
}else if(target < nums[mid]){
right = mid -1;//往左區間縮
}else{
left = mid +1;
}
mid = (left + right) >> 1;
}
return -1;
}
// public int binarySearch(int[] nums, int target, int start, int end){
// int mid = (start+end)/2;
// int find = -1;
// if(start > end){//沒有找到
// return -1;
// }
// if(target == nums[mid]){
// return mid;
// }else if(target < nums[mid]){
// find = binarySearch(nums, target, start, mid-1);
// }else{
// find = binarySearch(nums, target, mid+1, end);
// }
// return find;
// }
}
搜索插入位置
35
class Solution {
public int searchInsert(int[] nums, int target) {
// 有序陣列，考慮用二分查找
int left = 0;
int right = nums.length - 1;
int mid = (left + right) >> 1;
if(target < nums[left]){
return left;
}
if(target > nums[right]){
return right + 1;
}
while(left <= right){
if(target == nums[mid]){
return mid;
}else if(target < nums[mid]){
right = mid -1;
}else{
left = mid + 1;
}
mid = (left + right) >> 1;
}
return left;//找不到，回傳需要插入的位置
}
}
在排序陣列中查找元素的第一個和最后一個位置
34
class Solution {
public int[] searchRange(int[] nums, int target) {
// 非遞減說明是升序的，但可以有重復元素
int[] arr = {-1, -1};
if(nums.length == 0){
return arr;
}
int left = 0;
int right = nums.length - 1;
int mid = (left + right) >> 1;
if(target < nums[left] || target > nums[right]){
return arr;//邊界值
}
int leftPoint;//目標陣列的開始位置
int rightPoint;//目標陣列的結束位置
while(left <= right){
if(target == nums[mid]){
leftPoint = mid;
rightPoint = mid;
while(leftPoint >= 0 && target == nums[leftPoint]){
arr[0] = leftPoint;
leftPoint--;//向左尋找重復元素
}
while(rightPoint <= (nums.length - 1) && target == nums[rightPoint]){
arr[1] = rightPoint;
rightPoint++;//向右尋找重復元素
}
return arr;//回傳找到的目標值的位置
}else if(target < nums[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
mid = (left + right) >> 1;
}
return arr;//沒有找到
}
}
69、x的平方根
class Solution {
public int mySqrt(int x) {
// 使用二分查找
int left = 0;
int right = x;
int mid = (left + right) / 2;
while(left <= right){
if((long)mid * mid < x){
left = mid + 1;
}else if((long)mid * mid > x){
right = mid - 1;
}else{
return mid;
}
mid = (left + right) / 2;
}
return right;
}
}
367、有效的完全平方數
class Solution {
public boolean isPerfectSquare(int num) {
int left = 0, right = num;
while(left <= right){
int mid = (left + right) >> 1;
if((long) mid * mid == num){
return true;
}else if((long) mid * mid < num){
left = mid + 1;
}else{
right = mid - 1;
}
}
return false;
}
}
移除元素
27
class Solution {
public int removeElement(int[] nums, int val) {
// 原地移除，所有元素
// 陣列內元素可以亂序
// 方法一：暴力解法，不推薦，時間復雜度O(n^2)
// int right = nums.length;//目標陣列長度，右指標
// for(int i = 0; i < right; i++){
// if(val == nums[i]){
// right--;//找到目標數值，目標數長度減一，右指標左移
// for(int j = i; j < right; j++){
// nums[j] = nums[j + 1];//陣列整體左移一位（陣列元素不能洗掉，只能覆寫）
// }
// i--;//左指標左移
// }
// }
// return right;
// 方法二：快慢指標，時間復雜度O(n)
// int solwPoint = 0;
// for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
// if(nums[fastPoint] != val){
// nums[solwPoint] = nums[fastPoint];
// solwPoint++;
// }
// }
// return solwPoint;
// 方法三：注意元素的順序可以改變，使用相向指標，時間復雜度O(n)
int rightPoint = nums.length - 1;
int leftPoint = 0;
while(rightPoint >= 0 && nums[rightPoint] == val){
rightPoint--;
}
while(leftPoint <= rightPoint){
if(nums[leftPoint] == val){
nums[leftPoint] = nums[rightPoint--];
}
leftPoint++;
while(rightPoint >= 0 && nums[rightPoint] == val){
rightPoint--;
}
}
return leftPoint;
}
}
26、洗掉排序陣列中的重復項
class Solution {
public int removeDuplicates(int[] nums) {
// 相對順序一致，所以不能使用相向指標，
// 考慮使用快慢指標
if(nums.length == 1){
return 1;
}
int slowPoint = 0;
for(int fastPoint = 1; fastPoint < nums.length; fastPoint++){
if(nums[slowPoint] != nums[fastPoint]){
nums[++slowPoint] = nums[fastPoint];
}
}
return slowPoint + 1;
}
}
283、移動零
class Solution {
public void moveZeroes(int[] nums) {
// 要保持相對順序，不能用相向指標
int slowPoint = 0;
for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){
if(nums[fastPoint] != 0){
nums[slowPoint++] = nums[fastPoint];//所有非零元素移到左邊
}
}
for(; slowPoint < nums.length; slowPoint++){
nums[slowPoint] = 0;//把陣列末尾置零
}
}
}
844、比較含退格的字串
class Solution {
public boolean backspaceCompare(String s, String t) {
// 從前往后的話不確定下一位是不是"#"，當前位需不需要消除，所以采用從后往前的方式
int countS = 0;//記錄s中"#"的數量
int countT = 0;//記錄t中"#"的數量
int rightS = s.length() - 1;
int rightT = t.length() - 1;
while(true){
while(rightS >= 0){
if(s.charAt(rightS) == '#'){
countS++;
}else{
if(countS > 0){
countS--;
}else{
break;
}
}
rightS--;
}
while(rightT >= 0){
if(t.charAt(rightT) == '#'){
countT++;
}else{
if(countT > 0){
countT--;
}else{
break;
}
}
rightT--;
}
if(rightT < 0 || rightS < 0){
break;
}
if(s.charAt(rightS) != t.charAt(rightT)){
return false;
}
rightS--;
rightT--;
}
if(rightS == -1 && rightT == -1){
return true;
}
return false;
}
}
有序陣列的平方
977
class Solution {
public int[] sortedSquares(int[] nums) {
// 用相向的雙指標
int[] arr = new int[nums.length];
int index = arr.length - 1;
int leftPoint = 0;
int rightPoint = nums.length - 1;
while(leftPoint <= rightPoint){
if(Math.pow(nums[leftPoint], 2) > Math.pow(nums[rightPoint], 2)){
arr[index--] = (int)Math.pow(nums[leftPoint], 2);
leftPoint++;
}else{
arr[index--] = (int)Math.pow(nums[rightPoint], 2);
rightPoint--;
}
}
return arr;
}
}
長度最小的子陣列
209
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 注意是連續子陣列
// 使用滑動視窗，實際上還是雙指標
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for(int right = 0; right < nums.length; right++){//for回圈固定的是終止位置
sum += nums[right];
while(sum >= target){
result = Math.min(result, right - left + 1);//記錄最小的子陣列
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
904、水果成籃
class Solution {
public int totalFruit(int[] fruits) {
// 此題也可以使用滑動視窗
int maxNumber = 0;
int left = 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);//往籃子里面放水果
while(map.size() > 2){//放進去的水果不符合水果型別
map.put(fruits[left], map.get(fruits[left]) - 1);
if(map.get(fruits[left]) == 0){
map.remove(fruits[left]);
}
left++;
}
maxNumber = Math.max(maxNumber, right - left + 1);
}
return maxNumber;
}
}
螺旋矩陣 II
59
class Solution {
public int[][] generateMatrix(int n) {
// 方法一：直接按序輸出
int[][] arr = new int[n][n];
int top = 0;
int buttom = n - 1;
int left = 0;
int right = n - 1;;
int index = 1;
while(left <= right && top <= buttom && index <= n*n){
for(int i = left; i <= right; i++){
arr[top][i] = index++;
}
top++;
for(int i = top; i <= buttom; i++){
arr[i][right] = index++;
}
right--;
for(int i = right; i >= left; i--){
arr[buttom][i] = index++;
}
buttom--;
for(int i = buttom; i >= top; i--){
arr[i][left] = index++;
}
left++;
}
return arr;
}
}
54
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int top = 0;
int buttom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
List<Integer> list = new ArrayList<Integer>();
while(left <= right && top <= buttom){
for(int i = left; i <= right; i++){
if(top <= buttom)
list.add(matrix[top][i]);
}
top++;
for(int i = top; i <= buttom; i++){
if(left <= right)
list.add(matrix[i][right]);
}
right--;
for(int i = right; i >= left; i--){
if(top <= buttom)
list.add(matrix[buttom][i]);
}
buttom--;
for(int i = buttom; i >= top; i--){
if(left <= right)
list.add(matrix[i][left]);
}
left++;
}
return list;
}
}
29 、順時針列印矩陣
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0){
return new int[0];
}
int top = 0;
int buttom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
int[] arr = new int[matrix.length*matrix[0].length];
int index = 0;
while(left <= right && top <= buttom){
for(int i = left; i <= right; i++){
if(top <= buttom)
arr[index++] = matrix[top][i];
}
top++;
for(int i = top; i <= buttom; i++){
if(left <= right)
arr[index++] = matrix[i][right];
}
right--;
for(int i = right; i >= left; i--){
if(top <= buttom)
arr[index++] = matrix[buttom][i];
}
buttom--;
for(int i = buttom; i >= top; i--){
if(left <= right)
arr[index++] = matrix[i][left];
}
left++;
}
return arr;
}
}
鏈表：插入快，查詢慢，存盤不連續
分為單鏈表，雙鏈表和回圈鏈表
在鏈表中使用虛擬頭結點，可以減少增刪改查中對頭結點的特殊處理
移除鏈表元素
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; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
// 方法一：設定虛節點方式，推薦方式
ListNode dummy = new ListNode(-1,head);
ListNode pre = dummy;
ListNode cur = head;
while(cur != null){
if(cur.val == val){
pre.next = cur.next;
}else{
pre = cur;
}
cur = cur.next;
}
return dummy.next;
// 方法二：時間復雜度O(n)，空間復雜度O(1)
if(head == null){//空鏈表的情況
return head;
}
while(head != null && head.val == val){//頭結點為val的情況
head = head.next;
}
ListNode temp = head;
while(temp != null && temp.next != null){
while(temp != null && temp.next != null && temp.next.val == val){
if(temp.next.next != null){
temp.next = temp.next.next;
}else{//最后一個節點為val的情況
temp.next = null;
}
}
temp = temp.next;
}
return head;
}
}
707、設計鏈表
class MyLinkedList {
int size;
ListNode head;
ListNode tail;
// 初始化鏈表,構建虛擬的頭結點和尾節點
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
public int get(int index) {
ListNode cur = head;
if(index > size - 1 || index < 0){
return -1;
}
while(index >= 0){
cur = cur.next;
index--;
}
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;
}
if(index < 0 ){
index = 0;
}
size++;
ListNode temp = new ListNode(val);
ListNode cur = head;
while(index > 0){
cur = cur.next;
index--;
}
temp.next = cur.next;
cur.next = temp;
temp.prev = cur;
}
public void deleteAtIndex(int index) {
ListNode cur = head;
if(index > size - 1 || index < 0){
return;
}
while(index > 0){
cur = cur.next;
index--;
}
cur.next = cur.next.next;
size--;
}
}
class ListNode {
int val;
ListNode next;
ListNode prev;
public ListNode(int val) {
this.val = val;
}
}
反轉鏈表
206
/**
* 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; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 方法一：在頭結點不斷插入
// if(head == null){
// return head;//空節點不需要反轉
// }
// ListNode temp = head.next;//臨時節點前移一位
// head.next = null;//代反轉鏈表的頭結點拆出來
// ListNode newHead = head;//待反轉鏈表的頭結點賦給新的鏈表
// while(temp != null){
// head = temp;//找出待反轉鏈表的新頭結點
// temp = temp.next;//臨時節點前移一位
// head.next = null;//待反轉鏈表的新頭拆出來
// head.next = newHead;//待反轉鏈表的心頭指向新的鏈表
// newHead = head;//得到新的鏈表的新頭
// }
// return newHead;
// 方法二：壓堆疊，利用堆疊的先入后出
// if(head == null){
// return head;
// }
// Stack<ListNode> stack = new Stack<>();
// ListNode temp = head;
// while(head != null){
// temp = head.next;
// head.next = null;
// stack.push(head);
// head = temp;
// }
// ListNode newHead = new ListNode();
// temp = newHead;
// while(!stack.isEmpty()){
// temp.next = stack.pop();
// temp = temp.next;
// }
// return newHead.next;
// 方法三：遞回
return reverse(null, head);
// 方法四：從后往前遞回
// if(head == null){
// return null;
// }
// if(head.next == null){
// return head;
// }
// ListNode newHead = reverseList(head.next);
// head.next.next = head;
// head.next = null;
// return newHead;
}
public ListNode reverse(ListNode pre, ListNode cur){
if(cur == null){
return pre;
}
ListNode temp = cur.next;
cur.next = pre;
return reverse(cur,temp);
}
}
兩兩交換鏈表中的節點
24
/**
* 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; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 方法一：從前往后進行迭代
// if(head == null){
// return null;
// }
// if(head.next == null){
// return head;
// }
// ListNode temp = head.next;//依次記錄偶數節點的位置
// head.next = head.next.next;//交換相鄰的節點
// temp.next = head;
// temp.next.next = swapPairs(temp.next.next);//迭代交換下一個相鄰的節點
// return temp;
// 方法二：雙指標
if(head == null){
return null;
}
if(head.next == null){
return head;
}
ListNode temp = head.next;
ListNode pre = head.next;//記錄新的頭結點
while(temp != null){
head.next = head.next.next;//交換相鄰的節點
temp.next = head;
if(head.next == null || head.next.next == null){
break;
}else{
head = head.next;//指向下一個相鄰節點的奇數節點
temp.next.next = temp.next.next.next;//上一個相鄰節點的偶數節點指向下一個節點的偶數節點
temp = head.next;//下一個相鄰節點的偶數節點
}
}
return pre;
}
}
洗掉鏈表的倒數第 N 個結點
19
/**
* 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; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 方法一：快慢指標，回傳頭結點說明head的頭結點不能動，所以把鏈表的地址賦給另外一個物件
// 添加虛擬頭結點，方便操作，比如需要洗掉的是頭結點的時候不需要單獨考慮這種特殊情況
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode cur = dummyHead;
ListNode temp = dummyHead;
for(int i = 0; i < n; i++){
temp = temp.next;
}
while(temp.next != null){
cur = cur.next;
temp = temp.next;
}
cur.next = cur.next.next;
return dummyHead.next;
}
}
鏈表相交
02.07
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode dummyHeadA = headA;
int countA = 0;
int countB = 0;
ListNode dummyHeadB = headB;
while(dummyHeadA.next != null){
dummyHeadA = dummyHeadA.next;
countA++;
}
while(dummyHeadB.next != null){
dummyHeadB = dummyHeadB.next;
countB++;
}
if(dummyHeadA != dummyHeadB){
return null;//尾節點不相交則說明不相交
}
dummyHeadA = headA;
dummyHeadB = headB;
int index = (countA - countB) > 0 ? (countA - countB) : -(countA - countB);//兩個鏈表的長度差
for(int i = 0; i < index; i++){//讓較長的鏈表先移動index位
if((countA - countB) > 0){
dummyHeadA = dummyHeadA.next;
}else{
dummyHeadB = dummyHeadB.next;
}
}
while(dummyHeadA != dummyHeadB){//兩個鏈表逐次向前移動，找出相交的第一個節點
dummyHeadA = dummyHeadA.next;
dummyHeadB = dummyHeadB.next;
}
return dummyHeadA;
}
}
環形鏈表 II
142
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
int count = 0;
while(fast != null && fast.next != null){//判斷是否有環
fast = fast.next.next;
slow = slow.next;
count++;
if(fast == slow){
// 找環的入口
while(head != slow){
head = head.next;
slow = slow.next;
}
return head;
}
}
return null;
}
}
哈希表：也叫散串列，用來快速判斷一個元素是否出現在集合中，實際上是用空間換時間
有效的字母異位詞
242
class Solution {
public boolean isAnagram(String s, String t) {
// 方法一：使用hashmap
// if(s.length() != t.length()){
// return false;
// }
// HashMap<Character, Integer> map = new HashMap<>();
// for(int i = 0; i < s.length(); i++){
// map.put(s.charAt(i), (map.getOrDefault(s.charAt(i), 0) + 1));
// }
// for(int i = 0; i < t.length(); i++){
// if(map.containsKey(t.charAt(i))){
// if(map.get(t.charAt(i)) == 1){
// map.remove(t.charAt(i));
// }else{
// map.put(t.charAt(i), (map.get(t.charAt(i)) - 1));
// }
// }else{
// return false;
// }
// }
// return true;
// 方法二：用陣列來構造哈希表，字典解法
if(s.length() != t.length()){
return false;
}
int[] arr = new int[26];
for(int i = 0; i < s.length(); i++){
int index = s.charAt(i) - 'a';
arr[index] = arr[index] + 1;
}
for(int i = 0; i < t.length(); i++){
int index = t.charAt(i) - 'a';
if(arr[index] != 0){
arr[index] = arr[index] - 1;
}else{
return false;
}
}
return true;
}
}
兩個陣列的交集
349
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
// 使用hashset，無序，且不能存盤重復資料，符合題目要求
HashSet<Integer> set = new HashSet<>();
HashSet<Integer> record = new HashSet<>();
for(int i = 0; i < nums1.length; i++){
set.add(nums1[i]);
}
for(int i = 0; i < nums2.length; i++){
if(set.remove(nums2[i])){
record.add(nums2[i]);
}
}
return record.stream().mapToInt(x -> x).toArray();
}
}
快樂數
202
class Solution {
public boolean isHappy(int n) {
// 使用hashset，當有重復的數字出現時，說明開始重復，這個數不是快樂數
HashSet<Integer> set = new HashSet();
int sum = 0;
while(true){
while(n != 0){
sum = sum + (n%10)*(n%10);
n = n / 10;
}
if(sum == 1){
return true;
}
if(!set.add(sum)){
return false;
}
n = sum;
sum = 0;
}
}
}
兩數之和
1
class Solution {
public int[] twoSum(int[] nums, int target) {
// 方法一：暴力解法
// int[] arr = new int[2];
// for(int i = 0; i < nums.length - 1; i++){
// for(int j = i + 1 ; j < nums.length; j++){
// if(target == (nums[i] + nums[j])){
// return new int[]{i,j};
// }
// }
// }
// return new int[0];
// 方法二：HashMap
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int find = target - nums[i];
if(map.containsKey(find)){
return new int[]{i, map.get(find)};
}else{
map.put(nums[i],i);
}
}
return null;
}
}
四數相加 II
454
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
// 四個數，用哈希表，參考代碼隨想錄
HashMap<Integer,Integer> map = new HashMap<>();
int count = 0;
for(int i : nums1){
for(int j : nums2){
int temp = i + j;
if(map.containsKey(temp)){
map.put(temp, map.get(temp) + 1);
}else{
map.put(temp, 1);
}
}
}
for(int i : nums3){
for(int j : nums4){
int temp = 0- (i + j);
if(map.containsKey(temp)){
count += map.get(temp);
}
}
}
return count;
}
}
贖金信
383
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
// 方法一；hashmap
// HashMap<Character,Integer> map = new HashMap<>();
// char temp;
// for(int i = 0; i < ransomNote.length(); i++){
// temp = ransomNote.charAt(i);
// if(map.containsKey(temp)){
// map.put(temp, map.get(temp) + 1);
// }else{
// map.put(temp, 1);
// }
// }
// for(int i = 0; i < magazine.length(); i++){
// temp = magazine.charAt(i);
// if(map.containsKey(temp)){
// if(map.get(temp) == 1){
// map.remove(temp);
// }else{
// map.put(temp, map.get(temp) - 1);
// }
// }
// }
// if(map.isEmpty()){
// return true;
// }else{
// return false;
// }
// 方法二：陣列在哈希法的應用，比起方法一更加節省空間，因為字串只有小寫的英文字母組成
int[] arr = new int[26];
int temp;
for(int i = 0; i < ransomNote.length(); i++){
temp = ransomNote.charAt(i) - 'a';
arr[temp] = arr[temp] + 1;
}
for(int i = 0; i < magazine.length(); i++){
temp = magazine.charAt(i) - 'a';
if(arr[temp] != 0){
arr[temp] = arr[temp] - 1;
}
}
for(int i = 0; i < arr.length; i++){
if(arr[i] != 0){
return false;
}
}
return true;
}
}
三數之和
15
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 如果考慮使用跟四數之和類似的求解方式，由于三元組是在同一個陣列中尋找的，且要求不重復的三元組，因此求解會比較復雜
// 題目要求回傳的是三元組的具體數值，而不是索引值，因此可以考慮使用雙指標
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<Integer>();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
if(nums[i] > 0){
return result;
}
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
int left = i + 1;
int right = nums.length - 1;
while(left < right){
if((nums[i] + nums[left] + nums[right]) > 0){
right--;
}else if((nums[i] + nums[left] + nums[right]) < 0){
left++;
}else{
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
result.add(temp);
temp = new ArrayList<Integer>();
while(left < right && nums[right] == nums[right-1]){
right--;
}
while(left < right && nums[left] == nums[left+1]){
left++;
}
left++;
right--;
}
}
}
return result;
}
}
四數之和
18
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i=0;i<nums.length-1;i++){
for(int j=0;j<nums.length-1-i;j++){
if(nums[j]>nums[j+1]){
int temp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = temp;
}
}
}
for(int i = 0; i < nums.length; i++){
if (nums[i] > 0 && nums[i] > target) {
return list;
}
if(i > 0 && nums[i] == nums[i - 1]){
continue;
}
for(int j = i + 1; j < nums.length; j++){
if(j > i + 1 && nums[j] == nums[j - 1]){
continue;
}
int left = j + 1;
int right = nums.length - 1;
while(left < right){
long sum = (long)(nums[i] + nums[j] + nums[left] + nums[right]);
if(sum > target){
right--;
}else if(sum < target){
left++;
}else{
list.add(Arrays.asList(nums[i] , nums[j] , nums[left] , nums[right]));
while(left < right && nums[left] == nums[left + 1]){
left++;
}
while(left < right && nums[right] == nums[right - 1]){
right--;
}
left++;
right--;
}
}
}
}
return list;
}
}
字串：
反轉字串
344
class Solution {
public void reverseString(char[] s) {
// 左右指標
int leftNode = 0;
int rifhtNode = s.length - 1;
char temp;
while(leftNode <= rifhtNode){
temp = s[rifhtNode];
s[rifhtNode] = s[leftNode];
s[leftNode] = temp;
leftNode++;
rifhtNode--;
}
}
}
反轉字串 II
541
class Solution {
public String reverseStr(String s, int k) {
char[] arr = s.toCharArray();
for(int i = 0; i < arr.length; i=i+2*k){
if((i+k)<=arr.length){
reverse(arr,i,i+k-1);
}else{
reverse(arr,i,arr.length-1);
}
}
return new String(arr);
}
public void reverse(char[] arr, int left, int right){
while(left < right){
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
替換空格
offer 05
class Solution {
public String replaceSpace(String s) {
StringBuffer target = new StringBuffer();
char temp;
for(int i = 0; i < s.length(); i++){
temp = s.charAt(i);
if(temp == ' '){
target.append("%20");
}else{
target.append(temp);
}
}
return new String(target);
}
}
反轉字串中的單詞
151
class Solution {
public String reverseWords(String s) {
StringBuffer buffer = new StringBuffer();
int index = 0;
while(s.charAt(index)==' '){
index++;
}
for(;index < s.length();index++){
if(s.charAt(index)!=' '){
buffer.append(s.charAt(index));
}else{
while(index < s.length() && s.charAt(index)==' '){
index++;
}
if(index < s.length()){
buffer.append(' ');
buffer.append(s.charAt(index));
}
}
}
String arr = new String(buffer);
String[] result = arr.split(" ");
int left = 0;
int right = result.length - 1;
while(left < right){
String temp = result[left];
result[left] = result[right];
result[right] = temp;
left++;
right--;
}
StringBuffer buffer1 = new StringBuffer();
for(int a = 0; a < result.length; a++){
buffer1.append(result[a]);
if(a < result.length - 1){
buffer1.append(" ");
}
}
return new String(buffer1);
}
}
左旋轉字串
Offer 58 - II
class Solution {
public String reverseLeftWords(String s, int n) {
// 先整體反轉，在根據k進行部分反轉
char[] str = s.toCharArray();
reverse(str, 0, str.length - 1);
reverse(str, 0, str.length - 1 - n);
reverse(str, str.length - n, str.length - 1);
return new String(str);
}
public void reverse(char[] str, int start, int end){
while(start < end){
str[start] ^= str[end];
str[end] ^= str[start];
str[start] ^= str[end];
start++;
end--;
}
}
}
找出字串中第一個匹配項的下標
KMP字串匹配：在主串中尋找子串的程序，稱為模式匹配
KMP的主要思想是當出現字串不匹配時，可以知道一部分之前已經匹配的文本內容，可以利用這些資訊避免從頭再去做匹配了，
前綴表：記錄下標i之前（包括i）的字串中，有多大長度的相同前綴后綴，
28
class Solution {
public int strStr(String haystack, String needle) {
int[] arr = kmp(needle);
for(int i = 0, j = 0; i < haystack.length(); i++){
while(j > 0 && haystack.charAt(i) != needle.charAt(j)){
j = arr[j - 1];
}
if(haystack.charAt(i) == needle.charAt(j)){
j++;
}
if(j == needle.length()){
return i - j + 1;
}
}
return -1;
}
public int[] kmp(String needle){
int[] next = new int[needle.length()];
for(int i = 1, j = 0; i < next.length; i++){
while(j > 0 && needle.charAt(i) != needle.charAt(j)){
j = next[j - 1];
}
if(needle.charAt(i) == needle.charAt(j)){
j++;
}
next[i] = j;
}
return next;
}
}
重復的子字串
459
class Solution {
public boolean repeatedSubstringPattern(String s) {
int[] next = new int[s.length()];
next[0] = 0;
for(int i = 1, j = 0; i < s.length(); i++){
while(j > 0 && s.charAt(i) != s.charAt(j)){
j = next[j - 1];
}
if(s.charAt(i) == s.charAt(j)){
j++;
}
next[i] = j;
}
if(next[next.length - 1] != 0 && next.length%(next.length - next[next.length - 1]) == 0){
return true;
}
return false;
}
}
堆疊和佇列：容器配接器，不提供迭代器
232、用堆疊實作佇列
class MyQueue {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public MyQueue() {
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
public int peek() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
public boolean empty() {
if(stack1.isEmpty() && stack2.isEmpty()){
return true;
}
return false;
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
225、用佇列實作堆疊
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;//用來備份堆疊的資料（除堆疊頂）
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
// 方法一：較為繁瑣
// public void push(int x) {
// while(queue1.size() > 0){
// queue2.offer(queue1.poll());
// }
// while(queue2.size() > 0){
// queue1.offer(queue2.poll());
// }
// queue1.offer(x);
// }
// public int pop() {
// while(queue1.size() > 1){
// queue2.offer(queue1.poll());
// }
// int temp = queue1.poll();
// while(queue2.size() > 0){
// queue1.offer(queue2.poll());
// }
// return temp;
// }
// public int top() {
// while(queue1.size() > 1){
// queue2.offer(queue1.poll());
// }
// int temp = queue1.peek();
// while(queue1.size() > 0){
// queue2.offer(queue1.poll());
// }
// while(queue2.size() > 0){
// queue1.offer(queue2.poll());
// }
// return temp;
// }
// public boolean empty() {
// return queue1.isEmpty() && queue2.isEmpty();
// }
// 方法二：參考代碼隨想錄
// public void push(int x) {
// queue2.offer(x);
// while(!queue1.isEmpty()){
// queue2.offer(queue1.poll());
// }
// Queue<Integer> temp = new LinkedList<>();
// queue1 = queue2;
// queue2 = temp;
// }
// public int pop() {
// return queue1.poll();
// }
// public int top() {
// return queue1.peek();
// }
// public boolean empty() {
// return queue1.isEmpty() && queue2.isEmpty();
// }
// 方法三：用單佇列實作
public void push(int x) {
if(queue1.isEmpty()){
queue1.offer(x);
}else{
int count = queue1.size();
queue1.offer(x);
while(count > 0){
queue1.offer(queue1.poll());
count--;
}
}
}
public int pop() {
return queue1.poll();
}
public int top() {
return queue1.peek();
}
public boolean empty() {
return queue1.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
20、有效的括號
class Solution {
public boolean isValid(String s) {
// 方法一：用字串
// String s1 = "";
// if(s.length()%2 == 1){
// return false;
// }
// for(int i = 0; i < s.length(); i++){
// if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{'){
// s1 = s1 + s.charAt(i);
// }else if(s1.length() == 0){
// return false;
// }else if((s.charAt(i) == ']') && (s1.charAt(s1.length()-1) == '[')){
// s1 = s1.substring(0,s1.length() - 1);
// }else if((s.charAt(i) == '}') && (s1.charAt(s1.length()-1) == '{')){
// s1 = s1.substring(0,s1.length() - 1);
// }else if((s.charAt(i) == ')') && (s1.charAt(s1.length()-1) == '(')){
// s1 = s1.substring(0,s1.length() - 1);
// }else{
// return false;
// }
// }
// if(s1.length() == 0){
// return true;
// }else{
// return false;
// }
// 方法二：用堆疊
Stack<Character> stack = new Stack<>();
char[] arr = s.toCharArray();
for(int i = 0; i < arr.length; i++){
if(arr[i] == '(' || arr[i] == '[' || arr[i] == '{'){
stack.push(arr[i]);
}else if(arr[i] == ')'){
if(stack.isEmpty() || stack.pop() != '('){
return false;
}
}else if(arr[i] == ']'){
if(stack.isEmpty() ||stack.pop() != '['){
return false;
}
}else if(arr[i] == '}'){
if(stack.isEmpty() ||stack.pop() != '{'){
return false;
}
}
}
return stack.isEmpty();
}
}
1047、洗掉字串中的所有相鄰重復項
class Solution {
public String removeDuplicates(String s) {
// 方法一：用堆疊
char[] arr = s.toCharArray();
Stack<Character> stack = new Stack<>();
for(int i = 0; i < arr.length; i++){
if(stack.isEmpty()){
stack.push(arr[i]);
}else if(stack.peek() == arr[i]){
stack.pop();
}else{
stack.push(arr[i]);
}
}
String str = "";
while(!stack.isEmpty()){
str = stack.pop() + str;
}
return str;
// // 方法二：雙線佇列
// char[] arr = s.toCharArray();
// ArrayDeque<Character> arraydeque = new ArrayDeque<>();
// for(int i = 0; i < arr.length; i++){
// if(arraydeque.isEmpty()){
// arraydeque.push(arr[i]);
// }else if(arraydeque.peek() == arr[i]){
// arraydeque.pop();
// }else{
// arraydeque.push(arr[i]);
// }
// }
// String str = "";
// while(!arraydeque.isEmpty()){
// str = arraydeque.pop() + str;
// }
// return str;
}
}
150、逆波蘭運算式求值
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < tokens.length; i++){
if(tokens[i].equals("+")){
stack.push(stack.pop() + stack.pop());
}else if(tokens[i].equals("-")){
stack.push(-stack.pop() + stack.pop());
}else if(tokens[i].equals("*")){
stack.push(stack.pop() * stack.pop());
}else if(tokens[i].equals("/")){
int divisor = stack.pop();
int dividend = stack.pop();
int temp = dividend/divisor;
stack.push(temp);
}else{
stack.push(Integer.valueOf(tokens[i]));
}
}
return stack.pop();
}
}
239、滑動視窗最大值
單調佇列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new LinkedList<>();//單調雙向佇列
int[] result = new int[nums.length - k + 1];
for(int i = 0; i < nums.length; i++){
while(deque.peekFirst() != null && deque.peekFirst() < i - k + 1){
deque.pollFirst();
}
while(deque.peekLast() != null && nums[i] > nums[deque.peekLast()]){
deque.pollLast();
}
deque.offerLast(i);
if(i - k + 1 >= 0 ){
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
}
347、前 K 個高頻元素
優先級佇列，大頂堆，小頂堆
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int i: nums){
map.put(i, map.getOrDefault(i, 0) + 1);
}
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] m, int[] n){
return m[1] - n[1];
}
});
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
if(pq.size() < k){
pq.add(new int[]{entry.getKey(), entry.getValue()});
}else{
if(pq.peek()[1] < entry.getValue()){
pq.poll();
pq.add(new int[]{entry.getKey(), entry.getValue()});
}
}
}
int[] arr = new int[k];
for(int i = 0; i < arr.length; i++){
arr[i] = pq.poll()[0];
}
return arr;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/547624.html
標籤：其他
上一篇：keyclaok~web安全防護