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

leetcode java数据结构算法整理（更新中）_leetcode java 常用算法

作者：羊村懒王 | 2024-02-20 01:36:51

赞

踩

leetcode java 常用算法

目录

github地址

1.链表反转

2.快速排序

3.归并排序

4.两数之和

5.两数相加

6.无重复字符的最长子串

7.三个数的乘积

8.二叉树的最小高度--->深度优先（栈）

递归没看懂的可以留言。

9.二叉树的最小高度--->广度优先算法（队列）

10.最长连续递增数列-->贪心算法

11.最长的回文子字符串

github地址

1.链表反转

2.快速排序

  1.     public static int[] quickSortFun(int[] arr, int low, int high) {
  2.  
  3.         if (low < high) {
  4.             int mid = qSort(arr, low, high);
  5.             quickSortFun(arr, low, mid - 1);
  6.             quickSortFun(arr, mid + 1, high);
  7.         }
  8.         return arr;
  9.     }
  10.  
  11.     private static int qSort(int[] arr, int low, int high) {
  12.         int prviod = arr[high];
  13.         int i = low - 1;
  14.         int j = high;
  15.         while (i < j) {
  16.             while (arr[++i] < prviod && i < j) ;
  17.             arr[j] = arr[i];
  18.             while (arr[--j] > prviod && i < j) ;arr[i] = arr[j];
  19.  
  20.         }
  21.         arr[i] = prviod;
  22.         return i;
  23.     }

执行顺序：

  1. 原数组：1，2，5，3，4，7，0
  2.  
  3. （1）以0作为基准数
  4.        0，（2，5，3，4，7，1）
  5. （2）以1为基准数
  6.       0，1，（5，3，4，7，2）
  7. （3）以2为基准数
  8.       0，1，2，（3，4，7，5）
  9. （4）以5为基准数
  10.       0，1，2，（3，4）5，（7）
  11. （5）以4为基准数，以7为基准数
  12.      0，1，2，3，4，5，7

3.归并排序

  1.  public static void main(String[] args) {
  2.  
  3.         int[] arr = {2, 1, 5, 3, 9, 4, 0};
  4.         System.out.println("初始数组：" + Arrays.toString(arr));
  5.  
  6.         mergeSort1(arr, 0, arr.length - 1);
  7.  
  8.         System.out.println("排序后数组：" + Arrays.toString(arr));
  9.     }
  10.  
  11.     private static void mergeSort1(int[] arr, int low, int high) {
  12.  
  13.         if (low >= high) return;
  14.         int mid = (high + low) / 2;
  15.         mergeSort1(arr, low, mid);
  16.         mergeSort1(arr, mid + 1, high);
  17.         merge(arr, low, mid, high);
  18.  
  19.     }
  20.  
  21.     private static void merge(int[] arr, int low, int mid, int high) {
  22.  
  23.         int[] ret = new int[high - low + 1];
  24.         int s1 = low;
  25.         int s2 = mid + 1;
  26.         int index = 0;
  27.         
  28.         while (s1 <= mid && s2 <= high) ret[index++] = arr[s1] < arr[s2] ? arr[s1++] : arr[s2++];
  29.         while (s2 <= high) ret[index++] = arr[s2++];
  30.         while (s1 <= mid) ret[index++] = arr[s1++];
  31.         for (int j = 0; j < ret.length; j++) arr[j + low] = ret[j];
  32.  
  33.     }

 

  1. 初始数组：[2, 1, 5, 3, 9, 4, 0]
  2. 排序后数组：[0, 1, 2, 3, 4, 5, 9]

4.两数之和

  1. public class LeetCode1_twoSum {
  2.  
  3.     /**
  4.      * 解体思路：
  5.      * 1.创建一个map
  6.      * 2.for循环遍历nums数组
  7.      * 3.用target减去nums[i]
  8.      * 以计算那个数能根当前的数字相加得到target
  9.      * 4.检查map里面有没有这个数，
  10.      * 如果有则返回结果
  11.      * 如果没有则把nums[i]当作key
  12.      * i作为value放入map中
  13.      */
  14.     public static void main(String[] args) {
  15.  
  16.         int[] nums = {2, 3, 11, 7};
  17.         Map<Integer, Integer> map = new HashMap<>();
  18.  
  19.         int target = 9;
  20.  
  21.         for (int i = 0; i < nums.length; i++) {
  22.             if (!map.containsKey(target - nums[i])) {
  23.                 map.put(nums[i], i);
  24.             } else {
  25.                 System.out.println("第" + map.get(target - nums[i]) + "个数,即" + (target - nums[i]) + "和" + nums[i] + "的结果是" + target);
  26.             }
  27.         }
  28.  
  29.     }
  30. }
