2 两数相加

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
双指针 注意进位不为空 但两个数已经遍历完的情况
"""
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode res = new ListNode(-1);
ListNode cur = res;
int jinwei = 0;
while ((l1 != null && l2 != null) || jinwei != 0) {
int l1Val = 0, l2Val = 0;
if (l1 != null) {
l1Val = l1.val;
l1 = l1.next;
}
if (l2 != null) {
l2Val = l2.val;
l2 = l2.next;
}
int sum = (l1Val + l2Val + jinwei) % 10;
jinwei = (l1Val + l2Val + jinwei) / 10;
cur.next = new ListNode(sum);
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return res.next;
}
}

3 无重复字符的最长子串

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
双指针+map存数与index关系 方便查询是否出现过
"""
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length()<2) return s.length();
int left = 0; //代表无重复子串的左指针
int res = 0;
HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0; i<s.length(); i++){ //i为当前无重复子串的右指针
if(map.containsKey(s.charAt(i))){
left = Math.max(left, map.get(s.charAt(i))+1);
}
map.put(s.charAt(i), i);
res = Math.max(res, i-left+1);
}
return res;
}
}

4 寻找两个正序数组的中位数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
二分
比较这两个数组的第K/2小的数字midVal1和midVal2的大小,
如果第一个数组的第K/2个数字小的话,那么说明我们要找的数字肯定不在nums1中的前K/2个数字,所以我们可以将其淘汰,将nums1的起始位置向后移动K/2个,并且此时的K也自减去K/2,调用递归。
反之,我们淘汰nums2中的前K/2个数字,并将nums2的起始位置向后移动K/2个,并且此时的K也自减去K/2,调用递归即可。
"""
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int m=nums1.length,n=nums2.length;
//如果长度为奇数 k1=k2 如果长度为偶数 k1=k2-1
//奇数的话 第k1个数即为中位数
//偶数的话 中位数=(nums[k1]+nums[k2])/2
int k1=(m+n+1)/2,k2=(m+n+2)/2;
return (findk(nums1,0,nums2,0,k1)+findk(nums1,0,nums2,0,k2))/2.0;
}
//找到两个有序数组合并后的第k个数的值
// i是nums1的可能出现第k个数的最左边下标,j是nums2的可能出现第k个数的最左边下标
public int findk(int[] nums1,int i,int[] nums2,int j,int k){
//当某一个数组的起始位置大于等于其数组长度时,说明其所有数字均已经被淘汰了,相当于一个空数组了,那么实际上就变成了在另一个数组中找数字,直接就可以找出来了。
if(i>=nums1.length) return nums2[j+k-1];
if(j>=nums2.length) return nums1[i+k-1];
//如果K=1的话,那么我们只要比较nums1和nums2的起始位置i和j上的数字就可以了
if(k==1) return Math.min(nums1[i],nums2[j]);
//赋予最大值的意思只是说如果第一个数组的K/2不存在,则说明这个数组的长度小于K/2,那么第k个数肯定不在另外一个数组的前K/2个中
int valid1=(i+k/2-1<nums1.length)?nums1[i+k/2-1]:Integer.MAX_VALUE;
int valid2=(j+k/2-1<nums2.length)?nums2[j+k/2-1]:Integer.MAX_VALUE;
if(valid1<valid2) return findk(nums1,i+k/2,nums2,j,k-k/2);
else return findk(nums1,i,nums2,j+k/2,k-k/2);
}
}

8 字符串转换整数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int myAtoi(String s) {
char[] str=s.toCharArray();
int i=0;
int len=str.length;
int res=0;
int flag=1;
while(i<len){
while(i<len&&str[i]==' ') i+=1; //前导空格
if(i<len&&str[i]>='a'&&str[i]<='z') break; //若在数字之前出现字母 则直接返回0
//判断正负
if(i<len&&(str[i]=='+'||str[i]=='-') {
flag=str[i]=='-'?-1:1;
i+=1;
}
while(i<len&&str[i]>='0'&&str[i]<='9') {
int digit=str[i]-'0';
// *10 和 + digit 都有可能越界,所有都移动到右边去就可以了
if(res>(Integer.MAX_VALUE-digit)/10){
if(flag<0) return -2147483648;
else return 2147483647;
}
res=res*10+str[i]-'0';
i+=1;
}
break;
}
return res*flag;
}
}

11 盛最多水的容器

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
双指针 一开始ij指向两端 随后对应高度小的那个指针向内移动、
若height[i]<height[j] i若固定不动,j向左移,则对应的水量一定小于原本的ij
若原本水量是height[i]*(j-i) j移动后为j1的水量为min(height[i],height[j1])*(j1-i)必小于原来的
因为min(height[i],height[j1])<=height[i]
(j1-i)<(j-i)
"""
class Solution {
public int maxArea(int[] height) {
int res=0;
int i=0,j=height.length-1;
while(i<j){
res=Math.max(res,(Math.min(height[i],height[j])*(j-i)));
//指向数小的指针 向内移动
//若height[i]<height[j] i若固定不动,j向左移,则对应的水量一定小于原本的ij
//若原本水量是height[i]*(j-i) j移动后为j1的水量为min(height[i],height[j1])*(j1-i)必小于原来的
//因为min(height[i],height[j1])<=height[i] (j1-i)<(j-i)
if(height[i]<height[j]) i++;
else j--;
}
return res;
}
}

15 三数之和

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
"""
固定一个数 相当于求数组中是否存在两个数的和等于目标值
判断两数之和 用双指针+排序:
也是固定一个数下标为second 另一个数下标为third从最右边开始移动
因为排序过 所以nums[second]+nums[third]<nums[second+1]+nums[third]<nums[second+1]+nums[third+1] 所以third只要初始化一次即可 后续直接在上一个third的基础上继续往左移
注意跳过相同的数
"""
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res=new LinkedList<>();
Arrays.sort(nums); //排序
for(int first=0;first<nums.length;first++){
if(first>0&&nums[first]==nums[first-1]) continue; //跳过相同的数
int target=-nums[first]; //要找的另外两数之和
int third=nums.length-1; //初始化third
for(int second=first+1;second<nums.length;second++){ //每次固定second
if(second>first+1&&nums[second]==nums[second-1]) continue; //跳过相同的值
while (second<third&&nums[second]+nums[third]>target) third--; //指针移动
if(second==third) break; //second处于这个位置 不存在结果
if(nums[second]+nums[third]==target){ //找到结果
List<Integer> tmp=new LinkedList<>();
tmp.add(nums[first]);
tmp.add(nums[second]);
tmp.add(nums[third]);
res.add(tmp);
}
}
}
return res;
}
}

假如是6个数 问是否存在分为两堆 两堆和相等
那就是先排序数组 然后固定开头第一个值 因为该值要么在左边堆要么在右边堆 随后双指针对剩余数判断是否存在和为sum/2-arr[0]的两个数 存在即存在 不存在则无解

17 电话号码的字母组合

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
"""
要全遍历 当然想到回溯
"""
class Solution {
Map<Character, String> phoneMap = new HashMap<Character, String>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if(digits.length()<1) return res;
int len = digits.length();
StringBuilder cur = new StringBuilder();
backtrace(res, 0, cur, digits);
return res;

}
private void backtrace(List<String> res,int index, StringBuilder cur, String digits){
if(index == digits.length()){
res.add(cur.toString());
return;
}
String curStr = phoneMap.get(digits.charAt(index));
for(int i = 0;i<curStr.length();i++){
cur.append(curStr.charAt(i));
backtrace(res, index+1, cur, digits);
cur.deleteCharAt(index);
}
}
}

19 删除链表的倒数第N个节点

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
快慢指针 快指针先走n步 随后一起走 当快指针走到最后一个节点时,对应的慢指针指向要删除的节点的前一个节点
要注意假如要删除的是第一个指针 那直接返回head.next即可
"""
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast=head; //快指针
ListNode slow=head; //慢指针
while(n>0) {
fast=fast.next;
n-=1;
}
while(fast!=null&&fast.next!=null){
fast=fast.next;
slow=slow.next;
}
if(fast==null) return slow.next; //要删除的是头结点
slow.next=slow.next.next;
return head;
}
}

20 有效的括号

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
用linkedlist模仿栈 因为linkedlist是双向链表
"""
class Solution {
public boolean isValid(String s) {
LinkedList<Character> helper = new LinkedList<>();
for(int i = 0;i<s.length();i++){
char c = s.charAt(i);
if(c == '(' || c=='[' || c=='{'){
helper.add(c);
}else{
if(helper.isEmpty()) return false;
if((c == ')' && helper.getLast()=='(') ||
(c == ']' && helper.getLast()=='[') ||
(c == '}' && helper.getLast()=='{')){
helper.removeLast();
continue;
}
return false;
}
}
return helper.isEmpty();
}
}

21 合并两个有序链表

一、问题描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
伪节点来统一空指针问题
"""
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode pHead = new ListNode(-1);
ListNode cur = pHead;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return pHead.next;
}
}

22 括号生成

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
"""
回溯 用两个计数器记录当前左括号和右括号的个数
如果左括号数量不大于n,我们可以放一个左括号。
如果右括号数量小于左括号的数量,我们可以放一个右括号。
左括号必然在右括号之前放 所以第一个判断条件在前。
"""
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res=new ArrayList<>();
backtrace(res,new StringBuilder(),0,0,n);
return res;
}
public void backtrace(List<String> res,StringBuilder cur,int open,int close,int max){
if(cur.length()==max*2){ //返回
res.add(cur.toString());
}
//如果左括号数量不大于 n,我们可以放一个左括号。
if(open<max){
cur.append("(");
backtrace(res,cur,open+1,close,max);
cur.deleteCharAt(cur.length()-1);
}
//如果右括号数量小于左括号的数量,我们可以放一个右括号。
if(close<open){
cur.append(")");
backtrace(res,cur,open,close+1,max);
cur.deleteCharAt(cur.length()-1);
}
}
}

class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<String>();
generate(res, "", 0, 0, n);
return res;
}
//count1统计“(”的个数,count2统计“)”的个数
public void generate(List<String> res , String ans, int count1, int count2, int n){
if(count1 > n || count2 > n) return;
if(count1 == n && count2 == n) res.add(ans);
if(count1 >= count2){
String ans1 = new String(ans);
generate(res, ans+"(", count1+1, count2, n);
generate(res, ans1+")", count1, count2+1, n);
}
}
}

23 合并k个有序链表

一、问题描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
"""
k大的最小堆,k为lists的长度,每次弹出当前最小,然后把当前最小的next 若不为空 则入堆
"""
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>(new Comparator<ListNode>(){
@Override
public int compare(ListNode o1, ListNode o2){
return o1.val - o2.val;
}
});
int k = lists.length;
if(k<1) return null;
ListNode pHead = new ListNode(-1);
ListNode cur = pHead;
for(ListNode list : lists){
if(list == null) continue;
heap.add(list);
}
while(!heap.isEmpty()){
ListNode curMin = heap.poll();
if(curMin.next != null){ // 然后把当前最小的next 若不为空 则入堆
heap.add(curMin.next);
}
cur.next = curMin;
cur = curMin;
}
return pHead.next;
}
}

31 下一个排列

一、问题描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
输出全排列的下一个排列
我们需要将一个左边的「较小数」与一个右边的「较大数」交换,以能够让当前排列变大,从而得到下一个排列。

同时我们要让这个「较小数」尽量靠右,而「较大数」尽可能小。当交换完成后,「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下,使变大的幅度尽可能小。
首先从后向前查找第一个顺序对 (i,i+1),满足 a[i]<a[i+1]。这样「较小数」即为 a[i]。此时 [i+1,n) 必然是下降序列。

如果找到了顺序对,那么在区间 [i+1,n) 中从后向前查找第一个元素 j满足a[i]<a[j]。这样「较大数」即为 a[j]。

交换 a[i]与 a[j],此时可以证明区间 [i+1,n) 必为降序。我们可以直接使用双指针反转区间 [i+1,n) 使其变为升序,而无需对该区间进行排序。

"""
class Solution {
public void nextPermutation(int[] nums) {
if(nums.length<2) return;
int i = nums.length - 2;
while(i>=0){
if(nums[i]<nums[i+1]){
break;
}
i--;
}
int j = nums.length - 1;
if(i<0){ //已经是最大的排列了
reverse(nums, 0, nums.length-1);
return;
}
while(nums[j]<=nums[i]) j--;
// 找到满足条件的数最靠右且差最小的升序对
swap(nums, i, j);
// 保证右边是升序,即最靠近当前排列的 下一个排列
reverse(nums, i+1, nums.length-1);
}
private void reverse(int[] nums, int left, int right){
while(left<right){
swap(nums, left, right);
left++;
right--;
}
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

32 最长有效括号

一、问题描述


二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public int longestValidParentheses(String s) {
// 从左往右
int left = 0, right = 0, res = 0, startIdx = 0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='(') left++;
else{ right++;
if(right==left){
res = Math.max(res, i-startIdx+1);
}
if(right>left){
startIdx = i+1; //注意
right = 0;
left = 0;
}
}
}
// 从右往左
left = 0;
right = 0;
startIdx = s.length()-1;
for(int i=s.length()-1;i>=0;i--){
if(s.charAt(i)==')') right++;
else{ left++;
if(right==left){
res = Math.max(res, startIdx-i+1);
}
if(right<left){
startIdx = i-1; //注意
right = 0;
left = 0;
}
}
}
return res;
}
}

33 搜索旋转排序数组

一、问题描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
如果中间的数小于最右边的数,则右半段是有序的,
若中间数大于最右边数,则左半段是有序的,
我们只要在有序的半段里用首尾两个数组来判断目标值是否在这一区域内,这样就可以确定保留哪半边了
"""
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]==target) return mid;
else if(nums[mid]<nums[right]){
if(nums[mid]<target && target<=nums[right]) left = mid+1;
else right = mid - 1;
}else{
if(nums[mid]>target && nums[left]<=target) right = mid - 1;
else left = mid + 1;
}
}
return -1;
}
}

34 在排序数组中查找元素的第一个和最后一个位置

一、问题描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
"""
二分+双指针
"""
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = 0, right = nums.length-1;
int[] res = new int[2];
res[0] = -1;
res[1] = -1;
while(left<=right){
int mid =left + (right-left)/2;
if(nums[mid] == target){
left = mid-1;
right = mid+1;
while(left>=0&&nums[left]==target) left--;
while(right<nums.length&&nums[right]==target) right++;
res[0] = left+1;
res[1] = right-1;
return res;
}else{
if(nums[mid]>target) right = mid - 1;
else left = mid + 1;
}

}
return res;
}
}

42 接雨水

一、问题描述


二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
动态规划+双指针
"""
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (leftMax < rightMax) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
}

78 子集

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
"""
从前往后遍历:遇到一个数就把所有子集加上该数组成新的子集,遍历完毕即是所有子集
"""
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<>()); //一开始只有一个空集
for (int i = 0; i < nums.length; i++) {
int all = res.size();
for (int j = 0; j < all; j++) { //所有子集加上当前数
List<Integer> tmp = new ArrayList<>(res.get(j));
tmp.add(nums[i]);
res.add(tmp);
}
}
return res;
}
}
"""
回溯
"""
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res=new ArrayList<>();
res.add(new ArrayList<>());
backtrace(res,new ArrayList<>(),0,nums);
return res;
}
public void backtrace(List<List<Integer>> res,List<Integer> cur,int idx,int[] nums){
for(int i=idx;i<nums.length;i++){
cur.add(nums[i]);
res.add(new ArrayList<>(cur));
backtrace(res,cur,i+1,nums);
cur.remove(cur.size()-1);
}
}
}
"""
若包含重复元素 可以用hashset 自动去除重复子集
"""
class Solution {
public List<List<Integer>> subsets(int[] nums) {
HashSet<ArrayList<Integer>> res=new HashSet<>();
Arrays.sort(nums);
res.add(new ArrayList<>());
backtrace(res,new LinkedList<>(),0,nums);
return new ArrayList(res);
}
public void backtrace(HashSet<ArrayList<Integer>> res,List<Integer> cur,int idx,int[] nums){
for(int i=idx;i<nums.length;i++){
cur.add(nums[i]);
res.add(new ArrayList<>(cur));
backtrace(res,cur,i+1,nums);
cur.remove(cur.size()-1);
}
}
}

46 全排列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
回溯 用visited数组记录元素是否被访问过
"""
class Solution {
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
int[] visited=new int[nums.length];
backtrace(res,new ArrayList<>(),nums,visited);
return res;
}
public void backtrace(List<List<Integer>> res,List<Integer> path,int[] nums,int[] visited){
if(path.size()==nums.length){ //返回
res.add(new ArrayList<>(path));
return;
}
for(int i=0;i<nums.length;i++){ //每次从0开始
if(visited[i]==1) continue;
path.add(nums[i]); //选择
visited[i]=1;
backtrace(res,path,nums,visited);
path.remove(path.size()-1); //撤销选择
visited[i]=0;
}
}
}

49 字母异位词分组

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
"""
字母异位词每个字母出现的次数一致,于是拿字母与字母出现次数作为map 的key
比如eat ==> a1e1t1
eeaatt ==> a2e2t2

"""
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for(String s : strs){
StringBuilder sb = new StringBuilder();
int[] count = new int[26];
for(int i = 0;i<s.length();i++){
count[s.charAt(i)-'a']+=1;
}
for(int i=0;i<26;i++){
if(count[i]>0){
sb.append((char)('a'+i));
sb.append(count[i]);
}
}
String key = sb.toString();//字母+字母出现次数作为map 的key
List<String> temp = map.getOrDefault(key, new ArrayList<String>());
temp.add(s);
map.put(key, temp);
}
return new ArrayList<List<String>>(map.values());
}
}

48 旋转图像

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
顺时针旋转90度=先水平翻转 再对角线翻转
"""
class Solution {
public void rotate(int[][] matrix) {
int m=matrix.length;
int n=matrix[0].length;
//上下翻转
for(int i=0;i<m/2;i++){
for(int j=0;j<n;j++){
int tmp=matrix[i][j];
matrix[i][j]=matrix[m-i-1][j];
matrix[m-i-1][j]=tmp;
}
}
//对角线翻转
for(int i=0;i<m;i++){
for(int j=i+1;j<n;j++){
int tmp=matrix[i][j];
matrix[i][j]=matrix[j][i];
matrix[j][i]=tmp;
}
}
}
}

39 组合总和 即可重复选择元素进行组合

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
"""
回溯+去重
1、正常回溯不剪枝 利用hashset去重,每次把path先排序再加入hashset
"""
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
HashSet<List<Integer>> res=new HashSet<>(); //天然去重
backtrace(res,new ArrayList<>(),0,candidates,target);
return new ArrayList<>(res);
}
public void backtrace(HashSet<List<Integer>> res,List<Integer> path,int cur,int[] candidates,int target){
if(cur==target){
List<Integer> tmp=new ArrayList<>(path);
Collections.sort(tmp); //排序
res.add(tmp);
return;
}
if(cur>target) return;
for(int i=0;i<candidates.length;i++){ //因为可以无限取 每次从零开始
path.add(candidates[i]);
cur+=candidates[i];
backtrace(res,path,cur,candidates,target);
cur-=candidates[i];
path.remove(path.size()-1);
}
}
}
"""
2、对数组先排序 若和已大于target 后面的就不用再遍历了 因为一定更大
每次从begin开始遍历,不用倒回去 自然避免了重复
"""
class Solution {
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); //一定要记得排序
backtrace(new ArrayList<>(),0,candidates,target,0);
return res;
}
public void backtrace(List<Integer> path,int cur,int[] candidates,int target,int begin){
if(cur==target){
res.add(new ArrayList<>(path));
return;
}
for(int i=begin;i<candidates.length;i++){
if(cur+candidates[i]<=target){
path.add(candidates[i]);
cur+=candidates[i];
backtrace(path,cur,candidates,target,i);
cur-=candidates[i];
path.remove(path.size()-1);
}
else break; //大于的话 后续的不用再遍历
}
}

}

406 根据身高重建队列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
"""
先按照身高降序 k升序进行排序 则k为该人的绝对位置
按照顺序插入结果队列中即可
"""
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>() { //排序规则
@Override
public int compare(int[] o1, int[] o2) {
if(o1[0]!=o2[0]) return o2[0]-o1[0];
else return o1[1]-o2[1];
}
});
List<int[]> res=new ArrayList<>();
for(int[] p:people){ //按顺序插入到指定位置
res.add(p[1],p);
}
return res.toArray(new int[people.length][]); //转为int数组
}
}

238 除自身以外数组的乘积

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
"""
遍历两次:
第一次用res数组存左乘积结果 res[i]=nums[0]*nums[1]*···*nums[i-1]
第二次用res数组存结果 即乘上右乘积的结果 res[i]=res[i]*nums[i+1]*...
"""
class Solution {
public int[] productExceptSelf(int[] nums) {
int right=1; //right存的是右乘积,最后一个数右边没有值 赋为1
int[] res=new int[nums.length];
res[0]=1; //第一个数左边没有值 赋为1
for(int i=1;i<nums.length;i++){
res[i]=nums[i-1]*res[i-1];
}
for(int i=nums.length-1;i>=0;i--){
res[i]=res[i]*right; //res=res(左乘积)*right(右乘积)
right=right*nums[i]; //right存的是右乘积,更新right
}
return res;
}
}

208 实现Trie(前缀树)

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
前缀树是一种新的数据结构(又称字典树,前缀树,单词查找树
节点包含:
private boolean is_string=false; //该节点是否是一个字符串的结尾
private Trie next[]=new Trie[26]; //该节点链接的二十六个字母指针(字母映射表)
"""
public class Trie {
private boolean is_string=false;
private Trie next[]=new Trie[26];

public Trie(){}

// 首先从根结点的子结点开始与 word 第一个字符进行匹配,一直匹配到前缀链上没有对应的字符,
//这时开始不断开辟新的结点,直到插入完 word 的最后一个字符,
//同时还要将最后一个结点is_string = true;,表示它是一个单词的末尾。
public void insert(String word){//插入单词
Trie root=this;
char w[]=word.toCharArray();
for(int i=0;i<w.length;++i){
if(root.next[w[i]-'a']==null)root.next[w[i]-'a']=new Trie();//开辟新的结点
root=root.next[w[i]-'a'];
}
root.is_string=true;//表示它是一个单词的末尾。
}
//从根结点的子结点开始,一直向下匹配即可,
//如果出现结点值为空就返回 false,如果匹配到了最后一个字符,那我们只需判断 node->isEnd即可。
public boolean search(String word){//查找单词
Trie root=this;
char w[]=word.toCharArray();
for(int i=0;i<w.length;++i){
if(root.next[w[i]-'a']==null)return false;
root=root.next[w[i]-'a'];
}
return root.is_string;
}

public boolean startsWith(String prefix){//查找前缀
Trie root=this;
char p[]=prefix.toCharArray();
for(int i=0;i<p.length;++i){
if(root.next[p[i]-'a']==null)return false;
root=root.next[p[i]-'a'];
}
return true;
}
}

56 合并区间

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
先把各区间按照开始排序
假如两个区间有重叠,则取最远的end作为新数组的end即可
假如没有重叠,则前面的start end构成一个区间,新的区间的start end由后面区间构成
"""
class Solution {
public static int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0])); //排序
List<int[]> res = new ArrayList<>();
int start = intervals[0][0];
int end = intervals[0][1];
for(int i = 1;i<intervals.length;i++){ //遍历区间
if(intervals[i][0]>end){ //假如有重叠
res.add(new int[]{start, end});
start = intervals[i][0];
}
end = Math.max(end,intervals[i][1]);
}
res.add(new int[]{start,end});
return res.toArray(new int[res.size()][2]);
}
}

62 不同路径

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
"""
动态规划f(i,j)=f(i−1,j)+f(i,j−1)
当i=0或j=0的时候,只有一条路径
"""
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
dp[0][0] = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0||j==0){
dp[i][j] = 1;
}else{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
}

