devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode代码随想录

作者：2023面试高手 | 2024-05-13 00:48:17

赞

踩

代码随想录

代码随想录 (programmercarl.com)

目录

数组

2.二分查找

704.二分查找

35.搜索插入位置

c++ 

34.在排序数组中查找元素的第一个和最后一个位置 

69.X的平方根

367.有效的完全平方数

3.移除元素 

27.移除元素 

283.移动零

844.比较含退格的字符串

4.有序数组的平方 

97.有序数组的平方

5.长度最小的子数组 

209.长度最小的子数组(滑窗）

904.水果篮子（最大滑动窗口） 

6.螺旋矩阵2

59.螺旋矩阵 

链表

链表初始化

运行helloworld.java

2.移除链表元素 

203.移除链表元素

3.设计链表

707.设计链表

4.翻转链表

206.翻转链表

5.两两交换链表中的节点

24.两两交换链表中的节点

6.删除链表的倒数第N个节点

19.删除链表的倒数第N个节点

7. 链表相交

160.链表相交

8.环形链表

142.环形链表

哈希表

2.有效的字母异位词

242. 有效的字母异位词

3.两个数的交集 

hashset

 349.两个数的交集

4.快乐数

5.两数之和

hashmap

1.两数之和 

7.赎金信

 383.赎金信

6.四数相加

454. 四数相加2

8.三数之和

ArrayList

15.三数之和 

9.4数之和

字符串

1.翻转字符串

344.翻转字符串

2.翻转字符串

541.翻转字符串

3.替换空格

05.替换空格

 4.翻转字符串里的单词

151.翻转字符串里的单词

5.左旋转字符串

58.左旋转字符串

6.实现strStr()

28.实现strStr()

双指针

1.移除元素

26.删除有序数组中的重复项

数组

2.二分查找

704.二分查找

c++ 

  1. class Solution {
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.         int left = 0;
  5.         int right = nums.size() - 1;
  6.         while(left <= right){
  7.             int middle = (left + right)/2;
  8.             if(target > nums[middle]){
  9.                 left = middle + 1;
  10.             }else if(target < nums[middle]){
  11.                 right = middle - 1;
  12.             }else{
  13.                 return middle;
  14.             }
  15.         }
  16.         return -1;
  17.         
  18.     }
  19. };

java 

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.             int left = 0;
  4.             int right = nums.length - 1;
  5.             while(left <= right){
  6.                 int mid = (left + right) / 2;
  7.                 if(target > nums[mid]){
  8.                     left = mid + 1;
  9.                 }else if(target < nums[mid]){
  10.                     right = mid -1;
  11.                 }else{
  12.                     return mid;
  13.                 }
  14.             }
  15.             return -1;
  16.     }
  17. }

35.搜索插入位置

c++ 

  1. class Solution {
  2. public:
  3.     int searchInsert(vector<int>& nums, int target) {
  4.         int left = 0;
  5.         int right = nums.size() - 1;
  6.         while(left <= right){
  7.             int mid = (left + right) / 2;
  8.             if(target < nums[mid]){
  9.                 right = mid - 1;
  10.             }else if(target > nums[mid]){
  11.                 left  = mid + 1;
  12.             }else{
  13.                 return mid;
  14.             }
  15.         }
  16.         return right + 1;
  17.     }
  18. };

34.在排序数组中查找元素的第一个和最后一个位置 

c++

  1. class Solution {
  2. public:
  3.     vector<int> searchRange(vector<int>& nums, int target) {
  4.        int rightBorder = getRightBorder(nums, target);
  5.        int leftBorder = getLeftBorder(nums, target);
  6.        //
  7.        if(rightBorder == -2 || leftBorder == -2){
  8.            return {-1, -1};
  9.        }else if(rightBorder - leftBorder > 1){
  10.            return {leftBorder + 1, rightBorder - 1};
  11.        }else{
  12.            return {-1, -1};
  13.        }
  14.     }
  15. private:
  16.     int getRightBorder(vector<int>& nums, int target){
  17.         int left = 0;
  18.         int right = nums.size() - 1;
  19.         int rightBorder = -2;
  20.         while(left <= right){
  21.             int mid = (left + right) / 2;
  22.             if(target < nums[mid]){
  23.                 right = mid - 1;
  24.             }else{
  25.                 left = mid + 1;
  26.                 rightBorder = left;
  27.             }
  28.         }
  29.         return rightBorder;
  30.     }
  31.     int getLeftBorder(vector<int>& nums, int target){
  32.         int left = 0;
  33.         int right = nums.size() - 1;
  34.         int leftBorder = -2;
  35.         while(left <= right){
  36.             int mid = (left + right) / 2;
  37.             if(target <= nums[mid]){
  38.                 right = mid - 1;
  39.                 leftBorder = right;
  40.             }else{
  41.                 left = mid + 1;
  42.             }
  43.         }
  44.         return leftBorder;
  45.     }
  46. };

 java

  1. class Solution {
  2.     public int[] searchRange(int[] nums, int target) {
  3.         int rightBorder = getRightBorder(nums, target);
  4.         int leftBorder = getLeftBorder(nums, target);
  5.         if(rightBorder == -2 || leftBorder == -2){
  6.             return new int[]{-1, -1};
  7.         }else if(rightBorder - leftBorder > 1){
  8.             return new int[]{leftBorder + 1, rightBorder - 1};
  9.         }else{
  10.             return new int[]{-1 ,-1};
  11.         }
  12.  
  13.     }
  14.     int getRightBorder(int[] nums, int target){
  15.         int left = 0;
  16.         int right = nums.length - 1;
  17.         int rightBorder = -2;
  18.         while(left <= right){
  19.             int mid = (left + right)/2;
  20.             if(target < nums[mid]){
  21.                 right = mid - 1;
  22.             }else{
  23.                 left = mid + 1;
  24.                 rightBorder = left;
  25.             }
  26.         }
  27.         return rightBorder;
  28.     }
  29.     int getLeftBorder(int[] nums, int target){
  30.         int left = 0;
  31.         int right = nums.length - 1;
  32.         int leftBorder = -2;
  33.         while(left <= right){
  34.             int mid = (left + right)/2;
  35.             if(target >= nums[mid]){
  36.                 left = mid + 1;
  37.             }else{
  38.                 right = mid - 1;
  39.                 leftBorder = right;
  40.             }
  41.         }
  42.         return leftBorder;
  43.     }
  44. }

