每日一念
改掉自己想到哪写哪的坏习惯
哈希表
两数之和
class Solution {
/**
返回值是索引i
hashmap存储为nums[i] - i
res存 nums[i]的i,找target - nums[i] 对应的索引j
返回[i, j]
*/
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
int[] res = new int[2];
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])) {
res[0] = i;
res[1] = map.get(target - nums[i]);
}
map.put(nums[i], i);
}
return res;
}
}
字母的异位词分组
class Solution {
/**
排序后的str作为hashmap的key值,value存放这个key对应的异位词字母
最后取出map中所有values就是最后结果
*/
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> map = new HashMap();
for(String str: strs) {
char[] ch = str.toCharArray();
Arrays.sort(ch);
String key = new String(ch);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
最长连续序列
贪心解题有样例过不去
双指针
移动零
class Solution {
/**
fast, slow = 0
fast一路往后走
fast位置元素值不为0,把值给slow,slow ++
剩余的置0
*/
public void moveZeroes(int[] nums) {
int slow = 0;
int fast = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
for(int i = slow; i < nums.length; i++) {
nums[i] = 0;
}
}
}
盛最多水的容器
暴力解法,超时
三数之和
class Solution {
/**
三指针法
i
left i + 1 ;++
right nums.length - 1;--
去重:nums[i] == nums[i - 1] continue
同理去重 left、right
nums[i] + nums[left] + nums[right]
> 0 right--
< 0 left++
== 0 加入结果集
需要注意去重
*/
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList();
for(int i = 0; i < nums.length - 2; i++) {
if(i >= 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while(left < right) {
if(nums[i] + nums[left] + nums[right] == 0) {
// List<Integer> path = new ArrayList();
// path.add(nums[i]);
// path.add(nums[left]);
// path.add(nums[right]);
// if(!res.contains(path)) {
// res.add(path);
// }
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
while(left < right && nums[left + 1] == nums[left]) {
left++;
}
while(left < right && nums[right - 1] == nums[right]) {
right--;
}
left++;
right--;
}
else if(nums[i] + nums[left] + nums[right] > 0) {
right--;
}
else {
left++;
}
}
}
return res;
}
}
合并K个升序链表朴素写法
class Solution {
/**
结果链表res
将每个结点存到list链表中
[[1], [1], [2]]
取值最小的结点copy到下一个 node = node.next
while(not empty)
minIndex = 0
for遍历后面的结点
比minIndex值还小,设置为res.next,list更新为next
*/
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null) {
return null;
}
List<ListNode> list = new ArrayList();
for(ListNode node: lists) {
if(node != null) {
list.add(node);
}
}
if(list == null) {
return null;
}
ListNode res = new ListNode(-1);
ListNode cur = res;
while(!list.isEmpty()) {
int minIndex = 0;
for(int i = 1; i < list.size(); i++) {
if(list.get(i).val < list.get(minIndex).val) {
minIndex = i; // 找到最小val
}
}
cur.next = list.get(minIndex); //复制给res链表
cur = cur.next;
if(list.get(minIndex) == null) {
list.remove(minIndex);
}
else {
ListNode nodeNext = list.get(minIndex).next;
if(nodeNext == null) {
list.remove(minIndex);
}
else {
list.set(minIndex, nodeNext);
}
}
}
return res.next;
}
}
滑动窗口
无重复字符的最长子串
class Solution {
/**
滑动窗口法
i从头扫到尾
hashmap刷新最新出现的字符的位置 a - 0
i - get(a) + 1
比较并更新maxlen
*/
public int lengthOfLongestSubstring(String s) {
int maxlen = 0;
int left = 0;
HashMap<Character, Integer> map = new HashMap();
for(int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if(map.containsKey(ch)) {
left = Math.max(left, map.get(ch) + 1);
}
maxlen = Math.max(maxlen, i - left + 1);
map.put(ch, i);
}
return maxlen;
}
}
字符串中所有字母异位词
class Solution {
/**
用26字母表进行匹配,记录p的26字母表为pCnt
当s的某个滑动窗口内(长度为p.length()),26字母表sCnt == pCnt 这里注意要用Arrays.equals
把结果保存在结果数组中,起始索引为 i - p.length() + 1
*/
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList();
int pLen = p.length();
int sLen = s.length();
if(pLen > sLen) {
return res;
}
int[] pCnt = new int[26];
int[] sCnt = new int[26];
for(int i = 0; i < pLen; i++) {
pCnt[p.charAt(i) - 'a']++;
sCnt[s.charAt(i) - 'a']++;
}
if(Arrays.equals(pCnt, sCnt)) {
res.add(0);
}
for(int i = pLen; i < sLen; i++) {
sCnt[s.charAt(i - pLen) - 'a']--; // 窗口往右移动1,删除i - p.length() (最前1)
sCnt[s.charAt(i) - 'a']++;
if(Arrays.equals(pCnt, sCnt)) {
res.add(i - pLen + 1);
}
}
return res;
}
}