64 最小路径和

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
动态规划 不过要注意初始化边界的时候:
dp[i][0]=dp[i-1][0]+grid[i][0];
dp[0][j]=dp[0][j-1]+grid[0][j]; 是累加的不是直接=grid[0][j]
"""
class Solution {
public int minPathSum(int[][] grid) {
int[][] dp=new int[grid.length][grid[0].length];
dp[0][0]=grid[0][0];
for(int i=1;i<grid.length;i++){
dp[i][0]=dp[i-1][0]+grid[i][0];
}
for(int j=1;j<grid[0].length;j++){
dp[0][j]=dp[0][j-1]+grid[0][j];
}
for(int i=1;i<grid.length;i++){
for(int j=1;j<grid[0].length;j++){
dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[grid.length-1][grid[0].length-1];
}
}

75 最小路径和

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
"""
三路快排
"""
class Solution {
public void sortColors(int[] nums) {
int left = 0;
int right = nums.length-1;
while(left<=right&&nums[left]==0) left++;
while(right>=left&&nums[right]==2) right--;
for(int idx =left;idx<=right;idx++){
while(idx<=right && nums[idx] == 2){ //2换回来的可能是0,1,2 假如是2 继续换 假如是0走下面,1不用处理
swap(nums, idx, right);
right--;
}
if(nums[idx]==0){
swap(nums, idx ,left);
left++;
}
}
}
private void swap(int[] nums, int i ,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}

148 排序列表

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
"""
时间复杂度nlogn 那只能堆排序 归并排序 快排(最差n2)
常数级复杂度 那就只能归并排序
自顶向下的归并排序一般用递归 空间复杂度为n 所以要用自底向上的归并排序方法:
1、首先求得链表的长度length,然后将链表拆分成子链表进行合并。
2、用subLength 表示每次需要排序的子链表的长度,初始时subLength=1。
每次将链表拆分成若干个长度为subLength 的子链表(最后一个子链表的长度可以小于subLength),按照每两个子链表一组进行合并,合并后即可得到若干个长度为subLength×2 的有序子链表(最后一个子链表的长度可以小于2subLength×2)。
3、将subLength 的值加倍,重复第 2 步,对更长的有序子链表进行合并操作,直到有序子链表的长度大于或等于length,整个链表排序完毕。
"""
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
int length = 0;
ListNode node = head;
while (node != null) { //求长度
length++;
node = node.next;
}
ListNode dummyHead = new ListNode(0, head);
for (int subLength = 1; subLength < length; subLength <<= 1) {
ListNode prev = dummyHead, curr = dummyHead.next; //每次从头开始拆分长度为sublength的链表
while (curr != null) {
ListNode head1 = curr;//第一小块链表头结点
for (int i = 1; i < subLength && curr.next != null; i++) {
curr = curr.next;
}
ListNode head2 = curr.next;
curr.next = null; //小块与后续断开
curr = head2;//第二小块链表头结点
for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
curr = curr.next;
}
ListNode next = null;
if (curr != null) {
next = curr.next;
curr.next = null; //与后续断开
}
ListNode merged = merge(head1, head2);
prev.next = merged; //合并好的节点链接上
while (prev.next != null) {
prev = prev.next; //prev指向合并好链表的尾结点 用于后续链接合并好的节点
}
curr = next; //curr指向待合并的链表首节点 继续后续拆分
}
}
return dummyHead.next;
}

public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0);//尾结点 用来统一头结点和中间节点的操作
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}
"""
自顶向下的归并
利用快慢指针得到中间节点 一个走两步 一个走一步
"""
class Solution {
public ListNode sortList(ListNode head) {
if(head==null || head.next==null) return head;
ListNode slow = head, fast = head.next;
while(fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
ListNode head1 = slow.next;
slow.next = null;

return merge(sortList(head),sortList(head1));
}

public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}

287 寻找重复数

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
Floyd算法 龟兔赛跑 线性的时间复杂度 常数级的空间复杂度
一个fast指针每次走两步,一个slow指针每次走一步 终会在不是起点的地方相遇
相遇后slow回到起点 两个一起每次走一步 最终相与的点就是环入口
"""
class Solution {
public int findDuplicate(int[] nums) {
int slow=0,fast=0;
while(true){
fast=nums[nums[fast]];
slow=nums[slow];
if(fast==slow){
slow=0;
while (slow!=fast){
slow=nums[slow];
fast=nums[fast];
}
return slow;
}
}
}
}

283 寻找重复数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
1、双指针
i指向第一个零 j指向为整理的第一个非零 交换即可
"""
class Solution {
public void moveZeroes(int[] nums) {
int i=0,j=0;
while(i<nums.length){
while(i<nums.length&&nums[i]!=0) i++; //i指向第一个0处
while(j<nums.length&&nums[j]==0) j++;//j指向第一个非零处
if(j==nums.length||i==nums.length) return;
if(i<j){
int temp=nums[j];
nums[j]=nums[i];
nums[i]=temp;
}
j++;
}
}
}
"""
2、双指针 更好
因为末尾都是零 只需要把非零的全部移到前面即可(直接覆盖) 后面的用零覆盖
"""
class Solution {
public void moveZeroes(int[] nums) {
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[j++] = nums[i];
}
}
while (j<nums.length){
nums[j++]=0;
}
}
}

448 找到所有数组中消失的数字

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
利用数的范围都在1~n 将nums[nums[i]-1]转负数 nums[i]仍为正数的 那i+1就是没出现的 注意下标从0开始
"""
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res=new ArrayList<>();
int len=nums.length;
for(int i=0;i<len;i++){
int tmp=Math.abs(nums[i])-1;
if(nums[tmp]>0) nums[tmp]=-nums[tmp];
}
for(int i=0;i<len;i++){
if(nums[i]>0) res.add(i+1);
}
return res;
}
}

160 相交链表

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

"""
1、神之方法:定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
时间复杂度m(a的长度减去公共的)+n(b的长度减去公共的)+p(公共的)
"""
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pa=headA,pb=headB;
if(pa==null||pb==null) return null;
while (pa!=pb){
pa=pa==null?headB:pa.next;
pb=pb==null?headA:pb.next;
}
return pa;
}
}
"""
2、分别计算两者的长度len_a,len_b 然后长的先走abs(len_a-len_b)步 随后a,b两者一起走,相交点就是交点
时间复杂度max(a+b)+abs(a-b)+min(a,b)-p
"""
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pa=headA;
ListNode pb=headB;
int len_A=0;
int len_B=0;
while(pa!=null){
pa=pa.next;
len_A+=1;
}
while(pb!=null){
pb=pb.next;
len_B+=1;
}
pa=headA;
pb=headB;
if(len_A>=len_B){
int count=len_A-len_B;
while(count>0){
pa=pa.next;
count-=1;
}
while(pa!=pb){
pa=pa.next;
pb=pb.next;
}
}
else{
int count=len_B-len_A;
while(count>0){
pb=pb.next;
count-=1;
}
while(pa!=pb){
pa=pa.next;
pb=pb.next;
}
}
return pa;
}
}

java 正则表达式

(.)\1+ 表示 表示任意一个字符重复两次或两次以上(括号里的点表示任意字符,后面的 \1表示取第一个括号匹配的内容 ,后面的加号表示匹配1次或1次以上。二者加在一起就是某个字符重复两次或两次以上)
**$1是第一个小括号里的内容,$2是第二个小括号里面的内容**,

1
2
3
4
5
6
7
8
9
10
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int line = scanner.nextInt();
scanner.nextLine();
for (int i = 0; i < line; i++) {
System.out.println(scanner.nextLine().replaceAll("(.)\\1+","$1$1").replaceAll("(.)\\1(.)\\2","$1$1$2"));
}
}
}

万万没想到之抓捕孔连顺

  1. 我们在字节跳动大街的N个建筑中选定3个埋伏地点。

  2. 为了相互照应,我们决定相距最远的两名特工间的距离不超过D。

  3. 题目描述

    解题描述

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    """
    固定最左边的人i 让最右边的人移动 直到范围超出规定的distance
    该段的埋伏方案=(j-i-1)*(long)(j-i-2)/2; 即组合公式
    """
    import java.util.Scanner;
    public class Main{
    public static void main(String[] args){
    Scanner input=new Scanner(System.in);
    int numBuilding=input.nextInt();
    int maxLength=input.nextInt();
    input.nextLine();
    int[] distance=new int[numBuilding];
    for(int k=0;k<numBuilding;k++){
    distance[k]=input.nextInt();
    }

    int i=0,j=2;
    long res=0L;
    long mod=99997867;
    while(i<numBuilding-2){
    while(j>=i+2&&j<numBuilding&&(distance[j]-distance[i])<=maxLength){
    j+=1;
    }
    res+=(long)(j-i-1)*(long)(j-i-2)/2;
    i+=1;
    }
    System.out.println(res%mod);
    }
    }

雀魂启动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.util.*;

"""
回溯遍历
假如摸到某张牌 然后去判断是否能胡
判断是否能胡:
遍历 若该牌为雀头 是否能胡
若该牌为刻子 是否能胡
若该牌为顺子 是否能胡
最后若待匹配的牌为0 则能胡
"""
public class Main {

private void sln() {
Scanner sc = new Scanner(System.in);
int[] state = new int[9]; //手上拥有的牌
int[] helpArr = new int[9];
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < 13; i++) {
int num = sc.nextInt();
state[num - 1]++;
}
for (int i = 0; i < 9; i++) {
if (state[i] < 4) {
int num = i + 1;
System.arraycopy(state, 0, helpArr, 0, 9);
helpArr[i]++; //假如是摸到牌num
if (canHu(helpArr, 14, false)) res.add(num);
}
}
if (res.isEmpty()) System.out.println(0);
else {
StringBuffer sbf = new StringBuffer();
sbf.append(res.get(0));
for (int i = 1; i < res.size(); i++) {
sbf.append(" ");
sbf.append(res.get(i));
}
System.out.println(sbf.toString());
}
}
"""
arr 手上待匹配的牌
total 待匹配的牌数
hasHead 雀头已有
"""
private boolean canHu(int[] arr, int total, boolean hasHead) {
if (total == 0) return true;
if (!hasHead) {
for (int i = 0; i < 9; i++) {
if (arr[i] >= 2) {
arr[i] -= 2; //i+1为雀头
if (canHu(arr, total - 2, true)) return true;
arr[i] += 2; //撤销选择
}
}
return false;
} else {
for (int i = 0; i < 9; i++) {
if (arr[i] > 0) {
if (arr[i] >= 3) {
arr[i] -= 3; //作为刻子
if (canHu(arr, total - 3, true)) return true;
arr[i] += 3;
}
if (i + 2 < 9 && arr[i + 1] > 0 && arr[i + 2] > 0) {
arr[i]--;
arr[i + 1]--;
arr[i + 2]--;//作为顺子
if (canHu(arr, total - 3, true)) return true;
arr[i]++;
arr[i + 1]++;
arr[i + 2]++;
}
}
}
}
return false;
}

public static void main(String[] args) {
new Main().sln();
}
}

链表k反转

  1. 题目描述
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    """
    头插法
    按块反转
    pre是前一块最后的节点
    cur指向本块最后一个节点
    cur.next==temp
    temp是待头插节点

    """
    import java.util.*;

    /*
    * public class ListNode {
    * int val;
    * ListNode next = null;
    * }
    */

    public class Solution {
    /**
    *
    * @param head ListNode类
    * @param k int整型
    * @return ListNode类
    */
    public ListNode reverseKGroup (ListNode head, int k) {
    // write code here
    if(head==null||k==1||head.next==null) return head;
    ListNode pc=head;
    int len=0;
    while(pc!=null){
    len+=1;
    pc=pc.next;
    }
    ListNode p=new ListNode(-1);
    p.next=head;
    ListNode pre=p;
    ListNode cur=head;
    ListNode temp;
    for(int i=0;i<len/k;i++){
    for(int j=1;j<k;j++){
    temp=cur.next;
    cur.next=temp.next;
    temp.next=pre.next;
    pre.next=temp; //头插法

    }
    pre=cur;
    cur=cur.next;
    }
    return p.next;

    }
    }

判断链表是否有环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null||head.next==null||head.next.next==null) return false;
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(slow==fast) return true;
}
return false;
}
}

去重+排序 —TreeSet

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in =new Scanner(System.in);
while(in.hasNext()){
int len=in.nextInt();
Set<Integer> set=new TreeSet<>();
for(int i=0;i<len;i++){
int num=in.nextInt();
set.add(num);
}
set.forEach((T)->{System.out.println(T);});

}
}
}

十六进制转十进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in =new Scanner(System.in);
while(in.hasNext()){
String s=in.nextLine();
int len=s.length();
int res=0;
int t;
for(int i=2;i<len;i++){
char temp=s.charAt(i);
if(temp>='A') t=temp-'A'+10; //A--F
else t=temp-'0'; //0123456789
res=res*16+t;
}
System.out.println(res);
}
}
}