69.X的平方根

c++

  1. class Solution {
  2. public:
  3.     int mySqrt(int x) {
  4.         int left = 0;
  5.         int right = x;
  6.         int ans = -1;
  7.         while(left <= right){
  8.             int mid = (left + right)/2;
  9.             if((long long)mid * mid > x){
  10.                 right = mid - 1;
  11.             }else{
  12.                 left = mid + 1;
  13.                 ans = mid;
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18. };

java 

  1. class Solution {
  2.     public int mySqrt(int x) {
  3.         int left = 0;
  4.         int right = x;
  5.         int ans = -1;
  6.         while(left <= right){
  7.             int mid = left + (right - left)/2;
  8.             if((long)mid * mid <= x)
  9.             {
  10.                 ans = mid;
  11.                 left = mid + 1;
  12.             }else{
  13.                 right = mid - 1;
  14.             }
  15.         }
  16.         return ans;
  17.     }
  18. }

367.有效的完全平方数

 c++

  1. class Solution {
  2. public:
  3.     bool isPerfectSquare(int num) {
  4.         int left = 0;
  5.         int right = num;
  6.         int ans = -1;
  7.         while(left <= right){
  8.             int mid = left + (right - left)/2;
  9.             if((long long)mid * mid < num){
  10.                 left = mid + 1;
  11.             }else if((long long)mid * mid > num){
  12.                 right = mid - 1; 
  13.             }else{
  14.                 ans = mid;
  15.                 break;
  16.             }
  17.         }
  18.         if(ans == -1){
  19.             return false;
  20.         }else{
  21.             return true;
  22.         }
  23.     }
  24. };

java 

  1. class Solution {
  2.     public boolean isPerfectSquare(int num) {
  3.         int left = 0;
  4.         int right = num;
  5.         int ans = -1;
  6.         while(left <= right){
  7.             int mid = left + (right - left)/2;
  8.             if((long)mid * mid < num){
  9.                 left = mid + 1;
  10.             }else if((long)mid * mid > num){
  11.                 right = mid - 1; 
  12.             }else{
  13.                 ans = mid;
  14.                 break;
  15.             }
  16.         }
  17.         if(ans == -1){
  18.             return false;
  19.         }else{
  20.             return true;
  21.         }
  22.     }
  23. }

3.移除元素 

27.移除元素 

c++

  1. class Solution {
  2. public:
  3.     int removeElement(vector<int>& nums, int val) {
  4.         int fastIndex = 0;
  5.         int lowIndex = 0;
  6.         for(fastIndex=0;fastIndex<nums.size();fastIndex++){
  7.             if(nums[fastIndex]!=val){
  8.                 nums[lowIndex++] = nums[fastIndex];
  9.             }
  10.         }
  11.         return lowIndex;
  12.     }
  13. };

java 

  1. class Solution {
  2.     public int removeElement(int[] nums, int val) {
  3.         int fastIndex = 0;
  4.         int lowIndex = 0;
  5.         for(fastIndex=0;fastIndex<nums.length;fastIndex++){
  6.             if(val!=nums[fastIndex]){
  7.                 nums[lowIndex]=nums[fastIndex];
  8.                 lowIndex++;
  9.             }
  10.         }
  11.         return lowIndex;
  12.     }
  13. }

283.移动零

c++

  1. class Solution {
  2. public:
  3.     void moveZeroes(vector<int>& nums) {
  4.         int fastIndex = 0;
  5.         int lowIndex = 0;
  6.         for(fastIndex = 0; fastIndex < nums.size(); fastIndex ++){
  7.             if(nums[fastIndex] != 0){
  8.                 nums[lowIndex++] = nums[fastIndex];
  9.             }
  10.         }
  11.         for(;lowIndex < nums.size(); lowIndex ++){
  12.             nums[lowIndex] = 0;
  13.         }
  14.         
  15.     }
  16. };

java 

  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.         int lowIndex = 0;
  4.         for(int fastIndex = 0; fastIndex < nums.length; fastIndex ++){
  5.             if(nums[fastIndex] != 0){
  6.                 nums[lowIndex] = nums[fastIndex];
  7.                 lowIndex ++;
  8.             }
  9.         }
  10.         for(;lowIndex < nums.length; lowIndex ++){
  11.             nums[lowIndex] = 0;
  12.         }
  13.     }
  14. }

844.比较含退格的字符串

c++ 

  1. class Solution {
  2. public:
  3.     bool backspaceCompare(string s, string t) {
  4.         int sIndex = 0;
  5.         int tIndex = 0;
  6.         int i = s.size() - 1;
  7.         int j = t.size() - 1;
  8.         while(1){
  9.             while(i >= 0){
  10.                 if(s[i] == '#'){
  11.                     sIndex ++;
  12.                 }else{
  13.                     if(sIndex >0) sIndex --;
  14.                     else break;
  15.                 }
  16.                 i--;
  17.             }
  18.             while(j >= 0){
  19.                 if(t[j] == '#'){
  20.                     tIndex++;
  21.                 }else{
  22.                     if(tIndex > 0) tIndex--;
  23.                     else break;
  24.                 }
  25.                 j--;
  26.             }
  27.             if(i < 0 || j < 0) break;
  28.             if(s[i] != t[j]) return false;
  29.             i--;j--;
  30.         }
  31.         if(i == -1 && j == -1) return true;
  32.         return false;
  33.     }
  34. };

java :双指针

  1. class Solution {
  2.     public boolean backspaceCompare(String S, String T) {
  3.         int sIndex = 0;
  4.         int tIndex = 0;
  5.         int i = S.length() - 1;
  6.         int j = T.length() - 1;
  7.         char[] s = S.toCharArray();
  8.         char[] t = T.toCharArray();
  9.         while(true){
  10.             while(i >= 0){
  11.                 if(s[i] == '#'){
  12.                     sIndex ++;
  13.                 }else{
  14.                     if(sIndex >0) sIndex --;
  15.                     else break;
  16.                 }
  17.                 i--;
  18.             }
  19.             while(j >= 0){
  20.                 if(t[j] == '#'){
  21.                     tIndex++;
  22.                 }else{
  23.                     if(tIndex > 0) tIndex--;
  24.                     else break;
  25.                 }
  26.                 j--;
  27.             }
  28.             if(i < 0 || j < 0) break;
  29.             if(s[i] != t[j]) return false;
  30.             i--;j--;
  31.         }
  32.         if(i == -1 && j == -1) return true;
  33.         return false;
  34.     }
  35. }

java:栈 

  1. class Solution {
  2.     public boolean backspaceCompare(String S, String T) {
  3.         StringBuilder s = new StringBuilder();
  4.         StringBuilder t = new StringBuilder();
  5.         for(char c: S.toCharArray()){
  6.             if(c != '#'){
  7.                 s.append(c);
  8.             }else if(s.length() > 0){
  9.                 s.deleteCharAt(s.length() - 1);
  10.             }
  11.         }
  12.         for(char c: T.toCharArray()){
  13.             if(c != '#'){
  14.                 t.append(c);
  15.             }else if(t.length() > 0){
  16.                 t.deleteCharAt(t.length() - 1);
  17.             }
  18.         }
  19.         return s.toString().equals(t.toString());
  20.     }
  21. }

4.有序数组的平方 

97.有序数组的平方

 c++

  1. class Solution {
  2. public:
  3.     vector<int> sortedSquares(vector<int>& nums) {
  4.         int size = nums.size();
  5.         vector<int> ans(size,0);
  6.         int k = size - 1;
  7.         for(int i = 0,j = size - 1;i <= j;){
  8.             if(nums[i] * nums[i] < nums[j] * nums[j]){
  9.                 ans[k] = nums[j] * nums[j];
  10.                 j--;
  11.             }else{
  12.                 ans[k] = nums[i] * nums[i];
  13.                 i++;
  14.             }
  15.             k--;
  16.         }
  17.         return ans;
  18.     }
  19. };

java

  1. class Solution {
  2.     public int[] sortedSquares(int[] nums) {
  3.         int size = nums.length;
  4.         int[] ans = new int[size];
  5.         for(int i = 0,j = size -1, k = size -1;i <= j;k--){
  6.             if(nums[i] * nums[i] < nums[j] * nums[j]){
  7.                 ans[k] = nums[j] * nums[j];
  8.                 j--;
  9.             }else{
  10.                 ans[k] = nums[i] * nums[i];
  11.                 i++;
  12.             }
  13.         }
  14.         return ans;
  15.     }
  16. }

5.长度最小的子数组 

209.长度最小的子数组(滑窗）

c++ 

  1. class Solution {
  2. public:
  3.     int minSubArrayLen(int target, vector<int>& nums) {
  4.         int result = INT32_MAX;
  5.         int i = 0;
  6.         int sum = 0;
  7.         for(int j = 0; j < nums.size(); j++){
  8.             sum += nums[j];
  9.             while(sum >= target){
  10.                 int len = (j - i + 1);
  11.                 result = result > len ? len:result;
  12.                 sum -= nums[i++];
  13.             }
  14.         }
  15.         return result == INT32_MAX ? 0 : result;
  16.     }
  17. };

java 

  1. class Solution {
  2.     public int minSubArrayLen(int target, int[] nums) {
  3.         int result = Integer.MAX_VALUE;
  4.         int i = 0;
  5.         int sum = 0;
  6.         for(int j = 0; j < nums.length; j++){
  7.             sum += nums[j];
  8.             while(sum >= target){
  9.                 result = Math.min(result, j - i + 1);
  10.                 sum -= nums[i++];
  11.             }
  12.         }
  13.         return result == Integer.MAX_VALUE ? 0 : result;
  14.     }
  15. }

904.水果篮子（最大滑动窗口） 

c++

  1. class Solution {
  2. public:
  3.     int totalFruit(vector<int>& fruits) {
  4.         int n = fruits.size();
  5.         int left = 0;
  6.         int ans = 0;
  7.         unordered_map<int, int> cnt;
  8.         for(int right = 0; right < n; ++right){
  9.             ++cnt[fruits[right]];
  10.             while(cnt.size() > 2){
  11.                 auto it = cnt.find(fruits[left]);
  12.                 --it->second;
  13.                 if(it->second == 0){
  14.                     cnt.erase(fruits[left]);
  15.                 }
  16.                 ++left;
  17.             }
  18.             ans = max(ans, right - left + 1);
  19.         }
  20.         return ans;
  21.     }
  22. };

java

  1. class Solution {
  2.     public int totalFruit(int[] fruits) {
  3.         int n = fruits.length;
  4.         Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
  5.  
  6.         int left = 0, ans = 0;
  7.         for (int right = 0; right < n; ++right) {
  8.             cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);
  9.             while (cnt.size() > 2) {
  10.                 cnt.put(fruits[left], cnt.get(fruits[left]) - 1);
  11.                 if (cnt.get(fruits[left]) == 0) {
  12.                     cnt.remove(fruits[left]);
  13.                 }
  14.                 ++left;
  15.             }
  16.             ans = Math.max(ans, right - left + 1);
  17.         }
  18.         return ans;
  19.     }
  20. }
  21.

6.螺旋矩阵2

59.螺旋矩阵 

c++

  1. class Solution {
  2. public:
  3.     vector<vector<int>> generateMatrix(int n) {
  4.         int startx = 0, starty = 0;
  5.         int offest = 1;
  6.         vector<vector<int>> array(n, vector<int>(n, 0));
  7.         int count = 1;
  8.         int i,j;
  9.         int mid = n/2;
  10.         while(mid --){
  11.             i = startx;
  12.             j = starty;
  13.             for(j = starty; j < n - offest; j++){
  14.                 array[startx][j] = count++;
  15.             }
  16.             for(i = startx; i < n - offest; i++){
  17.                 array[i][j] = count++;
  18.             }
  19.             for(; j > starty; j--){
  20.                 array[i][j] = count++;
  21.             }
  22.             for(; i > startx; i--){
  23.                 array[i][j] = count++;
  24.             }
  25.             startx ++;
  26.             starty ++;
  27.             offest ++;
  28.         }
  29.         if(n % 2){
  30.             array[n/2][n/2] = count;
  31.         }
  32.         return array;
  33.     }
  34. };

java

  1. class Solution {
  2.     public int[][] generateMatrix(int n) {
  3.         int startx = 0, starty = 0;
  4.         int[][] res = new int[n][n];
  5.         int offset = 1;
  6.         int mid = n/2;
  7.         int i,j;
  8.         int count = 1;
  9.         while(mid-- > 0){
  10.             i = startx;
  11.             j = starty;
  12.             for(j = starty; j < n - offset; j++){
  13.                 res[startx][j] = count++;
  14.             }
  15.             for(i = startx; i < n - offset; i++){
  16.                 res[i][j] = count++;
  17.             }
  18.             for(; j > starty; j--){
  19.                 res[i][j] = count++;
  20.             }
  21.             for(; i > startx; i--){
  22.                 res[i][j] = count++;
  23.             }
  24.             startx++;
  25.             starty++;
  26.             offset++;
  27.         }
  28.         if(n % 2 != 0){
  29.             res[n/2][n/2] = count;
  30.         }
  31.         return res;
  32.     }
  33. }

链表

链表初始化

运行helloworld.java

用力扣刷算法没有输入输出，以下是配置环境然后运行的博客

(28条消息) idea创建并运行第一个java程序_LYSnowy的博客-CSDN博客

2.移除链表元素 

203.移除链表元素

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode removeElements(ListNode head, int val) {
  13.         if(head == null){
  14.             return head;
  15.         }
  16.         ListNode dummy = new ListNode(-1);
  17.         dummy.next = head;//添加头结点
  18.         ListNode pre = dummy;
  19.         ListNode cur = head;
  20.         while(cur != null){
  21.             if(cur.val == val){
  22.                 pre.next = cur.next;
  23.             }else{
  24.                 pre = cur;
  25.             }
  26.             cur = cur.next;
  27.         }
  28.         return dummy.next;
  29.     }
  30. }

