算法刷题笔记

算法刷题笔记，包括优化、递归思想和非递归思想、基数排序、桶排序：间接比较排序、刷算法的思路、leetcode等。

算法

• 优化
  • for循环对值的统计减少代码量
  • 函数对参数变量的统计减少代码量
• 递归思想和非递归思想
  • 递归和非递归都具有图灵完备性，所以一个问题可以用递归解决那一定可以用非递归，只是实现的难度不一样
  • 递归优点：代码简洁，容易理解和维护
  • • 递归缺点：函数调用会拖慢程序
  • 本质是函数执行流程
• 基数排序
  • 把比较的数拆分成个十百千位多次排序
• 桶排序：间接比较排序
  • 主要是通过间接比较数组的序号来排序，不能说没有比较
• 刷算法的思路
  • 难算法是由许多小算法组成的，只要将大部分小算法搞得非常熟练，大算法自然写的快，所以小算法要精炼效率高执行时间短
  • 先看答案再刷题
• leetcode
  • 两数之和
    • 定一移一
      • 循环嵌套方式：o n2
      • 循环记录方式：o n 牺牲存储空间换取时间效率，把java数组看成字典
        • 查是否有它对应的数，有则打印，然后必须都记录在数组字典中
      • 第一种丢弃了之前努力的结果，第二种方式没有浪费之前的点滴努力，还牺牲了空间
    • 实现
      • 哈希表
        • 正负数组
        • 存取
      • public class LeetCode { public static void main(String[] args) { // 目标数组 int [] array = new int[]{2, 1, 7, 11, 19}; int target = 9; // 哈希表 Hash hash = new Hash(); for(int i = 0; i < array.length; i++){ int other = 9 - array[i]; if (hash.get(other)!=0){ System.out.println(array[i]); System.out.println(hash.get(other)); } else { hash.put(array[i]); } } } } class Hash{ int [] positive_array = new int[20]; int [] negative_array = new int[20]; void put(int num){ if(num<0){ negative_array[-num] = num; } else { positive_array[num] = num; } } public int get(int num){ if(num<0){ return negative_array[-num]; } else { return positive_array[num]; } } }
  • 两数相加
    • 代码实现
      • public class LeetCode { public static void main(String[] args) { // 03 + 45 ListNode list_node1 = new ListNode(0); list_node1.next_node = new ListNode(3); ListNode list_node2 = new ListNode(4); list_node2.next_node = new ListNode(5); ListNode p1 = list_node1; ListNode p2 = list_node2; ListNode result = new ListNode(0); int carry = 0; while (p1 != null || p2 != null) { if (p1 == null) { result.next_node = new ListNode((carry + p2.val) % 10); carry = (carry + p2.val) / 10; } else if (p2 == null) { result.next_node = new ListNode((carry + p1.val) % 10); carry = (carry + p1.val) / 10; } else { result.next_node = new ListNode((carry + p1.val + p2.val) % 10); carry = (carry + p1.val + p2.val) / 10; } System.out.println(result.next_node.val); p1 = p1.next_node; p2 = p2.next_node; result = result.next_node; } } } class ListNode { int val; ListNode next_node; ListNode(int val) { this.val = val; } }