leecode 27 移除元素

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
left为不含val的数组右侧下标
假如遍历到的idx>left代表中间有val,那就移动idx的元素到left
"""
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
for(int i = 0;i<nums.length;i++){
if(nums[i]==val){
continue;
}
if(i>left){
nums[left] = nums[i];
}
left++;
}
return left;
}
}

leecode 45 跳跃游戏

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int jump(int[] nums) {
int step = 0;
int maxJumpedIdx = 0;
int end = 0;
for(int i = 0; i < nums.length-1; i++){
maxJumpedIdx = Math.max(maxJumpedIdx, i+nums[i]); //更新本次可跳范围内的最新的最远可跳范围 也就是下一个新的起跳点
if(i==end){ //到达下一个起跳点 也就是跳了一次
end = maxJumpedIdx;
step+=1;
}
}
return step;
}
}

leecode 55 跳跃游戏

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public boolean canJump(int[] nums) {
int maxJumpIdx = 0; //最大可跳跃位置
for(int i = 0;i<nums.length-1;i++){
if(i>maxJumpIdx) return false; //若当前i已是不可到达的,则最后一个位置必不可能到达
if(maxJumpIdx>=nums.length-1) return true; //若最后一个位置已在可达范围内
maxJumpIdx = Math.max(maxJumpIdx, i+nums[i]); //更新最大可达位置
}
return maxJumpIdx>=nums.length-1;
}
}

leecode 76 跳跃游戏

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
"""
滑动窗口
"""
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>(); //存t中字母分布情况 字母,次数
Map<Character, Integer> window = new HashMap<>(); //存滑动窗口中字母分布情况
int valid = 0,len = Integer.MAX_VALUE; //valid 已匹配字母个数, len 满足条件的滑动窗口的最小值
for(char c : t.toCharArray()){
need.put(c, need.getOrDefault(c,0)+1);
}
int start = 0, left=0, right = 0; //start 满足条件的最小滑动窗口的起始下标 left 滑动窗口起始下标 right 滑动窗口终止下标
while(right<s.length()){ //向右移
char c = s.charAt(right);
right+=1;
if(need.containsKey(c)){ //遇到需要的字母才更新
int c_count = window.getOrDefault(c, 0) + 1;
window.put(c, c_count);
if(c_count == need.get(c)){ //若该字母所需的个数与滑动窗口中已有的个数相等,那么该字母已满足匹配 valid+1
valid += 1;
}
}
// 已满足所有字母数量,接下来需要缩小滑动窗口,left向左移
while(need.size()==valid){
if(right-left<len){
start = left;
len = right-left;
}
char cl = s.charAt(left);
left++;
if(need.containsKey(cl)){ //要移除需要的字母才更新
// 只有临界的时候 valid才需要减1 存在window中字母的个数大于need的情况,这种不用减
if(window.get(cl).equals(need.get(cl))){
valid-=1;
}
window.put(cl, window.get(cl)-1);
}
}
}
return len==Integer.MAX_VALUE?"":s.substring(start, start+len);
}
}

leecode 123 买卖股票的最佳时机

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
"""
分为k要遍历和 不需要遍历(0、1、无穷)
k=2
动态规划
fb first buy
sb second buy
"""
class Solution {
public int maxProfit(int[] prices) {
int fb = Integer.MIN_VALUE, fs=0;
int sb = Integer.MIN_VALUE, ss=0;
for(int price:prices){
fb = Math.max(fb, -price);
fs = Math.max(fs, fb + price);
sb = Math.max(sb, fs - price);
ss = Math.max(ss, sb + price);
}
return ss;
}
}

class Solution {
public int maxProfit(int[] prices) {
int k=2;
int len=prices.length;
if(len<1) return 0;
int[][][] dp = new int[prices.length][k+1][2];
for (int i = 0; i < prices.length; i++) {
for (int i1 = 0; i1 <= k; i1++) {
// 初始化
if(i==0){
dp[0][i1][0] = 0;
dp[0][i1][1] = -prices[0];
continue;
}
if(i1==0){
dp[i][0][0] = 0;
dp[i][0][1] = -prices[i];
continue;
}
//状态转移
dp[i][i1][0] = Math.max(dp[i-1][i1][0], dp[i-1][i1][1]+prices[i]);
dp[i][i1][1] = Math.max(dp[i-1][i1][1], dp[i][i1-1][0]-prices[i]);
}
}
return dp[prices.length-1][k][0];
}
}


"""
k笔 0 <= k <= 100
交易次数 k 最多有多⼤呢?
⼀次交易由买⼊和卖出构成,⾄少需要两天。所以说有效的限制 k 应该不超过 n/2,如果超过,就没有约束作⽤了,相当于 k = +infinity。这种情况是之前解决过的。
"""
class Solution {
public int maxProfit(int k, int[] prices) {
int len=prices.length;
if(len<1) return 0;
if (k>len/2) return maxProfit_infi(prices);
// 相当于k=2的情况
int[][][] dp = new int[prices.length][k+1][2];
for (int i = 0; i < prices.length; i++) {
for (int i1 = 0; i1 <= k; i1++) {
// 初始化
if(i==0){
dp[0][i1][0] = 0;
dp[0][i1][1] = -prices[0];
continue;
}
if(i1==0){
dp[i][0][0] = 0;
dp[i][0][1] = -prices[i];
continue;
}
//状态转移
dp[i][i1][0] = Math.max(dp[i-1][i1][0], dp[i-1][i1][1]+prices[i]);
dp[i][i1][1] = Math.max(dp[i-1][i1][1], dp[i][i1-1][0]-prices[i]);
}
}
return dp[len-1][k][0];

}
// k = +infinity
public int maxProfit_infi(int[] prices) {
int[] dp = new int[2];
dp[0] = 0;
dp[1] = -prices[0];
for (int price : prices) {
dp[0] = Math.max(dp[0],dp[1]+price);
dp[1] = Math.max(dp[1],dp[0]-price);
}
return dp[0];
}
}
"""
动态规划
k无穷+手续费
第i天手上没有股票的最大利润=max(第i-1天没有股票的最大利润,第i-1天有股票的最大利润+第i天买了股票赚的钱(股票价格-手续费)
第i天手上有股票的最大利润=max(第i-1天有股票的最大利润,第i-1天没有股票的最大利润-第i天买股票的钱(股票价格)
"""
class Solution {
public int maxProfit(int[] prices, int fee) {
int have=-prices[0];
int nohave=0;
for(int i=1;i<prices.length;i++){
int temp=have;
have=Math.max(have,nohave-prices[i]);
nohave=Math.max(nohave,temp+prices[i]-fee);
}
return nohave;
}
}

leecode 309 买卖股票的最佳时机含冷冻期

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
k = +infinity 并且含有冷冻期
动态规划
今天买入的 = max(昨天买入的,前天卖出的-今天的价格)
今天卖出的 = max(昨天卖出的,昨天买入的+今天的价格)
"""
class Solution {
public int maxProfit(int[] prices) {
int lb = Integer.MIN_VALUE, ls = 0;
int ps = 0;// 前天卖出
for(int price : prices){
int temp = ls; //昨天卖出
lb = Math.max(lb, ps-price);
ls = Math.max(ls, lb+price);
ps = temp;
}
return ls;
}
}

leecode 139 单词拆分

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
dp[i] 转移条件 dp[j]==true 并且 子串[j,i]存在于单词表中(遍历j)
"""
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length()+1];
Arrays.fill(dp, false);
dp[0] = true;
for(int i=1;i<=s.length();i++){
for(int j=i-1;j>=0;j--){
if(dp[j] && wordDict.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}

leecode 152 乘积最大子数组

一、问题描述

题目描述
解题思路

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int maxProduct(int[] nums) {
int mxNum = nums[0], minNum = nums[0], res = nums[0];
for(int i = 1; i<nums.length; i++){
int tmpMax = mxNum, tmpMin = minNum;
mxNum = Math.max(tmpMax*nums[i], Math.max(tmpMin*nums[i], nums[i]));
minNum = Math.min(tmpMin*nums[i], Math.min(tmpMax*nums[i], nums[i]));
res = Math.max(res, mxNum);
}
return res;
}
}

leecode 207 课程表

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
"""
有向图判断是否有环 邻接表存
"""
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 初始化
int[] indegrees = new int[numCourses]; //入度表
Arrays.fill(indegrees, 0);
Queue<Integer> queue = new LinkedList<>();
List<List<Integer>> adjList = new ArrayList<>();
for(int i = 0;i<numCourses;i++){
adjList.add(new ArrayList<>());
}
for(int[] rel : prerequisites){
indegrees[rel[0]]++;
adjList.get(rel[1]).add(rel[0]);
}

// 目前可以修的课程,即入度为0
for(int i = 0;i<indegrees.length;i++){
if(indegrees[i]==0) queue.add(i);
}
// BFS 遍历
while(!queue.isEmpty()){
int nowClass = queue.poll();
numCourses-=1;
for(int nextClass : adjList.get(nowClass)){
indegrees[nextClass]-=1;
if(indegrees[nextClass]==0) queue.add(nextClass);
}
}

return numCourses==0;
}
}

leecode 292 Nim游戏

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
'''
要赢的话 你必须要拿到n-4 n-8 n-4*k
所以当n-4*k==0时 代表你必须要拿到第0颗石子 但你是先手 你拿到的必是第一颗石子 必失败 于是当石子个数为4的倍数的时候 你必输
堆中恰好有四块石头,你就会失败。因为在这种情况下不管你取走多少石头,总会为你的对手留下几块,使得他可以在游戏中打败你。因此,要想获胜,在你的回合中,必须避免石头堆中的石子数为 4 的情况。

同样地,如果有五块、六块、或是七块石头,你可以控制自己拿取的石头数,总是恰好给你的对手留下四块石头,使他输掉这场比赛。但是如果石头堆里有八块石头,你就不可避免地会输掉,因为不管你从一堆石头中挑出一块、两块还是三块,你的对手都可以选择三块、两块或一块,以确保在再一次轮到你的时候,你会面对四块石头。

'''
class Solution {
public boolean canWinNim(int n) {
return n%4!=0;
}
}

leecode 300 最长递增子序列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
'''
1、动态规划
dp[i] 为考虑前 i 个元素,以第 i 个数字结尾的最长上升子序列的长度,注意 nums[i] 必须被选
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
整个数组的最长上升子序列即所有dp[i] 中的最大值。
'''
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}

"""
贪心 + 二分
维护一个数组 d[i] ,表示长度为 ii 的最长上升子序列的末尾元素的最小值,用 len 记录目前最长上升子序列的长度,起始时 len 为 1,d[1]=nums[0]。
无序列表最关键的一句在于: 数组 d[i]表示长度为 i 的最长上升子序列的末尾元素的最小值,即在数组 1,2,3,4,5,6中长度为3的上升子序列可以为 1,2,3也可以为 2,3,4等等但是d[3]=3,即子序列末尾元素最小为3。

设当前已求出的最长上升子序列的长度为len(初始时为 11),从前往后遍历数组nums,在遍历到nums[i] 时:

如果nums[i]>d[len] ,则直接加入到 d 数组末尾,并更新 len=len+1;
否则,在 dd 数组中二分查找,找到第一个比nums[i] 小的数d[k] ,并更新 d[k+1]=nums[i]
"""

leecode 322 零钱兑换

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
'''
动态规划
dp[i] 代表凑成总金额i所需的 最少的硬币个数
有转移方程:

'''
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, amount+1);
dp[0] = 0;
for(int i=1;i<=amount;i++){
for(int j=0;j<coins.length;j++){
if(i>=coins[j]){
dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount]>amount?-1:dp[amount];
}
}

leecode 319 灯泡游戏

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
也就是第一轮 切换全部开关
第二轮 切换为2的倍数的开关
第二轮 切换为3的倍数的开关
。。。
即每个开关会被切换k次 k为该开关的因子个数
比如第6个开关会被切换4次 最终为关闭状态 (1,2,3,6)
所以最终亮着的灯泡的特征是因子个数为奇数
也就是存在平方根 比如9(1,3,9)
那n有几个这样的数呢 有sqrt(n)个---(1*1,2*2,...,sqrt(n)*sqrt(n))
'''
class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
}

leecode 331 验证二叉树的前序序列化

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
二叉树的根节点入度为0,出度为2
非叶子节点 入度为1 出度为2
叶子节点 入度为1 出度为0
所有节点的入度和==出度和
'''
class Solution {
public boolean isValidSerialization(String preorder) {
int diff = 1;
String[] arr = preorder.split(",");
for(int i = 0; i < arr.length; i++){
diff-=1;
if(diff<0) return false;
if(!arr[i].equals("#")){
diff+=2;
}
}
return diff == 0;
}
}

leecode 394 字符串解码

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
'''
字符串栈 存 待重复字符串
数字栈 存 重复次数
遇到[时入栈
遇到]时
'''
class Solution {
public String decodeString(String s) {
Stack<String> strStack = new Stack<>();
Stack<Integer> numStack = new Stack<>();
StringBuilder str = new StringBuilder();
int mulit = 0;
for(char c : s.toCharArray()){
if(Character.isDigit(c)){
mulit = mulit*10+c-'0'; //重复次数
}else if(Character.isLetter(c)){ //待重复字符串
str.append(c);
}else if(c=='[') { //将其他字符串入栈
strStack.push(str.toString());
str = new StringBuilder(); //清空str 因为[之后是待本框内的待重复字符串
numStack.push(mulit); //本框的重复次数
mulit = 0;//清零 用于下一个重复次数
}
else {
// 此时的str代表[]内的待重复字符串
int count = numStack.pop();
StringBuilder tmpStr = new StringBuilder();
tmpStr.append(strStack.pop());
while(count>0){
tmpStr.append(str.toString());
count--;
}
str = tmpStr; //代表外一层[]内的待重复字符串 解码了一层[]的字符串
}
}
return str.toString();
}
}

leecode 413 等差数列划分

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
'''
这道题主要是需要找到其规律,从小的例子出发,仔细观察,会发现当整个数组为(1, 2, 3, 4, 5, 6)的时候,
我们先取出前三个,(1, 2, 3)的等差数列的个数为1,
(1, 2, 3, 4)的等差数列的个数为3,
(1, 2, 3, 4, 5)的等差数列的个数为6,
(1, 2, 3, 4, 5, 6)的等差数列个数为10,
以此类推我们可以很容易的发现在一个等差数列中加入一个数字,如果还保持着等差数列的特性,每次的增量都会加1,如果刚加进来的数字与原先的序列构不成等差数列,就将增量置为0,接下来继续循环,执行以上的逻辑即可.
'''
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
if(nums.length<3) return 0;
int res = 0;
int add = 0;
for(int i = 1;i<nums.length-1;i++){
if(nums[i]-nums[i-1]==nums[i+1]-nums[i]){
res+= (++add);
}else{
add = 0;
}
}
return res;
}
}

leecode 438 找到字符串中所有字母异位词

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
''' 
滑动窗口
'''
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for(char c : p.toCharArray()){
need.put(c, need.getOrDefault(c, 0)+1);
}
int left = 0, right = 0, valid=0;
while(right<s.length()){
char cr = s.charAt(right);
if(need.containsKey(cr)){
window.put(cr, window.getOrDefault(cr, 0)+1);
if(window.get(cr).equals(need.get(cr))){
valid+=1;
}
}
right++;
while(right-left>=p.length()){
if(valid==need.size()){ //找到之后添加
res.add(left);
}
char cl = s.charAt(left); //继续向右滑
if(need.containsKey(cl)){
if(need.get(cl).equals(window.get(cl))){
valid-=1;
}
window.put(cl, window.get(cl)-1);
}
left++;
}
}
return res;
}
}

leecode 516 最长回文子序列

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
'''
动态规划
if (s[i] == s[j])
// 它俩一定在最长回文子序列中
dp[i][j] = dp[i + 1][j - 1] + 2;
else
// s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长?
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

'''
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] dp = new int[len][len];
for(int i =len - 1 ;i>=0;i--){
dp[i][i] = 1;
for(int j = i+1;j<len;j++){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1] + 2;
}else{
dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
}
}
}
return dp[0][len-1];
}
}

leecode 567 字符串的排列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
''' 
滑动窗口
'''
class Solution {
public boolean checkInclusion(String s1, String s2) {
Map<Character,Integer> needMap = new HashMap<Character,Integer>();
Map<Character,Integer> windowsMap = new HashMap<Character,Integer>();
//将目标字符串的所有字符记录到needMap中
for(char c : s1.toCharArray()){
needMap.put(c,needMap.getOrDefault(c,0)+1);
}
//记录窗口的左右边界
int left = 0,right = 0;
//记录窗口中符合needMap条件的字符数量
int valid = 0;
while(right <s2.length()){
//找到入窗口的元素
char c = s2.charAt(right);
//右移窗口
right++;
//更新窗口内的数据
if(needMap.containsKey(c)){
windowsMap.put(c,windowsMap.getOrDefault(c,0)+1);
//如果该字符全部被涵盖,则valid加一
if(windowsMap.get(c).equals(needMap.get(c))){
valid++;
}
}
//判断左侧窗口是否需要收缩 right自增过一次大于窗口的右边界
while(right - left >= s1.length()){
if(valid == needMap.size()){
return true;
}
//找到出窗口的元素
char d = s2.charAt(left);
//窗口右移
left++;
//更新窗口中的数据
if(windowsMap.containsKey(d)){
if(windowsMap.get(d).equals(needMap.get(d))){
valid--;
}
windowsMap.put(d,windowsMap.getOrDefault(d,0)-1);
}
}
}
return false;
}
}

leecode 583 两个字符串的删除操作

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
动态规划
'''
public class Solution {
public int minDistance(String s1, String s2) {
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
for(int i=0;i<s1.length()+1;i++){
for(int j=0;j<s2.length()+1;j++){
if(i==0||j==0){
dp[i][j] = i+j;
}else if(s1.charAt(i-1)==s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];
else dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+1;
}
}
return dp[s1.length()][s2.length()];
}
}

leecode 684 冗余连接 并查集

一、问题描述

题目描述
题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int[] parent = new int[edges.length+1];
for(int i=1;i<edges.length;i++){ //1~N节点
parent[i] = i;
}
int[] res = new int[2];
for(int[] curEdge : edges){
if(find(parent, curEdge[0])==find(parent, curEdge[1])){
// 假如连通,保存该边,因为要求如果有多个答案,则返回数组 edges 中最后出现的边。
res[0] = curEdge[0];
res[1] = curEdge[1];
}else{
// 假如不连通,则加该边,将其连通
union(parent, curEdge[0], curEdge[1]);
}
}
return res;

}
// 找到其连通的根节点
private int find(int[] parent, int index){
if(parent[index]!=index){
return find(parent, parent[index]);
}
return index;
}

// 合并两个连通分量,即将一个分量的根节点的父节点设为另一个分量的根节点
private void union(int[] parent, int node1, int node2){
int parent1 = find(parent, node1);
int parent2 = find(parent, node2);
if(parent1 != parent2){
parent[parent1] = parent2;
}
}
}

leecode 785 二分图

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public boolean isBipartite(int[][] graph) { // 邻接矩阵存储图
int[] colors = new int[graph.length]; // 记录节点染色情况
Arrays.fill(colors, -1);
for (int i = 0; i < graph.length; i++) { // 处理图不是连通的情况
if (colors[i] == -1 && !isBipartite(i, 0, colors, graph)) {
return false;
}
}
return true;
}

private boolean isBipartite(int curNode, int curColor, int[] colors, int[][] graph) {
if (colors[curNode] != -1) {
return colors[curNode] == curColor;
}
colors[curNode] = curColor;
for (int nextNode : graph[curNode]) {
if (!isBipartite(nextNode, 1 - curColor, colors, graph)) {
return false;
}
}
return true;
}

leecode 1312 让字符串成为回文串的最少插入次数

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
"""
当前字符串要变成回文,那只要把不一样的找出来就好了.即:求出反过来的字符串和当前字符串的最长公共子序列,然后减一下.
"""
class Solution {
public int minInsertions(String s) {
int len = s.length();
int[][] dp = new int[len][len];
for(int i =len - 1 ;i>=0;i--){
dp[i][i] = 1;
for(int j = i+1;j<len;j++){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i+1][j-1] + 2;
}else{
dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
}
}
}
return len - dp[0][len-1];
}
}

例1、二进制手表

例2、N皇后问题

例3、全排列

例4、搜索

例5、将数组拆分成斐波那契数列

例1、二进制手表

github 401题

一、问题描述

题目描述

使用回溯算法

一般:

dfs(全部可取节点borad,当前节点下标ij,节点状态visited,目标路径,path,已走到路径的下标idx)

参考了labuladong大佬的算法框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return

for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

private void backtrack("原始参数") {
//终止条件(递归必须要有终止条件)
if ("终止条件") {
//一些逻辑操作(可有可无,视情况而定)
return;
}

for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
//一些逻辑操作(可有可无,视情况而定)

//做出选择

//递归
backtrack("新的参数");
//一些逻辑操作(可有可无,视情况而定)

//撤销选择
}
}

作者:sdwwld
链接:https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/solution/javahui-su-suan-fa-tu-wen-xiang-jie-ji-b-vg5z/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

框架链接

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution(object):
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
nums=[8,4,2,1,32,16,8,4,2,1] #前四个是时 后6个是分
self.res=[]
track=[] #存所选的led灯下标i,nums[i]即为对应的数
def backtrack(nums,track,num):
if len(track)==num:
h=0
f=0
for i in track:
if i <=3:
h+=nums[i] #时
else:
f+=nums[i] #分
if f<10: #进行分钟上的补零
temp=str(h)+":0"+str(f)
else:
temp=str(h)+":"+str(f)
self.res.append(temp)
return
for i in range(len(nums)):
if not isValid(track,i):
continue
track.append(i)
backtrack(nums,track,num)
track.pop()
def isValid(track,i): #判断合理性
if track==[]:
return True
if i <=track[-1]: #8,9 和 9,8表示的时间一致 所以只取8,9
return False
res=0
if i<=3:
for j in track:
if j<=3:
res+=nums[j]
res+=nums[i]
if res<12: #时针合理性
return True
else:
return False
else:
for j in track:
if j>3:
res+=nums[j]
res+=nums[i]
if res<60: #分针合理性
return True
else:
return False
backtrack(nums,track,num)
return self.res

例2、N皇后问题

github 51题

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {

List<List<String>> res = new ArrayList<>();

/* 输入棋盘的边长n,返回所有合法的放置 */
public List<List<String>> solveNQueens(int n) {
// "." 表示空,"Q"表示皇后,初始化棋盘
char[][] board = new char[n][n];
for (char[] c : board) {
Arrays.fill(c, '.');
}
backtrack(board, 0);
return res;
}

public void backtrack(char[][] board, int row) {
// 每一行都成功放置了皇后,记录结果
if (row == board.length) {
res.add(charToList(board));
return;
}

int n = board[row].length;
// 在当前行的每一列都可能放置皇后
for (int col = 0; col < n; col++) {
// 排除可以相互攻击的格子
if (!isValid(board, row, col)) {
continue;
}
// 做选择
board[row][col] = 'Q';
// 进入下一行放皇后
backtrack(board, row + 1);
// 撤销选择
board[row][col] = '.';
}
}

/* 判断是否可以在 board[row][col] 放置皇后 */
public boolean isValid(char[][] board, int row, int col) {
int n = board.length;
// 检查列是否有皇后冲突
for (int i = 0; i < n; i++) {
if (board[i][col] == 'Q') {
return false;
}
}

// 检查右上方是否有皇后冲突
for (int i = row - 1, j = col + 1; i >=0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}

// 检查左上方是否有皇后冲突
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}

public List charToList(char[][] board) {
List<String> list = new ArrayList<>();
for (char[] c : board) {
list.add(String.valueOf(c));
}
return list;
}
}

例3、全排列

一、问题描述

给定n,返回n的全排列

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
int[] visited=new int[nums.length];
backtrace(res,new ArrayList<>(),nums,visited);
return res;
}
public void backtrace(List<List<Integer>> res,List<Integer> path,int[] nums,int[] visited){
if(path.size()==nums.length){
res.add(new ArrayList<>(path));
return;
}
for(int i=0;i<nums.length;i++){
if(visited[i]==1) continue;
path.add(nums[i]);
visited[i]=1;
backtrace(res,path,nums,visited);
path.remove(path.size()-1);
visited[i]=0;
}
}
}

47_1 全排列II

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
"""
回溯+剪枝
private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res)
int[] nums:输入的待排列数组
int len:最终终止时数组长度
int depth:目前数组的长度
boolean[] used:记录哪些数字被使用过 使用过true 没使用过false
path:记录已选的数字
res:记录全部结果
"""
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
// 排序(升序或者降序都可以),排序是剪枝的前提
Arrays.sort(nums);
boolean[] used = new boolean[len];
// 使用 Deque 是 Java 官方 Stack 类的建议
Deque<Integer> path = new ArrayDeque<>(len);
dfs(nums, len, 0, used, path, res);
return res;
}

private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {
if (depth == len) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < len; ++i) {
if (used[i]) {
continue;
}
// 剪枝条件:i > 0 是为了保证 nums[i - 1] 有意义
// 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
path.addLast(nums[i]);
used[i] = true;
dfs(nums, len, depth + 1, used, path, res);
// 回溯部分的代码,和 dfs 之前的代码是对称的
used[i] = false;
path.removeLast();
}
}
}

### 剑指 Offer 38 字符串的全排列
#### 一、问题描述
![题目描述](剑指offer/38.png)
#### 二、具体代码
```Java
"""
回溯+剪枝
"""
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
public String[] permutation(String s) {
int len = s.length();
if (len == 0) {
return new String[0];
}
// 转换成字符数组是常见的做法
char[] charArr = s.toCharArray();
// 排序是为了去重方便
Arrays.sort(charArr);
// 由于操作的都是字符,使用 StringBuilder
StringBuilder path = new StringBuilder();
boolean[] used = new boolean[len];

// 为了方便收集结果,使用动态数组
List<String> res = new ArrayList<>();
dfs(charArr, len, 0, used, path, res);

// 记得转成字符串数组
return res.toArray(new String[0]);
}

/**
* @param charArr 字符数组
* @param len 字符数组的长度
* @param depth 当前递归深度
* @param used 当前字符是否使用
* @param path 从根结点到叶子结点的路径
* @param res 保存结果集的变量
*/
private void dfs(char[] charArr,
int len,
int depth,
boolean[] used,
StringBuilder path,
List<String> res) {
if (depth == len) {
// path.toString() 恰好生成了新的字符对象
res.add(path.toString());
return;
}
for (int i = 0; i < len; i++) {
if (!used[i]) {
if (i > 0 && charArr[i] == charArr[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
path.append(charArr[i]);

dfs(charArr, len, depth + 1, used, path, res);

// 递归完成以后,需要撤销选择,递归方法执行之前做了什么,递归方法执行以后就需要做相应的逆向操作
path.deleteCharAt(path.length() - 1);
used[i] = false;
}
}
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
## 例4、搜索 
### 一、问题描述
![题目描述](Backtrack/search.png)
### 二、具体代码

```Python
class Solution:
def exist(self, board, word):
def check(i, j, k): #判断从(i,j)处开始搜索 能否匹配到word[k:]
if board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True

visited.add((i, j))
result = False
for di, dj in directions:
newi, newj = i + di, j + dj
if 0 <= newi < len(board) and 0 <= newj < len(board[0]):
if (newi, newj) not in visited:
if check(newi, newj, k + 1):
result = True
break

visited.remove((i, j))
return result

directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
h, w = len(board), len(board[0])
visited = set()
for i in range(h):
for j in range(w):
if check(i, j, 0):
return True

return False

例5、将数组拆分成斐波那契数列

一、问题描述

题目描述

二、具体代码

问题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
"""
回溯
"""
public List<Integer> splitIntoFibonacci(String S) {
List<Integer> res = new ArrayList<>();
backtrack(S.toCharArray(), res, 0);
return res;
}

public boolean backtrack(char[] digit, List<Integer> res, int index) {
//边界条件判断,如果截取完了,并且res长度大于等于3,表示找到了一个组合。
if (index == digit.length && res.size() >= 3) {
return true;
}
for (int i = index; i < digit.length; i++) {
//两位以上的数字不能以0开头
if (digit[index] == '0' && i > index) {
break;
}
//截取字符串转化为数字
long num = subDigit(digit, index, i + 1);
//如果截取的数字大于int的最大值,则终止截取
if (num > Integer.MAX_VALUE) {
break;
}
int size = res.size();
//如果截取的数字大于res中前两个数字的和,说明这次截取的太大,直接终止,因为后面越截取越大
if (size >= 2 && num > res.get(size - 1) + res.get(size - 2)) {
break;
}
if (size <= 1 || num == res.get(size - 1) + res.get(size - 2)) {
//把数字num添加到集合res中
res.add((int) num);
//如果找到了就直接返回
if (backtrack(digit, res, i + 1)) //1确定 继续后面的分
return true;
//如果没找到,就会走回溯这一步,然后把上一步添加到集合res中的数字给移除掉
res.remove(res.size() - 1); //1排除 尝试12
}
}
return false;
}

//相当于截取字符串S中的子串然后转换为十进制数字
private long subDigit(char[] digit, int start, int end) {
long res = 0;
for (int i = start; i < end; i++) {
res = res * 10 + digit[i] - '0';
}
return res;
}

每日一题 0926 路径总和 II

每日一题 0927 二叉搜索树的最近公共祖先

每日一题 0928 填充每个节点的下一个右侧节点指针II

每日一题 0930 二叉搜索树中的插入操作

每日一题 1009 环形链表

每日一题 1010 环形链表II

每日一题 1011 分割等和子集

每日一题 1014 查找常用字符

每日一题 1016 有序数组的平方

每日一题 1126 最大间距

每日一题 1127 四数相加||

每日一题 1130 重构字符串

每日一题 1201 重构字符串

每日一题 1202 拼接最大数

每日一题 1203 计数质数

每日一题 1204 分割数组为连续子序列

每日一题 1206 杨辉三角

每日一题 1207 杨辉三角

每日一题 1208 将数组拆分成斐波那契数列

每日一题 1209 不同路径

每日一题 1210 柠檬水找零

每日一题 1211 Dota2 参议院

每日一题 1212 摆动序列

每日一题 1213 存在重复元素

每日一题 1214 字母异位词分组

每日一题 1215 单调递增的数字

每日一题 1216 单词规律

每日一题 1217 买卖股票的最佳时机含手续费

每日一题 1218 找不同

每日一题 1219 旋转图像

每日一题 1221 使用最小花费爬楼梯

每日一题 1222 二叉树的锯齿形层序遍历

每日一题 1224 分发糖果

每日一题 1225 分发饼干

每日一题 1226 最大矩形

每日一题 1227 同构字符串

每日一题 1228 买卖股票的最佳时机

每日一题 1229 按要求补齐数组

每日一题 1230 最后一块石头的重量

每日一题 0102 滑动窗口最大值

每日一题 0103 分割链表

每日一题 0104 斐波那契数列

每日一题 0105 较大分组的位置

每日一题 0106 除法求值

每日一题 0107 省份数量

每日一题 0108 旋转数组

每日一题 0110 旋转数组

每日一题 0115 移除最多的同行或同列石头

每日一题 0122 旋转数组

每日一题 0201 公平的糖果棒交换

每日一题 0228 公平的糖果棒交换

每日一题 0301 公平的糖果棒交换

每日一题 0302 公平的糖果棒交换

每日一题 0303 比特位计数

每日一题 0304 俄罗斯套娃信封问题

每日一题 0926 二叉树中和为某一值的路径

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'''
dfs到每个叶子节点 判断路径和是否等于sum
'''
class Solution(object):
def pathSum(self, root, sum):
self.path=[]
self.res=[]
def dfs(root,sum):
if root==None:
return
self.path.append(root.val) #选择root这条路,路径和
sum-=root.val
if root.left==None and root.right==None and sum==0:
self.res.append(list(self.path)) #记得把一个list的内容赋给另一个list,需要强制类型转换
dfs(root.left,sum)
dfs(root.right,sum)
self.path.pop() #不选择root这条路
dfs(root,sum)
return self.res

每日一题 0927 二叉搜索树的最近公共祖先

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
若根节点的值在两个节点中间,则根节点为最近公共祖先
若根节点大于两者的最大值,则最近公共祖先在根节点的右子树中
反之 小于最小值,在左子树中
'''
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
m=p.val
n=q.val
if root==p or root==q:
return root
if root.val < min(m,n):
return self.lowestCommonAncestor(root.right,p,q)
elif root.val >max(m,n):
return self.lowestCommonAncestor(root.left,p,q)
else:
return root

每日一题 0928 填充每个节点的下一个右侧节点指针II

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
'''
每次遍历当前层时记录下一层的节点总数 省一个栈的层序遍历
'''
class Solution(object):
def connect(self, root):
if root==None:
return None
stack=[root]
now_count=1 #当前层所剩未遍历节点
next_count=0 #下一层的所有节点数
while stack:
p=stack.pop(0) #每行的第一个结点
now_count-=1
if p.left:
stack.append(p.left)
next_count+=1
if p.right:
stack.append(p.right)
next_count+=1
while now_count>0:
cur=stack.pop(0)
p.next=cur #构建next关系
p=cur
now_count-=1
if p.left:
stack.append(p.left)
next_count+=1
if p.right:
stack.append(p.right)
next_count+=1
now_count=next_count
next_count=0
return root

每日一题 0930 二叉搜索树中的插入操作

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
'''
每次遍历当前层时记录下一层的节点总数 省一个栈的层序遍历
'''
class Solution(object):
def insertIntoBST(self, root, val):
if root==None:
root=TreeNode(val)
else:
if root.val<val:
root.right=self.insertIntoBST(root.right,val)
else:
root.left=self.insertIntoBST(root.left,val)
return root

每日一题 1009 环形链表

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
'''
快慢指针
我们定义两个指针,一快一满。慢指针每次只移动一步,而快指针每次移动两步。
初始时,慢指针在位置 head,而快指针在位置 head.next。这样一来,如果在移动的过程中,快指针反过来追上慢指针,就说明该链表为环形链表。否则快指针将到达链表尾部,该链表不为环形链表。

'''
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head or not head.next:
return False
slow=head
fast=head.next
while slow!=fast:
if not fast or not fast.next:
return False
slow=slow.next
fast=fast.next.next
return True

每日一题 1010 环形链表II

一、问题描述

题目描述
求解思路

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
'''
快慢指针
分两步,第一步利用快慢指针判断是否是环形链表:
我们定义两个指针,一快一满。慢指针每次只移动一步,而快指针每次移动两步。
初始时,慢指针,快指针在位置 head,这样一来,如果在移动的过程中,快指针反过来追上慢指针,就说明该链表为环形链表。否则快指针将到达链表尾部,该链表不为环形链表。
第二步是找环形的第一个节点:
当发现 slow 与 fast 相遇时,我们再额外使用一个指针ptr。起始,它指向链表头部;随后,它和slow 每次向后移动一个位置。最终,它们会在入环点相遇。

'''
class Solution(object):
def detectCycle(self, head):
if not head or not head.next:
return None
slow=head
fast=head
while slow.next and fast.next and fast.next.next and slow.next!=fast.next.next: #判断是否是环形链表 停在第一个相遇处 slow.next就是相遇点
slow=slow.next
fast=fast.next.next
if slow.next==None or fast.next==None or fast.next.next==None :
return None #不是环形链表
pre=head
while pre!=slow.next: #找环的第一个节点
pre=pre.next
slow=slow.next
return pre

每日一题 1011 分割等和子集

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
'''
动态规划
转化为0-1背包问题 能否在一系列配重中选择子集,使其刚好为和的一半
dp[i][j] 代表在0~i的配重中选择子集 能否使其和等于j
因为存在j=0 的情况 所以数组大小开为[len(nums)][sum+1]
分为两种情况:
1、前i-1个配重已经可以满足和的要求 即不需要第i个配重-->>dp[i-1][j]
2、需要第i个配重 则前i-1个配重只需要满足和=j-nums[i]-->>dp[i-1][j-nums[i]]
'''
class Solution(object):
def canPartition(self, nums):
all_sum=0
for i in range(len(nums)):
all_sum+=nums[i]
if all_sum%2==1:
return False
part_sum=all_sum//2
if max(nums)>part_sum:
return False
dp=[[False for col in range(part_sum+1)] for row in range(len(nums))]
for i in range(len(nums)):
dp[i][0]=True
dp[0][nums[0]]=True
for i in range(len(nums)):
for j in range(part_sum+1):
if dp[i][j]==True:
continue
if dp[i-1][j] or dp[i-1][j-nums[i]]:
dp[i][j]=True
return dp[len(nums)-1][part_sum]

每日一题 1014 查找常用字符

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
'''
即各字符串的交集
'''
class Solution(object):
def commonChars(self, A):
c_dict=[0]*26 #0a 1b ...
res=[]
flag=1 #第一字符串不用算交集
c="abcdefghijklmnopqrstuvwxyz" #用于数字转字符
for i in A:
temp=[0]*26 #计算每个字符串中各字符出现的次数
for j in i:
index=ord(j)-ord('a')
if flag==1:
c_dict[index]+=1
else:
temp[index]+=1
for index in range(len(c)): #更新交集
if flag==1:
break
if c_dict[index]>temp[index]:
c_dict[index]=temp[index]
flag=0
for i in range(len(c_dict)):
while c_dict[i] >0: #重复出现多次的都要输出
res.append(c[i])
c_dict[i]-=1
return res

每日一题 1016 有序数组的平方

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
双指针 最大的值一定在两侧
'''
class Solution {
public int[] sortedSquares(int[] A) {
int start=0;
int end=A.length;
int i=end-1;
int[] res=new int[end--];
while(i>=0){
res[i--]=A[start]*A[start]>=A[end]*A[end]?A[start]*A[start++]:A[end]*A[end--];
}
return res;
}
}

每日一题 1126 最大间距

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
'''
桶排序

'''
class Solution {
// 线性时间复杂度和空间复杂度 不能用Arrays.sort
public int maximumGap(int[] nums) {
int l=nums.length;
if(l<2){
return 0;
}
int n_min=Integer.MAX_VALUE,n_max=-1;
//获得最大最小值
for(int i:nums){
if (i>n_max){
n_max=i;
}
if (i<n_min){
n_min=i;
}
}
if ((n_max-n_min)==0){
return 0;
}
//桶容量
int b_size=(int)Math.ceil((double)(n_max-n_min)/(l-1));

//桶个数
int b_num=l-1;
int[] b_min=new int[b_num];
int[] b_max=new int[b_num];
Arrays.fill(b_max,-1);
Arrays.fill(b_min,Integer.MAX_VALUE);
for (int i:nums){
if(i==n_max || i==n_min) continue;
int index=(i-n_min)/b_size; //第几个桶
b_max[index]=Math.max(b_max[index],i);
b_min[index]=Math.min(b_min[index],i);
}

int res=0;
int premax=n_min;
for(int i=0;i<b_num;i++){
if(b_max[i]==-1) continue;
res=Math.max(b_min[i]-premax,res);
premax=b_max[i];
}
res=Math.max(n_max-premax,res);
return res;

}
}


class Solution {
public int maximumGap(int[] nums) {
int n = nums.length;
if (n < 2) {
return 0;
}
int minVal = Arrays.stream(nums).min().getAsInt();
int maxVal = Arrays.stream(nums).max().getAsInt();
int d = Math.max(1, (maxVal - minVal) / (n - 1));
int bucketSize = (maxVal - minVal) / d + 1;

int[][] bucket = new int[bucketSize][2];
for (int i = 0; i < bucketSize; ++i) {
Arrays.fill(bucket[i], -1); // 存储 (桶内最小值,桶内最大值) 对, (-1, -1) 表示该桶是空的
}
for (int i = 0; i < n; i++) {
int idx = (nums[i] - minVal) / d;
if (bucket[idx][0] == -1) {
bucket[idx][0] = bucket[idx][1] = nums[i];
} else {
bucket[idx][0] = Math.min(bucket[idx][0], nums[i]);
bucket[idx][1] = Math.max(bucket[idx][1], nums[i]);
}
}

int ret = 0;
int prev = -1;
for (int i = 0; i < bucketSize; i++) {
if (bucket[i][0] == -1) {
continue;
}
if (prev != -1) {
ret = Math.max(ret, bucket[i][0] - bucket[prev][1]);
}
prev = i;
}
return ret;
}
}

每日一题 1127 四数相加||

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
'''
遍历 A 和 B 所有元素和的组合情况,并记录在 ab_map 中,ab_map 的 key 为两数和,value 为该两数和出现的次数
遍历 C 和 D 所有元素和的组合情况,取和的负值判断其是否在 ab_map 中,若存在则取出 ab_map 对应的 value 值,count = count + value
'''
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer, Integer> countAB = new HashMap<Integer, Integer>();
for (int u : A) {
for (int v : B) {
countAB.put(u + v, countAB.getOrDefault(u + v, 0) + 1);
}
}
int ans = 0;
for (int u : C) {
for (int v : D) {
if (countAB.containsKey(-u - v)) {
ans += countAB.get(-u - v);
}
}
}
return ans;
}
}

每日一题 1130 重构字符串

一、问题描述

题目描述

问题思路

解题思路
解题思路

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
'''
遍历 A 和 B 所有元素和的组合情况,并记录在 ab_map 中,ab_map 的 key 为两数和,value 为该两数和出现的次数
遍历 C 和 D 所有元素和的组合情况,取和的负值判断其是否在 ab_map 中,若存在则取出 ab_map 对应的 value 值,count = count + value
'''
class Solution {
public String reorganizeString(String S) {
int all_l=S.length();
//长度小于2 直接返回
if(all_l<2){
return S;
}
// 用charnum存出现的字符及其对应的出现次数
//charnum[字符在26个字母中的位置]=该字符出现的次数
int[] charnum=new int[26];
for(int i=0;i<all_l;i++){
char ch=S.charAt(i);
charnum[(int)(ch-'a')]++;
if(charnum[(int)(ch-'a')]>(all_l+1)/2){
return "";
}
}
//用优先队列建大堆(以字符出现的次数为比较)
PriorityQueue<Character> queue=new PriorityQueue<Character>(new Comparator<Character>() {
@Override
public int compare(Character o1, Character o2) {
return charnum[(int)(o2-'a')]-charnum[(int)(o1-'a')];
}
});
//出现的字符入堆
for(int i=0;i<26;i++){
if(charnum[i]>0){
queue.offer((char)(i+97));
}
}
//建立返回字符串
StringBuilder res=new StringBuilder();
while (queue.size()>1){
char q1=queue.poll();//选出现次数最大的两个字符
char q2=queue.poll();
res.append(q1);
res.append(q2);
if(--charnum[q1-'a']>0){ //若该字符出现次数>1 则再次入堆
queue.offer(q1);
}
if(--charnum[q2-'a']>0){
queue.offer(q2);
}
}
if(queue.size()>0){ //剩最后一个字符 直接输出
res.append(queue.poll());
}
return res.toString();
}
}

每日一题 1201 重构字符串

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
'''
二分查找找到该数后 向两边拓展找到全部数字
'''
class Solution {
public int[] searchRange(int[] nums, int target) {
int low=0;
int high=nums.length-1;
int pivot=(low+high)/2;
int[] res={-1,-1};
if(nums.length==0){
return res;
}
while(nums[pivot]!=target){
if(nums[pivot]>target){
high=pivot-1;
}
else{
low=pivot+1;
}
if(high<low){ //找不到
return res;
}
pivot=(low+high)/2;
}
low=pivot-1;
high=pivot+1;
while(low>=0 && nums[low]==target)low--; //向两边拓展
while(high<nums.length&&nums[high]==target)high++;
res[0]=low+1;
res[1]=high-1;
return res;
}
}

每日一题 1202 拼接最大数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
"""
为了找到长度为 k 的最大数,需要从两个数组中分别选出最大的子序列,这两个子序列的长度之和为 k,然后将这两个子序列合并得到最大数。两个子序列的长度最小为 0,最大不能超过 kk 且不能超过对应的数组长度。

"""
class Solution {
public int[] maxNumber(int[] nums1, int[] nums2, int k) {
int l1=nums1.length;
int l2=nums2.length;
int start=Math.max(0,k-l2); //第一个数组子串的长度的最小值
int end=Math.min(k,l1); //第一个数组子串的长度的最大值
int[] maxres=new int[k];
for(int i=start;i<=end;i++){ //遍历所有子串组合 选出最大数对应的组合
int[] sub1=maxSub(nums1,i);
int[] sub2=maxSub(nums2,k-i);
int[] tempmax=merge(sub1,sub2);
if(compare(tempmax,0,maxres,0)>0){
System.arraycopy(tempmax,0,maxres,0,k);
}
}
return maxres;
}
//从数组nums中选出长度为k的最大子串 该子串为保持在元序列中相对位置的递减序列
//用数组实现单调栈
public int[] maxSub(int[] nums,int k ){
int[] stack=new int[k];
int top=-1;
int remain=nums.length-k;
for(int i=0;i<nums.length;i++){
int num=nums[i];
//栈顶元素小于待入栈元素
while ( top>=0 && stack[top]<num && remain>0){
top--;
remain--;
}
if(top<k-1){
stack[++top]=num;
}
else{
remain--;
}
}
return stack;
}
//合并两个数组的子序列
public int[] merge(int[] sub1,int[] sub2){
int l1=sub1.length;
int l2=sub2.length;
int[] res=new int[l1+l2];
if(l1==0){
return sub2;
}
if(l2==0){
return sub1;
}
int i=0;
int index1=0;
int index2=0;
while(index1<l1||index2<l2){
if(compare(sub1,index1,sub2,index2)>0){
res[i]=sub1[index1++];
}
else {
res[i]=sub2[index2++];
}
i++;
}
return res;
}
//比较待合并的两个序列大小 若当前待比较数字相同 则看后面的数
public int compare(int[] sub1,int index1,int[] sub2,int index2){
while (index1<sub1.length&&index2<sub2.length){
if(sub1[index1]!=sub2[index2]){
return sub1[index1]-sub2[index2];
}

index1++;
index2++;

}
return (sub1.length-index1)-(sub2.length-index2);
}
}


每日一题 1203 计数质数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
"""
方法一:枚举 判断每一个数是否为质数 判断方法是看[2,根号x]是否为其因数
"""
class Solution {
public int countPrimes(int n) {
int res=0;
for(int i=2;i<n;i++){
res+=isPrime(i)?1:0;
}
return res;
}
public boolean isPrime(int num){

for(int i=2;i*i<=num;i++){
if(num%i==0){
return false;
}
}
return true;
}
}
"""
方法二:埃氏筛 若一个数为质数 则其倍数都为合数 从x*x开始赋为合数 因为其余的2x 3x都会在x之前就被其他数的倍数标记过了,例如2 的所有倍数,3 的所有倍数等。
"""
class Solution {
public static int countPrimes(int n) {
int res=0;
int[] prime=new int[n];
Arrays.fill(prime,1);
for(int i=2;i<n;i++){
if(prime[i]==1){
res+=1;
if((long)i*i<n){
for(int x=i*i;x<n;x+=i){
prime[x]=0;
}
}
}
}
return res;
}
}

每日一题 1204 分割数组为连续子序列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
"""
贪心
对于数组中的元素 x,如果存在一个子序列以x−1 结尾,则可以将 x加入该子序列中。将 x 加入已有的子序列总是比新建一个只包含 x 的子序列更优,因为前者可以将一个已有的子序列的长度增加 1,而后者新建一个长度为 1 的子序列,而题目要求分割成的子序列的长度都不小于 3,因此应该尽量避免新建短的子序列。

"""
public static boolean isPossible(int[] nums) {
//存储数组中的每个数字的剩余次数
HashMap<Integer,Integer> numscntmap=new HashMap<Integer,Integer>();
//存储数组中的每个数字作为结尾的子序列的数量。
HashMap<Integer,Integer> numsendmap=new HashMap<Integer,Integer>();
for(int num:nums){
numscntmap.put(num,numscntmap.getOrDefault(num,0)+1);
}
for(int num:nums){
if(numscntmap.get(num)==0) { //只有当一个数字的剩余次数大于 00 时,才需要考虑这个数字是否属于某个子序列。
continue;
}
numscntmap.put(num,numscntmap.get(num)-1);
if(numsendmap.containsKey(num-1)&& numsendmap.get(num-1)>0){ //若存在以num-1为结束的子串 则将num加入该子串 以num-1为结束的子串减1,以num为结束的子串加1
numsendmap.put(num-1,numsendmap.get(num-1)-1);
numsendmap.put(num,numsendmap.getOrDefault(num,0)+1);
}
//不然就看是否存在num+1,num+2,这三个凑成一个子串
else if (numscntmap.containsKey(num+1)&&numscntmap.get(num+1)>0&&numscntmap.containsKey(num+2)&&numscntmap.get(num+2)>0){
numsendmap.put(num+2,numsendmap.getOrDefault(num+2,0)+1);
numscntmap.put(num+1,numscntmap.get(num+1)-1);
numscntmap.put(num+2,numscntmap.get(num+2)-1);
}
else {
return false;
}
}
return true;
}

每日一题 1206 杨辉三角

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
主要是二维集合的初始化和赋值
杨辉三角就是第i层的元素个数都为i
第i层第j个元素的值等于 第i-1层第j-1个元素+第i-1层第j个元素
注意j的范围[1,i-1]
"""
class Solution {
public List<List<Integer>> generate(int numRows) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < numRows; i++) {
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(1);
for (int j = 1; j < i; j++) {
int sumnum = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j);
temp.add(sumnum);
}
if (i > 0) {
temp.add(1);
}
res.add(temp);
}
return (List)res; //记得转型
}
}