3.设计链表

707.设计链表

理论考研的时候就会了，但是不一定会ac，链表定义很重要。

  1. class ListNode{
  2.     int val;
  3.     ListNode next;
  4.     ListNode(){}
  5.     ListNode(int val){this.val = val;}
  6.     ListNode(int val, ListNode next){this.val = val; this.next = next;}
  7. }
  8.  
  9. class MyLinkedList {
  10.  
  11.     int size; //存储链表元素的个数
  12.  
  13.     ListNode head; //虚拟头结点
  14.  
  15.     public MyLinkedList() {
  16.         size = 0;
  17.         head = new ListNode(0);
  18.     }
  19.     
  20.     public int get(int index) {
  21.  
  22.         if(index < 0 || index >= size) return -1;
  23.  
  24.         ListNode cur = head;
  25.         for(int i = 0; i <= index; i++){
  26.             cur = cur.next;
  27.         }
  28.         return cur.val;
  29.     }
  30.     
  31.     public void addAtHead(int val) {
  32.         addAtIndex(0, val);
  33.     }
  34.     
  35.     public void addAtTail(int val) {
  36.  
  37.         addAtIndex(size, val);
  38.  
  39.     }
  40.     
  41.     public void addAtIndex(int index, int val) {
  42.  
  43.         if(index > size) return ;
  44.  
  45.         if(index < 0) index = 0;
  46.         size++;
  47.  
  48.         ListNode pred = head;
  49.         for(int i = 0; i < index; i++){
  50.             pred = pred.next;
  51.         }
  52.         ListNode toAdd = new ListNode(val);
  53.         toAdd.next = pred.next;
  54.         pred.next = toAdd;
  55.     }
  56.     
  57.     public void deleteAtIndex(int index) {
  58.         if(index < 0 || index >= size)
  59.             return ;
  60.  
  61.         size--;
  62.  
  63.         if(index == 0)
  64.         {
  65.             head = head.next;
  66.         }else{
  67.             ListNode pred = head;
  68.             for(int i = 0; i < index; i++){
  69.                 pred = pred.next;
  70.             }
  71.         
  72.             pred.next = pred.next.next;
  73.         }
  74.         
  75.         
  76.     }
  77. }
  78.  
  79. /**
  80.  * Your MyLinkedList object will be instantiated and called as such:
  81.  * MyLinkedList obj = new MyLinkedList();
  82.  * int param_1 = obj.get(index);
  83.  * obj.addAtHead(val);
  84.  * obj.addAtTail(val);
  85.  * obj.addAtIndex(index,val);
  86.  * obj.deleteAtIndex(index);
  87.  */

