近期的一些总结
发布时间
阅读量：
阅读量
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0){
return 0;
}
HashMap<Character,Integer> map = new HashMap<>();
int max = 0;
int left = 0;
for (int i = 0; i < s.length(); i++){
if (map.containsKey(s.charAt(i))){
left = Math.max(left,map.get(s.charAt(i)) + 1);
}
map.put(s.charAt(i),i);
max = Math.max(max,i - left + 1);
}
return max;
}
class LRUCache {
int cap;
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
// 将 key 变为最近使用
makeRecently(key);
return cache.get(key);
}
public void put(int key, int val) {
if (cache.containsKey(key)) {
// 修改 key 的值
cache.put(key, val);
// 将 key 变为最近使用
makeRecently(key);
return;
}
if (cache.size() >= this.cap) {
// 链表头部就是最久未使用的 key
int oldestKey = cache.keySet().iterator().next();
cache.remove(oldestKey);
}
// 将新的 key 添加链表尾部
cache.put(key, val);
}
private void makeRecently(int key) {
int val = cache.get(key);
// 删除 key，重新插入到队尾
cache.remove(key);
cache.put(key, val);
}
}
public int findKth(int[] a, int n, int K) {
quick(a,0,n-1);
int res = a[n - K];
return res;
}
public static int postion(int[] array,int low,int high){
int tmp = array[low];
while (low < high){
while (low < high && tmp <= array[high]) {
high--;
}
array[low] = array[high];
while (low < high && tmp >= array[low]){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void quick(int[] array,int low,int high){
if(low >= high){
return;
}
int priot = postion(array,low,high);
quick(array,low,priot-1);
quick(array,priot+1,high);
}
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// 区间 [a, b) 包含 k 个待反转元素
ListNode a, b;
a = b = head;
for (int i = 0; i < k; i++) {
// 不足 k 个，不需要反转，base case
if (b == null) return head;
b = b.next;
}
// 反转前 k 个元素
ListNode newHead = reverse(a, b);
// 递归反转后续链表并连接起来
a.next = reverseKGroup(b, k);
return newHead;
}
/* 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;
pre = null;
cur = a;
nxt = a;
// while 终止的条件改一下就行了
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
// 返回反转后的头结点
return pre;
}
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
int len = nums.length;
if(nums == null || len < 3) return ans;
Arrays.sort(nums); // 排序
for (int i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
int L = i+1;
int R = len-1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L<R && nums[L] == nums[L+1]) L++; // 去重
while (L<R && nums[R] == nums[R-1]) R--; // 去重
L++;
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}
public int[] MySort (int[] arr) {
quick(arr,0,arr.length-1);
return arr;
}
public static void quicksort(int[] a){
quick(a,0,a.length);
}
public static int postion(int[] array,int low,int high){
int tmp = array[low];
while (low < high){
while (low < high && tmp <= array[high]) {
high--;
}
array[low] = array[high];
while (low < high && tmp >= array[low]){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void quick(int[] array,int low,int high){
if(low >= high){
return;
}
int priot = postion(array,low,high);
quick(array,low,priot-1);
quick(array,priot+1,high);
}
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
if (n == 0){
return 0;
}
for (int i = 1; i < n; i++){
dp[i] = Math.max(nums[i],nums[i] + dp[i-1]);
}
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++){
res = Math.max(res,dp[i]);
}
return res;
}
public int[] twoSum(int[] nums, int target) {
// 维护 val -> index 的映射
HashMap<Integer, Integer> valToIndex = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
// 查表，看看是否有能和 nums[i] 凑出 target 的元素
int need = target - nums[i];
if (valToIndex.containsKey(need)) {
return new int[]{valToIndex.get(need), i};
}
// 存入 val -> index 的映射
valToIndex.put(nums[i], i);
}
return null;
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res= new LinkedList<>();
if (root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
List<Integer> list = new LinkedList<>();
for (int i = 0; i < size; i++){
TreeNode cur = queue.poll();
list.add(cur.val);
if (cur.left != null){
queue.offer(cur.left);
}
if (cur.right != null){
queue.offer(cur.right);
}
}
res.add(list);
}
return res;
}
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
for (int i = 0; i < n; i++) {
if (i - 1 == -1) {
// base case
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
}
return dp[n - 1][0];
}
}
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null){
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast){
if (fast == null || fast.next == null){
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0){
return -1;
}
if (n == 1){
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r){
int mid = (l + r) / 2;
if (nums[mid] == target){
return mid;
}
if (nums[0] <= nums[mid]){
if (nums[0] <= target && target < nums[mid]){
r = mid - 1;
}else {
l = mid + 1;
}
}else {
if (nums[mid] < target && target <= nums[n - 1]){
l = mid + 1;
}else {
r = mid - 1;
}
}
}
return -1;
}
public int numIslands(char[][] grid) {
int res = 0;
int m = grid.length,n = grid[0].length;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (grid[i][j] == '1'){
res++;
dfs(grid,i,j);
}
}
}
return res;
}
private void dfs(char[][] grid, int i, int j) {
int m = grid.length,n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n){
return;
}
if (grid[i][j] == '0'){
return;
}
grid[i][j] = '0';
dfs(grid,i+1,j);
dfs(grid,i,j+1);
dfs(grid,i-1,j);
dfs(grid,i,j-1);
}
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new LinkedList<>();
if (root == null) {
return res;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// 为 true 时向右，false 时向左
boolean flag = true;
// while 循环控制从上向下一层层遍历
while (!q.isEmpty()) {
int sz = q.size();
// 记录这一层的节点值
LinkedList<Integer> level = new LinkedList<>();
// for 循环控制每一层从左向右遍历
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 实现 z 字形遍历
if (flag) {
level.addLast(cur.val);
} else {
level.addFirst(cur.val);
}
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
// 切换方向
flag = !flag;
res.add(level);
}
return res;
}
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 以 s[i] 为中心的最长回文子串
String s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
String s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
String palindrome(String s, int l, int r) {
// 防止索引越界
while (l >= 0 && r < s.length()
&& s.charAt(l) == s.charAt(r)) {
// 向两边展开
l--;
r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l + 1, r);
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null){
return null;
}
if (root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if (left != null && right !=null){
return root;
}
if (left == null && right == null){
return null;
}
return left == null ? right : left;
}
public void merge(int A[], int m, int B[], int n) {
int index = m + n - 1;
int i = m - 1;
int j = n - 1;
while ( i>= 0 && j>=0){
if(A[i] > B[j]){
A[index--] = A[i--];
}else{
A[index--] = B[j--];
}
}
while (i >= 0){
A[index--] = A[i--];
}
while (j >= 0){
A[index--] = B[j--];
}
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> set = new HashSet<>();
ListNode tmp = headA;
while (tmp != null){
set.add(tmp);
tmp = tmp.next;
}
tmp = headB;
while (tmp != null){
if (set.contains(tmp)){
return tmp;
}
tmp = tmp.next;
}
return null;
}
List<List<Integer>> res = new LinkedList<>();
/* 主函数，输入一组不重复的数字，返回它们的全排列 */
List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
// 「路径」中的元素会被标记为 true，避免重复使用
boolean[] used = new boolean[nums.length];
backtrack(nums, track, used);
return res;
}
// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素（used[i] 为 false）
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (used[i]) {
// nums[i] 已经在 track 中，跳过
continue;
}
// 做选择
track.add(nums[i]);
used[i] = true;
// 进入下一层决策树
backtrack(nums, track, used);
// 取消选择
track.removeLast();
used[i] = false;
}
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
// 虚拟头结点
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
// 优先级队列，最小堆
PriorityQueue<ListNode> pq = new PriorityQueue<>(
lists.length, (a, b)->(a.val - b.val));
// 将 k 个链表的头结点加入最小堆
for (ListNode head : lists) {
if (head != null)
pq.add(head);
}
while (!pq.isEmpty()) {
// 获取最小节点，接到结果链表中
ListNode node = pq.poll();
p.next = node;
if (node.next != null) {
pq.add(node.next);
}
// p 指针不断前进
p = p.next;
}
return dummy.next;
}
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++){
for (int j = i; j < n; j++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for (int[] row : matrix){
reverse(row);
}
}
public void reverse(int[] arr){
int i = 0, j = arr.length - 1;
while (i < j){
int tmp= arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
public ListNode detectCycle(ListNode head) {
ListNode pos = head;
HashSet<ListNode> set = new HashSet<>();
while (pos != null){
if (set.contains(pos)){
return pos;
}else {
set.add(pos);
}
pos = pos.next;
}
return null;
}
class Solution {
public String addStrings(String num1, String num2) {
int i = num1.length() - 1, j = num2.length() - 1, add = 0;
StringBuffer ans = new StringBuffer();
while (i >= 0 || j >= 0 || add != 0) {
int x = i >= 0 ? num1.charAt(i) - '0' : 0;
int y = j >= 0 ? num2.charAt(j) - '0' : 0;
int result = x + y + add;
ans.append(result % 10);
add = result / 10;
i--;
j--;
}
// 计算完以后的答案需要翻转过来
ans.reverse();
return ans.toString();
}
}
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp,1);
for (int i = 0; i < nums.length; i++){
for (int j = 0; j < i; j++){
if (nums[i] > nums[j]){
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
}
int res = 0;
for (int i = 0; i < dp.length; i++){
res = Math.max(res,dp[i]);
}
return res;
}
public int trap(int[] height) {
if (height.length == 0){
return 0;
}
int n = height.length;
int res = 0;
int[] L_max = new int[n];
int[] R_max = new int[n];
L_max[0] = height[0];
R_max[n-1] = height[n-1];
for (int i = 1; i < n; i++){
L_max[i] = Math.max(height[i],L_max[i-1]);
}
for (int i = n - 2; i >= 0; i--){
R_max[i] = Math.max(height[i],R_max[i+1]);
}
for (int i = 1; i < n -1; i++){
res += Math.min(L_max[i],R_max[i]) - height[i];
}
return res;
}
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
List<ListNode> list = new ArrayList<ListNode>();
ListNode node = head;
while (node != null) {
list.add(node);
node = node.next;
}
int i = 0, j = list.size() - 1;
while (i < j) {
list.get(i).next = list.get(j);
i++;
if (i == j) {
break;
}
list.get(j).next = list.get(i);
j--;
}
list.get(i).next = null;
}
}
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
// 计算单边路径和时顺便计算最大路径和
oneSideMax(root);
return res;
}
// 定义：计算从根节点 root 为起点的最大单边路径和
int oneSideMax(TreeNode root) {
if (root == null) {
return 0;
}
int leftMaxSum = Math.max(0, oneSideMax(root.left));
int rightMaxSum = Math.max(0, oneSideMax(root.right));
// 后序遍历位置，顺便更新最大路径和
int pathMaxSum = root.val + leftMaxSum + rightMaxSum;
res = Math.max(res, pathMaxSum);
// 实现函数定义，左右子树的最大单边路径和加上根节点的值
// 就是从根节点 root 为起点的最大单边路径和
return Math.max(leftMaxSum, rightMaxSum) + root.val;
}
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
private Stack<Integer> s1, s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
public void push(int x) {
s1.push(x);
}
public int pop() {
// 先调用 peek 保证 s2 非空
peek();
return s2.pop();
}
public int peek() {
if (s2.isEmpty())
// 把 s1 元素压入 s2
while (!s1.isEmpty())
s2.push(s1.pop());
return s2.peek();
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0,head);
Stack<ListNode> stack = new Stack<>();
ListNode cur = dummy;
while (cur != null){
stack.push(cur);
cur = cur.next;
}
for (int i = 0; i < n; i++){
stack.pop();
}
ListNode prev = stack.peek();
prev.next = prev.next.next;
return dummy.next;
}
public int[][] merge(int[][] intervals) {
LinkedList<int[]> res = new LinkedList<>();
// 按区间的 start 升序排列
Arrays.sort(intervals, (a, b) -> {
return a[0] - b[0];
});
res.add(intervals[0]);
for (int i = 1; i < intervals.length; i++) {
int[] curr = intervals[i];
// res 中最后一个元素的引用
int[] last = res.getLast();
if (curr[0] <= last[1]) {
last[1] = Math.max(last[1], curr[1]);
} else {
// 处理下一个待合并区间
res.add(curr);
}
}
return res.toArray(new int[0][0]);
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode fast = head.next;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null){
if (left.val < right.val){
h.next = left;
left = left.next;
}else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}全部评论 (0)
还没有任何评论哟~