Leedcode Top 100

Questions:

sliding window & hashtable
Commonly used tables are:
- int[26] for Letters ‘a’ - ‘z’ or ‘A’ - ‘Z’
- int[128] for ASCII
- int[256] for Extended ASCII

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128]; // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            i = Math.max(index[s.charAt(j)], i);
            ans = Math.max(ans, j - i + 1);
            index[s.charAt(j)] = j + 1;
        }
        return ans;
    }
}

2. 位运算判断奇偶数

考虑复数
问input有什么情况 考虑coding style 和精简

i%2==1是平时判断奇数的常用方法，这个方法有个弊端就是当i为负数的时候，判断结果是错误的，因为在java中，%运算的结果和左操作数具有相同的符号。

改进的方法有两种

i%2!=0,这样即使是负的奇数也可以正确的判断
i&1!=0,奇数的最后一位总是1，这样和1的二进制格式向AND，结果一定是1，而正负位都被1二进制格式中的0 给AND掉了。在书中这是个推荐的方法

贪婪算法：The problem to find maximum (or minimum) element (or sum) with a single array as the input is a good candidate to be solved by the greedy approach in linear time
leetcode 53.最大子序和题目描述：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
O(n)解法
从动态规划角度来思考问题，我们假设Fin是最大子序列和，i表示起点下标，n表示终点下标。那么，要么是前（n-1项+n项）和最大，要么是第n项最大，即有
F(n) = Max(F(n-1)+F(n), F(n))
那么，如果是F(n-1)+F(n)较大，则有：F(n-1)+F(n) > F(n)，等价于：F(n-1) > 0，所以得出解法如下：
```
public maxSubArray = function(nums) {
 let sum = nums[0]
 let max = nums[0]
 for (let i=1; i<nums.length; ++i) {
     sum = sum > 0 ? sum + nums[i] : nums[i]
     if (sum > max) {
         max = sum
     }
 }
 return max
}
```
Leetcode 121.买卖股票的最佳时机题目描述：给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。
输入: [7, 6, 4, 3, 1]
输出: 0
在这种情况下, 没有交易完成, 即最大利润为 0。
动态规划（最优）思路：
始终保存最小的买入价格（遇见更小时更新minPrice）
始终保存最大的利润（向前遍历到的卖出价格-当前minPrice，如果利润增加则保存该利润值）
比如数据2,7,1.3
首先找到最小买入是2，然后做差7-2=5，保存利润，然后到最小买入变成1，此时利润还是5，然后还是3
如果1后面出现的数字足够大，大到和1做差的值大于5，那么最大利润值就改变，否则，最大利润还是5。后面的数如果减1的差肯定比减2的差要更大。
重点minPrice和maxProfit并不是在某一条件下同时更新的；更新minPrice的逻辑是，对于未来会遇到的卖出价格，当下更低的买入价格只会让利润不变或增加。
另外一点值得看看两种代码的差别：
```
for (int price : prices) {
 minPrice = Math.min(minPrice, price);
 maxProf = Math.max(maxProf, price - minPrice);
}
```
```
 for (int i = 0; i < prices.length; i++) {
 if (prices[i] < minprice)
     minprice = prices[i];
  else if (prices[i] - minprice > maxprofit)
     maxprofit = prices[i] - minprice;
 }
```
Leetcode 146.LRU缓存机制
题目描述：运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作？

可以用hashmap和doublylinkedlist来解决
符合条件的现有结构是LinkedHashMap
题目中的顺序‘最少使用’说明改写会改变顺序

LinkedHashMap 两种顺序：access-order & insertion-order，本题需要前者
与hashmap的不同在于，本结构用链表储存了所有的entries
This technique is particularly useful if a module takes a map on input, copies it, and later returns results whose order is determined by that of the copy.

public LinkedHashMap (int initialCapacity,
                      float loadFactor,
                     boolean accessOrder)

accessOrder: true for access-order, false for insertion-order
default initial capacity (16) and load factor (0.75)，
default order is insertion-order

本题需要设定所有的param，为了设定到第三个是true，前面的可以手动输入成默认值：16和0.75f

注意改写removeEldestEntry这个方法

protected boolean removeEldestEntry(Map.Entry<K,V> eldest)

@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
  return size() > LRUCache.this.capacity;
}

getOrDefault方法可以设定-1为默认值，再key不存在的情况下返回

class LRUCache extends LinkedHashMap<Integer, Integer>{
  private int capacity;
    
  public LRUCache(int capacity) {
      super(capacity, 0.75F, true);
      this.capacity = capacity;
  }

  public int get(int key) {
      return super.getOrDefault(key, -1);
  }

  public void put(int key, int value) {
      super.put(key, value);
  }

  @Override
  protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
      return size() > capacity; 
  }
}

Leetcode 5.最长回文子串题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
思路：中心扩展法
Leetcode 202. happynumber “快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
两个思考点：
- 给定int n，下一个数字是什么？
- 如果无限循环，如何检测到并退出？

HashSet
记录每次对一个数进行平方操作后的数，记录一次判断一次这个数是否出现过，或者是否为1，
如果出现过说明不是快乐数，如果为1则说明是快乐数。
set.contains(num) == true说明该数出现过，可以跳出循环。

public boolean isHappy(int n) {
    Set<Integer> seen = new HashSet<>();
    while (n != 1 && !seen.contains(n)) {
        seen.add(n);
        n = getNext(n);
    }
    return n == 1;
}

hardcoded recursion
当n小于10时，不只有n=1，还有n=7也满足。加入这个特例就可以使用recursion

LeetCode.937 重新排序日志数组(Reorder Log Files)
你有一系列日志。每个日志都是以空格分隔的单词串。每个日志中的第一个单词是标识符，由字母数字组成。字母日志，标识符后面的每个单词只包含小写字母。数字日志，标识符后面的每个单词只包含数字。每个日志在其标识符后至少有一个单词。重新排序日志，以便所有字母日志都在任何数字日志之前。字母日志按字典顺序排序，忽略标识符，在特定的情况下使用标识符。数字日志应按其原始顺序排列。返回日志数组的最终顺序。例如：

输入：[“a1 9 2 3 1”, “g1 act car”, “zo4 4 7”, “ab1 off key dog”, “a8 act zoo”]
输出：[“g1 act car”, “a8 act zoo”, “ab1 off key dog”, “a1 9 2 3 1”, “zo4 4 7”]
输入：[“a1 9 2 3 1”, “g1 act car”, “zo4 4 7”, “ab1 act car”, “a8 act car”]
输出：[“a8 act car”, “ab1 act car”, “g1 act car”, “a1 9 2 3 1”, “zo4 4 7”]
注意：

0 <= logs.length <= 100
3 <= logs [i] .length <= 100
logs[i]保证有标识符，标识符后面有一个单词。

力扣常见100题

Questions:

2. 位运算判断奇偶数

FEATURED TAGS