4.翻转链表

206.翻转链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }   双指针 ****************************************
  10.  */
  11. class Solution {
  12.     public ListNode reverseList(ListNode head) {
  13.  
  14.         ListNode pre = null;
  15.         ListNode cur = head;
  16.  
  17.         while(cur != null){
  18.  
  19.             ListNode temp = cur.next;
  20.             cur.next = pre;
  21.             pre = cur;
  22.             cur = temp;
  23.         }
  24.  
  25.         return pre;
  26.     }
  27. }
  28.  
  29. /**
  30.  * Definition for singly-linked list.
  31.  * public class ListNode {
  32.  *     int val;
  33.  *     ListNode next;
  34.  *     ListNode() {}
  35.  *     ListNode(int val) { this.val = val; }
  36.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  37.  * }  递归 ***********************************
  38.  */
  39. class Solution {
  40.  
  41.     public ListNode reverseList(ListNode cur, ListNode pre){
  42.  
  43.         if(cur == null) return pre;
  44.  
  45.         ListNode temp = cur.next;
  46.         cur.next = pre;
  47.      
  48.         return reverseList(temp, cur);
  49.     }
  50.  
  51.     public ListNode reverseList(ListNode head) {
  52.  
  53.         return reverseList(head, null);
  54.  
  55.     }
  56. }

