算法导论

  1. 字符串处理

    • 原地reverse字符串单测

  2. 数组

    • Find All Numbers Disappeared in an Array

      比较讨巧，因为题目限定了Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array)，所以可以通过原数组来记录某个数字是否出现，如果出现，将nums[i]设为nums[i]*-1，然后找到nums[i] 大于0的即可。

    • Find All Duplicates in an Array

      接上题Find All Numbers Disappeared in an Array，遍历两次，第一次找出没有出现过得，则出现过得数字对应下标变为负数，第二遍将出现过一次的数字对应的下标变为正数，剩下的负数表示出现两次的

    • First Missing Positive

      • 将nums[i] -1数字放入对应下标位置。如果nums[i]-1>=0&&nums[i]-1<nums.length&&nums[nums[i]-1]=nums[i]
      • 也可以通过将原数组改为负数的方式，同上两题。但是要注意有原数组有负数和0存在

    • Majority Element

      找到数组中出现次数大于一半的元素，可以通过计数的方式，相同的计数加1，不相同减一，记录count为零时的元素，最后一个即为出现次数超过一半的元素

  3. 树遍历

    • 树对称

  4. 链表

    • 链表反转

      遍历或者递归计算

  5. 二分搜索

    • Divide Two Integers

      不能用乘法、除法、取模操作进行除法操作。只能通过加分来操作。由于一个个加太慢，所以可以通过两倍两倍加来模拟乘法，类似二分

    • three sum问题

      在一个数组中找到三个数，和为0。类似一个数组中找到两个数相加为target，可以通过对数组排序后使用二分查找来查询。对于三个元素，可以先排序数组后，遍历数组过程中先指定一个元素i，然后通过二分查询在[i+1,n]中找到合为0-nums[i]的两个元素

    • four sum问题

      在three sum问题基础上，先确定一个元素，然后调用three sum找到特定和的三个元素即可

    • Trapping Rain Water

      蓄水池算法，左右两边找到柱子，中间的水是可以保留下来。有点像二分查询

  6. 贪心

    • Maximum Length of Pair Chain

      dp和贪心都可以，但是本题可以用贪心来解决

  7. 数组动态规划

    1. Climbing Stairs

      fibonacci数列 f(n) =f(n-1)+f(n-2)

    2. Min Cost Climbing Stairs

      在Climbing Stairs基础上增加了cost，问题分解为

      sum[i] 到达i节阶梯的花费，sum[i] = min(sum[i-1]+cost[i-1],sum[i-2]+cost[i-2])

    3. Continuous Subarray Sum

      求任意子数组的和是不是等于k的倍数

      一个比较巧妙的思路是每个和模k，如果出现一个数之前出现过，即中间的数和为k的倍数

    4. House Robber

      动态规划入门，sum[i]表示盗取i获得的最大钱数，sum[i] = max(sum[i-2]+c[i],sum[i-1])

    5. Partition to K Equal Sum Subsets

      从数组中找到和为特定值的子数组，貌似没什么特别好的方法，暴力枚举

    6. Counting Bits

      统计每个元素的二进制1个数，可以依赖之前的计算结果

      f(n) = k if n == 2^k

      f(n) = 1 + f(n-2^k) if 2^k<n<2^k+1

    7. Split Array Largest Sum

      分解为两道题目：

      • 给定一个数组int[]nums，份数m，最大值max，需要将数组nums切分为连续的最多m份，每一份的和<=max
      • Given a lower bound (left), an upper bound (right), an unknown bool array (B), and an API uses i as input and tells you whether B[i] is true. If we know there exists an index k, that B[i] is false when i < k, and B[i] is true when i >= k. What is the fastest way to find this k (the lower bound)?

      第一问通过贪心算法，不断累加数组，如果超过>max，之前的数组作为一段，并重新开始累加，最多形成m份数组

      第二问可以用二分查找方法找到k。

      组合这两个问题，原问题是找到一个数k，满足将原数组切分为m份，并且每一份的和<=k,使得k最小。由于k>=每一份数组的和，即max(nums)<=k<=sum(nums)。

    8. 最长有效子数组Longest Valid Parentheses

      动态规划：longest[i] 表示i为结尾的最长有效括号对

      如果s[i]==’(‘ 则忽略，如果s[i] == ‘)’ 并且s[i - longest[i-1] - 1] == ‘(‘ 则配对成功，长度加二，并且如果i - longest[i-1] - 2也是一个最长子串，则可以拼接成为新的最大子串

      if s[i] == ‘(‘ longest[i] = 0;

      if s[i] == ‘)’ && s[i - longest[i-1] - 1] == ‘(‘ then: longest[i] = longest[i-1] + 2 + longest[i-longest[i-1]-2]

    9. 丢鸡蛋问题

      100层楼，有两个鸡蛋。如果鸡蛋从第k层丢下去不碎，则[0, k-1]都不会碎。问最少丢多少次，才知道从k层下丢不碎，k+1层会碎

      保守策略：第一次从k层下丢，如果碎了，则从[0,k-1]一层层尝试，一共k次。如果不碎，第二次尝试k+k-1,如果碎了，则尝试[k+1,k+k-1]，一共k次。所以可以得到k+k-1+k-2+…. = 100，即(1+k)*2/k = 100，可以得到k=14次

      dp：这个是个dp问题，f(n,m)表示n层楼，m个鸡蛋，需要的次数。

      f(0,m) = 0

      f(n,1) = n

      f(n,m) 表示从i楼下降，如果碎了即f(i-1,m-1)，如果不碎，则结果为f(n-i,m) ，即

      f(n,m) = min(max(f(i-1,m-1),f(n-i,m)))+1 for i = 1 ~ n，+1表示从i楼的那一次尝试

    10. Longest Increasing Subsequence

      动态规划：dp[i]表示[i]的最长LIS

      dp[i] = max(1+dp[j]); for nums[j] > nums[i], j =[i+1,n]

    11. Largest Sum of Averages

      问题分解：dp[0][k] 表示[0-n]中选择k段可以获得的LSA，则

      dp[0][k] = max(dp[i][k-1]+avg(0,i)) for i = [1,n]

    12. Longest Palindromic Substring

      最大回文串：将数组变为奇数个元素。遍历数组，对于每一元素像两边扩展找回文，记录最长回文

    13. Split Array with Equal Sum

      求和问题一般都会用一个数组sum[i]记录[0,i]之间的元素和，那如果要求任意两段数据和为sum[i,j] = sum[i] - sum[j]。该题目的方法是找到i, j 使得 sum[0,i-1] = sum[i+1,j-1]，然后再在j右边找到k，是得sum[j+1,k-1] = sum[k+1,n-1]

  8. 图论

    邻接矩阵edge方法存储

    搜索算法：Dfs,bfs,Dijkstra算法

  9. ​