每日一题 1207 杨辉三角

一、问题描述

题目描述

二、具体代码

问题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
贪心 理清逻辑思路 不需要实际去改变矩阵
"""
class Solution {
public int matrixScore(int[][] A) {
int m=A.length;
int n=A[0].length;
int res=m*(1<<(n-1)); //首列必全为1
for(int i=1;i<n;i++){
int temp_num=0;
for(int j=0;j<m;j++){
if(A[j][0]==0){ //经过了行翻转
temp_num+=1-A[j][i];
}
else{ //无需行翻转
temp_num+=A[j][i];
}
}
temp_num=Math.max(temp_num,m-temp_num); //翻转能得到的该列最大值
res+=temp_num*(1<<(n-1-i));
}
return res;
}
}

每日一题 1208 将数组拆分成斐波那契数列

一、问题描述

题目描述

二、具体代码

问题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
"""
回溯
"""
public List<Integer> splitIntoFibonacci(String S) {
List<Integer> res = new ArrayList<>();
backtrack(S.toCharArray(), res, 0);
return res;
}

public boolean backtrack(char[] digit, List<Integer> res, int index) {
//边界条件判断,如果截取完了,并且res长度大于等于3,表示找到了一个组合。
if (index == digit.length && res.size() >= 3) {
return true;
}
for (int i = index; i < digit.length; i++) {
//两位以上的数字不能以0开头
if (digit[index] == '0' && i > index) {
break;
}
//截取字符串转化为数字
long num = subDigit(digit, index, i + 1);
//如果截取的数字大于int的最大值,则终止截取
if (num > Integer.MAX_VALUE) {
break;
}
int size = res.size();
//如果截取的数字大于res中前两个数字的和,说明这次截取的太大,直接终止,因为后面越截取越大
if (size >= 2 && num > res.get(size - 1) + res.get(size - 2)) {
break;
}
if (size <= 1 || num == res.get(size - 1) + res.get(size - 2)) {
//把数字num添加到集合res中
res.add((int) num);
//如果找到了就直接返回
if (backtrack(digit, res, i + 1)) //1确定 继续后面的分
return true;
//如果没找到,就会走回溯这一步,然后把上一步添加到集合res中的数字给移除掉
res.remove(res.size() - 1); //1排除 尝试12
}
}
return false;
}

//相当于截取字符串S中的子串然后转换为十进制数字
private long subDigit(char[] digit, int start, int end) {
long res = 0;
for (int i = start; i < end; i++) {
res = res * 10 + digit[i] - '0';
}
return res;
}

每日一题 1209 不同路径

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
"""
动态规划 只能通过左边或者上面到达当前节点:dp[i][j]=dp[i][j-1]+dp[i-1][j];
"""
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp=new int[m][n];
for(int i=0;i<m;i++){
dp[i][0]=1;
}
for(int i=0;i<n;i++){
dp[0][i]=1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
}
return dp[m-1][n-1];
}
}

每日一题 1210 柠檬水找零

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
"""
用两个int变量存老板手上5元和10元张数
"""
class Solution {
public boolean lemonadeChange(int[] bills) {
int five=0;
int ten=0;
for(int bill:bills){
//5元的 直接五元加1
if(bill==5){
five+=1;
}
//10元的 判断是否有一张五元
else if(bill==10){
if(five<0) return false;
else{
five-=1;
ten+=1;
}
}
//20元的 判断是否有3张五元或者一张10元一张5元
else{
if(ten>0&&five>0){
ten-=1;
five-=1;
}
else if(five>=3){
five-=3;
}
else{
return false;
}
}
}
return true;
}
}

每日一题 1211 Dota2 参议院

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
"""
贪心算法:每个R阵营的参议员禁止下一个离他最近的D阵营的参议员,反之亦然。
* 算法流程:
* 使用两个队列分别保存R阵营和D阵营的参议员索引,
* 在每一轮循环中,比较相邻两个R和D阵营的参议员的索引,
* 保留索引小(min)的,并将该(min + senate.length)添加到该阵营队列尾部
* 去除索引大的,即不添加到末尾。
"""
class Solution {
public String predictPartyVictory(String senate) {
Queue<Integer> r=new LinkedList<Integer>();
Queue<Integer> d=new LinkedList<Integer>();
for(int i=0;i<senate.length();i++){
if(senate.charAt(i)=='R'){
r.offer(i);
}
else {
d.offer(i);
}
}
while(!r.isEmpty()&&!d.isEmpty()){
int r_idx=r.remove();
int d_idx=d.remove();
if(r_idx<d_idx) r.add(r_idx+senate.length());
else d.add(d_idx+senate.length());
}
return r.isEmpty()?"Dire":"Radiant";

}
}

每日一题 1212 摆动序列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
动态规划
谷:nums[i]<nums[i-1]
峰:nums[i]>nums[i-1]
若是谷:
1、上一个峰+1(把i纳入序列)
2、上一个谷(不纳入序列)
选择12中大的更新谷
峰相反即可。
"""
class Solution {
public int wiggleMaxLength(int[] nums) {
int down=1,up=1;
if(nums.length<2){
return nums.length;
}
for(int i=1;i<nums.length;i++){
if(nums[i]<nums[i-1]){
down=Math.max(down,up+1);
}
else if(nums[i]>nums[i-1]){
up=Math.max(down+1,up);
}
}
return Math.max(up,down);
}
}

每日一题 1213 存在重复元素

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
for (int x : nums) {
if (!set.add(x)) {
return true;
}
}
return false;
}
}

每日一题 1214 字母异位词分组

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
"""
排序
"""
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List <List<String>> res= new ArrayList<>(); //存结果
int idx=0;
//如 <eat,0>代表eat的字母异位词都存在res[0]这一个list中
Map<String,Integer> map=new HashMap<>(); //存字母异位词与结果中字母异位词list下标
for(int i=0;i<strs.length;i++){
String temp=sortstring(strs[i]);
if(map.containsKey(temp)){ //若已有字母异位词,则加入res对应的list中
List<String> strtemp=new ArrayList<>();
//二维list末尾增加元素
strtemp=res.get(map.get(temp));
strtemp.add(strs[i]);
res.set(map.get(temp),strtemp);
}
else{ //若结果中没有,则将当前字符加入 注意新开一个list
map.put(temp,idx);
List<String> res_temp=new ArrayList<>();
res_temp.add(strs[i]);
res.add(res_temp);
idx+=1;
}
}
return res;
}
//给字符串的字符排序
public String sortstring(String s){
char[] temp=s.toCharArray();
Arrays.sort(temp);
return s.valueOf(temp);
}
}
"""
大神简易写法
直接用map 存字母异位词 以及对应的字符串list
最后再把map转二维list
"""
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}

每日一题 1215 单调递增的数字

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
"""
使用贪心法 若原本单调递增则直接返回
如果前面的值大于后面的值就把当前位数减一然后把后面的值变成9
"""
"""
我自己写的 很多可以直接用内置函数完成
"""
public int monotoneIncreasingDigits(int N) {
if(N<10){
return N;
}
int[] ori=new int[10];
int[] res=new int[10];
int idx=0;
while(N>0){
ori[idx]=N%10;
N=N/10;
idx+=1;
}
System.out.println(Arrays.toString(ori));
int len=idx;
idx-=1;
for(int i=idx;i>=0;i--){
if(i>0&&ori[i]>ori[i-1]){
while(i<len&&ori[i]-1<ori[i+1]){
i+=1;
}
res[i]=ori[i]-1;

i-=1;
while(i>=0){
res[i]=9;
i-=1;
}
break;
}
else {
res[i]=ori[i];
}
}
System.out.println(Arrays.toString(res));
int result=0;
for(int i=len-1;i>=0;i--){
result=result*10;
result+=res[i];

}
return result;
}
"""
大神简易版
"""
public int monotoneIncreasingDigits(int N) {
char[] ori=String.valueOf(N).toCharArray();
int len=ori.length;
for(int i=len-1;i>0;i--){
if(ori[i]<ori[i-1]){
ori[i-1]-=1;
for(int j=i;j<len;j++){
ori[j]='9';
}
}
}
return Integer.parseInt(String.valueOf(ori));
}

每日一题 1216 单词规律

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] s1=s.split(" "); //分割
char[] p1=pattern.toCharArray();
if(s1.length!=p1.length){ //若长度不一致 当然错误
return false;
}
Map<Character,String> map=new HashMap<>();
for(int i=0;i<p1.length;i++){
for(char key:map.keySet()){
String value=map.get(key);
}
if(map.containsKey(p1[i])){ //若已有字符 则比较是否一致
if(map.get(p1[i]).equals(s1[i])){
continue;
}
else return false;
}
else{
if(map.containsValue(s1[i])){ //若没有字符 则先判断字符串是否已入map 放置ab都对应一个字符串的情况
return false;
}
else map.put(p1[i],s1[i]);
}
}
return true;
}
}

每日一题 1217 买卖股票的最佳时机含手续费

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
动态规划
第i天手上没有股票的最大利润=max(第i-1天没有股票的最大利润,第i-1天有股票的最大利润+第i天买了股票赚的钱(股票价格-手续费)
第i天手上有股票的最大利润=max(第i-1天有股票的最大利润,第i-1天没有股票的最大利润-第i天买股票的钱(股票价格)
"""
class Solution {
public int maxProfit(int[] prices, int fee) {
int have=-prices[0];
int nohave=0;
for(int i=1;i<prices.length;i++){
int temp=have;
have=Math.max(have,nohave-prices[i]);
nohave=Math.max(nohave,temp+prices[i]-fee);
}
return nohave;
}
}

每日一题 1218 找不同

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
1、求和
求字符串各个字符的和 两个和之差就是答案
"""
class Solution {
public char findTheDifference(String s, String t) {
int sums=0,sumt=0;
for(int i=0;i<s.length();i++){
sums+=s.charAt(i);
sumt+=t.charAt(i);
}
sumt+=t.charAt(s.length());
return (char)(sumt-sums);
}
}
"""
2、位运算
将字符串拼接起来 用位运算 就成了找出现字符次数为奇数的字符问题了 异或就可以
"""
class Solution {
public char findTheDifference(String s, String t) {
int res=0;
for(int i=0;i<s.length();i++){
res=res^(int)s.charAt(i);
}
for(int i=0;i<t.length();i++){
res=res^(int)t.charAt(i);
}
return (char)res;
}
}

每日一题 1219 旋转图像

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
顺时针选择90度=先水平翻转 再主对角线翻转
"""
class Solution {
public void rotate(int[][] matrix) {
//水平翻转
int len=matrix.length;
for(int i=0;i<len/2;i++){
for(int j=0;j<len;j++){
int temp=matrix[i][j];
matrix[i][j]=matrix[len-i-1][j];
matrix[len-i-1][j]=temp;
}
}
//主对角线翻转
for(int i=0;i<len;i++){
for(int j=len-1;j>i;j--){
int temp=matrix[i][j];
matrix[i][j]=matrix[j][i];
matrix[j][i]=temp;
}
}
}
}

每日一题 1221 使用最小花费爬楼梯

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
"""
动态规划
dp2=Math.min(dp1+cost[idx-2],dp2+cost[idx-1]);//取从下两级迈步和下一级迈步中的最小值
dp代表到达第几级所需的体力 还没有迈步
cost代表从第几级迈步所需的体力
(题目描述有点问题 记得动态规划就可以)
"""
class Solution {
public int minCostClimbingStairs(int[] cost) {
int dp1=0,dp2=0;//初始状态 可以第一级或者第二级都不费力
int idx=2;
while(idx<=cost.length){
int temp=dp2;
dp2=Math.min(dp1+cost[idx-2],dp2+cost[idx-1]);//取从下两级迈步和下一级迈步中的最小值
dp1=temp;
idx+=1;
}
return dp2;
}
}

每日一题 1222 二叉树的锯齿形层序遍历

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
二叉树的单栈层序遍历 由于知道每层的个数 直接在遍历本层的时候 赋值list 用boolean变量标记头入还是尾入

"""
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res=new LinkedList<>();
Queue<TreeNode> nowstack=new LinkedList<>();//队列 存储当前层节点
if(root!=null) nowstack.offer(root);
Boolean flag=true;
while(!nowstack.isEmpty()){
Deque<Integer> temp=new LinkedList<>(); //存当前层对应的值
int len=nowstack.size(); //size为本层节点数
while(len>0){
TreeNode p=nowstack.poll();
if(flag)temp.offerLast(p.val); //尾入
else temp.offerFirst(p.val); //头入
if(p.left!=null){
nowstack.offer(p.left);
}
if(p.right!=null){
nowstack.offer(p.right);
}
len--;
}
flag=!flag;
res.add(new LinkedList<Integer> (temp));//deque转list
}
return res;
}
}