445.两数相加

 

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode reverse(ListNode l){
  13.         if(l == null) return l;
  14.         ListNode pre = null;
  15.         ListNode cur = l;
  16.         ListNode tmp = null;
  17.         while(cur != null){
  18.             tmp = cur.next;
  19.             cur.next = pre;
  20.             pre = cur;
  21.             cur = tmp; 
  22.         }
  23.         return pre;
  24.     }
  25.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  26.         int len1=0,len2=0;
  27.         ListNode cur1 = l1;
  28.         ListNode cur2 = l2;
  29.         //step1：求链表长度
  30.         while(cur1 != null){
  31.             len1++;
  32.             cur1 = cur1.next;
  33.         }
  34.         while(cur2 != null){
  35.             len2++;
  36.             cur2 = cur2.next;
  37.         }
  38.         //step2:翻转
  39.         l1 = reverse(l1);
  40.         l2 = reverse(l2);
  41.         //step3:相加
  42.         int add = 0,carry = 0;
  43.         if(len1<len2){
  44.             ListNode tmp = l1;
  45.             l1 = l2;
  46.             l2 = tmp;
  47.         }
  48.         cur1 = l1;
  49.         cur2 = l2;
  50.         //长度重合部分
  51.         while(cur1 != null && cur2 != null){
  52.             add = (cur1.val + cur2.val + carry);
  53.             if(add >= 10){//进位
  54.                 carry = add / 10;
  55.             }else{
  56.                 carry = 0;
  57.             }
  58.             cur1.val = add % 10;
  59.             cur1 = cur1.next;
  60.             cur2 = cur2.next;
  61.         }
  62.         //多出来的部分
  63.         while(cur1 != null && carry > 0){
  64.                 add = cur1.val + carry;
  65.                 if(add >= 10){//进位
  66.                     carry = add / 10;
  67.                 }else{
  68.                     carry = 0;
  69.                 }
  70.                 cur1.val = add % 10;
  71.                 cur1 = cur1.next;
  72.             }
  73.         //step4:翻转
  74.         l1 = reverse(l1);
  75.         //头插法，溢出
  76.         if(carry > 0){
  77.             ListNode addList = new ListNode(carry);
  78.             addList.next = l1;
  79.             l1 = addList;
  80.         }
  81.         return l1;
  82.     }
  83.  
  84.     
  85. }

5.两两交换链表中的节点

24.两两交换链表中的节点

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode swapPairs(ListNode head) {
  13.  
  14.         ListNode dummy = new ListNode(-1);
  15.         dummy.next = head;
  16.         ListNode cur = dummy;
  17.         while(cur.next != null && cur.next.next != null){
  18.  
  19.             ListNode temp = cur.next;
  20.             ListNode temp1 = cur.next.next.next;
  21.             cur.next = cur.next.next;
  22.             cur.next.next = temp;
  23.             temp.next = temp1;
  24.             cur = cur.next.next;
  25.  
  26.         }
  27.         return dummy.next;
  28.         
  29.     }
  30. }

6.删除链表的倒数第N个节点

19.删除链表的倒数第N个节点

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode removeNthFromEnd(ListNode head, int n) {
  13.  
  14.         ListNode dummy = new ListNode(-1);
  15.         dummy.next = head;
  16.         ListNode fast = dummy;
  17.         ListNode slow = dummy;
  18.         while(n > 0){
  19.             fast = fast.next;
  20.             n--;
  21.         }
  22.         while(fast.next != null){
  23.             fast = fast.next;
  24.             slow = slow.next;
  25.         }
  26.         slow.next = slow.next.next;
  27.         return dummy.next;
  28.  
  29.     }
  30. }

7. 链表相交

160.链表相交

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. class Solution {
  13.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  14.         ListNode curA = headA;
  15.         ListNode curB = headB;
  16.         int lenA = 0;
  17.         int lenB = 0;
  18.         while(curA != null){
  19.             curA = curA.next;
  20.             lenA++;
  21.         }
  22.         while(curB != null){
  23.             curB = curB.next;
  24.             lenB++;
  25.         }
  26.         curA = headA;
  27.         curB = headB;
  28.         if(lenA > lenB){
  29.             int gap = lenA - lenB;
  30.             while(gap > 0){
  31.                 curA = curA.next;
  32.                 gap--;
  33.             }
  34.         }else{
  35.             int gap = lenB - lenA;
  36.             while(gap > 0){
  37.                 curB = curB.next;
  38.                 gap--;
  39.             }
  40.         }
  41.         while(curA != curB){
  42.             curA = curA.next;
  43.             curB = curB.next;
  44.         }
  45.         return curB;
  46.     }
  47. }

