2549 统计桌面上的不同数字(Easy)
给你一个正整数 n ，开始时，它放在桌面上。在 10^9 天内，每天都要执行下述步骤：
对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
然后，将这些数字放在桌面上。
返回在 10^9 天之后，出现在桌面上的 不同 整数的数目。
简单题重拳出击
正常解
发现可以进行递归，假设n=7，那么第一次递归就是6和3，因为7%3=1，7%6=1，那么怎么样解决重复的问题呢，用一个set就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
HashSet<Integer> hashSet = new HashSet<>();
public int distinctIntegers(int n) {
dp(n);
return hashSet.size();
}
public void dp(int n){
hashSet.add(n);
for (int i = n-1; i >=1; i--) {
if (n % i ==1){
distinctIntegers(i);
}
}
}
|
那是比不上最快点方法的，其实找规律直接出来就是n-1，我这个方法还算是有点编程的，自然速度快不过那些n-1的
146 LRU缓存（Medium）非常重要这道题
实现LRU算法，关键是要时间复杂度和空间都是o（1）
虽然从前在os上还是手搓过这个算法的，但是这里要用常数的复杂度。
那必然是要哈希，但是哈希还不够，在搜寻在队列里面的时候必然还是要遍历，这个时候就要想到另一种数据结构，链表
这里为什么用双向链表，因为前驱还是要找的，总不能每次都去遍历吧，那还是浪费一点空间吧。
哈希表+双向链表
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
| class LRUCache{
class LinkNode{
int key;
int value;
LinkNode front = null;
LinkNode behind = null;
LinkNode(int key,int value){
this.key = key;
this.value = value;
}
LinkNode(){}
}
private int capacity;
private LinkNode head,tail;
private int linkSize = 0;
private HashMap<Integer,LinkNode> hashMap = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
head = new LinkNode();
tail = new LinkNode();
}
public int get(int key) {
if (hashMap.containsKey(key)){
LinkNode linkNode = hashMap.get(key);
moveToHead(linkNode);
return linkNode.value;
}
else {
return -1;
}
}
public void put(int key, int value) {
if (linkSize < capacity){
if (!hashMap.containsKey(key)){
LinkNode linkNode = new LinkNode(key,value);
handleInsert(linkNode);
linkSize++;
hashMap.put(key,linkNode);
}
else {
LinkNode linkNode = hashMap.get(key);
linkNode.value = value;
moveToHead(linkNode);
hashMap.replace(key,linkNode);
}
}
else {
if (!hashMap.containsKey(key)){
int removeKey = handleRemove();
hashMap.remove(removeKey);
LinkNode linkNode = new LinkNode(key,value);
handleInsert(linkNode);
hashMap.put(key,linkNode);
}
else {
LinkNode linkNode = hashMap.get(key);
linkNode.value = value;
moveToHead(linkNode);
hashMap.replace(key,linkNode);
}
}
}
public void handleInsert(LinkNode linkNode){
LinkNode temp = head.behind;
if (temp != null){
linkNode.behind = temp;
head.behind = linkNode;
temp.front = linkNode;
linkNode.front = head;
}
else {
head.behind = linkNode;
linkNode.front = head;
tail = linkNode;
}
}
public int handleRemove(){
int ans = tail.key;
tail = tail.front;
tail.behind = null;
return ans;
}
public void moveToHead(LinkNode linkNode){
if (linkNode.behind == null){
tail = linkNode.front;
linkNode.front.behind = null;
linkNode.front = null;
handleInsert(linkNode);
}
else {
LinkNode left = linkNode.front;
LinkNode right = linkNode.behind;
left.behind = right;
right.front = left;
linkNode.front = null;
linkNode.behind = null;
handleInsert(linkNode);
}
}
}
|
大同小异这些答案，主要还是哈希+双向
283 移动零(Easy)
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
没什么好说的这个题
直接插入排序思想
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public void moveZeroes(int[] nums) {
for (int i = nums.length-2; i >=0; i--) {
if (nums[i] == 0){
int j=i+1;
while (j <= nums.length-1&&nums[j] != 0 ){
nums[j-1] = nums[j];
j++;
}
nums[j-1] = 0;
}
}
}
}
|
236.二叉树的最近公共祖先(Medium)
题目意思就是字面意思
这个题居然还没有考研那段时间做得好，这里思路就是找到这两个节点的路径序列，然后找到最近的那个重复元素就完事。
2024.3.23
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
| class Solution {
List<TreeNode> list1 = new ArrayList<>();
List<List<TreeNode>> list = new ArrayList<>();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
hxbl(root,p);
hxbl(root,q);
return findSame(list.get(0),list.get(1));
}
public void hxbl(TreeNode root,TreeNode target){
list1.add(root);
if (root.val == target.val){
list.add(new ArrayList<>(list1));
}
if (root.left != null){
hxbl(root.left,target);
}
if (root.right != null){
hxbl(root.right,target);
}
list1.remove(list1.size()-1);
}
public TreeNode findSame(List<TreeNode> list1, List<TreeNode> list2){
for (int i = list1.size()-1; i >=0; i--) {
for (int j = list2.size()-1; j >=0; j--) {
if (list1.get(i).val == list2.get(j).val){
return list1.get(i);
}
}
}
return null;
}
}
|
2023.8.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
30
31
32
33
34
35
36
37
38
| class Solution {
List<TreeNode> treeList = new ArrayList<>();
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
find(root,p);
List<TreeNode> treeList1 = new ArrayList<>(treeList);
treeList = new ArrayList<>();
find(root,q);
List<TreeNode> treeList2 = new ArrayList<>(treeList);
boolean flag = true;
if (treeList1.size()>treeList2.size()){
flag = false;
}
for (int i = 0;i<Math.max(treeList1.size(),treeList2.size());i++){
if (!flag && treeList2.contains(treeList1.get(i))){
return treeList1.get(i);
}
if (flag && treeList1.contains(treeList2.get(i))){
return treeList2.get(i);
}
}
return null;
}
public boolean find(TreeNode root,TreeNode p){
if (root!=null){
boolean left = find(root.left,p);
boolean right = find(root.right,p);
if (root == p||left||right){
treeList.add(root);
return true;
}
else return false;
}
else {
return false;
}
}
}
|