每日一题 1224 分发糖果

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
波谷必为1 至于波峰要看左右两个波谷递增上来 取其最大值
"""
class Solution {
public int candy(int[] ratings) {
int res=0;
int len=ratings.length;
int[] left=new int[len];
left[0]=1;
int[] right=new int[len];
right[len-1]=1;
for(int i=1;i<len;i++){ //左规则
if(ratings[i]>ratings[i-1]) left[i]=left[i-1]+1;
else left[i]=1;
}
for(int i=len-1;i>0;i--){ //右规则
if(ratings[i-1]>ratings[i]) right[i-1]=right[i]+1;
else right[i-1]=1;
}
for(int i=0;i<len;i++){ //取最大
res+=Math.max(right[i],left[i]);
}
return res;
}
}

每日一题 1225 分发饼干

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
"""
排序+贪心
每次将最小满足该孩子的饼干 分给孩子
"""
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int i=0,j=0;
int count=0;
while (i<g.length&&j<s.length){
while (j<s.length&&g[i]>s[j]) j++;
if(j==s.length) break;
count+=1;
i++;
j++;
}
return count;
}
}

每日一题 1226 最大矩形

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
"""
暴力
left[i][j]记录节点ij左边的1的个数(包括本身
"""
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length==0||matrix[0].length==0) return 0;
int m=matrix.length,n=matrix[0].length;
int[][] left = new int[m][n];
int width=0,area=0,res=0;
//求left[i][j]
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='0'){
continue;
}
else{
left[i][j]=(j==0?0:left[i][j-1])+1;
}
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++) {
if(matrix[i][j]=='0') continue;
width=left[i][j];
area=width;
for(int k=i-1;k>=0;k--){
width=Math.min(width,left[k][j]);//右下角ij 左上角kj
area=Math.max(area,width*(i-k+1));
}
res=Math.max(res,area);
}
}
return res;
}
}
"""
2、单调栈
"""
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length==0||matrix[0].length==0) return 0;
int m=matrix.length,n=matrix[0].length;
int[][] left = new int[m][n];
int width=0,area=0,res=0;
//求left[i][j]
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='0'){
continue;
}
else{
left[i][j]=(j==0?0:left[i][j-1])+1;
}
}
}
//单调栈
Deque<Integer> stack=new ArrayDeque<>();
int[] tmp=new int[m+2];
for(int j=0;j<n;j++){
for(int i=0;i<m;i++){
tmp[i+1]=left[i][j];
}
for(int i=0;i<m+2;i++){
while(!stack.isEmpty()&&tmp[i]<tmp[stack.peek()]){
int h=tmp[stack.pop()];
area=Math.max(area,(i-stack.peek()-1)*h);
}
stack.push(i);
}
res=Math.max(res,area);
}
return res;
}
}

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
单调栈
"""
class Solution {
public int largestRectangleArea(int[] heights) {
// 这里为了代码简便,在柱体数组的头和尾加了两个高度为 0 的柱体。 加最后一个0是为了计算栈中剩余的递增面积 若不加最后一个零 剩余递增不会被计算
int[] tmp = new int[heights.length + 2];
System.arraycopy(heights, 0, tmp, 1, heights.length);

Deque<Integer> stack = new ArrayDeque<>();
int area = 0;
for (int i = 0; i < heights.length+2; i++) {
// 对栈中柱体来说,栈中的下一个柱体就是其「左边第一个小于自身的柱体」;
// 若当前柱体 i 的高度小于栈顶柱体的高度,说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
// 因此以栈顶柱体为高的矩形的左右宽度边界就确定了,可以计算面积🌶️ ~
while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
int h = tmp[stack.pop()];
area = Math.max(area, (i - stack.peek() - 1) * h);
}
stack.push(i);
}

return area;
}
}

每日一题 1227 同构字符串

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
用map存映射 若存在则判断是否一致 若不存在先判断t对应的字符是否已有对应 若有 则直接报错 因为不能两个字符映射到同一个字符
"""
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character,Character> map=new HashMap<>();
for(int i=0;i<s.length();i++){
char s1=s.charAt(i);
if(map.containsKey(s1)){
if(map.get(s1)==t.charAt(i)) continue;
else return false;
}
else{
if(map.containsValue(t.charAt(i))) return false;
map.put(s1,t.charAt(i));
}
}
return true;
}
}

每日一题 1228 买卖股票的最佳时机

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
"""
不考虑k次交易限制
用两个一维数组存
have:第i天有股票的最大利润
free:第i天没有股票的最大利润
状态转移公式为:
free[i]=Math.max(free[i-1],have[i-1]+prices[i]);
have[i]=Math.max(have[i-1],free[i-1]-prices[i]);
"""
class Solution {
public int maxProfit(int k, int[] prices) {

int len=prices.length;
if(len<1) return 0;
int[] free=new int[len];
int[] have=new int[len];
free[0]=0;
have[0]=-prices[0];
for(int i=1;i<len;i++){
free[i]=Math.max(free[i-1],have[i-1]+prices[i]);
have[i]=Math.max(have[i-1],free[i-1]-prices[i]);
}
return free[len-1];

}
}
"""
考虑交易次数的限制
买入+卖出算一次交易次数
用二维数组存
free[i][j] 代表第i天手上没有股票 且交易了j次最大的利润
"""
class Solution {
public int maxProfit(int k, int[] prices) {
int len=prices.length;
if(len<1) return 0;
k=Math.min(k,len/2);
int[][] free=new int[len][k+1];
int[][] have=new int[len][k+1];
free[0][0]=0;
have[0][0]=-prices[0];
for(int i=1;i<=k;i++){
free[0][i]=Integer.MIN_VALUE/2;//边界 没有意义
have[0][i]=Integer.MIN_VALUE/2;
}
for(int i=1;i<len;i++){
have[i][0]=Math.max(free[i-1][0]-prices[i],have[i-1][0]);//0次交易 也就是没有完整的买入以及卖出 只买了或者根本没买
for(int j=1;j<=k;j++){
free[i][j]=Math.max(free[i-1][j],have[i-1][j-1]+prices[i]);
have[i][j]=Math.max(have[i-1][j],free[i-1][j]-prices[i]);
}
}
int res=0;
for(int i=0;i<=k;i++){
if(res<free[len-1][i]) res=free[len-1][i];
}
return res;
}
}

每日一题 1229 按要求补齐数组

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
"""
贪心
一个数组[a1,a2,a3...an]当前能用和表示的数字区间为[1,cur_range],此时往数组内补充新数num,则此时能表示的区间为[1,cur_range]∩[num,cur_range + num]
所以若插入num=cur_range+1,覆盖的区间就为[1,cur_range+cur_range+1]
每次若已能覆盖的最大长度cur_range小于待实现的数num,并且已拥有的nums[pos]大于num,也就是需要插入值 统一插入cur_range+1这个数
不然的话 就用nums[pos]来增加覆盖的最大长度cur_range=cur_range+nums[pos]
当前能表示的最大数字为cur_range,则下一个需要达到的目标数字是cur_range + 1,而当前(未使用)的数组元素为num = nums[pos]
判断num与目标值cur_range + 1的大小关系:
1、如果num > cur_range + 1,则说明[cur_range + 1, num - 1]区间内的数字无法表示,必须补充插入新数。为了使插入的新数既能表示ach + 1,又能尽可能覆盖更多的数组(贪心的关键之处),插入的数字就是cur_range + 1,更新cur_range = cur_range + cur_range + 1
2、如果num < cur_range + 1,说明当前的目标值cur_range + 1必然可以实现(因为num >= 1),此时更新cur_range = cur_range + num
"""
class Solution {
public int minPatches(int[] nums, int n) {
long cur_range=0;
int pos=0;
int res=0;
while(cur_range<n){
if(pos>=nums.length||nums[pos]>cur_range+1){ //插值
res+=1;
cur_range+=cur_range+1;
}
else {
cur_range+=nums[pos];
pos+=1;
}
}
return res;
}
}

每日一题 1230 最后一块石头的重量

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
"""
用大堆来模拟过程
"""
class Solution {
public int lastStoneWeight(int[] stones) {
if(stones.length<1) return 0;
//建大堆
//也可以直接PriorityQueue<Integer> queue=new PriorityQueue<Integer>((x,y)->(y-x));
PriorityQueue<Integer> queue =new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
for(int i=0;i<stones.length;i++){
queue.offer(stones[i]);
}
while(queue.size()>1){
int m1=queue.poll();//堆中最大的数
int m2=queue.poll();//堆中第二大的数
if(m1!=m2) queue.offer(m1-m2);
}
return queue.size()>0?queue.poll():0;

}
}

每日一题 0102 滑动窗口最大值

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
单调队列
用双端队列存一个递减队列对应的下标
"""
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int idx=0;
int[] res=new int[nums.length-k+1];
Deque<Integer> queue=new ArrayDeque<>();
for(int i=0;i<k;i++){ //第一个窗口维护
while(!queue.isEmpty()&&nums[queue.getLast()]<=nums[i]){
queue.removeLast();
}
queue.addLast(i);
}
res[idx]=nums[queue.getFirst()];
for(int i=k;i<nums.length;i++){
//保证递减
while(!queue.isEmpty()&&nums[queue.getLast()]<=nums[i]){
queue.removeLast();
}
queue.add(i);
//将窗口缩到k大 维护窗口大小
while(!queue.isEmpty()&&queue.peekFirst()<=i-k) queue.removeFirst();
res[++idx]=nums[queue.peekFirst()];
}
return res;
}
}


每日一题 0103 分割链表

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
"""
维护两个链表 一个是小于x的节点 一个是大于等于x的节点
最后将小于x节点的尾结点next指向大于x的头结点即可
增加虚拟节点来统一头结点为空不为空的情况。
"""
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode lhead=new ListNode(0); //小于x的节点链表
ListNode hhead=new ListNode(0); //大于x的节点链表
ListNode tmp=head;
ListNode tmpl=lhead; // 小于x的节点链表的尾指针
ListNode tmph=hhead; //大于x的节点链表的尾指针
while(tmp!=null){
if(tmp.val<x) {
tmpl.next=tmp;
tmpl=tmp;
}
else {
tmph.next=tmp;
tmph=tmp;
}
tmp=tmp.next;
}
tmph.next=null; //最后一个节点的next置空
tmpl.next=hhead.next; //连接两个链表
return lhead.next; //跳过虚拟节点 返回真正的头结点
}
}

每日一题 0104 斐波那契数列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"""
动态规划 用两个变量存状态即可
"""
class Solution {
public int fib(int n) {
int dp0=0,dp1=1,idx=2;
if(n<2) return n;
while(idx<=n){
int tmp=dp1;
dp1=dp0+dp1;
dp0=tmp;
idx+=1;
}
return dp1;
}
}

每日一题 0105 较大分组的位置

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
一次遍历 用l指针指向重复字符的第一个位置 idx指向最后一个位置 idx-l+1即为连续字符的长度
"""
class Solution {
public List<List<Integer>> largeGroupPositions(String s) {
char[] arr=s.toCharArray();
List<List<Integer>> res=new ArrayList<>();
int l=0,idx=0;
while(idx<arr.length){
while (idx+1<arr.length&&arr[idx]==arr[idx+1]) {
idx+=1;
}
if(idx-l+1>=3){
List<Integer> tmp=new ArrayList<>();
tmp.add(l);
tmp.add(idx);
res.add(new ArrayList<>(tmp));
}
l=idx+1;
idx=idx+1;
}
return res;
}
}

每日一题 0106 除法求值

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
"""
图 利用除法的传递性
变量就是节点
商就是边的权值
建立图后 两个变量的商就是图中两个节点的路径乘积
"""
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String,Integer> variables=new HashMap<>();
List<String> tmp_val=new ArrayList<>(2);
int vid=0;
//给每个变量编号 即节点号 从0开始 依次加1
for(int i=0;i<equations.size();i++){
tmp_val=equations.get(i);
if(!variables.containsKey(tmp_val.get(0))){
variables.put(tmp_val.get(0),vid++);
}
if(!variables.containsKey(tmp_val.get(1))){
variables.put(tmp_val.get(1),vid++);
}
}
//edges有vid个 edges[i]代表从节点i出发的所有边
//边:pair类 有对应终端点endid和边权值val
List<Pair>[] edges=new List[vid];
//分配空间
for(int i=0;i<vid;i++){
edges[i]=new ArrayList<Pair>();
}
for(int i=0;i<equations.size();i++){
//获得边两端对应的id(ia,ib) 分别赋权值(value,1/value)
int ia=variables.get(equations.get(i).get(0)),ib=variables.get(equations.get(i).get(1));
edges[ia].add(new Pair(ib, values[i]));
edges[ib].add(new Pair(ia,1/values[i]));
}
int ia,ib;
double[] res=new double[queries.size()];
Arrays.fill(res,-1.0);//默认-1
for(int i=0;i<queries.size();i++){//依次寻找 为每次查询都独立搜索一次
String sa=queries.get(i).get(0),sb=queries.get(i).get(1);
if(variables.containsKey(sa)&&variables.containsKey(sb)){
ia=variables.get(sa);
ib=variables.get(sb);
if(ia==ib) { //是同一个节点 即自己除自己
res[i]=1;
continue;
}
//BFS
Queue<Integer> queue=new LinkedList<>();
queue.add(ia);
double[] ratios=new double[vid]; //存从ia出发到各个节点的路径值---商
Arrays.fill(ratios,-1.0);
ratios[ia]=1.0;
while (!queue.isEmpty()&&ratios[ib]<0){
int start=queue.poll();
for(Pair pair:edges[start]){ //遍历与start节点相连的所有边
if(ratios[pair.endid]<0){//没访问过该端节点
ratios[pair.endid]=ratios[start]*pair.val; //更新路径值
queue.add(pair.endid); //将该节点加入队列中
}
}
}
res[i]=ratios[ib];
}
}
return res;
}
}
class Pair{
int endid;
double val;
public Pair(int e,double v){
endid=e;
val=v;
}
}

每日一题 0107 省份数量

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
"""
题目就是求图的连通分量个数
用dfs或者bfs
1、dfs
遍历所有城市,对于每个城市,如果该城市尚未被访问过,则从该城市开始深度优先搜索。
通过矩阵isConnected 得到与该城市直接相连的城市有哪些,这些城市和该城市属于同一个连通分量,然后对这些城市继续深度优先搜索,直到同一个连通分量的所有城市都被访问到,即可得到一个省份。
遍历完全部城市以后,即可得到连通分量的总数,即省份的总数。

"""
class Solution {
public int findCircleNum(int[][] isConnected) {
int res=0;
int num=isConnected.length;
boolean[] visited=new boolean[num];
for(int i=0;i<num;i++){
if(visited[i]==false){
dfs(visited,i,isConnected);
res+=1;
}
}
return res;

}
public void dfs(boolean[] visited,int cur,int[][]isConnected){
for(int j=0;j<visited.length;j++){
if(isConnected[cur][j]==1&&visited[j]==false){
visited[j]=true;
dfs(visited,j,isConnected);
}
}
}
}
"""
2、bfs
对于每个城市,如果该城市尚未被访问过,则从该城市开始广度优先搜索,直到同一个连通分量中的所有城市都被访问到,即可得到一个省份。
"""
class Solution {
public int findCircleNum(int[][] isConnected) {
int res = 0;
int num = isConnected.length;
boolean[] visited = new boolean[num];
Queue<Integer> queue=new LinkedList<>();
for(int i=0;i<num;i++){
if(visited[i]==false){
queue.add(i);
res+=1;
while (!queue.isEmpty()){ //bfs
int j=queue.poll();
for(int k=0;k<num;k++){
if(isConnected[j][k]==1&&visited[k]==false){
queue.add(k);
visited[k]=true;
}
}
}
}
}
return res;
}
}

每日一题 0108 旋转数组

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
"""
1、翻转数组
向右旋转 相当于全部翻转 然后各自翻转 0~k-1 k~nums.length-1
"""
public void rotate_2(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}


private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
"""
2、双重循环 每次只移动一位
"""
public void rotate_1(int[] nums, int k) {
int n = nums.length;
k %= n;
for (int i = 0; i < k; i++) {
int temp = nums[n - 1];
for (int j = n - 1; j > 0; j--) {
nums[j] = nums[j - 1];
}
nums[0] = temp;
}
}

每日一题 0110 汇总区间

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
"""
用start指向连续区间开头 每次判断nums[i]是不是区间末尾
"""
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> res=new ArrayList<>();
if(nums.length<1) return res;
int start=nums[0];
for(int i=0;i<nums.length;i++){
if((i<nums.length-1&&nums[i]+1!=nums[i+1])||i==nums.length-1){//是区间末尾
StringBuilder tmp=new StringBuilder();
if(start!=nums[i]){ //区间不止一个数
tmp.append(start).append("->").append(nums[i]);
}
else tmp.append(nums[i]); //区间只有一个数
res.add(tmp.toString());
if(i<nums.length-1) start=nums[i+1]; //新的区间起点
}
}
return res;
}
}

每日一题 0115 移除最多的同行或同列石头

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
"""
将同行或同列的石头连接起来成图 也就是求联通分量
所有横坐标为 x 的石头和所有纵坐标为 y 的石头都属于同一个连通分量。
需要在并查集里区分「横坐标」和「纵坐标」,它们在并查集里不能相等,根据题目的提示 0 <= x_i, y_i <= 10^4,可以把其中一个坐标 映射 到另一个与 [0, 10000] 不重合的区间,可以的做法是把横坐标全部减去 10001 或者全部加上 10001
用并查集
init 初始化
find 查找节点的父节点(联通的根节点)
union 合并两个节点所在的联通分量(根节点合并)
新建节点时联通分量+1,合并节点时联通分量-1
"""
class Solution {
public int removeStones(int[][] stones) {
UnionFind uf=new UnionFind();
for(int[] stone:stones){
uf.union(stone[0]+10001,stone[1]);
}
return stones.length-uf.getCount();
}
}
class UnionFind{
private Map<Integer,Integer> parent; //节点对应的父节点(联通分量的根节点)
private int count; //联通分量的个数
//初始化
public UnionFind(){
this.parent=new HashMap<>();
this.count=0;
}
public int getCount(){
return count;
}
//查找x所在联通分量的根节点
public int find(int x){
if(!parent.containsKey(x)){
parent.put(x,x); //若父节点中没有 则其本身就是其父节点 为新的一个联通分量
count++;
}
if(x!=parent.get(x)){
parent.put(x,find(parent.get(x))); //若父节点不是根节点 则把根节点赋给父节点 路径压缩
}
return parent.get(x);
}
public void union(int x,int y){ //合并x,y两个节点所在的联通分量
int px=find(x);
int py=find(y);
if(px==py) return; //无需合并
parent.put(px,py); //合并两个根节点 即合并了联通分量
count-=1;

}
}

每日一题 0122 数组形式的整数加法

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
"""
方法1 将数组的末尾以此加到数K上 去加的结果的末尾给res
也就是将进位直接体现在数K上
"""
class Solution {
public List<Integer> addToArrayForm(int[] A, int K) {
LinkedList<Integer> res=new LinkedList<>();
int tmp;
int idx=A.length-1;
int jinwei=0;
while(K>0||idx>=0){
if(idx>=0){
K+=A[idx];
}
res.addFirst(K%10);
K/=10;
idx-=1;
}
return res;
}
}
"""
方法2
分类讨论 无技巧
"""
class Solution {
public List<Integer> addToArrayForm(int[] A, int K) {
List<Integer> res=new LinkedList<>();
int tmp;
int idx=A.length-1;
int jinwei=0;
while (K>0&&idx>=0){ //对应位上都有数
tmp=K%10;
int tmp_add=tmp+A[idx]+jinwei;
if(tmp_add<10){
res.add(0,tmp_add);
jinwei=0;
}
else {
res.add(0,tmp_add-10);
jinwei=1;
}
idx-=1;
K=K/10;
}
while(idx>=0){ //K为0了 也就是X的位数大于K
int tmp_add=A[idx]+jinwei;
if(tmp_add>9){
jinwei=1;
res.add(0,tmp_add-10);
}
else{
jinwei=0;
res.add(0,tmp_add);
}
idx-=1;
}
while(K>0){ //X为0了 也就是X的位数小于K
int tmp_add=K%10+jinwei;
if(tmp_add>9){
jinwei=1;
res.add(0,tmp_add-10);
}
else{
jinwei=0;
res.add(0,tmp_add);
}
K/=10;
}
if(jinwei>0){ //两者都为0
//输入:A = [9,9,9,9,9,9,9,9,9,9], K = 1
//输出:[1,0,0,0,0,0,0,0,0,0,0] 最后一个1需要分类讨论
res.add(0,jinwei);
}
return res;
}
}

每日一题 0201 公平的糖果棒交换

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int[] fairCandySwap(int[] A, int[] B) {
int sumA=Arrays.stream(A).sum();
int sumB=Arrays.stream(B).sum();
int delta=(sumA-sumB)/2;
int[] res=new int[2];
Set<Integer> tmp=new HashSet<>();
for(int i=0;i<A.length;i++){
tmp.add(A[i]);
}
for(int b:B){
if(tmp.contains(b+delta)){
res[0]=b+delta;
res[1]=b;
return res;
}
}
return res;
}
}

每日一题 0228 公平的糖果棒交换

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public boolean isMonotonic(int[] A) {
if(A.length<2) return true;
int flag=0; //flag=1 为递增 -1为递减
int i=1,len=A.length;
while(i<len){
if(A[i-1]>A[i]) {
if(flag==-1) return false; //提前终止遍历
flag=1;
}
if(A[i-1]<A[i]) {
if(flag==1) return false;
flag=-1;
}
i+=1;
}
return true;
}
}

每日一题 0301 公平的糖果棒交换

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class NumArray {
int[] res;
public NumArray(int[] nums) {
if(nums.length<1) return;
res=new int[nums.length+1];
for(int i=0;i<nums.length;i++){
res[i+1]=res[i]+nums[i];
}
}
public int sumRange(int i, int j) {
return res[j+1]-res[i];
}
}

/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/

每日一题 0302 公平的糖果棒交换

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class NumMatrix {
public int[][] mat;
public int[][] presum; //presum[i][j]=matrix[i][0]+..+matrix[i][j-1]
public NumMatrix(int[][] matrix) {
this.mat=matrix;
int m=matrix.length;
if(m>0){
int n=matrix[0].length;
presum=new int[m][n+1];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
presum[i][j+1]=presum[i][j]+matrix[i][j];
}
}
}
}

public int sumRegion(int row1, int col1, int row2, int col2) {
int sum=0;
for(int i=row1;i<=row2;i++){
sum+=presum[i][col2+1]-presum[i][col1];
}
return sum;
}

}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/

每日一题 0303 比特位计数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int[] countBits(int num) {
int[] dp=new int[num+1];
for(int i=0;i<=num/2;i++){
dp[i*2]=dp[i];
if(i*2+1<=num){
dp[i*2+1]=dp[i]+1;
}
}
return dp;
}
}

每日一题 0304 俄罗斯套娃信封问题

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
"""
动态规划
首先我们将所有的信封按照 w 值第一关键字升序、h 值第二关键字降序进行排序;
随后我们就可以忽略 w 维度,求出 h 维度的最长严格递增子序列,其长度即为答案。

"""
class Solution {
public int maxEnvelopes(int[][] envelopes) {
int len=envelopes.length;
if(len<2) return len;
//排序
Arrays.sort(envelopes, new Comparator<int[]>() {
public int compare(int[] e1, int[] e2) {
if (e1[0] != e2[0]) {
return e1[0] - e2[0];
} else {
return e2[1] - e1[1];
}
}
});
int res=1;
int[] dp=new int[len];
Arrays.fill(dp,1);
//dp[i]=h 的前 i 个元素可以组成的最长严格递增子序列的长度
for(int i=1;i<len;i++){
for(int j=0;j<i;j++){
if(envelopes[i][1]>envelopes[j][1]){
dp[i]=Math.max(dp[j]+1,dp[i]);
}
}
res=Math.max(res,dp[i]);
}
return res;
}
}

技巧:

1、求中间下标用low + (high - low) // 2 而不是 (high + low) // 2,是为了防止low+high溢出
2、有序 二分
3、划分数组 一半一半 想到双指针
4、倒数第k个节点 也是双指针 一个先走k步(快慢指针)
5、求矩形最大面积—单调栈
6、图(建图 bfs求两结点的最短路径)
7、前缀树 新的一种数据结构 用于字符串匹配
8、判断链表是否有环 以及环的起点和长度(Floyd判环算法 龟兔赛跑
9、top-k 用堆或者二叉搜索树
10、LRU缓存实现 hashmap+LinkedList
11、最小编辑距离
12、同样的数出现偶数次 找出奇数次的数(异或 然后以异或为1的最低位分为两组 各自异或可得出现奇数次的数)
同样的数出现奇数次,找出偶数次的数 各位相加 若奇数次和可被其整除,不能整除的则为偶数次的数

树遍历

层序遍历

1、单栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
ArrayList<Integer> res = new ArrayList<>();
if(root!=null) queue.add(root);
while(!queue.isEmpty()){
int len = queue.size();
while(len-->0){
TreeNode cur = queue.poll();
res.add(cur.val);
if(cur.left!=null) queue.add(cur.left);
if(cur.right!=null) queue.add(cur.right);
}
}
return res;
}
}

2、双栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int maxDepth(TreeNode root) {
//层序遍历
if(root==null) return 0;
List<TreeNode> now_layer=new ArrayList<TreeNode>();
List<TreeNode> next_layer=new ArrayList<TreeNode>();
int res=0;
now_layer.add(root);
while(now_layer.size()>0){
res+=1;
for(TreeNode p:now_layer){
if(p.left!=null) next_layer.add(p.left);
if(p.right!=null) next_layer.add(p.right);
}
now_layer=next_layer;//更新当前栈
next_layer=new ArrayList<TreeNode>();
}
return res;
}
}

排序

1、冒泡排序 (稳定、N2,1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
从左到右不断交换相邻逆序的元素,在一轮的循环之后,可以让未排序的最大元素上浮到右侧。
在一轮循环中,如果没有发生交换,那么说明数组已经是有序的,此时可以直接退出。
"""
public void sort(int[] nums){
boolean issorted=false;
int len=nums.length;
for(int i=len-1;i>0&&(issorted==false);i--){
issorted=true;
for(int j=0;j<i;j++){
if(nums[j]>nums[j+1]){
issorted=false;
swap(nums,j,j+1);
}
}
}
}