第0个数,即2和7的结果是9

5.两数相加

  1. /**
  2.  * @Title: LinkedNode
  3.  * @Description: 链表节点类
  4.  */
  5. public class LinkedNode {
  6.  
  7.     public int data;
  8.     public LinkedNode next;
  9.  
  10.     //实例化
  11.     public LinkedNode(int data) {
  12.         this.data = data;
  13.     }
  14.  
  15.     @Override
  16.     public String toString() {
  17.         return "LinkedNode{" +
  18.                 "data=" + data +
  19.                 ", next=" + next +
  20.                 '}';
  21.     }
  22. }
  1.  
  2. /**
  3.  * @Title: SingleLinkedList
  4.  * @Description: 实例化链表
  5.  */
  6. public class SingleLinkedList {
  7.  
  8.     private LinkedNode head = new LinkedNode(0);
  9.  
  10.     //头节点
  11.     public LinkedNode getHead() {
  12.         return head;
  13.     }
  14.  
  15.     //添加节点
  16.     public void addLinkedNode(LinkedNode node) {
  17.         //因为head节点是不能动得，因此我们需要一个辅助节点 temp来遍历
  18.         LinkedNode temp = head;
  19.         while (temp.next != null) {
  20.             temp = temp.next;
  21.         }
  22.         temp.next = node;
  23.     }
  24.  
  25.     //显示列表
  26.     public void showLinkedList(LinkedNode head) {
  27.         if (head.next == null) {
  28.             System.out.println("链表为空");
  29.             return;
  30.         }
  31.         //因为头节点不能动，所以需要辅助变量来遍历
  32.         LinkedNode temp = head.next;
  33.         if (temp == null) {
  34.             System.out.println("空链表");
  35.             return;
  36.         }
  37.         ArrayList<Integer> integers = new ArrayList<>();
  38.         while (temp != null) {
  39.             integers.add(temp.data);
  40.             temp = temp.next;
  41.         }
  42.         //逆序输出
  43.         for (int i = integers.size() - 1; i >= 0; i--) {
  44.             System.out.print(integers.get(i));
  45.         }
  46.  
  47.  
  48.     }
  49.  
  50.     //修改链表节点数据
  51.     public void updateLinkedList(LinkedNode node) {
  52.         if (head.next == null) {
  53.             System.out.println("空链表");
  54.             return;
  55.         }
  56.  
  57.         LinkedNode temp = head.next;
  58.         boolean flag = false;
  59.  
  60.         while (true) {
  61.             if (temp.next == null) break;
  62.             if (temp.data == node.data) {
  63.                 flag = true;
  64.                 break;
  65.             }
  66.             temp = temp.next;
  67.         }
  68.         if (flag) {
  69.             temp.data = node.data;
  70.         } else {
  71.             System.out.println("没有找到该" + node.data);
  72.         }
  73.     }
  74.  
  75.  
  76.  
  77. }
  1. public class LeetCode2_AddTwoNumbers {
  2.  
  3.     /**
  4.      * 给出两个非空的链表用来表示两个非负的整数，其中他们各自的位数是按照逆序的方式存储，并且它们的每个节点只能存储一位数字
  5.      * 如果我们将这两个数相加起来，则会返回一个新的链表来表示他们的和
  6.      * 例如：（2->4->3）+(5->6->7->1)=(7->0->1->2)
  7.      * 原因：342+465=807
  8.      */
  9.     public static void main(String[] args) {
  10.  
  11.         /**
  12.          * 初始化两个链表
  13.          */
  14.         SingleLinkedList l1 = new SingleLinkedList();
  15.  
  16.         l1.addLinkedNode(new LinkedNode(8));
  17.  
  18.  
  19.         SingleLinkedList l2 = new SingleLinkedList();
  20.  
  21.         l2.addLinkedNode(new LinkedNode(2));
  22.         l2.addLinkedNode(new LinkedNode(0));
  23.         l2.addLinkedNode(new LinkedNode(1));
  24.  
  25.  
  26.         /**
  27.          * 结果写入到新的链表
  28.          */
  29.         SingleLinkedList dummy = new SingleLinkedList();
  30.         LinkedNode curr = dummy.getHead();
  31.  
  32.         LinkedNode node1 = l1.getHead().next;
  33.         LinkedNode node2 = l2.getHead().next;
  34.  
  35.  
  36.         int carry = 0;
  37.         while (node1 != null || node2 != null) {
  38.             int sum = 0;
  39.             if (node1 != null) {
  40.                 sum += node1.data;
  41.                 node1 = node1.next;
  42.             }
  43.             if (node2 != null) {
  44.                 sum += node2.data;
  45.                 node2 = node2.next;
  46.             }
  47.             sum += carry;
  48.             LinkedNode node = new LinkedNode(sum % 10);
  49.  
  50.             curr.next = node;
  51.             carry = sum / 10;
  52.             curr = curr.next;
  53.  
  54.         }
  55.  
  56.         if(carry>0){
  57.             curr.next=new LinkedNode(carry);
  58.         }
  59.         dummy.showLinkedList(dummy.getHead());
  60.  
  61.  
  62.     }
  63.  
  64.  
  65. }