8.环形链表

142.环形链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) {
  7.  *         val = x;
  8.  *         next = null;
  9.  *     }
  10.  * }
  11.  */
  12. class Solution {
  13.     public ListNode detectCycle(ListNode head) {
  14.         
  15.         ListNode fast = head;
  16.         ListNode slow = head;
  17.  
  18.         while(fast != null && fast.next != null){
  19.  
  20.             fast = fast.next.next;
  21.             slow = slow.next;
  22.  
  23.             if(slow == fast){
  24.                 ListNode index1 = head;
  25.                 ListNode index2 = fast;
  26.  
  27.                 while(index1 != index2){
  28.  
  29.                     index1 = index1.next;
  30.                     index2 = index2.next;
  31.                 }
  32.                 return  index1;
  33.             }
  34.         }
  35.  
  36.         return null;
  37.     }
  38. }

哈希表

数组、hashset、hashmap

2.有效的字母异位词

242. 有效的字母异位词

  1. class Solution {
  2.     public boolean isAnagram(String s, String t) {
  3.  
  4.         int[] hash = new int[26];
  5.  
  6.         for(int i = 0;i < s.length() ; i++){
  7.  
  8.             hash[s.charAt(i) - 'a']++;
  9.  
  10.         }
  11.         for(int i = 0; i < t.length() ; i++){
  12.  
  13.             hash[t.charAt(i) - 'a']--;
  14.         }
  15.         for(int i = 0; i < 26; i++){
  16.             if(hash[i] != 0){
  17.                 return false;
  18.             }
  19.         }
  20.         return true;
  21.     }
  22. }

3.两个数的交集 

hashset

  1. import java.util.HashSet; //引入HashSet类
  2. HashSet<String> a = new HashSet<String>(); //新建实例
  3. a.add(1); //添加元素
  4. a.contains(1); //判断元素是否存在于集合当中
  5. a.remove(1); //删除集合中的元素
  6. a.clear(); //删除所有元素
  7. a.size(); //计算元素数量
  8. //迭代
  9. for(int i : a){
  10.     System.out.println(i);
  11. }

 349.两个数的交集

  1. import java.util.HashSet;
  2.  
  3. class Solution {
  4.     public int[] intersection(int[] nums1, int[] nums2) {
  5.  
  6.         HashSet<Integer> result = new HashSet<Integer>();
  7.         HashSet<Integer> hash = new HashSet<Integer>();
  8.  
  9.         for(int i : nums1){
  10.             if(!hash.contains(i)){
  11.                 hash.add(i);
  12.             }
  13.         }
  14.         for(int i : nums2){
  15.             if(hash.contains(i)){
  16.                 result.add(i);
  17.             }
  18.         }
  19.  
  20.         int[] res = new int[result.size()];
  21.         int j = 0;
  22.         for(int i : result){
  23.  
  24.             res[j++] = i;
  25.         }
  26.         
  27.         return res;
  28.     }
  29. }

HashSet 不是线程安全的， 如果多个线程尝试同时修改 HashSet，则最终结果是不确定的。 您必须在多线程访问时显式同步对 HashSet 的并发访问。

4.快乐数

202.快乐数

  1. import java.util.HashSet;
  2.  
  3.  
  4. class Solution {
  5.  
  6.     int SUM(int n){
  7.  
  8.         int sum = 0;
  9.         while(n > 0){
  10.             sum += (n % 10)*(n % 10);
  11.             n /= 10;
  12.         }
  13.         
  14.         return sum;
  15.     }
  16.  
  17.     public boolean isHappy(int n) {
  18.  
  19.         HashSet<Integer> hash = new HashSet<Integer>();
  20.         int sum = 0;
  21.         while(true){
  22.             if(n == 1) return true;
  23.             sum = SUM(n);
  24.             if(hash.contains(sum)){
  25.                 return false;
  26.             }else{
  27.                 hash.add(sum);
  28.                 n = sum;
  29.             }
  30.         }
  31.     }
  32. }

5.两数之和

hashmap

  1. import java.util.HashMap; //引入HashMap类
  2. HashMap<Integer, String> a = new HashMap<Integer, String>();
  3. a.put(1,'a'); //添加
  4. a.get(1); //获取key对应的value
  5. a.remove(1); //删除
  6. a.clear(); //删除所有
  7. a.size(); //计算大小
  8. //迭代
  9. for(int i : a.keySet()){
  10.     
  11.     System.out.println(i + a.get(i));
  12.  
  13. }
  14.  
  15. for(int i : a.values()){
  16.     
  17.     System.out.println(i);
  18.  
  19. }
  20.  
  21. //方法
  22. clone() //复制
  23. isEmpty() // 判断是否为空
  24. putAll() //将所有键/值对添加到 hashMap 中
  25. putIfAbsent() //将所有键/值对添加到 hashMap 中
  26. containsKey() //检查 hashMap 中是否存在指定的 key 对应的映射关系。
  27. containsValue() //检查 hashMap 中是否存在指定的 key 对应的映射关系。
  28. replace() //检查 hashMap 中是否存在指定的 key 对应的映射关系。
  29. replaceAll() //将 hashMap 中的所有映射关系替换成给定的函数所执行的结果。
  30. getOrDefault() //获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值
  31. forEach() //获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值
  32. entrySet() //返回 hashMap 中所有映射项的集合集合视图
  33. merge() //返回 hashMap 中所有映射项的集合集合视图
  34. compute() //返回 hashMap 中所有映射项的集合集合视图
  35. computeIfAbsent() //返回 hashMap 中所有映射项的集合集合视图
  36. computeIfPresent() //返回 hashMap 中所有映射项的集合集合视图