2、归并排序(稳定、NlogN,N(merge时辅助数组))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void sort(int[] nums){
mergeandsort(nums,0,nums.length-1);
}
public void mergeandsort(int[] nums,int l,int h){
if(l<h){
int m=(l+h)/2;
mergeandsort(nums,l,m);
mergeandsort(nums,m+1,h);
merge(nums,l,m,h);
}
else return;
}
public void merge(int[] nums,int l,int m,int h){
int i=l,j=m+1;
int[] temp=nums.clone();
for(int k=l;k<=h;k++){
if(i>m) nums[k]=temp[j++];
else if(j>h) nums[k]=temp[i++];
else if(temp[i]>temp[j]) nums[k]=temp[j++];
else nums[k]=temp[i++];

}
}

3、快速排序 (使用之前可以先随机打乱,不稳定,NlogN,logN(栈))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public void sort(int[] nums){
quicksort(nums,0,nums.length-1);
}
public void quicksort(int[] nums,int l,int h){
if(l<h){
int m=partition(nums,l,h);
quicksort(nums,l,m-1);
quicksort(nums,m+1,h);
}

}
public int partition(int[] nums,int l,int h){
int pivot=nums[l];
int i=l+1,j=h;
while(true){
while(i<=h&&nums[i]<=pivot) i++;
while (j>=0&&nums[j]>pivot) j--;
if(i>j) break;
swap(nums,i,j);
}
swap(nums,l,j);
return j;
}
public void swap(int[] nums,int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}

单调栈

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
"""
单调栈
"""
class Solution {
public int largestRectangleArea(int[] heights) {
// 这里为了代码简便,在柱体数组的头和尾加了两个高度为 0 的柱体。 加最后一个0是为了计算栈中剩余的递增面积 若不加最后一个零 剩余递增不会被计算
int[] tmp = new int[heights.length + 2];
System.arraycopy(heights, 0, tmp, 1, heights.length);

Deque<Integer> stack = new ArrayDeque<>();
int area = 0;
for (int i = 0; i < heights.length+2; i++) {
// 对栈中柱体来说,栈中的下一个柱体就是其「左边第一个小于自身的柱体」;
// 若当前柱体 i 的高度小于栈顶柱体的高度,说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
// 因此以栈顶柱体为高的矩形的左右宽度边界就确定了,可以计算面积🌶️ ~
while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
int h = tmp[stack.pop()];
area = Math.max(area, (i - stack.peek() - 1) * h);
}
stack.push(i);
}

return area;
}
}

8、Floyd判环算法 龟兔赛跑

参考博客:https://blog.csdn.net/u012534831/article/details/74231581
题目描述
题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead==null ||pHead.next==null) return null;
ListNode fast = pHead;
ListNode slow = pHead;
do{
fast = fast.next.next;
slow = slow.next;
}while(fast!=null && fast.next!=null && fast!=slow);

if(fast==null ||fast.next==null) return null;

fast = pHead;
while(fast!=slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
"""
弗洛伊德(Floyd )使用了两个指针,一个慢指针(龟)每次前进一步,快指针(兔)指针每次前进两步(两步或多步效果是等价的,只要一个比另一个快就行。但是如果移动步数增加,算法的复杂度可能增加)。
如果两者在链表头以外(不包含开始情况)的某一点相遇(即相等)了,那么说明链表有环,否则,如果(快指针)到达了链表的结尾(如果存在结尾,肯定无环),那么说明没环。

环的起点:将慢指针(或快指针)移到链表起点,然后两者同时移动,每次移动一步,那么两者相遇的地方就是环的起点。

环的长度:当两者相遇之后,固定一个指针,让另一个指针行走一圈,使用count计数,如果两个指针相等(即相遇),则count即为环的长度。
"""

9、堆

剑指 Offer 40 最小的k个数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
"""
1、大堆
我们用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中,随后从第 k+1 个数开始遍历,如果当前遍历到的数比大根堆的堆顶的数要小,就把堆顶的数弹出,再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。

"""
public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
if (k > nums.length || k <= 0)
return new ArrayList<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int num : nums) {
maxHeap.add(num);
if (maxHeap.size() > k)
maxHeap.poll();
}
return new ArrayList<>(maxHeap);
}

"""
2、快排
"""
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(k==0 || arr.length==0){
return new int[0];
}
else
return quicksort(arr,0,arr.length-1,k-1);//第k个数的下标为k-1
}
//nums[k]的左边都小于它 右边都大于它
//其中k为下标
private int[] quicksort(int[] nums,int lo,int hi,int k){
int pivot=partition(nums,lo,hi);
if(pivot==k){
return Arrays.copyOf(nums,k+1);
}
else{
return pivot>k?quicksort(nums,lo,pivot-1,k):quicksort(nums,pivot+1,hi,k);
}
}
// 将nums[lo]作为基准 进行划分 最后返回pivot
//nums[pivot]的左边都小于它 右边都大于它
private int partition(int[] nums,int lo,int hi){
int pivot_value=nums[lo];
int i=lo,j=hi+1;
while(true){
while(++i<=hi && nums[i]<pivot_value);
while (--j>=lo && nums[j]>pivot_value);
if(i>=j){
break;
}
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
nums[lo]=nums[j];
nums[j]=pivot_value;
return j;
}
}
"""
3、二叉搜索树--TreeMap
我们遍历数组中的数字,维护一个数字总个数为 K 的 TreeMap:
1.若目前 map 中数字个数小于 K,则将 map 中当前数字对应的个数 +1;
2.否则,判断当前数字与 map 中最大的数字的大小关系:若当前数字大于等于 map 中的最大数字,就直接跳过该数字;若当前数字小于 map 中的最大数字,则将 map 中当前数字对应的个数 +1,并将 map 中最大数字对应的个数减 1。

"""
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// TreeMap的key是数字, value是该数字的个数。
// cnt表示当前map总共存了多少个数字。
TreeMap<Integer, Integer> map = new TreeMap<>();
int cnt = 0;
for (int num: arr) {
// 1. 遍历数组,若当前map中的数字个数小于k,则map中当前数字对应个数+1
if (cnt < k) {
map.put(num, map.getOrDefault(num, 0) + 1);
cnt++;
continue;
}
// 2. 否则,取出map中最大的Key(即最大的数字), 判断当前数字与map中最大数字的大小关系:
// 若当前数字比map中最大的数字还大,就直接忽略;
// 若当前数字比map中最大的数字小,则将当前数字加入map中,并将map中的最大数字的个数-1。
//Map.Entry是为了更方便的输出map键值对。entry.getvalue()获得当前entry的值 entry.getkey()获得当前entry的键
//java.util.TreeMap.lastEntry() 返回具有最大键的键值对;如果没有这样的键,则返回null。
Map.Entry<Integer, Integer> entry = map.lastEntry();
if (entry.getKey() > num) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (entry.getValue() == 1) {
map.pollLastEntry(); //若最大的数只有一个 则直接删除
} else {
map.put(entry.getKey(), entry.getValue() - 1); //若不止一个 则删除一个
}
}
}
// 最后返回map中的元素
int[] res = new int[k];
int idx = 0;
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
int freq = entry.getValue();
while (freq-- > 0) {
res[idx++] = entry.getKey();
}
}
return res;
}
}

10、堆

LRU缓存实现

一、问题描述

题目描述

节点用LinkedHashMap存 k,value
set:若map长度小于缓存大小,则直接存;不然就删除map最前面的那个节点(用迭代器)

get:利用key获得对应节点 并且将该节点删除,在链表末重新加上该节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
import java.util.*;
public class Solution {
/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LRU (int[][] operators, int k) {
// write code here
Map<Integer, Integer> map = new LinkedHashMap<>();
List<Integer> list = new LinkedList<>();
for (int[] operator : operators) {
int key = operator[1];
switch(operator[0]) {
case 1:
int value = operator[2];
if (map.size() < k) {
map.put(key, value);
} else {
Iterator it = map.keySet().iterator();
map.remove(it.next());
map.put(key, value);
}
break;
case 2:
if (map.containsKey(key)) {
int val = map.get(key);
list.add(val);
map.remove(key);
map.put(key, val);
} else {
list.add(-1);
}
break;
default:
}
}
int[] res = new int[list.size()];
int i = 0;
for (int val : list) {
res[i++] = val;
}
return res;
}
}

"""
使用LinkedHashMap不过关 双向队列也要自己写
"""
public class LRUCache {
HashMap<Integer, Node> map; //用于辅助查找 key是关键字,value就是存数据的node节点 其中node节点的value为真正的value
DoubleLinkedList cache; //真正存数据的 队列头是最近最常使用的数据
int cap; //缓存大小,超过这个大小 put的时候就要删除最近最少使用的数据
public LRUCache(int capacity){
map = new HashMap<>();
cache = new DoubleLinkedList();
cap = capacity;
}

public void put(int key, int val){
Node newNode = new Node(key, val);

if(map.containsKey(key)){ //若该值已在缓存,则移到队列头(先删除 然后头插)
cache.delete(map.get(key));
cache.addFirst(newNode);
map.put(key, newNode);
}else{ //若该值不存在,检查缓存是否已满,不满的话头插,不然删除队尾的数据然后头插
if(map.size() == cap){
int k = cache.deleteLast();
map.remove(k);
}
cache.addFirst(newNode);
map.put(key, newNode);

}
}

public int get(int key){ //根据hashmap直接得到对应存数据的节点
if(!map.containsKey(key)) return -1;

int val = map.get(key).val;
put(key, val);

return val;
}
}

/**
* 自己写双向列表
* head: recently used
* tail: LRU least recent used
*/
class DoubleLinkedList{
Node head;
Node tail;

public DoubleLinkedList(){
head = new Node(0,0);
tail = new Node(0,0);

head.next = tail;
tail.prev = head;
}

public void addFirst(Node node){

node.next = head.next;
node.prev = head;

head.next.prev = node;
head.next = node;
}

public int delete(Node n){
int key = n.key;
n.next.prev = n.prev;
n.prev.next = n.next;

return key;
}

public int deleteLast(){
if(head.next == tail) return -1;

return delete(tail.prev);
}
}

class Node{
public int key;
public int val;
public Node prev;
public Node next;

public Node(int key, int val){
this.key = key;
this.val = val;
}
}


/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/

最小编辑距离 dp

一、问题描述

题目描述

对“dp[i-1][j-1] 表示替换操作,dp[i-1][j] 表示删除操作,dp[i][j-1] 表示插入操作。”的补充理解:
以 word1 为 “horse”,word2 为 “ros”,且 dp[5][3] 为例,即要将 word1的前 5 个字符转换为 word2的前 3 个字符,也就是将 horse 转换为 ros,因此有:

(1) dp[i-1][j-1],即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro,然后将第五个字符 word1[4](因为下标基数以 0 开始) 由 e 替换为 s(即替换为 word2 的第三个字符,word2[2])

(2) dp[i][j-1],即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro,然后在末尾补充一个 s,即插入操作

(3) dp[i-1][j],即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros,然后删除 word1 的第 5 个字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
int minEditCost(string str1, string str2, int ic, int dc, int rc) {
if(str1==""&&str2=="") return 0;
int len1 = str1.size();
int len2 = str2.size();
//想清楚状态矩阵的定义,下标代表长度!!
int dp[len1+1][len2+1];
for(int i=0;i<=len1;i++){
dp[i][0] = i*dc;//str1所有字符全部删除变成str2
}
for(int j=0;j<=len2;j++){
dp[0][j] = j*ic;//空字符串str1全部插入变成str2
}
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(str1[i-1]==str2[j-1]) dp[i][j] = dp[i-1][j-1];
else{
//等价于str1的前i-1个字符和str2的前j-1个字符编辑距离的子问题。
//即对于str1的第i个字符'X',对于str2的第j个字符'W',我们在str1的末尾'X'替换为字符'W',
//那么dp[i][j]最小可以为dp[i-1][j-1]+rc;
int choice1 = dp[i-1][j-1] + rc;//替换

//等价于str1的前i个字符和str2的前j-1个字符编辑距离的子问题。
//即对于str2的第j个字符'X',我们在str1的末尾添加了一个相同的字符'X',
//那么dp[i][j]最小可以为dp[i][j-1]+ic;
int choice2 = dp[i][j-1]+ic;//插入

//等价于str1的前i-1个字符和str2的前j个字符编辑距离的子问题。
//即对于str1的第i个字符'X',我们在str2的末尾添加了一个相同的字符'X',等价于在str1的末尾删除了该字符'X',
//那么dp[i][j]最小可以为dp[i][j-1]+dc;
int choice3 = dp[i-1][j]+dc;//删除
dp[i][j] = min(choice1,min(choice2,choice3));
}
}
}
return dp[len1][len2];
}
};

无向图的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
"""
dfs 判断连通图个数
"""
class Solution {
public int findCircleNum(int[][] isConnected) {
int res=0;
int num=isConnected.length;
boolean[] visited=new boolean[num];
for(int i=0;i<num;i++){
if(visited[i]==false){
dfs(visited,i,isConnected);
res+=1;
}
}
return res;
}
public void dfs(boolean[] visited,int cur,int[][]isConnected){
for(int j=0;j<visited.length;j++){
if(isConnected[cur][j]==1&&visited[j]==false){
visited[j]=true;
dfs(visited,j,isConnected);
}
}
}
}
"""
2、bfs
对于每个城市,如果该城市尚未被访问过,则从该城市开始广度优先搜索,直到同一个连通分量中的所有城市都被访问到,即可得到一个省份。
"""
class Solution {
public int findCircleNum(int[][] isConnected) {
int res = 0;
int num = isConnected.length;
boolean[] visited = new boolean[num];
Queue<Integer> queue=new LinkedList<>();
for(int i=0;i<num;i++){
if(visited[i]==false){
queue.add(i);
res+=1;
while (!queue.isEmpty()){ //bfs
int j=queue.poll();
for(int k=0;k<num;k++){
if(isConnected[j][k]==1&&visited[k]==false){
queue.add(k);
visited[k]=true;
}
}
}
}
}
return res;
}
}

有序–二分

不会:34

剑指 Offer 04. 二维数组中的查找

剑指 Offer 07. 重建二叉树

剑指 Offer 08. 二叉树的下一个结点

剑指 Offer 09. 用两个栈实现队列

剑指 Offer 10-1 求斐波那契数列

剑指 Offer 10-2 青蛙跳台阶问题

剑指 Offer 10-3 矩形覆盖

剑指 Offer 10-4 变态跳台阶

剑指 Offer 11 旋转数组的最小数字

剑指 Offer 12 矩阵中的路径

剑指 Offer 13 机器人的运动范围

剑指 Offer 14 剪绳子

剑指 Offer 15 二进制中1的个数

剑指 Offer 16 数值的整数次方

剑指 Offer 18-2 删除链表中重复的结点

剑指 Offer 19 正则表达式匹配

剑指 Offer 21 调整数组顺序使奇数位于偶数前面

剑指 Offer 22 链表中倒数第k个节点

剑指 Offer 23 链表中环的入口结点

剑指 Offer 24 反转链表

剑指 Offer 25 合并两个排序的链表

剑指 Offer 26 树的子结构

剑指 Offer 29 顺时针打印矩阵

剑指 Offer 30 包含min函数的栈)

剑指 Offer 31 栈的压入、弹出序列

剑指 Offer 33 二叉搜索树的后序遍历序列

剑指 Offer 34 二叉树中和为某一值的路径

剑指 Offer 35 复制链表的复制

剑指 Offer 36 二叉搜索树与双向链表

剑指 Offer 37 序列化二叉树

剑指 Offer 38 字符串的全排列

剑指 Offer 39 数组中出现次数超过一半的数字

剑指 Offer 40 最小的k个数

剑指 Offer 42 连续子数组的最大和

剑指 Offer 41 数据流中的中位数

剑指 Offer 43 1~n整数中1出现的次数

剑指 Offer 44 数字序列中某一位的数字

剑指 Offer 45 把数组排成最小的数

剑指 Offer 46 把数字翻译成字符串

剑指 Offer 47 礼物的最大价值

剑指 Offer 48 最长不含重复字符的子字符串

剑指 Offer 49 丑数

剑指 Offer 50 第一个只出现一次的字符

剑指 Offer 51 数组中的逆序对

剑指 Offer 52 两个链表的第一个公共节点

剑指 Offer 53_1 在排序数组中查找数字

剑指 Offer 53_2 0~n-1中缺失的数字

剑指 Offer 54 二叉搜索树的第k大节点

剑指 Offer 55 二叉树的深度

剑指 Offer 55-1 平衡二叉树

剑指 Offer 56-1 数组中数字出现的次数

剑指 Offer 56-2 数组中数字出现的次数2

剑指 Offer 57 和为s的两个数字

剑指 Offer 57_2 和为s的两个数字

剑指 Offer 58_1 和为s的两个数字

剑指 Offer 58_2 左旋转字符串

剑指 Offer 59_1 滑动窗口的最大值

剑指 Offer 59_2 队列的最大值

剑指 Offer 60 n个骰子的点数

剑指 Offer 61 扑克牌中的顺子

剑指 Offer 62 圆圈中最后剩下的数字

剑指 Offer 63 股票的最大利润

剑指 Offer 64 求1+2+…+n

剑指 Offer 65 不用加减乘除做加法

剑指 Offer 66 构建乘积数组

剑指 Offer 67 把字符串转换为整数

剑指 Offer 68_1 二叉搜索树的最近公共祖先

大数的和

接雨水

剑指 Offer 04. 二维数组中的查找

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'''
有序就要想到二分 从数组右上角出发 其实是二叉搜索树
'''
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix.length<1||matrix[0].length<1) return false;
int i=0,j=matrix[0].length-1;
while(i<matrix.length&&j>=0){
if(matrix[i][j]>target) j--;
else if(matrix[i][j]<target) i++;
else return true;
}
return false;
}
}

剑指 Offer 07. 重建二叉树

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
'''
前序遍历性质: 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。
中序遍历性质: 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。
利用map 存中序遍历的值与其对应的下标,这样方便查找根节点在中序遍历数组的下标
'''
class Solution {
int[] preorder;
HashMap<Integer,Integer> map=new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for(int i=0;i<inorder.length;i++){
map.put(inorder[i],i);
}
this.preorder=preorder;
return recur(0,0,inorder.length-1);
}
//根节点在前序遍历的索引:root
//子树在中序遍历的左边界:left
//子树在中序遍历的右边界:right(闭) ;
public TreeNode recur(int root,int left,int right){
if(left>right) return null;
TreeNode node=new TreeNode(preorder[root]);
int idx=map.get(node.val);
node.left=recur(root+1,left,idx-1);
node.right=recur(root+1+idx-left,idx+1,right);
return node;
}
}

剑指 Offer 08. 二叉树的下一个结点

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'''
中序遍历某个节点的下一个节点 要么是该节点右子树的最左边的数,要么是其父节点(该节点是父节点的左子节点) 或者是父节点的父节点....
'''
public TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode.right != null) {
TreeLinkNode node = pNode.right;
while (node.left != null)
node = node.left;
return node;
} else {
while (pNode.next != null) {
TreeLinkNode parent = pNode.next;
if (parent.left == pNode)
return parent;
pNode = pNode.next;
}
}
return null;
}

剑指 Offer 09. 用两个栈实现队列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
'''
用两个栈 实现队列
队列入操作:直接入左边的栈
队列出操作:假如右边的栈不为空,则直接输出右边栈顶;假如右边栈为空,则将左边的数都弹出压到右边,再输出右边栈顶
'''
class CQueue {
Stack<Integer> s1;
Stack<Integer> s2;
public CQueue() {
s1=new Stack<>();
s2=new Stack<>();
}

public void appendTail(int value) {
s1.push(value);
}

public int deleteHead() {
if(!s2.empty()) return s2.pop();
else if(!s1.empty()){
while (!s1.empty()){
s2.push(s1.pop());
}
return s2.pop();
}
else return -1;
}
}

# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

剑指 Offer 10-1 求斐波那契数列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
由于只跟前两个数有关,于是用两个变量存前两个数
'''
class Solution {
public int fib(int n) {
int f0=0,f1=1;
if(n<2) return n;
int i=1;
while(i<n){
int temp=f1;
f1=(f0+f1)%1000000007;
f0=temp;
i+=1;
}
return f1;
}
}

剑指 Offer 10-2 青蛙跳台阶问题

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
跟10-1一样 也是动态规划问题 F(N)=F(N-1)+F(N-2)) 区别在于F(0)=1
因为跳台阶
等于最后剩两步 一次跳两步;
最后剩一步 一次跳一步,
全部情况等于上述两种情况的和
'''
class Solution {
public int numWays(int n) {
if(n<2) return 1;
int dp0=1,dp1=1,i=2;
while(i<=n){
int temp=dp1;
dp1=(dp0+dp1)%1000000007;
dp0=temp;
i+=1;
}
return dp1;
}
}

剑指 Offer 10-3 矩形覆盖

一、问题描述