结果展示：

  1.  
  2. 110
  3. Process finished with exit code 0

6.无重复字符的最长子串

  1. /**
  2.  * @Title: LeetCode3_LongestSubstringWithoutRepeatingCharacters
  3.  * @Description: 无重复字符的最长子串--->滑动窗口
  5.  */
  6. public class LeetCode3_LongestSubstringWithoutRepeatingCharacters {
  7.     public static void main(String[] args) {
  8.         String word = "abcabcdb";
  9.         char[] chars = word.toCharArray();
  10.         List<Character> list = new ArrayList<>();
  11.  
  12.         int maxLength = 0, j = 0;
  13.  
  14.         for (int i = 0; i < chars.length; i++) {
  15.             if (!list.contains(chars[i])) {
  16.                 list.add(chars[i]);
  17.                 maxLength = Math.max(maxLength, list.size());
  18.             } else {
  19.                 while (list.contains(chars[i])) {
  20.  
  21.                     list.remove(new Character(chars[j]));
  22.                     j++;
  23.                 }
  24.                 list.add(chars[i]);
  25.             }
  26.  
  27.  
  28.         }
  29.  
  30.  
  31.         System.out.println(maxLength);
  32.     }
  33.  
  34. }

输出结果：

  1. 4
  2.  
  3. Process finished with exit code 0

7.三个数的乘积

  1. /**
  2.  * @Title: LeetCode4_ThreeNumberMultiply
  3.  * @Description: 三个数的乘积：整型数组nums，在数组中找出三个数组组成的最大乘积，并输出这个乘积
  4.  * 1.数组中全部为正数，选出最大的三个正数
  5.  * 2.数组中全部为负数，选出最大的三个负数
  6.  * 3.数组中有正有负，选出两个最小的负数乘上最大的正数，如果只有一个负数就回到 1 的情况中了
  7.  * <p>
  8.  * 综上所属：就只需要考虑两种情况（1）找出三个最大的数，求乘积
  9.  * （2）找出两个最小的数和一个最大的数，求乘积
  10.  * 判断上面两种情况那个结果最大
  11.  */
  12. public class LeetCode4_ThreeNumberMultiply {
  13.  
  14.     public static void main(String[] args) {
  15.  
  16.         int[] nums = {-1, -2, 3, 4, 6, -7};
  17.  
  18.         System.out.println(sort(nums));
  19.         System.out.println(getMaxMin(nums));
  20.  
  21.  
  22.     }
  23.  
  24.     //解法1：先进行排序找出最大的数
  25.     public static int sort(int[] nums) {
  26.         Arrays.sort(nums);//内部使用的是快排，时间复杂度是  NlogN
  27.         int n = nums.length;
  28.  
  29.         return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 1] * nums[n - 2] * nums[n - 3]);
  30.     }
  31.  
  32.     //解法2：线性扫描
  33.     public static int getMaxMin(int[] nums) {
  34.         int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
  35.         int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
  36.  
  37.         for (int x : nums) {
  38.             //找出最小的两个数
  39.             if (x < min1) {
  40.                 min2 = min1;
  41.                 min1 = x;
  42.             } else if (x < min2) {
  43.                 min2 = x;
  44.             }
  45.  
  46.             //找出最大的三个数
  47.             if (x > max1) {
  48.                 max3 = max2;
  49.                 max2 = max1;
  50.                 max1 = x;
  51.             } else if (x > max2) {
  52.                 max3 = max2;
  53.                 max2 = x;
  54.             } else if (x > max3) {
  55.                 max3 = x;
  56.             }
  57.  
  58.         }
  59.  
  60.         return Math.max(min1 * min2 * max1, max1 * max2 * max3);
  61.     }
  62. }

