leetcode热题100刷题计划
题目3
无重复字符的最长子串
思路
滑动窗口，设定当前窗口左侧为i，右侧为right，当到达右侧边界时，记录长度，
然后删掉最左侧的字符，即i+1；right则继续向后搜。
代码
public int lengthOfLongestSubstring(String s) {// 哈希集合，记录每个字符是否出现过Set<Character> occ = new HashSet<Character>();int n = s.length();// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动int rk = -1, ans = 0;for (int i = 0; i < n; ++i) {if (i != 0) {// 左指针向右移动一格，移除一个字符occ.remove(s.charAt(i - 1));}while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {// 不断地移动右指针occ.add(s.charAt(rk + 1));++rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串ans = Math.max(ans, rk - i + 1);}return ans;}
题目128
最长连续序列
思路
- 先把序列遍历到set当中
- 设以k为起点的序列，如果有k+1，k+2存在，则直接长度响应增加。
- 为了防止重复记录，如果有k-1存在，则条件2必然满足；所以只有在k-1不存在时，才会去执行2条件
代码
public int longestConsecutive(int[] nums) {Set<Integer> numset=new HashSet<Integer>();for(int num:nums){numset.add(num);}int longestStreak=0;for(int num:nums){if(!numset.contains(num-1)){int current=num;int curlength=1;while(numset.contains(current+1)){current++;curlength++;}longestStreak=Math.max(longestStreak,curlength);}}return longestStreak;}题目102
二叉树的层次遍历
思路
使用队列。同层结点会一起输出。每次循环时，把队列里的所有元素出队并且把各自的孩子结点进队，如此这般就是一层一层的层次遍历。
代码
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result=new LinkedList<>();Queue<TreeNode> queue=new LinkedList<>();if(root==null){return result;}queue.add(root);while(!queue.isEmpty()){int size=queue.size();List<Integer> temp=new LinkedList<>();//全部出队，保证这层全部输出while(size>0){TreeNode t=queue.poll();temp.add(t.val);if(t.left!=null)queue.add(t.left);if(t.right!=null)queue.add(t.right);size--;}result.add(temp);}return result;}
}