数据结构和算法练习

地址

• 小浩算法
• 题型分类
• 《玩儿转算法面试》
• 大厂刷题热度top
• 图解LeetCode
• 刷题套路总结fucking-algorithm

解题思路：

• 开辟新的临时数组tmp,
• 分别为原有两个数组的最后一个index设置指针i和j,
• 如果A[i]<B[j],那么就把A[j]放到tmp，反之，则把A[i]放到tmp，这叫做双指针解法

发现刷题重在思路，这道题首先要确定“链表相交”的概念，链表A和链表B相交与D，那么从D往后的链表都是相同的， 因为他们共用的next指针，假定两个指针分别指向两个链表的头结点，链表A指针从头走到尾，然后再从链表B头开始走，相同的速度， 相同的路径，所以两个链表会相遇

链表是一种天然的动态数据结构，何谓动态，就是可以增加数据，对比数组，数组是静态的，当然此处说的并不是数组的包装函数ArrayList

链表是由n个节点组成的，而节点中包含数据元素和指针，指针指的就是数据元素存放在内存中的地址，那如何将某个数存到该内存上呢？ 通过

a.next = b

表明将a指针指向b,意思是将b放到了叫做a的内存地址上，而

b = a.next

意思是指将a的内存地址等于b 再看反转链表这道题，引入两个指针pre和cur,pre是新添加指针，作为头结点的前继节点，cur作为当前节点，然后不断遍历当前节点，并将 cur指针指向后继节点，原cur节点作为pre,一直遍历到cur为空

我咋没想到用递归呢？通过题解中的图就能明白如何解了

比较两个链表的头结点，如果a小于b,则将a指向剩下的部分，同时a链表后移一位

如果a为空，则证明a被遍历完全，则返回b

发现链表的题差不多都一个套路

• 创建空的节点作为哨兵或者哑结点指向头结点
• 用两个指针移动 此题就是这样，指针a先移动，当距指针b n个单位时，同时后移，当a为空时，就证明b移到了需要删除指针的前一个指针

1.一个指针用来指向head,作为奇链表，一个指针作为偶链表，也指向head, 一个指针用来暂存head,作为偶链表的head,然后分别排奇链表，偶链表

2.奇指针的下下指针指向奇数，偶的下下指向偶数

3.循环跳出条件：指针为空时

1.将链表放到数组里

2.利用首尾两个指针往中间遍历，如果不相等就意味着不是回文

首先理解什么是栈，栈是一种操作受限的链表，只能从一头操作数据，这头叫做栈顶 本题可以用两个链表linkedList，一个作为输入，一个作为输出，然后组成栈

遍历字符串，如果是左括号，则将对应的右括号入栈，如果是右括号，则出栈并与当前的字符比对， 如果不相同，则没有对应括号，因为总是成对出现，所以遍历后，如果栈为空，则证明有对应括号

首先要明白栈和队列各自的特点，同一段序列存到栈和队列里，输出的顺序是相反的，所以，可以 用两个栈，一个作为输入，一个作为输出，输入的栈先存入数据，然后pop到输出栈中，就可以实现 队列的出对和入队的操作

可以将字符串存到栈中，然后通过当前字符和栈顶比对，如果相等则出栈

遍历数组，将出现过的数据置为-1,并作为循环的终止条件

遍历数组，统计每个数字位数，为2则为偶数

快指针走两步，慢指针走一步，如果有环，相当于环形跑道，快慢指针会相遇

暂时不会，先跳过

可以将删除节点之前节点的指针指向删除节点之后之后的节点，但这个问题的难点在于不知道删除节点的之前节点， 所以可以通过将删除节点赋值为之后节点的值，然后删除之后的节点

此题掌握关键解法滑动窗口法

1.先取前k个数,大于k*threshold则+1

2.然后以k个数为单位不断后移，减去前一个数并加上后一个数，结果大于k*threshold则+1

动态规划？先跳过

看了思路没看实现，自己做出来了，哈哈哈 貌似链表问题的通用思路就是快慢指针

1. 将cur先走k步

2. 然后head和cur同步走，cur走到空的时候，head正好走到k

二叉搜索树也叫二叉排序树，规则是每个节点都大于其左子树节点，都小于其右子树节点

1. 对链表使用快慢指针，快指针走两步，慢指针走一步，快指针走到尾节点的时候，慢指针指向中间节点，即可作为二次搜索树 的根节点，此时注意将左链表断开
2. 将原头节点作为左子树，将mid.next作为右子树，递归构建

1. 将原尾指向原头，组成环
2. 找到n-k%n-1为新尾，n-k%n为新头
3. 断开新尾和新头的指针

如果删除结点为中间结点，则可以直接将pre指向删除结点的下一个结点，但是如果删除的是头结点呢？ 所以需要一个哨兵结点，哨兵结点是空值，只为了便于操作链表

• 从哨兵结点开始不断遍历链表，
  • 如果比对是删除的结点，则pre->next=cur->next;
  • 否则pre=cur;
• 返回哨兵结点->next

注意C语言中如何创建对象，其实就是开辟空间，通过malloc(sizeof(需要创建对象的类型))

中序遍历指的是先遍历左子树，再遍历根结点，再遍历右子树，即左根右

• 中序遍历二叉搜索树的结果是排序后的结果

递归是最简单的方法，

public  void inorder(TreeNode root) {
    inorder(root.left);
    print(root.val);
    inorder(root.right);
} 

但递归是操作系统帮我们自动完成了函数的栈操作，所以尝试非递归方式, 从根结点开始入栈，不断找左子树，直到找到左子树，然后出栈，然后再找右子树

import java.TreeNode;class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(stack.size() > 0 || root != null) {
            if(root != null) {
                stack.push(root);
                root = root.left;
            }else {
                TreeNode tmp = stack.pop();
                list.add(tmp.val);
                root = tmp.right;
            }
        }
        return list;
    }
}

可以用计数排序，搞不太懂，先跳过

字符“唯一”，保证字符唯一的数据结构想到散列表

1. 将每个字符put进散列表中作为key,出现的次数作为value
2. 重新遍历字符串，字符出现次数为1即表示唯一

1. 通过指针j来遍历数组，将非0的值移到数组的左边，第一次遍历完后，指针j指向最后一个非0元素
2. 第二次遍历，将指针右边的非0元素全部置为0

因为遇到“#”则退回一个字符，很符合栈的弹栈操作，所以此处重构字符串，可以将非“#”的字符入栈，如果是“#”则出栈

利用双指针，从各自链表head开始遍历，如果到tail,则指向对方head开始遍历，如果有相交肯定会相遇

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *aP = headA;
    struct ListNode *bP = headB;
    while(aP != bP) {
        aP = aP == NULL?headB:aP->next;
        bP = bP == NULL?headA:bP->next;
    }
    return aP;
}

LRU,最近最少使用算法，即如果超出链表的容量，则会将最近最少使用的元素删除，然后插入新元素 java中的实现是LinkedHashMap,实现原理是双向链表，关键方法是

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

该方法表示删除缓存策略

利用hashset的元素唯一性

利用hashmap的值唯一性，疑问，算法要不要使用工具类