结果展示：

  1. 84
  2. 84
  3.  
  4. Process finished with exit code 0

8.二叉树的最小高度--->深度优先（栈）

  1.  
  2. /**
  3.  * @Title: LeetCode6_LongestPalidromicSubstring
  4.  * @Description: 二叉树的最小深度：深度优先算法
  5.  * 二叉树逻辑结构：
  6.  *          1
  7.  *      2      3
  8.  *   4   5   6
  9.  *          7
  10.  */
  11. public class LeetCode6_BiTreeMinDepth {
  12.  
  13.     public static void main(String[] args) {
  14.         //构建一颗二叉树
  15.         TreeNode node7 = new TreeNode(7, null, null);
  16.         TreeNode node6 = new TreeNode(6, node7, null);
  17.         TreeNode node5 = new TreeNode(5, null, null);
  18.         TreeNode node4 = new TreeNode(4, null, null);
  19.         TreeNode node3 = new TreeNode(3, node6, null);
  20.         TreeNode node2 = new TreeNode(2, node4, node5);
  21.         TreeNode node1 = new TreeNode(1, node2, node3);
  22.  
  23.         System.out.println(minDepth(node1));
  24.  
  25.     }
  26.  
  27.     public static int minDepth(TreeNode root) {
  28.         //首先判断树是否为空
  29.         if (root == null) {
  30.             System.out.println("二叉树为空");
  31.             return 0;
  32.         }
  33.  
  34.         //此为叶子节点
  35.         if (root.left == null && root.right == null) {
  36.             return 1;
  37.         }
  38.         int min = Integer.MAX_VALUE;
  39.         if (root.left != null) {
  40.             min = Math.min(minDepth(root.left), min);
  41.         }
  42.         if (root.right != null) {
  43.             min = Math.min(minDepth(root.right), min);
  44.         }
  45.         return min + 1;
  46.     }
  47.  
  48.     //二叉树的静态内部类
  49.     static class TreeNode {
  50.         int val;
  51.         TreeNode left;
  52.         TreeNode right;
  53.  
  54.         TreeNode(int val, TreeNode left, TreeNode right) {
  55.             this.val = val;
  56.             this.left = left;
  57.             this.right = right;
  58.         }
  59.     }
  60.  
  61. }

递归没看懂的可以留言。

9.二叉树的最小高度--->广度优先算法（队列）

  1.  
  2. /**
  3.  * @Title: LeetCode7_BiTreeMinDepthBreadth
  4.  * @Description: 二叉树的最小深度：广度优先  时间复杂度：O（n）  空间复杂度：O（n）
  5.  * 二叉树逻辑结构：
  6.  *          1
  7.  *      2      3
  8.  *   4   5   6
  9.  *          7
  10.  */
  11. public class LeetCode7_BiTreeMinDepthBreadth {
  12.     public static void main(String[] args) {
  13.         //构建一颗二叉树
  14.         TreeNode node7 = new TreeNode(7, null, null);
  15.         TreeNode node6 = new TreeNode(6, node7, null);
  16.         TreeNode node5 = new TreeNode(5, null, null);
  17.         TreeNode node4 = new TreeNode(4, null, null);
  18.         TreeNode node3 = new TreeNode(3, node6, null);
  19.         TreeNode node2 = new TreeNode(2, node4, node5);
  20.         TreeNode node1 = new TreeNode(1, node2, node3);
  21.  
  22.         System.out.println(minDepth(node1));
  23.     }
  24.  
  25.     public static int minDepth(TreeNode root) {
  26.  
  27.         if (root == null) {
  28.             return 0;
  29.         }
  30.         Queue<TreeNode> queue = new LinkedList();
  31.         root.deep = 1;
  32.         queue.offer(root);
  33.  
  34.         while (!queue.isEmpty()) {
  35.             TreeNode node = queue.poll();
  36.             if (node.left == null && node.right == null) {
  37.                 return node.deep;
  38.             }
  39.             if (node.left != null) {
  40.                 node.left.deep = node.deep + 1;
  41.                 queue.offer(node.left);
  42.             }
  43.  
  44.             if (node.right != null) {
  45.                 node.right.deep = node.deep + 1;
  46.                 queue.offer(node.right);
  47.             }
  48.         }
  49.         return 0;
  50.     }
  51.  
  52.     //二叉树的静态内部类
  53.     static class TreeNode {
  54.         int val;
  55.         TreeNode left;
  56.         TreeNode right;
  57.         int deep;
  58.  
  59.         TreeNode(int val, TreeNode left, TreeNode right) {
  60.             this.val = val;
  61.             this.left = left;
  62.             this.right = right;
  63.         }
  64.     }
  65. }