题目描述
题目分析

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
public int rectCover(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 0;
for (int i = 3; i <= n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}

剑指 Offer 10-4 变态跳台阶

一、问题描述

题目描述
题目分析

二、具体代码

1
2
3
public int JumpFloorII(int target) {
return (int) Math.pow(2, target - 1);
}

剑指 Offer 11 旋转数组的最小数字

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
1、找到波谷
"""
class Solution {
public int minArray(int[] numbers) {
int i=1;
while(i<numbers.length&&numbers[i-1]<=numbers[i]) i+=1;
if(i==numbers.length) return numbers[0];
else return numbers[i];
}
}
"""
2、因为递增 有序就要想到二分
数组最后一个数一定小于等于数组第一个数
"""
class Solution {
public int minArray(int[] numbers) {
int l=0,h=numbers.length-1;
while(l<h){
int m=l+(h-l)/2; //防止high加low溢出
if(numbers[m]<numbers[h]) h=m; //m右边一定是递增的 都是最小值右边的数
else if(numbers[m]>numbers[h]) l=m+1; //m与h之间一定有最小值
else h--; //去重
}
return numbers[h];
}
}

剑指 Offer 12 矩阵中的路径

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
'''
回溯
'''
class Solution {
public boolean exist(char[][] board, String word) {
if(board.length<1||board[0].length<1||word.length()<1) return false;
int w=board[0].length,h=board.length;
boolean[][] visited=new boolean[h][w];
char[] words=word.toCharArray();
for(int i=0;i<h;i++) {
for (int j=0;j<w;j++){
if(words[0]==board[i][j]){ //遍历所有节点 看可以从哪个出发
if(dfs(board,i,j,visited,words,0)) return true;
}
}
}
return false;
}
//dfs(可访问的所有节点,本步想访问的节点下标,所有节点的访问状态,目标路径,已走到路径的哪一步)
public boolean dfs(char[][] board,int i,int j,boolean[][] visited,char[] words,int idx){
//找到满足条件的路径 返回
if(words.length==idx) return true;
//是否可以访问board[i][j] 条件判断
if(i<0||j<0||i==board.length||j==board[0].length||visited[i][j]||board[i][j]!=words[idx]){
return false;
}
//访问
visited[i][j]=true;
idx+=1;
if(dfs(board,i-1,j,visited,words,idx)||dfs(board,i+1,j,visited,words,idx)||dfs(board,i,j-1,visited,words,idx)||dfs(board,i,j+1,visited,words,idx)){
return true;
}
//撤销访问
visited[i][j]=false;
idx-=1;
return false;
}
}

剑指 Offer 13 机器人的运动范围

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
'''
题目就是从[0,0]出发,能够达到哪些地方,只能往上下左右移动,且下标数位和小于k,其实也只需计算往右下移动的 因为左上都是回到已访问过的节点
注意 这道题选择后不能撤销 因为算的是全部能访问到的节点 访问后不可撤销
递归
'''
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited=new boolean[m][n];
return dfs(visited,0,0,k);

}
public int dfs(boolean[][] visited,int i,int j,int k){
if(isvalid(i,j,k,visited)){
visited[i][j]=true;
//下方搜索的可达解总数+1也就是本节点 + 右方搜索的可达解总数
return dfs(visited,i+1,j,k)+dfs(visited,i,j+1,k)+1;
}
else return 0;
}
//判断是否可访问节点(i,j)
public boolean isvalid(int i,int j,int k,boolean[][] visited){
int temp=0;
if(i<0||j<0||i==visited.length||j==visited[0].length||visited[i][j]) return false;
while(i>0){
temp+=i%10;
i/=10;
}
while (j>0){
temp+=j%10;
j/=10;
}
if(temp>k) return false;
return true;
}
}

剑指 Offer 14 剪绳子

一、问题描述

题目描述
理论推导

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
当每段都为3时,乘积最大
若最后为4,因为2*2大于1*3,所以乘4
其余情况就每段取3 再乘以小于3的
'''
class Solution {
public int cuttingRope(int n) {
int res=1;
if(n<4) return n-1;
while(n>4){
res*=3;
n-=3;
}
return res*n;
}
}

剑指 Offer 15 二进制中1的个数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
'''
最右一位和1与 若最右一位为1 则结果为1 否则为0
判断完后 将数往右移一位
'''
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count=0;
int help=1;
while(n!=0){
if((help&n)!=0) count+=1;
n=n>>>1; //无符号右移 如果有符号 负数右移补1 死循环
}
return count;
}
}

剑指 Offer 16 数值的整数次方

一、问题描述

题目描述
理论推导

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
'''
快速幂法(二分法角度)
'''
class Solution {
public double myPow(double x, int n) {
if(n==0) return 1.0;
//Java 代码中 int32 变量in [-2147483648, 2147483647] n∈[−2147483648,2147483647] ,因此当 n = -2147483648时执行 n = -n会因越界而赋值出错。解决方法是先将n 存入 long 变量b,后面用 b操作即可。
long b=n;
double res=1.0;
if(n<0){
x=1/x;
b=-b;
}
while(b>0){
if((b&1)!=0) res*=x;
x*=x;
b=b>>1;
}
return res;
}
}

剑指 Offer 18-2 删除链表中重复的结点

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
'''
伪造头结点来统一节点为空的情况
'''
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
ListNode preHead = new ListNode(-1); //伪造的头结点
ListNode pre = preHead;
ListNode now = pHead; //当前节点
ListNode nextNode;
while(now != null){
nextNode = now.next;
if(nextNode!=null && now.val==nextNode.val){ //假如是重复节点,一直遍历到不同的节点
while(now!=null && now.next!=null && now.val==nextNode.val){
now = nextNode;
nextNode = nextNode.next;
}
now = nextNode; // 因为要删除重复节点,所以直接跳过重复节点,now到下一个不一样的节点(也可能是重复的)
}else{
pre.next = now;
pre = now;
now = nextNode;
}
}
pre.next = now; //假如由于重复节点一直到链表末,那么会由于now==null跳出循环,这时候要把不重复链表的最后一个节点指向now。否则会保留最后一段重复节点链表
return preHead.next;
}
}

剑指 Offer 19 正则表达式匹配

一、问题描述

题目描述
理论推导

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
'''
class Solution:
def isMatch(self, s, p):
m,n = len(s),len(p)
dp = [[False for _ in range(n+1)] for _ in range(m+1)]
dp[0][0] = True #空正则 空串

for i in range(0,m+1):
for j in range(1,n+1):
if p[j-1]!='*':
if i>0 and (p[j-1]==s[i-1] or p[j-1]=='.'):
dp[i][j]=dp[i-1][j-1]
else:
if j>=2 and dp[i][j-2]==True: # 不看*前的字符
dp[i][j]=True
if i>=1 and j>=2 and (s[i-1]==p[j-2] or p[j-2]=='.') and dp[i-1][j]==True: #看
dp[i][j]=True
return dp[m][n]

剑指 Offer 21 调整数组顺序使奇数位于偶数前面

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'''
双指针法 i指向偶数 j指向奇数 若i<j则交换
这种可以用于 不要求稳定性的情况
'''
class Solution {
public int[] exchange(int[] nums) {
int l=0,h=nums.length-1;
while(l<h){
while(l<nums.length&&(nums[l]&1)==1)l++;
while(h>0&&(nums[h]&1)==0)h--;
if(l>=h) return nums;
int temp=nums[h];
nums[h]=nums[l];
nums[l]=temp;
}
return nums;
}
}

剑指 Offer 22 链表中倒数第k个节点

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
'''
双指针法 helper先走k步 随后helper和res同时走,当helper到达末尾时,res也就到达了倒数第k个数
若如果该链表长度小于k,请返回一个长度为 0 的链表。
'''
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
ListNode res = pHead;
ListNode p = pHead;
while(p!=null && k>0){
p = p.next;
k--;
}
if(k>0) return null;
while(p!=null){
res=res.next;
p=p.next;
}
return res;
}

剑指 Offer 23 链表中环的入口结点

一、问题描述

一个链表中包含环,请找出该链表的环的入口结点。要求不能使用额外的空间。
参考博客:https://blog.csdn.net/u012534831/article/details/74231581
题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
'''
快慢指针
'''
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead==null ||pHead.next==null) return null;
ListNode fast = pHead;
ListNode slow = pHead;
do{
fast = fast.next.next;
slow = slow.next;
}while(fast!=null && fast.next!=null && fast!=slow);
if(fast==null ||fast.next==null) return null;

fast = pHead;
while(fast!=slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}

剑指 Offer 24 反转链表

一、问题描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"""
pre p tmp 转p.next=pre 然后pre p后移一位
"""
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode p=head;
while(p!=null){
ListNode tmp=p.next;
p.next=pre;
pre=p;
p=tmp;
}
return pre;
}
}

剑指 Offer 25 合并两个排序的链表

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
'''
双指针法 i指向链表1待比较节点 j指向链表2待比较节点
'''
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode pre = new ListNode(-1);
ListNode now = pre;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
now.next = list1;
list1 = list1.next;
}else{
now.next = list2;
list2 = list2.next;
}
now = now.next;
}
if(list2 == null) now.next = list1;
if(list1 == null) now.next = list2;
return pre.next;
}
}
'''
同样思路 大佬的写法
'''
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dum=new ListNode(0);//伪节点
ListNode head=dum;
while(l1!=null&&l2!=null){
if(l1.val>l2.val) {
dum.next=l2;
l2=l2.next;
}
else {
dum.next=l1;
l1=l1.next;
}
dum=dum.next;
}
dum.next=(l1!=null)?l1:l2;
return head.next;
}
}

剑指 Offer 26 树的子结构

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
'''
递归
'''
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A==null||B==null) return false;
if(issame(A,B)) return true;
else return isSubStructure(A.left,B)||isSubStructure(A.right,B);
}
public boolean issame(TreeNode A,TreeNode B){
if(B==null) return true; //遍历完了
else if(A==null) return false;
if(A.val!=B.val) return false;
else return issame(A.left,B.left)&&issame(A.right,B.right);
}
}
'''
二叉树的镜像(翻转左右子树)
'''
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root==null||(root.left==null&&root.right==null)) return root;
mirrorTree(root.left);
mirrorTree(root.right);
TreeNode tmp=root.right;
root.right=root.left;
root.left=tmp;
return root;
}
}
'''
判断是否左右对称
'''
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return true;
return issame(root.left,root.right);
}
public boolean issame(TreeNode A,TreeNode B){
if(A==null&&B==null) return true;
if(A==null||B==null) return false;
return A.val==B.val&&issame(A.left,B.right)&&issame(A.right,B.left); //注意左右对称 是要左孩子与右孩子比
}
}

剑指 Offer 29 顺时针打印矩阵

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
"""
模拟打印
用二维数组存方向和对应的i,j边界变量增量 简化代码
"""
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length<1||matrix[0].length<0) return new int[0];
int[][] directions={{0,1},{1,0},{0,-1},{-1,0}};
int m=matrix.length,n=matrix[0].length;
boolean[][] visited=new boolean[m][n];
int[] res=new int[m*n];
res[0]=matrix[0][0];
visited[0][0]=true;
int i=0,j=0,idx=1,direct_idx=0;
while (idx<res.length){
int di=directions[direct_idx][0];
int dj=directions[direct_idx][1];
while(i+di<m&&i+di>=0&&j+dj<n&&j+dj>=0&& !visited[i + di][j + dj]){//按一个方向走到不能走
i+=di;
j+=dj;
res[idx]=matrix[i][j];
visited[i][j]=true;
idx+=1;
}
direct_idx=(direct_idx+1)%4; //走不通 换方向
}
return res;
}
}

剑指 Offer 30 包含min函数的栈

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
辅助栈
"""
class MinStack {
Stack<Integer> stack,minstack;
/** initialize your data structure here. */
public MinStack() {
stack=new Stack<>();
minstack=new Stack<>();
}

public void push(int x) {
stack.push(x);
if(minstack.isEmpty()||minstack.peek()>=x){
minstack.push(x);
}
}

public void pop() {
int tmp=stack.pop();
if(minstack.peek().equals(tmp)) minstack.pop();
}

public int top() {
return stack.peek();
}

public int min() {
return minstack.peek();
}
}

剑指 Offer 31 栈的压入、弹出序列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
    """
辅助栈模拟弹入弹出过程中的栈
根据弹出序列
1、若该待弹出元素还没入栈 即在弹入序列中,则将弹入序列中排在该元素前的元素都压入栈中
2、若该待弹出元素在栈中,则一定是栈顶元素 不然就False
"""
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack= new Stack<>();
int push_idx=0,i=0;
while (i<popped.length){
if(stack.isEmpty()||stack.peek()!=popped[i]){//栈顶元素不为待弹出元素
while(push_idx<pushed.length&&pushed[push_idx]!=popped[i]){
stack.add(pushed[push_idx]);
push_idx+=1;
}
if(push_idx<pushed.length) {
i+=1;
push_idx+=1;
continue;
}
return false;//待弹入没有待弹出元素
}
else { //若栈顶元素为待弹出的 直接出栈
stack.pop();
i+=1;
}
}
return true;
}
}

剑指 Offer 32_1 从上到下打印二叉树

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
"""
层序遍历
"""
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null) return new int[0];
Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};
ArrayList<Integer> ans = new ArrayList<>();
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
ans.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
int[] res = new int[ans.size()];
for(int i = 0; i < ans.size(); i++)
res[i] = ans.get(i);
return res;
}
}
"""
2、分层 二维矩阵输出
"""

class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) return new LinkedList<>();
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
int len;
List<List<Integer>> res=new LinkedList<>();
while(!queue.isEmpty()){
List<Integer> tmplayer= new LinkedList<>();
len=queue.size();
while(len>0){
TreeNode tmp=queue.poll();
len-=1;
tmplayer.add(tmp.val);
if(tmp.left!=null) queue.add(tmp.left);
if(tmp.right!=null) queue.add(tmp.right);
}
res.add(tmplayer);
}
return res;
}
}
"""
3、分层 隔层逆序输出 加个flag就可
"""
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) return new LinkedList<>();
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
int len;
List<List<Integer>> res=new LinkedList<>();
boolean flag=false;
while(!queue.isEmpty()){
List<Integer> tmplayer= new LinkedList<>();
len=queue.size();
while(len>0){
TreeNode tmp=queue.poll();
len-=1;
if(flag){
tmplayer.add(0,tmp.val);
}
else
{tmplayer.add(tmp.val);}
if(tmp.left!=null) queue.add(tmp.left);
if(tmp.right!=null) queue.add(tmp.right);
}
flag=!flag;
res.add(tmplayer);
}
return res;
}
}

剑指 Offer 33 二叉搜索树的后序遍历序列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
"""
二叉搜索树的后序遍历有个特点:
根节点是最后一个数 并且可以将序列按顺序切割 前一截小于根节点的为左子树,后一截大于根节点的为右子树。
l,m-1为左子树
m,h-1为右子树
"""
class Solution {
public boolean verifyPostorder(int[] postorder) {
return recur(postorder,0,postorder.length-1);
}
public boolean recur(int[] postorder,int l,int h){
if(l>=h) return true;
int m,p=l;
int root=postorder[h];
while(postorder[p]<root) p++;
m=p;
while(postorder[p]>root) p++;
return p==h&&recur(postorder,l,m-1)&&recur(postorder,m,h-1);
}
}

剑指 Offer 34 二叉树中和为某一值的路径

一、问题描述

题目描述

二、具体代码

回溯+dfs 先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
private ArrayList<Integer> path = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
backtrace(root, target);
return res;
}
private void backtrace(TreeNode root, int target){
if(root == null) return;
path.add(root.val); //选择
if(root.left==null && root.right==null && root.val==target){
res.add(new ArrayList<>(path));
}else{
backtrace(root.left, target-root.val);
backtrace(root.right, target-root.val);
}
path.remove(path.size()-1); //撤销选择
}
}

剑指 Offer 35 复杂链表的复制

一、问题描述

题目描述

二、具体代码

具体分为3步:

1、在每个原节点后面新增一个节点 值与原节点一致 temp=Node(cur.val,cur.next)

2、复制原节点的randan指针  新节点的randan指向原节点randan的后一个节点  copycur.random=cur.random.next

3、拆分链表  要注意两个链表的末尾的next都为None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node cur = head;
// 1. 复制各节点,并构建拼接链表
while(cur != null) {
Node tmp = new Node(cur.val);
tmp.next = cur.next;
cur.next = tmp;
cur = tmp.next;
}
// 2. 构建各新节点的 random 指向
cur = head;
while(cur != null) {
if(cur.random != null)
cur.next.random = cur.random.next;
cur = cur.next.next;
}
// 3. 拆分两链表
cur = head.next;
Node pre = head, res = head.next;
while(cur.next != null) {
pre.next = pre.next.next;
cur.next = cur.next.next;
pre = pre.next;
cur = cur.next;
}
pre.next = null; // 单独处理原链表尾节点
return res; // 返回新链表头节点
}
}

剑指 Offer 36 二叉搜索树与双向链表

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
利用二叉搜索树中序遍历是递增的这一特性
递归中序遍历
另外新增两个指针节点 head和pre
"""

public class Solution {
private TreeNode pre;
private TreeNode head;
public TreeNode Convert(TreeNode pRootOfTree) {
inOrder(pRootOfTree);
return head;
}
private void inOrder(TreeNode root){
if(root == null) return;
inOrder(root.left);
root.left = pre;
if(pre!=null) pre.right = root;
if(head == null) head = root;
pre = root;
inOrder(root.right);
}
}

剑指 Offer 37 序列化二叉树

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
"""
序列化的字符串实际上是二叉树的 “层序遍历”(BFS)结果
队列模仿层序遍历
string->int Integer.parseInt(string)
int ->string string.valueof(int)
string截断 .substring()

"""

public class Codec {
public String serialize(TreeNode root) {
if(root==null) return "[]";
StringBuilder res=new StringBuilder("[");
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode temp=queue.poll();
if(temp!=null){
res.append(temp.val+",");
queue.add(temp.left);//左右节点入队
queue.add(temp.right);
}
else res.append("null,");
}
res.delete(res.length()-1,res.length()-1);
res.append("]");
return res.toString();
}
public TreeNode deserialize(String data) {
if(data.equals("[]")) return null;
String[] nums=data.substring(1,data.length()-1).split(",");
Queue<TreeNode> queue=new LinkedList<>();
TreeNode root=new TreeNode(Integer.parseInt(nums[0]));
queue.add(root);
int i=1;
while (!queue.isEmpty()){
TreeNode temp=queue.poll();
if(temp!=null){
if(!nums[i].equals("null")){
temp.left=new TreeNode(Integer.parseInt(nums[i]));
queue.add(temp.left);
}
i+=1;
if(!nums[i].equals("null")){
temp.right=new TreeNode(Integer.parseInt(nums[i]));
queue.add(temp.right);
}
i+=1;
}
}
return root;
}
}

剑指 Offer 38 字符串的全排列

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
"""
回溯+剪枝
"""
import java.util.*;

public class Solution {
public String[] permutation(String s) {
int len = s.length();
if (len == 0) {
return new String[0];
}
// 转换成字符数组是常见的做法
char[] charArr = s.toCharArray();
// 排序是为了去重方便
Arrays.sort(charArr);
// 由于操作的都是字符,使用 StringBuilder
StringBuilder path = new StringBuilder();
boolean[] used = new boolean[len];

// 为了方便收集结果,使用动态数组
List<String> res = new ArrayList<>();
dfs(charArr, len, 0, used, path, res);

// 记得转成字符串数组
return res.toArray(new String[0]);
}

/**
* @param charArr 字符数组
* @param len 字符数组的长度
* @param depth 当前递归深度
* @param used 当前字符是否使用
* @param path 从根结点到叶子结点的路径
* @param res 保存结果集的变量
*/
private void dfs(char[] charArr,
int len,
int depth,
boolean[] used,
StringBuilder path,
List<String> res) {
if (depth == len) {
// path.toString() 恰好生成了新的字符对象
res.add(path.toString());
return;
}
for (int i = 0; i < len; i++) {
if (!used[i]) {
if (i > 0 && charArr[i] == charArr[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
path.append(charArr[i]);

dfs(charArr, len, depth + 1, used, path, res);

// 递归完成以后,需要撤销选择,递归方法执行之前做了什么,递归方法执行以后就需要做相应的逆向操作
path.deleteCharAt(path.length() - 1);
used[i] = false;
}
}
}
}

剑指 Offer 39 数组中出现次数超过一半的数字

一、问题描述

题目描述
题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
"""
摩尔投票法:
设输入数组 nums 的众数为 x ,数组长度为 n 。
推论一: 若记 众数 的票数为 +1 ,非众数 的票数为 −1 ,则一定有所有数字的 票数和 > 0。
推论二: 若数组的前 a 个数字的 票数和 =0 ,则 数组剩余 (n-a)个数字的 票数和一定仍 >0 ,即后(n−a) 个数字的 众数仍为x 。

算法流程:
初始化: 票数统计 votes = 0 , 众数 x;
循环: 遍历数组 nums 中的每个数字 num ;
当 票数 votes 等于 0 ,则假设当前数字 num 是众数;
当 num = x 时,票数 votes 自增 1 ;当 num != x 时,票数 votes 自减 1 ;
返回值: 返回 x 即可;
"""

class Solution {
public int majorityElement(int[] nums) {
int num=nums[0];
if(nums.length<3){
return nums[0];
}
int count=0;
for(int i:nums){
if(i==num){
count+=1;
}
else if(count>1){
count-=1;
}
else{
num=i;
count=1;
}
}
return num;
}
}

"""
若找出投票超过1/3的候选人
"""
class Solution {
public List<Integer> majorityElement(int[] nums) {
// 创建返回值
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0) return res;
// 初始化两个候选人candidate,和他们的计票
int cand1 = nums[0], count1 = 0;
int cand2 = nums[0], count2 = 0;

// 摩尔投票法,分为两个阶段:配对阶段和计数阶段
// 配对阶段
for (int num : nums) {
// 投票
if (cand1 == num) {
count1++;
continue;
}
if (cand2 == num) {
count2++;
continue;
}

// 第1个候选人配对
if (count1 == 0) {
cand1 = num;
count1++;
continue;
}
// 第2个候选人配对
if (count2 == 0) {
cand2 = num;
count2++;
continue;
}

count1--;
count2--;
}

// 计数阶段
// 找到了两个候选人之后,需要确定票数是否满足大于 N/3
count1 = 0;
count2 = 0;
for (int num : nums) {
if (cand1 == num) count1++;
else if (cand2 == num) count2++;
}

if (count1 > nums.length / 3) res.add(cand1);
if (count2 > nums.length / 3) res.add(cand2);

return res;
}
}

作者:wotxdx
链接:https://leetcode-cn.com/problems/majority-element-ii/solution/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

剑指 Offer 40 最小的k个数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
"""
1、大堆
我们用一个大根堆实时维护数组的前 k 小值。每次大根堆中数字的个数超过k后,将最大的弹出,这样每次留下来的都是最小的k个数

"""
public ArrayList<Integer> GetLeastNumbers_Solution(int[] nums, int k) {
if (k > nums.length || k <= 0)
return new ArrayList<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int num : nums) {
maxHeap.add(num);
if (maxHeap.size() > k)
maxHeap.poll();
}
return new ArrayList<>(maxHeap);
}


"""
2、快排
"""
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(k==0 || arr.length==0){
return new int[0];
}
else
return quicksort(arr,0,arr.length-1,k-1);//第k个数的下标为k-1
}
//nums[k]的左边都小于它 右边都大于它
//其中k为下标
private int[] quicksort(int[] nums,int lo,int hi,int k){
int pivot=partition(nums,lo,hi);
if(pivot==k){
return Arrays.copyOf(nums,k+1);
}
else{
return pivot>k?quicksort(nums,lo,pivot-1,k):quicksort(nums,pivot+1,hi,k);
}
}
// 将nums[lo]作为基准 进行划分 最后返回pivot
//nums[pivot]的左边都小于它 右边都大于它
private int partition(int[] nums,int lo,int hi){
int pivot_value=nums[lo];
int i=lo,j=hi+1;
while(true){
while(++i<=hi && nums[i]<pivot_value);
while (--j>=lo && nums[j]>pivot_value);
if(i>=j){
break;
}
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
nums[lo]=nums[j];
nums[j]=pivot_value;
return j;
}
}
"""
3、二叉搜索树--TreeMap
我们遍历数组中的数字,维护一个数字总个数为 K 的 TreeMap:
1.若目前 map 中数字个数小于 K,则将 map 中当前数字对应的个数 +1;
2.否则,判断当前数字与 map 中最大的数字的大小关系:若当前数字大于等于 map 中的最大数字,就直接跳过该数字;若当前数字小于 map 中的最大数字,则将 map 中当前数字对应的个数 +1,并将 map 中最大数字对应的个数减 1。

"""
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// TreeMap的key是数字, value是该数字的个数。
// cnt表示当前map总共存了多少个数字。
TreeMap<Integer, Integer> map = new TreeMap<>();
int cnt = 0;
for (int num: arr) {
// 1. 遍历数组,若当前map中的数字个数小于k,则map中当前数字对应个数+1
if (cnt < k) {
map.put(num, map.getOrDefault(num, 0) + 1);
cnt++;
continue;
}
// 2. 否则,取出map中最大的Key(即最大的数字), 判断当前数字与map中最大数字的大小关系:
// 若当前数字比map中最大的数字还大,就直接忽略;
// 若当前数字比map中最大的数字小,则将当前数字加入map中,并将map中的最大数字的个数-1。
//Map.Entry是为了更方便的输出map键值对。entry.getvalue()获得当前entry的值 entry.getkey()获得当前entry的键
//java.util.TreeMap.lastEntry() 返回具有最大键的键值对;如果没有这样的键,则返回null。
Map.Entry<Integer, Integer> entry = map.lastEntry();
if (entry.getKey() > num) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (entry.getValue() == 1) {
map.pollLastEntry(); //若最大的数只有一个 则直接删除
} else {
map.put(entry.getKey(), entry.getValue() - 1); //若不止一个 则删除一个
}
}
}
// 最后返回map中的元素
int[] res = new int[k];
int idx = 0;
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
int freq = entry.getValue();
while (freq-- > 0) {
res[idx++] = entry.getKey();
}
}
return res;
}
}

剑指 Offer 42 连续子数组的最大和

一、问题描述

题目描述
问题思路

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
动态规划
dp 以当前节点为结尾的数组和的最大值 若前一个节点的最大值为正 直接加上即可 不然就不加
随时更新全局最大值
"""
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length<2){
return nums[0];
}
int pre_dp=nums[0];
int now_dp;
int res=pre_dp;
for(int i=1;i<nums.length;i++){
now_dp=nums[i];
if (pre_dp>0){
now_dp+=pre_dp;
}
pre_dp=now_dp;
res=res>now_dp?res:now_dp;
}
return res;
}
}

剑指 Offer 41 数据流中的中位数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
"""
左右均分用大小堆存 注意返回要为double,所以最后/2.0
"""
class MedianFinder {
Queue<Integer> left,right; //数组排序后均分到left,right
/** initialize your data structure here. */
public MedianFinder() {
left=new PriorityQueue<>((x,y)->(y-x));//大堆 堆顶元素为最靠近middle的元素
right=new PriorityQueue<>();//小堆 堆顶元素为最靠近middle的元素
}
//默认把多的一个数加到left 中位数就为left的堆顶
public void addNum(int num) {
if(left.size()==right.size()){
right.add(num);//先加到右边 再把右边最小的元素加到左边
left.add(right.poll());
}
else {
left.add(num);
right.add(left.poll());
}
}

public double findMedian() {
if(left.size()==right.size()){
return (left.peek()+right.peek())/2.0;
}
else return left.peek();
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/

剑指 Offer 43 1~n整数中1出现的次数

一、问题描述

题目描述

二、具体代码

问题思路
问题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int countDigitOne(int n) {
int digit=1,low=0,high=n/10;
int cur=n%10,res=0;
while(cur!=0||high!=0){
if(cur==0) res+=high*digit;
else if(cur==1) res+=high*digit+low+1;
else res+=(high+1)*digit;
low+=cur*digit;
digit*=10;
cur=high%10;
high/=10;
}
return res;
}
}

剑指 Offer 44 数字序列中某一位的数字

一、问题描述

题目描述

二、具体代码

问题思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int findNthDigit(int n) {
int digit = 1; // n所在数字的位数
long start = 1; // 数字范围开始的第一个数
long count = 9; // 占多少位
while(n>count){
n-=count;
digit+=1;
start*=10;
count=digit*start*9; //每个位数对应数字占的总个数
}
//属于哪个数
long num=start+(n-1)/digit;
int res=(n-1)%digit; //属于该数的第几位
return Long.toString(num).charAt(res)-'0';
}
}

剑指 Offer 45 把数组排成最小的数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public String minNumber(int[] nums) {
String[] strs=new String[nums.length];
for(int i=0;i<nums.length;i++){
strs[i]=String.valueOf(nums[i]); //把int数组转化为string数组
}
//string数组排序 排序规则 x+y(字符串拼接)>y+x 则x大 否则y大
//lamda表达式 (参数)->{表达式}
Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x));
//把string数组转化为string
StringBuilder res=new StringBuilder();
for(String temp:strs){
res.append(temp);
}
return res.toString();
}
}

