日常学习算法总结

一、基本数据结构之数组

自定义数组（类似ArrayList），数组必须存在在连续的地址空间，实现数组的增删操作。

public class CustomArray { private int[] array; // 元素个数 private int size; private static final String TAG = "CustomArray"; public CustomArray(int capacity) { array = new int[capacity]; size = 0; } public void insert(int index, int element) { // 判断下标是否合法 if (index < 0 || index > size) { throw new ArrayIndexOutOfBoundsException("数组越界，超出已有元素范围"); } // 如果实际元素个数达到数组容量的上限，则进行扩容 if (size >= array.length) { LogUtils.d(TAG, "我扩容了"); expansionArray(); } // 数组在内存中占有连续的内存空间，数组插入一个元素，插入位置后面的元素需要依次像后移动一位 /*for (int i = size - 1; i >= index; i--) { array[i + 1] = array[i]; }*/ if (size - 1 - index >= 0) System.arraycopy(array, index, array, index + 1, size - 1 - index); array[index] = element; size++; } public int delete(int index) { if (index < 0 || index >= size) { throw new ArrayIndexOutOfBoundsException("数组越界，超出已有元素范围"); } int delElement = array[index]; // 需要将元素向前移动一位 /*for (int i = index; i < size - 1; i++) { array[i] = array[i + 1]; }*/ // 下面这种方式其实是牺牲空间复杂度来提升时间复杂度 if (size - 1 - index >= 0) System.arraycopy(array, index + 1, array, index, size - 1 - index); size--; return delElement; } public int get(int index) { if (index < 0 || index >= size) { throw new ArrayIndexOutOfBoundsException("数组越界，超出已有元素范围"); } return array[index]; } public void set(int index, int element) { if (index < 0 || index >= size) { throw new ArrayIndexOutOfBoundsException("数组越界，超出已有元素范围"); } array[index] = element; } private void expansionArray() { // 进行两倍扩容 int[] newArray = new int[array.length * 2]; System.arraycopy(array, 0, newArray, 0, array.length); array = newArray; } public void outArray() { if (array == null) { return; } for (int element : array) { LogUtils.d(TAG, "数组元素:" + element); } } public int[] getArray() { return array; } public int getSize() { return size; } }

二、基本数据结构之链表

自定义链表（类似LinkedList），实现增删操作

2.1、定义节点类

public class Node { public int data; public Node next; public Node() { } public Node(int data) { this.data = data; } }

2.2、实现链表

public class CustomLinkedList { // 头结点指针 private Node head; // 尾节点指针 private Node last; // 链表长度 private int size; public void insert(int index, int element) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("链表越界，超出链表实际范围"); } Node insertNode = new Node(element); if (size == 0) { // 链表长度为0，空链表 head = insertNode; last = insertNode; } else if (index == 0) { // 插入头部 insertNode.next = head; head = insertNode; } else if (index == size) { // 插入尾部 last.next = insertNode; last = insertNode; } else { // 插入中间 // 获取前一个节点 Node preNode = get(index - 1); Node nextNode = preNode.next; preNode.next = insertNode; insertNode.next = nextNode; } size++; } public Node remove(int index) { if (index < 0 || index >= size) { throw new ArrayIndexOutOfBoundsException("链表越界，超出链表实际范围"); } Node removeNode = null; if (index == 0) { // 删除头部 removeNode = head; head = head.next; } else if (index == size - 1) { // 删除尾节点 Node preNode = get(index - 1); removeNode = preNode.next; preNode.next = null; last = preNode; } else { // 删除中间节点 Node preNode = get(index - 1); Node nextNode = preNode.next.next; removeNode = preNode.next; preNode.next = nextNode; } size--; return removeNode; } /** * 查询 * * @param index * @return */ public Node get(int index) { if (index < 0 || index >= size) { throw new ArrayIndexOutOfBoundsException("链表越界，超出链表实际范围"); } Node tempNode = head; for (int i = 0; i < index; i++) { tempNode = tempNode.next; } return tempNode; } public String outPut() { StringBuilder builder = new StringBuilder(); Node tempNode = head; while (tempNode != null) { builder.append(tempNode.data).append(" "); tempNode = tempNode.next; } return builder.toString(); } public Node getNode() { return head; } public String outNode(Node node) { StringBuilder builder = new StringBuilder(); Node tempNode = node; while (tempNode != null) { builder.append(tempNode.data).append(" "); tempNode = tempNode.next; } return builder.toString(); } }

三、反转链表

刚好利用上诉我们自定义的链表实现链表反转

/** * 反转链表 * @param node * @return */ public Node reverseLinkedList(Node node) { // 当前节点，将传递进来的头结点赋值给当前节点 Node curNode = node; // 下一个节点 Node nextNode; // 前一个节点 Node preNode = null; while (curNode != null) { // 取出当前节点的下一个节点赋值给我们定义好的nextNode nextNode = curNode.next; // 将当前节点指向前一个节点实现反转 curNode.next = preNode; // 将当前节点赋值给前一节点 preNode = curNode; // 移动当前节点到下一个节点 curNode = nextNode; } return preNode; }

调用：

val cusLinkedList = CustomLinkedList() cusLinkedList.insert(0, 0) cusLinkedList.insert(1, 1) cusLinkedList.insert(2, 2) cusLinkedList.insert(3, 3) cusLinkedList.insert(4, 4) cusLinkedList.insert(5, 5) cusLinkedList.insert(6, 6) cusLinkedList.insert(7, 7) cusLinkedList.insert(8, 8) val node = reverseLinkedList(cusLinkedList.node) val nodeStr = cusLinkedList.outNode(node) LogUtils.d(TAG, "反转链表: $nodeStr")

结果：

TestAlgorithmFragment==>: 反转链表: 8 7 6 5 4 3 2 1 0

四、获取数组中出现次数最多的元素

4.1、双层for循环

/** * 获取数组中出现最多的元素和次数 * * @param arr * @return */ public int getArrayMostFrequent(int[] arr) { int mostElement = 0; int tempCount = 0; int timeCount = 0; for (int i = 0; i < arr.length; i++) { tempCount = 0; for (int j = 0; j < arr.length; j++) { if (arr[i] == arr[j]) { tempCount++; } } if (tempCount > timeCount) { timeCount = tempCount; mostElement = arr[i]; } } LogUtils.d(TAG, "出现次数最多的元素: " + mostElement + "==>次数: " + timeCount); return timeCount; }

4.2、利用map集合，将当前元素作为key，出现次数作为value，然后遍历map集合，value值最大的元素就是出现次数最多的元素

/** * 获取数组中出现最多的元素和次数 * 使用map优化 * * @param arr * @return */ public int getArrayMostFrequentForMap(int[] arr) { Map<Integer, Integer> map = new HashMap<>(); int mostElement = 0; int count = 0; int timeCount = 0; for (int i = 0; i < arr.length; i++) { if (map.containsKey(arr[i])) { map.put(arr[i], map.get(arr[i]) + 1); } else { map.put(arr[i], 1); } } for (Integer key : map.keySet()) { if (map.get(key) > timeCount) { timeCount = map.get(key); mostElement = key; } count++; } LogUtils.d(TAG + "使用Map优化", "出现次数最多的元素: " + mostElement + "==>最多元素次数: " + timeCount + "元素合并之后遍历次数: " + count); return timeCount; }

五、有效的字母异位词（leetcode第242题）

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例1：

输入: s = “anagram”, t = “nagaram” 输出: true

示例2：

输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母。

思路：就是统计两个字母字符串中拥有的字母个数是否相同 1.可以利用两个长度都为 26 的字符数组来统计每个字符串中小写字母出现的次数，然后再对比是否相等； 2.可以只利用一个长度为 26 的字符数组，将出现在字符串 s 里的字符个数加 1，而出现在字符串 t 里的字符个数减 1，最后判断每个小写字母的个数是否都为 0。

解题：

private boolean isAnagram(String s, String t) { // 第一种方式 /*if (s.length() != t.length()) { return false; } int[] arr1 = new int[26]; int[] arr2 = new int[26]; for (int i = 0; i < s.length(); i++) { arr1[s.charAt(i) - 'a']++; arr2[t.charAt(i) - 'a']++; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true;*/ // 第二种方式 if (s.length() != t.length()) { return false; } int[] arr = new int[26]; for (int i = 0; i < s.length(); i++) { arr[s.charAt(i) - 'a']++; arr[t.charAt(i) - 'a']--; } for (int count : arr) { if (count != 0) { return false; } } return true; /*if (s.length() != t.length()) { return false; } int[] arr = new int[26]; for (int i = 0; i < s.length(); i++) { arr[s.charAt(i) - 'a']++; } for (int i = 0; i < t.length(); i++) { arr[t.charAt(i) - 'a']--; if (arr[t.charAt(i) - 'a'] < 0) { return false; } } return true;*/ // 使用Java自带的高级函数 /*if (s.length() != t.length()) { return false; } Map<Character, Integer> table = new HashMap<Character, Integer>(); for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); table.put(ch, table.getOrDefault(ch, 0) + 1); } for (int i = 0; i < t.length(); i++) { char ch = t.charAt(i); table.put(ch, table.getOrDefault(ch, 0) - 1); if (table.get(ch) < 0) { return false; } } return true;*/ /*if (s.length() != t.length()) { return false; } char[] str1 = s.toCharArray(); char[] str2 = t.toCharArray(); Arrays.sort(str1); Arrays.sort(str2); return Arrays.equals(str1, str2);*/ }

六、K 个一组翻转链表（leetcode 25题）

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例： 给你这个链表：1->2->3->4->5 当 k = 2 时，应当返回: 2->1->4->3->5 当 k = 3 时，应当返回: 3->2->1->4->5

说明： 你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

迭代法

/** * k个一组翻转链表 * 1、迭代法 * 2、递归 * @param head * @param k * @return */ public ListNode reverseKGroup(ListNode head, int k) { // 迭代 // 构建一个边界节点 ListNode virtualNode = new ListNode(0); virtualNode.next = head; // 头结点的前一个节点 ListNode pre = virtualNode; while (head != null) { // 构建尾节点 ListNode tail = pre; // 查看剩余部分长度是否大于等于 k for (int i = 0; i < k; i++) { tail = tail.next; if (tail == null) { return virtualNode.next; } } // 下一个k组的头结点 ListNode next = tail.next; // 翻转head -- tail之间的数据 ListNode[] reverseArr = reverse(head, tail); // 重新给头、尾赋值，将翻转之前的尾赋值给头，反之亦然 head = reverseArr[0]; tail = reverseArr[1]; // 把子链表重新接回原链表 pre.next = head; tail.next = next; pre = tail; head = tail.next; } return virtualNode.next; } private ListNode[] reverse(ListNode head, ListNode tail) { ListNode pre = tail.next; ListNode cur = head; ListNode next; while (pre != tail) { next = cur.next; cur.next = pre; pre = cur; cur = next; } return new ListNode[]{tail, head}; }

迭代法

public ListNode reverseKGroup1(ListNode head, int k) { // 迭代 // 构建一个边界节点 ListNode virtualNode = new ListNode(0); virtualNode.next = head; // 头结点的前一个节点 ListNode pre = virtualNode; // 构建尾节点 ListNode tail = virtualNode; while (tail.next != null) { // 找到尾节点 for (int i = 0; i < k && tail != null; i++) { tail = tail.next; } if (tail == null) { break; } // 每次循环都需要对当前节点和下一组的开始节点 ListNode cur = pre.next; ListNode next = tail.next; tail.next = null; // 将翻转之后的子链表重新连接到总的链表中 pre.next = reverse(cur); cur.next = next; // 移动pre节点和尾节点 pre = cur; tail = pre; } return virtualNode.next; } /** * 翻转链表 * @param head * @return */ private ListNode reverse(ListNode head) { ListNode cur = head; ListNode pre = null; ListNode next; while (cur != null) { next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; }

七、两两交换链表中的节点（leetcode 24题）

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例： 输入：head = [1,2,3,4] 输出：[2,1,4,3]

/** * 两两交换链表中的节点 * 1、迭代法 * 2、递归 * @param head * @return */ public ListNode swapPairs(ListNode head) { // 迭代 /*ListNode virtualNode = new ListNode(0); virtualNode.next = head; ListNode pre = virtualNode; // 两两交换至少要有两个才能进入交换逻辑 while (pre.next != null && pre.next.next != null) { // 赋值两个临时变量，代表交换的两个节点 ListNode one = pre.next; ListNode two = pre.next.next; // 节点交换 pre.next = two; one.next = two.next; two.next = one; pre = one; } return virtualNode.next;*/ // 递归 if (head == null || head.next == null) { return head; } ListNode next = head.next; head.next = swapPairs(next.next); next.next = head; return next; }

八、有效的括号（leetcode 20题）

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

示例 2：

输入：s = “()[]{}” 输出：true

代码编写：：

public boolean isValid(String s) { char[] chars = s.toCharArray(); if (chars.length == 0) return true; Map<Character, Character> map = new HashMap<>(); map.put(')', '('); map.put(']', '['); map.put('}', '{'); Stack<Character> stack = new Stack<>(); for (char aChar : chars) { if (!isContains(aChar)) { return false; } if (aChar == '(' || aChar == '[' || aChar == '{') { stack.push(aChar); } else if (!stack.empty() && map.get(aChar) == stack.peek()) { stack.pop(); } else { return false; } } return stack.empty(); } private boolean isContains(char c) { List<Character> list = new ArrayList<>(); list.add('('); list.add(')'); list.add('['); list.add(']'); list.add('{'); list.add('}'); return list.contains(c); }

简单优化之后：

/** * 括号的有效性 * * @param s * @return */ public boolean isValid(String s) { char[] chars = s.toCharArray(); if (chars.length == 0) return true; if (chars.length % 2 != 0) return false; /*Map<Character, Character> map = new HashMap<>(); map.put(')', '('); map.put(']', '['); map.put('}', '{');*/ Stack<Character> stack = new Stack<>(); for (char aChar : chars) { if (!isContains(aChar)) { return false; } if (aChar == '(' || aChar == '[' || aChar == '{') { stack.push(aChar); } else if (!stack.empty() && getBracket(aChar) == stack.peek() /*map.get(aChar) == stack.peek()*/) { stack.pop(); } else { return false; } } return stack.empty(); } private char getBracket(char bracket) { if (bracket == ')') { return '('; } else if (bracket == ']') { return '['; } else if (bracket == '}') { return '{'; } else { return ' '; } } private boolean isContains(char c) { return c == '(' || c == ')' || c == '[' || c == ']' || c == '{' || c == '}'; }