10.最长连续递增数列-->贪心算法

  1.  
  2. /**
  3.  * @Title: LeetCode8_LongestContinuousIncreasingSequence
  4.  * @Description: 给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回其长度--->贪心算法
  5.  * 从数组的下标为0的位置开始，
  6.  * 依次往后数当后一个数（i）大于等于前一个数(j)的时候将开始位置变为i，
  7.  * 将走过的长度记录到max中
  8.  * 最后返回max
  9.  */
  10. public class LeetCode8_LongestContinuousIncreasingSequence {
  11.  
  12.     public static void main(String[] args) {
  13.         int length = findLength(new int[]{1, 2, 3, 2, 3, 4, 3, 4, 5, 6});
  14.         System.out.println(length);
  15.     }
  16.  
  17.     private static int findLength(int[] ints) {
  18.  
  19.         int start = 0, max = 0;
  20.  
  21.         for (int i = 1; i < ints.length; i++) {
  22.             if (ints[i] <= ints[i - 1]) {
  23.                 start = i;
  24.             }
  25.             max = Math.max(max, i - start + 1);
  26.         }
  27.  
  28.         return max;
  29.     }
  30.  
  31. }

11.最长的回文子字符串

  1.  
  2. /**
  3.  * @Title: LeetCode5_LongestPalidromicSubstring
  4.  * @Description: 最长的回文子字符串
  5.  * 解题思路：
  6.  * 1.如果字符串长度小于2，直接返回源字符串
  7.  * 2.定义两个变量，一个start存储当前找到的最大回文字符串的起始位置，另一个maxLength记录字符串的长度（终止位置就是start+maxLength）
  8.  * 3.创建一个helper function，判断左边和右边是否越界，同时最左边的字符是否等于最右边的字符。
  9.  * 如果以上三个条件都满足，则判断是否需要更新回文字符串的最大长度及最大字符串的起始位置。然后将left--，right++继续判断，直到不满足三个条件为止
  10.  * 4.遍历字符串，每个位置调用helper function 两遍，第一遍检查i-1，i+1，第二遍检查i ，i+1
  11.  *
  12.  * 时间复杂度为O(n^2)
  13.  */
  14. public class LeetCode5_LongestPalidromicSubstring {
  15.  
  16.     public static void main(String[] args) {
  17.  
  18.         System.out.println(getPalidromicSubstring("abcbc"));
  19.  
  20.     }
  21.  
  22.     public static String getPalidromicSubstring(String str) {
  23.  
  24.         if (str.length() < 2) {
  25.             return str;
  26.         }
  27.         int start = 0;
  28.         int maxLength = 1;
  29.  
  30.  
  31.         for (int i = 0; i < str.length(); i++) {
  32.  
  33.             int left = i;
  34.             int right = i + 1;
  35.             while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
  36.  
  37.                 if (right - left + 1 > maxLength) {
  38.                     maxLength = right - left + 1;
  39.                     start = left;
  40.                 }
  41.                 left--;
  42.                 right++;
  43.             }
  44.         }
  45.  
  46.         for (int i = 0; i < str.length(); i++) {
  47.             int left = i - 1;
  48.             int right = i + 1;
  49.             while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
  50.  
  51.                 if (right - left + 1 > maxLength) {
  52.                     maxLength = right - left + 1;
  53.                     start = left;
  54.                 }
  55.                 left--;
  56.                 right++;
  57.             }
  58.         }
  59.         return str.substring(start, start + maxLength);
  60.     }
  61.  
  62. }

 

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

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

  

闽ICP备14008679号