1.两数之和 

  1. import java.util.HashMap;
  2.  
  3. class Solution {
  4.     public int[] twoSum(int[] nums, int target) {
  5.  
  6.         HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
  7.         int[] result = new int[2];
  8.  
  9.         for(int i = 0; i < nums.length; i++){
  10.             if(hash.isEmpty()){
  11.                 hash.put(nums[i], i);
  12.             }else{
  13.                 if(hash.containsKey(target - nums[i])){
  14.  
  15.                     result[1] = i;
  16.                     result[0] = hash.get(target - nums[i]);
  17.                     break;
  18.                 }else{
  19.                     hash.put(nums[i], i);
  20.                 }
  21.             }
  22.             
  23.         }
  24.         return result;
  25.     }
  26. }

7.赎金信

 383.赎金信

  1. class Solution {
  2.     public boolean canConstruct(String ransomNote, String magazine) {
  3.  
  4.         int[] hash = new int[26];
  5.         for(int i = 0; i < magazine.length(); i++){
  6.  
  7.             hash[magazine.charAt(i) - 'a']++;
  8.  
  9.         }
  10.         for(int i = 0; i < ransomNote.length(); i++){
  11.  
  12.             hash[ransomNote.charAt(i) - 'a']--;
  13.  
  14.         }
  15.         for(int i = 0; i < 26; i++){
  16.  
  17.             if(hash[i] < 0){
  18.                 return false;
  19.             }
  20.         }
  21.         return true;
  22.         
  23.     }
  24. }

6.四数相加

454. 四数相加2

  1. import java.util.HashMap;
  2.  
  3. class Solution {
  4.     public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
  5.  
  6.         HashMap<Integer, Integer> AB = new HashMap<Integer, Integer>();
  7.         int sum = 0;
  8.  
  9.         for(int i : nums1){
  10.             for(int j : nums2){
  11.                 sum = i + j;
  12.                 AB.put(sum, AB.getOrDefault(sum, 0) + 1);
  13.                 
  14.             }
  15.         }
  16.         int count = 0;
  17.         for(int i : nums3){
  18.             for(int j : nums4){
  19.                 sum = (i + j) * (-1);
  20.                 count += AB.getOrDefault(sum, 0);
  21.             }
  22.         }
  23.         return count;
  24.  
  25.     }
  26. }

8.三数之和

ArrayList

  1. import java.util.ArrayList; 
  2. ArrayList<E> a = new ArrayList<>();
  3. a.add(1);
  4. a.get(0);
  5. a.set(0,2); //修改
  6. a.remove(0);
  7. a.size();
  8. //迭代
  9. for(int i = 0; i < a.size(); i++){
  10.  
  11.     System.out.println(a.get(i));
  12.  
  13. }
  14. a.sort();
  15. a.indexOf(); //返回索引值
  16. a.subList(); // 截取元素
  17. a.toArray(); 
  18. a.toString();

15.三数之和 

  1. import java.util.Arrays;
  2.  
  3. class Solution {
  4.     public List<List<Integer>> threeSum(int[] nums) {
  5.  
  6.         List<List<Integer>> res = new ArrayList<>();
  7.         Arrays.sort(nums);
  8.         
  9.         for(int i=0; i<nums.length; i++){
  10.  
  11.             if(nums[i] > 0) return res;
  12.             if(i > 0 && nums[i] == nums[i - 1]) continue;
  13.             int left = i + 1,right = nums.length -1 ;
  14.             while(right > left){
  15.                 int sum = nums[i] + nums[left] + nums[right];
  16.                 if(sum >0){
  17.                     right--;
  18.                 }else if(sum < 0){
  19.                     left++;
  20.                 }else{
  21.                     res.add(Arrays.asList(nums[i], nums[left], nums[right]));
  22.                     //去重
  23.                     while(right > left && nums[right] == nums[right - 1]) right--;
  24.                     while(right > left && nums[left] == nums[left + 1]) left++;
  25.  
  26.                     right--;
  27.                     left++;
  28.                 }
  29.             }
  30.             
  31.         }
  32.         return res;
  33.     }
  34. }

9.4数之和

4数之和

  1. class Solution {
  2.     public List<List<Integer>> fourSum(int[] nums, int target) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         Arrays.sort(nums);
  5.         for(int i = 0; i < nums.length; i++){
  6.             //剪枝
  7.             if(nums[i] > 0 && nums[i] > target) return res;
  8.             //去重
  9.             if(i > 0 && nums[i - 1] == nums[i]) continue;
  10.  
  11.             for(int j = i + 1; j < nums.length; j++){
  12.                 //去重
  13.                 if(j > i + 1 && nums[j - 1] == nums[j]) continue;
  14.  
  15.                 int left = j + 1;
  16.                 int right = nums.length - 1;
  17.                 while(right > left){
  18.                     long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
  19.                     if(sum > target) right--;
  20.                     else if(sum < target) left++;
  21.                     else{
  22.                         res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
  23.                         while(right > left && nums[right] == nums[right - 1]) right--;
  24.                         while(right > left && nums[left] == nums[left + 1]) left++;
  25.  
  26.                         left++;
  27.                         right--;
  28.                     }
  29.                 }
  30.             }
  31.             
  32.         }
  33.         return res;
  34.     }
  35. }

字符串

1.翻转字符串

344.翻转字符串

  1. class Solution {
  2.     public void reverseString(char[] s) {
  3.         char temp;
  4.         int right = s.length - 1;
  5.         int left = 0;
  6.         while(left < right){
  7.             temp = s[left];
  8.             s[left] = s[right];
  9.             s[right] = temp;
  10.             left++;
  11.             right--;
  12.         }
  13.  
  14.     }
  15. }

2.翻转字符串