剑指 Offer 46 把数字翻译成字符串

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"""
递归 也可以dp
"""
class Solution {
public int translateNum(int num) {
if(num<10){ //单位数 只有一种翻译
return 1;
}
int yushu=num%100;
if(yushu<10 || yushu>25) //只有一种翻译
{return translateNum(num/10);}
else{
return translateNum(num/10)+translateNum(num/100); //可以有两种翻译 既可以当做一个字母,也可以当做两个字母
}
}
}

剑指 Offer 47 礼物的最大价值

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
dp
"""
class Solution {
public int maxValue(int[][] grid) {
int[][] dp=new int[grid.length][grid[0].length];
dp[0][0]=grid[0][0];//dp[i][j]代表到达(i,j)能拿到的最大礼物价值
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
int left=j>0?dp[i][j-1]:0; //从左边到达
int top=i>0?dp[i-1][j]:0; //从上边到达
dp[i][j]=Math.max(left,top)+grid[i][j]; //取最大
}
}
return dp[grid.length-1][grid[0].length-1];
}
}

剑指 Offer 48 最长不含重复字符的子字符串

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length()==0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
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;
}
}

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"""
动态规划
"""
class Solution {
public int lengthOfLongestSubstring(String s) {
int res=0;
int temp=0; // dp[j-1]
Map<Character,Integer> map=new HashMap<>();
for(int j=0;j<s.length();j++) {
int i = map.getOrDefault(s.charAt(j),-1); // 获取最新出现字符j对应的索引 i
map.put(s.charAt(j),j); //更新索引表
temp=temp<j-i?temp+1:j-i; //获得dp[j] 若dp[j-1]<j-i即i在子串dp[j-1]区间之外 dp[j]=dp[j-1]+1 不然就在区间内 dp[j]=j-i
res=Math.max(temp,res);
}
return res;
}
}

剑指 Offer 49 丑数

一、问题描述

题目描述

二、具体代码

具体思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
三指针法 所有丑数的排列,必定就是ABC3个数组的合并结果然后去重得到的,就转换成了三个有序数组的无重复元素合并的问题
"""
class Solution {
public int nthUglyNumber(int n) {
if(n==0){
return 0;
}
int[] ugly = new int[n];
ugly[0]=1;
int i=0,j=0,k=0;
for(int idx=1;idx<n;idx++){
int temp=Math.min(ugly[i]*2,Math.min(ugly[j]*3,ugly[k]*5));
if(temp==ugly[i]*2)i++;
if(temp==ugly[j]*3)j++;
if(temp==ugly[k]*5)k++;
ugly[idx]=temp;
}
return ugly[n-1];
}
}

剑指 Offer 50 第一个只出现一次的字符

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
"""
数组存出现次数 再遍历一次找第一个出现次数为一次的字符返回即可
"""
class Solution {
public char firstUniqChar(String s) {
int[] count=new int[26];
for(char c:s.toCharArray()){
count[c-'a']+=1;
}
for(char c:s.toCharArray()){
if(count[c-'a']==1){
return c;
}
}
return ' ';
}
}

"""
维持一个队列,其中队首永远是目前只出现一次的数
也就是每次insert的时候,都去检测队首,若队首出现不止一次,则删除,直到队首只出现一次为止
由于是字符,ASCII码只有128个字符,所以可以用128长的数组来记录出现次数
"""
import java.util.*;
public class Solution {
//Insert one char from stringstream
int[] cnt = new int[128];
Queue<Character> queue = new LinkedList<>();
public void Insert(char ch)
{
cnt[ch]++;
queue.add(ch);
while(!queue.isEmpty() && cnt[queue.peek()]>1){
queue.poll();
}

}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
return queue.isEmpty()?'#':queue.peek();
}
}

剑指 Offer 51 数组中的逆序对

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
"""
归并排序
在于「归并」当中「并」的过程:在左右两个有序数组合并的过程中计算逆序对
"""
public class Solution {
public int reversePairs(int[] nums) {
int len = nums.length;

if (len < 2) {
return 0;
}

int[] copy = new int[len];
for (int i = 0; i < len; i++) {
copy[i] = nums[i];
}

int[] temp = new int[len];
return reversePairs(copy, 0, len - 1, temp);
}
/**
* nums[left..right] 计算逆序对个数并且排序
*
* @param nums
* @param left
* @param right
* @param temp
* @return
*/
private int reversePairs(int[] nums, int left, int right, int[] temp) {
if (left == right) {
return 0;
}
int mid = left + (right - left) / 2;
int leftPairs = reversePairs(nums, left, mid, temp);
int rightPairs = reversePairs(nums, mid + 1, right, temp);

if (nums[mid] <= nums[mid + 1]) {
return leftPairs + rightPairs;
}

int crossPairs = mergeAndCount(nums, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}

/**
* nums[left..mid] 有序,nums[mid + 1..right] 有序
*
* @param nums
* @param left
* @param mid
* @param right
* @param temp
* @return
*/
private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}

int i = left;
int j = mid + 1;

int count = 0;
for (int k = left; k <= right; k++) {

if (i == mid + 1) {
nums[k] = temp[j];//左边已全部入栈 将右边顺序入就可以
j++;
} else if (j == right + 1) { //右边已全部入栈 将左边顺序入就可以
nums[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i];
i++;
} else { //只有左边大于右边 才需要计算逆序对
nums[k] = temp[j];
j++;
count += (mid - i + 1); //重点!逆序对个数
}
}
return count;
}
}

剑指 Offer 52 两个链表的第一个公共节点

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
"""
求得A,B的长度 由于公共节点,则最后的末节点一定一致
双指针 将两者的长度调为一致后 一起往后移动 遇到第一个相同的节点即为第一个公共节点
"""
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int len1 = 0;
int len2 = 0;
ListNode p1 = pHead1, p2 = pHead2;
//
while(p1!= null){
len1+=1;
p1= p1.next;
}
while(p2 != null){
len2+=1;
p2 = p2.next;
}
if(len1>len2){
int k = len1-len2;
while(k>0){
pHead1 = pHead1.next;
k-=1;
}
}else{
int k = len2-len1;
while(k>0){
pHead2 = pHead2.next;
k-=1;
}
}
while(pHead2 != pHead1){
pHead2 = pHead2.next;
pHead1 = pHead1.next;
}
return pHead2;
}
}

"""
设 A 的长度为 a + c,B 的长度为 b + c,其中 c 为尾部公共部分长度,可知 a + c + b = b + c + a。

当访问链表 A 的指针访问到链表尾部时,令它从链表 B 的头部重新开始访问链表 B;同样地,当访问链表 B 的指针访问到链表尾部时,令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
"""
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode l1 = pHead1, l2 = pHead2;
while (l1 != l2) {
l1 = (l1 == null) ? pHead2 : l1.next;
l2 = (l2 == null) ? pHead1 : l2.next;
}
return l1;
}

剑指 Offer 53_1 在排序数组中查找数字

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
"""
二分查找+双指针拓展找边界
"""
class Solution {
public int search(int[] nums, int target) {
//二分查找
int index=bisearch(nums,target);
if(index==-1){
return 0;
}
int low=index-1,high=index+1;
//拓展找边界
while(low>=0&&nums[low]==target)low--;
while (high<nums.length&&nums[high]==target) high++;
return high-low-1;
}
//二分查找
public int bisearch(int[] nums,int target){
int low=0,high=nums.length-1;
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid]<target){
low=mid+1;
}
else {
high=mid-1;
}
}
return -1;
}
}

剑指 Offer 53_2 0~n-1中缺失的数字

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
二分查找
"""
class Solution {
public int missingNumber(int[] nums) {
int low=0,high=nums.length-1;
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==mid){
low=mid+1;
}
else{
high=mid-1;
}
}
return low; //low指向右子数组的首位元素
}
}

剑指 Offer 54 二叉搜索树的第k大节点

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""
利用二叉搜索树中序遍历递增的规则 右中左遍历 第k个数即为所求结果。
"""
class Solution {
int res, k;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}
void dfs(TreeNode root) {
if(root == null) return;
dfs(root.right);
if(k == 0) return;
if(--k == 0) res = root.val;
dfs(root.left);
}
}
"""
递归 但时间复杂度高 若k=1 则重复计算右子树个数
"""
public int kthLargest(TreeNode root, int k) {
int right=treenum(root.right);
if(right<k){
if(right==k-1){
return root.val;
}
else {
return kthLargest(root.left,k-right-1);
}
}
else {
return kthLargest(root.right,k);
}
}
public int treenum(TreeNode root){
if(root==null){
return 0;
}
return treenum(root.left)+treenum(root.right)+1;
}

剑指 Offer 55 二叉树的深度

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
"""
层序遍历
"""
class Solution {
public int maxDepth(TreeNode root) {
//层序遍历
if(root==null) return 0;
List<TreeNode> now_layer=new ArrayList<TreeNode>();
List<TreeNode> next_layer=new ArrayList<TreeNode>();
int res=0;
now_layer.add(root);
while(now_layer.size()>0){
res+=1;
for(TreeNode p:now_layer){
if(p.left!=null) next_layer.add(p.left);
if(p.right!=null) next_layer.add(p.right);
}
now_layer=next_layer;
next_layer=new ArrayList<TreeNode>();
}
return res;
}
}
"""
深度遍历(递归)
"""
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}

剑指 Offer 55-1 平衡二叉树

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
"""
自底向上 剪枝
"""
public class code {
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
return treedepth(root)!=-1;
}
//在计算高度的时候同时判断是否平衡 若不平衡 直接返回
public int treedepth(TreeNode root){
if(root==null) return 0; //高度为0
int left=treedepth(root.left);
if(left==-1) return -1;
int right=treedepth(root.right);
if(right==-1) return -1;
return Math.abs(left-right)<=1?Math.max(left,right)+1:-1; //若平衡 则返回高度 不然就返回-1;
}
}
"""
自上而下直接递归算子树高度 判断平衡条件 因为会有重复计算 所以时间复杂度会比较高
"""
class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
if(isBalanced(root.left)&&isBalanced(root.right)){
if(Math.abs(treedepth(root.left)-treedepth(root.right))<=1){
return true;
}
}
return false;
}
public int treedepth(TreeNode root){
if(root==null){
return 0;
}
return Math.max(treedepth(root.left),treedepth(root.right))+1;
}
}

剑指 Offer 56-1 数组中数字出现的次数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
先对所有数字进行一次异或,得到两个出现一次的数字的异或值。
在异或结果中找到任意为 1 的位(取最低位为1的那位)。
根据这一位对所有的数字进行分组。
在每个组内进行异或操作,得到两个数字。
"""
class Solution {
public int[] singleNumbers(int[] nums) {
int res=0;
int[] result=new int[2];
for(int temp:nums){
res^=temp; //得到两个数的异或
}
int k=1;
while((k&res)==0){ //得到最低位为1的那个位
k=k<<1;
}
int a=0,b=0;
for(int temp:nums){
if((k&temp)==0){
a^=temp;
}
else{
b^=temp;
}
}
result[0]=a;
result[1]=b;
return result;
}
}

剑指 Offer 56-2 数组中数字出现的次数2

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1;
同样适用于某位数字出现一次 其余数字出现奇数次的情况
若其余数字出现偶数次 则可以直接用异或
"""
public class Solution56_2 {

public int singleNumber(int[] nums) {//本算法同样适用于数组nums中存在负数的情况
if(nums.length==0) return -1;//输入数组长度不符合要求,返回-1;
int[] bitSum = new int[32];//java int类型有32位,其中首位为符号位
int res=0;
for(int num:nums){
int bitMask=1;//需要在这里初始化,不能和res一起初始化
for(int i=31;i>=0;i--){//bitSum[0]为符号位
//这里同样可以通过num的无符号右移>>>来实现,否则带符号右移(>>)左侧会补符号位,对于负数会出错。
//但是不推荐这样做,最好不要修改原数组nums的数据
if((num&bitMask)!=0) bitSum[i]++;//这里判断条件也可以写为(num&bitMask)==bitMask,而不是==1
bitMask=bitMask<<1;//左移没有无符号、带符号的区别,都是在右侧补0
}
}
for(int i=0;i<32;i++){//这种做法使得本算法同样适用于负数的情况
res=res<<1;
res+=bitSum[i]%3;//这两步顺序不能变,否则最后一步会多左移一次
}
return res;
}
}

剑指 Offer 57 和为s的两个数字

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
递增所以可以用双指针法
不然直接用Hashmap遍历
"""
import java.util.ArrayList;
import java.util.*;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
int left = 0;
int right = array.length-1;
while(left<right){
int now_sum = array[left]+array[right];
if(now_sum==sum){
return new ArrayList<>(Arrays.asList(array[left],array[right]));
}else if(now_sum<sum){
left++;
}else{
right--;
}
}
return new ArrayList<>();
}
}

剑指 Offer 57_2 和为 S 的连续正数序列

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
"""
用双指针法
"""
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
int left = 1, right = 2, curSum = 3;
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
while(right<sum){
if(curSum<sum){ //若和小
right++;
curSum+=right;
}else if(curSum>sum){ //若和大
curSum-=left;
left++;
}else{
ArrayList list = new ArrayList<>();
for(int i = left; i<=right; i++){
list.add(i);
}
res.add(list);
// 整体往后移,找新的连续序列
// 新的肯定left++ left增加后 cursum肯定小于sum,于是直接right++
curSum-=left;
left+=1;
right+=1;
curSum+=right;
}
}
return res;
}
}

剑指 Offer 58_1 翻转单词顺序列

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
用双指针法
public String trim()
返回一个字符串,其值为此字符串,删除了所有前导和尾随空格
"""
class Solution {
public String reverseWords(String s) {
s = s.trim(); // 删除首尾空格
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while(i >= 0) {
while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
j = i; // j 指向下个单词的尾字符
}
return res.toString().trim(); // 转化为字符串并返回
}
}
"""
用java内置函数split
public String[] split​(String regex)
将此字符串拆分为给定regular expression的匹配项 。
结尾的空字符串不包含在结果数组中。
"""
class Solution {
public String reverseWords(String s) {
String[] strs = s.trim().split(" "); // 删除首尾空格,分割字符串
StringBuilder res = new StringBuilder();
for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
if(strs[i].equals("")) continue; // 遇到空单词则跳过
res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
}
return res.toString().trim(); // 转化为字符串,删除尾部空格,并返回
}
}

剑指 Offer 58_2 左旋转字符串

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
"""
左旋 右旋 然后一起旋
"""
public String LeftRotateString(String str, int n) {
if (n >= str.length())
return str;
char[] chars = str.toCharArray();
reverse(chars, 0, n - 1);
reverse(chars, n, chars.length - 1);
reverse(chars, 0, chars.length - 1);
return new String(chars);
}

private void reverse(char[] chars, int i, int j) {
while (i < j)
swap(chars, i++, j--);
}

private void swap(char[] chars, int i, int j) {
char t = chars[i];
chars[i] = chars[j];
chars[j] = t;
}
"""
内置substring函数
"""
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n)+s.substring(0,n);
}
}
"""
stringbuilder .charAt() .append() .toString
"""
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder res = new StringBuilder();
for(int i = n; i < s.length(); i++)
res.append(s.charAt(i));
for(int i = 0; i < n; i++)
res.append(s.charAt(i));
return res.toString();
}
}

"""
string函数 .charAt()
"""
class Solution {
public String reverseLeftWords(String s, int n) {
String res = "";
for(int i = n; i < s.length(); i++)
res += s.charAt(i);
for(int i = 0; i < n; i++)
res += s.charAt(i);
return res;
}
}

剑指 Offer 59_1 滑动窗口的最大值

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
用双端队列来维护窗口内的单调栈(单调递减
"""
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size) {
if(num.length<0 || size>num.length || size<1){
return new ArrayList<>();
}
Deque<Integer> deque = new LinkedList<>();
ArrayList<Integer> res = new ArrayList<>();
for(int i=0;i<size;i++){ //窗口未形成
while(!deque.isEmpty() && deque.peekLast()<num[i]){
deque.removeLast();
}
deque.addLast(num[i]);
}
for(int i = size;i<num.length;i++){
res.add(deque.peekFirst());
//移动 需要删除头部
if(num[i-size]==deque.peekFirst()){
deque.removeFirst();
}
//移动 需要添加尾部
while(!deque.isEmpty() && deque.peekLast()<num[i]){
deque.removeLast();
}
deque.addLast(num[i]);
}
res.add(deque.peekFirst());
return res;
}
}

剑指 Offer 59_2 队列的最大值

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
"""
用双端队列来维护队列内的单调栈(单调递减
"""
class MaxQueue {
Queue<Integer> q;
Deque<Integer> d;

public MaxQueue() {
q = new LinkedList<Integer>();
d = new LinkedList<Integer>();
}

public int max_value() {
if (d.isEmpty()) {
return -1;
}
return d.peekFirst();
}

public void push_back(int value) {
while (!d.isEmpty() && d.peekLast() < value) {
d.removeLast();
}
d.addLast(value);
q.add(value);
}

public int pop_front() {
if (q.isEmpty()) {
return -1;
}
int ans = q.remove();
if (ans == d.peekFirst()) {
d.removeFirst();
}
return ans;
}
}

剑指 Offer 60 n个骰子的点数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
"""
动态规划
n个筛子能投的点数k的次数等于n-1个筛子能投的点数(k-6,k-5,k-4,k-3,k-2,k-1)的个数和
for (第n枚骰子的点数 i = 1; i <= 6; i ++) {
dp[n][j] += dp[n-1][j - i]
}
"""
class Solution {
public double[] dicesProbability(int n) {
int[] counts=new int[n*6+1];
double[] res=new double[n*5+1];
for(int i=1;i<=6;i++) {
counts[i]=1; //一个筛子 能得到点数i(1~6)的次数为1
}
for(int i=2;i<=n;i++){
for(int j=6*i;j>=i;j--){ //i个筛子能得到点数��[i,6*i]
int count=6;
counts[j]=0; //去除脏数据 counts[j]代表i个筛子能得到点数和为j的次数
while(count>0){
if(j-count+1>=i){
counts[j]+=counts[j-count]; //转移方程
}
count-=1;
}
}
}
for(int i=n;i<=6*n;i++){
res[i-n]=counts[i]/Math.pow(6,n);
}
return res;
}
}

剑指 Offer 61 扑克牌中的顺子

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
先找到最小的牌 然后向后遍历5个数 若没有 就用大小王代替 没有大小王就报错 若有则跳过
"""
class Solution {
public boolean isStraight(int[] nums) {
int[] count=new int[14];
for(int i=0;i<5;i++){
count[nums[i]]+=1;
}
int magic=count[0]; //大小王个数
int i=1;
while(count[i]==0) i+=1 //最小的牌;
for(int idx=1;idx<5;idx++){
if(i+idx<14&&count[i+idx]>0) continue; //当前牌与上一张连续
else{
if(magic>0){ //不连续 就用掉一张大小王
magic-=1;
}
else return false; //没有 就报错
}
}
return true;
}
}

剑指 Offer 62 圆圈中最后剩下的数字

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
模拟过程
"""
class Solution {
public int lastRemaining(int n, int m) {
int idx=0,len=n;
List<Integer> nums=new ArrayList<>();
for(int j=0;j<n;j++){ //初始化
nums.add(j);
}
while(len>1){
idx=(idx+m-1)%len;
nums.remove(idx);
len-=1;
}
return nums.get(0);
}
}

剑指 Offer 63 股票的最大利润

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
"""
动态规划
第i天的最大利润=max(第i-1天的最大利润,第i天卖出(第i天的价格-前i-1天的最低价格)
"""
class Solution {
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, profit = 0;
for(int price : prices) {
cost = Math.min(cost, price); //前i-1天的最低价格
profit = Math.max(profit, price - cost);
}
return profit;
}
}

剑指 Offer 63-1 股票的最大利润 可买卖多次

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
爬坡两端卖出
降坡不卖
"""
class Solution {
public int maxProfit(int[] prices) {
int i =0, j=1;
int minIdx = 0;
int res = 0;
while(j<prices.length){
minIdx = i;
if(prices[i]<prices[j]){
while(j<prices.length&&prices[i]<prices[j]){
i++;
j++;
}
res+=prices[i] - prices[minIdx];
}else{
while(j<prices.length&&prices[i]>=prices[j]){
i++;
j++;
}
}
}
return res;
}
}

剑指 Offer 64 求1+2+…+n

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
"""
利用&&实现递归判断
以逻辑运算符 && 为例,对于 A && B 这个表达式,如果 A 表达式返回 False ,那么 A && B 已经确定False ,此时不会去执行表达式 B
将判断是否为递归的出口看作 A && B 表达式中的 A 部分,递归的主体函数看作 B 部分。如果不是递归出口,则返回True,并继续执行表达式 B 的部分,否则递归结束。
"""
class Solution {
public int sumNums(int n) {
Boolean x=n>0&&((n+=sumNums(n-1))>0);
return n;
}
}

剑指 Offer 65 不用加减乘除做加法

一、问题描述

题目描述

二、具体代码

题目描述

1
2
3
4
5
6
7
8
9
10
11
"""
利用位运算实现加法
a^b 等于a与b不考虑进位的加法结果
a&b 等于a与b加法的进位结果
"""
class Solution {
public int add(int a, int b) {
if(b==0) return a;
return add(a^b,(a&b)<<1);
}
}

剑指 Offer 66 构建乘积数组

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"""
可以将B[i] 拆分为两部分:
A[0]×A[1]×…×A[i-1]
A[i+1]×…×A[n-1]
"""
class Solution {
public int[] constructArr(int[] a) {
int n=a.length;
int[] B=new int[n];
for(int i=0,product=1;i<n;product*=a[i],i++){ //A[0]×A[1]×…×A[i-1]
B[i]=product;
}
for(int i=n-1,product=1;i>=0;product*=a[i],i--){ //A[i+1]×…×A[n-1]
B[i]*=product;
}
return B;
}
}

剑指 Offer 67 把字符串转换为整数

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
"""
可以将B[i] 拆分为两部分:
A[0]×A[1]×…×A[i-1]
A[i+1]×…×A[n-1]
"""
class Solution {
public int strToInt(String str) {
char[] s=str.toCharArray();
int i=0,flag=1;
long res=0;
if(s.length==0) return 0; //str=""
while(i<s.length&&s[i]==' '){ //找到第一个非空字符
i++;
}
if(i<s.length&&(s[i]=='-'||s[i]=='+')){ //若开头为正负
if(s[i]=='-') flag=-1;
i+=1;
}
//若只有正负(i会越界) 若第一个非空字符不为字符整数
if(i>=s.length ||!((s[i]>='0'&&s[i]<='9')||s[i]=='-'||s[i]=='+')){
return 0;
}
while(i<s.length&&s[i]>='0'&&s[i]<='9'){
res=res*10+(s[i]-'0');
if(res>Integer.MAX_VALUE) return flag>0?Integer.MAX_VALUE:Integer.MIN_VALUE;//中间就可以判断是否大于int最大值 不然太大long也装不下
i++;
}
return flag*(int)res;
}
}

剑指 Offer 68_1 二叉搜索树的最近公共祖先

一、问题描述

题目描述

二、具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
"""
利用二叉搜索树 左<中<右这个规律
"""
"""
1、递归
"""
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return root;
if (root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val)
return lowestCommonAncestor(root.right, p, q);
return root;
}
"""
2、迭代
循环搜索: 当节点 root为空时跳出;
当 p, q都在 root 的 右子树 中,则遍历至 root.right;
否则,当 p, q 都在 root 的 左子树 中,则遍历至 root.left;
否则,说明找到了 最近公共祖先 ,跳出。
返回值: 最近公共祖先 root 。

"""
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(root != null) {
if(root.val < p.val && root.val < q.val) // p,q 都在 root 的右子树中
root = root.right; // 遍历至右子节点
else if(root.val > p.val && root.val > q.val) // p,q 都在 root 的左子树中
root = root.left; // 遍历至左子节点
else break;
}
return root;
}
}
"""
若为普通二叉树
"""
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
//类似于搜索 若以p或q存在于root.left为根 则left不为空
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null) return right;
if(right == null) return left;
return root;
}
}

大数的和

1
2
3
4
5
6
7
8
9
10
11
12
public String solve(String s, String t) {
StringBuilder stringBuilder = new StringBuilder();
int i = s.length() - 1, j = t.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
int x = i < 0 ? 0 : s.charAt(i--) - '0';
int y = j < 0 ? 0 : t.charAt(j--) - '0';
int sum = x + y + carry;
stringBuilder.append(sum % 10);//添加到字符串尾部
carry = sum / 10;
}
return stringBuilder.reverse().toString();//对字符串反转
}

42接雨水


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}

int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}

int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}

int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
"""
对于下标 i,下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值,下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去height[i]。

如果 height[left]<height[right],则必有 leftMax<rightMax,下标left 处能接的雨水量等于 leftMax−height[left],将下标left 处能接的雨水量加到能接的雨水总量,然后将 left 加 1(即向右移动一位);

"""
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (leftMax < rightMax) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
}