541.翻转字符串

  1. class Solution {
  2.  
  3.     public String reverseStr(String s, int k) {
  4.       
  5.         char[] ch = s.toCharArray();
  6.         for(int i = 0; i < ch.length; i += 2 * k){
  7.             int start = i;
  8.             int end = Math.min(ch.length - 1, start + k - 1);
  9.             while(start < end){
  10.                 char temp = ch[start];
  11.                 ch[start] = ch[end];
  12.                 ch[end] = temp;
  13.                 start++;
  14.                 end--;
  15.             }
  16.         }
  17.         return new String(ch);
  18.     }
  19. }

3.替换空格

05.替换空格

  1. class Solution {
  2.     public String replaceSpace(String s) {
  3.         if(s.isEmpty()) return "";
  4.  
  5.         StringBuffer sb = new StringBuffer();
  6.  
  7.         for(int i = 0; i < s.length(); i++){
  8.             if(s.charAt(i)== ' '){
  9.                 sb.append("%20");
  10.             }else{
  11.                 sb.append(s.charAt(i));
  12.             }
  13.         }
  14.         return sb.toString();
  15.     }
  16. }

 4.翻转字符串里的单词

151.翻转字符串里的单词

  1. class Solution {
  2.  
  3.     private StringBuilder removeSpace(String s){
  4.         int start = 0;
  5.         int end = s.length() - 1;
  6.         while(s.charAt(start) == ' ') start++;
  7.         while(s.charAt(end) == ' ') end--;
  8.         StringBuilder sb = new StringBuilder();
  9.         while(start <= end){
  10.             char c = s.charAt(start);
  11.             if(c != ' ' || sb.charAt(sb.length() - 1) != ' ') 
  12.                 sb.append(c);
  13.             start++;
  14.  
  15.         }
  16.  
  17.         return sb;
  18.     }
  19.  
  20.     public void reverseString(StringBuilder sb, int start, int end){
  21.         while(start < end){
  22.             char temp = sb.charAt(start);
  23.             sb.setCharAt(start, sb.charAt(end));
  24.             sb.setCharAt(end, temp);
  25.             start++;
  26.             end--;
  27.             
  28.         }
  29.     }
  30.     public void reverseEachWord(StringBuilder sb){
  31.         int start = 0;
  32.         int end = 1;
  33.         int n = sb.length();
  34.         while(start < n){
  35.             while(end < n && sb.charAt(end) != ' '){
  36.                 end++;
  37.             }
  38.             reverseString(sb, start, end - 1);
  39.             start = end + 1;
  40.             end = start + 1;
  41.         }
  42.     }
  43.     public String reverseWords(String s) {
  44.         
  45.         //移除多余空格
  46.         StringBuilder sb = removeSpace(s);
  47.         //将整个字符串反转
  48.         reverseString(sb, 0 , sb.length() - 1);
  49.         //将每个单词反转
  50.         reverseEachWord(sb);
  51.         return sb.toString();
  52.     }
  53. }

5.左旋转字符串

58.左旋转字符串

  1. //1、另开一个存储空间
  2. class Solution {
  3.     public String reverseLeftWords(String s, int n) {
  4.         StringBuilder sb = new StringBuilder(s);
  5.         StringBuilder res = new StringBuilder();
  6.         for(int i = n; i < sb.length(); i++){
  7.             res.append(sb.charAt(i));
  8.         }
  9.         for(int i = 0; i < n; i++){
  10.             res.append(sb.charAt(i));
  11.         }
  12.         return res.toString();
  13.     }
  14. }
  15.  
  16. //2、使用一个存储空间
  17. class Solution {
  18.     public void reverse(StringBuilder sb, int start, int end){
  19.         while(start < end){
  20.             char temp = sb.charAt(start);
  21.             sb.setCharAt(start, sb.charAt(end));
  22.             sb.setCharAt(end, temp);
  23.             start++;
  24.             end--;
  25.         }
  26.         
  27.     }
  28.     public String reverseLeftWords(String s, int n) {
  29.         int len = s.length();
  30.         StringBuilder sb = new StringBuilder(s);
  31.         reverse(sb , 0 , n - 1);
  32.         reverse(sb , n , len - 1);
  33.         reverse(sb , 0 , len - 1);
  34.         return sb.toString();
  35.     }
  36. }

6.实现strStr()

28.实现strStr()

  1. class Solution {
  2.     private void getNext(int[] next, String s){
  3.         int j = 0;
  4.         next[0] = 0;
  5.         for(int i = 1; i < s.length(); i++){
  6.             while(j > 0 && s.charAt(j) != s.charAt(i))
  7.                 j = next[j - 1];
  8.             if(s.charAt(j) == s.charAt(i)) j++;
  9.             next[i] = j;
  10.         }
  11.     }
  12.     public int strStr(String haystack, String needle) {
  13.         if(needle.length() == 0) return 0;
  14.         int[] next = new int[needle.length()];
  15.         getNext(next, needle);
  16.  
  17.         int j = 0;
  18.         for(int i = 0; i < haystack.length(); i++){
  19.             while(j > 0 && needle.charAt(j) != haystack.charAt(i))
  20.                 j = next[j - 1];
  21.             if(needle.charAt(j) == haystack.charAt(i))
  22.                 j++;
  23.             if(j == needle.length())
  24.                 return i - needle.length() + 1;
  25.         }
  26.         return -1;
  27.     }
  28. }

双指针

1.移除元素

26.删除有序数组中的重复项

  1. class Solution {
  2.     public int removeDuplicates(int[] nums) {
  3.         int slow=0;
  4.         for(int fast=0;fast<nums.length;fast++){
  5.             if(fast!=0 && nums[fast]==nums[fast-1]){
  6.                 slow--;
  7.             }
  8.             nums[slow++]=nums[fast];
  9.         }
  10.         return slow;
  11.     }
  12. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/561216
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号