哈希

1、创建

  1. //创建一个 HashMap 对象 Sites， 整型（Integer）的 key 和字符串（String）类型的 value
  2. HashMap<Integer, String> Sites = new HashMap<Integer, String>();

2、常用函数

  1. //put() 方法将指定的键/值对插入到 HashMap 中。
  2.  HashMap<Integer, String> sites = new HashMap<>();
  4. // 往 HashMap 添加一些元素
  5.  sites.put(1, "Google");
  6.  sites.put(2, "Runoob");
  8.  // 获得该 HashMap 中键/值对映射的数量
  9.  int size = sites.size();
  11. // 得到 value
  12.   String value = sites.get(1);
  14.  // 替换key为2的映射
  15.  String value = sites.replace(2, "Wiki");
  17.  // 删除key为2的映射关系
  18.  String siteName = sites.remove(2);  // return Wiki
  20.   //检查 key 为 4 是否存在，不存在插入该 key/value 对
  21.   // 使用 ! 符号来对布尔结果取相反的值
  22.         if(!sites.containsKey(4)) {
  23.             sites.put(4, "Wiki");
  24.         }
  26.  //检查映射中值value是否有Java
  27.         if(sites.containsValue("Runoob")) {
  28.             System.out.println("Runoob 存在于 sites 中");
  29.         }

链表

1、表示

  1. //定义HeroNode ， 每个HeroNode 对象就是一个节点
  2. class HeroNode {
  3.     public int no;
  4.     public String name;
  5.     public String nickname;
  6.     public HeroNode next; //指向下一个节点
  7.     //构造器
  8.     public HeroNode(int no, String name, String nickname) {
  9.         this.no = no;
  10.         this.name = name;
  11.         this.nickname = nickname;
  12.     }
  13.     //为了显示方法，我们重新toString
  14.     @Override
  15.     public String toString() {
  16.         return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  17.     }    
  18. }

2、链表遍历

  1. //显示链表[遍历]
  2. public void list() {
  3.         //判断链表是否为空
  4.         if(head.next == null) {
  5.             System.out.println("链表为空");
  6.             return;
  7.         }
  8.         //因为头节点，不能动，因此我们需要一个辅助变量来遍历
  9.         HeroNode temp = head.next;
  10.         while(true) {
  11.             //判断是否到链表最后
  12.             if(temp == null) {
  13.                 break;
  14.             }
  15.             //输出节点的信息
  16.             System.out.println(temp);
  17.             //将temp后移， 一定小心
  18.             temp = temp.next;
  19.         }
  20.     }
  21. }

3、删除

  1.     //删除节点
  2.     //思路
  3.     //1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
  4.     //2. 说明我们在比较时，是temp.next.no 和  需要删除的节点的no比较
  5.     public void del(int no) {
  6.         HeroNode temp = head;
  7.         boolean flag = false; // 标志是否找到待删除节点的
  8.         while(true) {
  9.             if(temp.next == null) { //已经到链表的最后
  10.                 break;
  11.             }
  12.             if(temp.next.no == no) {
  13.                 //找到的待删除节点的前一个节点temp
  14.                 flag = true;
  15.                 break;
  16.             }
  17.             temp = temp.next; //temp后移，遍历
  18.         }
  19.         //判断flag
  20.         if(flag) { //找到
  21.             //可以删除
  22.             temp.next = temp.next.next;
  23.         }else {
  24.             System.out.printf("要删除的 %d 节点不存在\n", no);
  25.         }
  26.     }

4、修改链表信息

  1. //修改节点的信息, 根据no编号来修改，即no编号不能改.
  2.     //说明
  3.     //1. 根据 newHeroNode 的 no 来修改即可
  4.     public void update(HeroNode newHeroNode) {
  5.         //判断是否空
  6.         if(head.next == null) {
  7.             System.out.println("链表为空~");
  8.             return;
  9.         }
  10.         //找到需要修改的节点, 根据no编号
  11.         //定义一个辅助变量
  12.         HeroNode temp = head.next;
  13.         boolean flag = false; //表示是否找到该节点
  14.         while(true) {
  15.             if (temp == null) {
  16.                 break; //已经遍历完链表
  17.             }
  18.             if(temp.no == newHeroNode.no) {
  19.                 //找到
  20.                 flag = true;
  21.                 break;
  22.             }
  23.             temp = temp.next;
  24.         }
  25.         //根据flag 判断是否找到要修改的节点
  26.         if(flag) {
  27.             temp.name = newHeroNode.name;
  28.             temp.nickname = newHeroNode.nickname;
  29.         } else { //没有找到
  30.             System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
  31.         }
  32.     }

面试题1

查找单链表中的倒数第k个结点 【新浪面试题】

本人思路 题解思路
1、遍历单链表
2、两个辅助指针，第一个指针遍历到第k个时，第二个指针开始遍历，当第一个的next指向空时，第二个指针指向倒数k的位置
3、输出第二个指针内容		 1. 编写一个方法，接收head节点，同时接收一个index
2. index 表示是倒数第index个节点
3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
5. 如果找到了，则返回该节点，否则返回nulll
更加容易理解 
  1.     public static HeroNode findLastIndexNode(HeroNode head, int index) {
  2.         //判断如果链表为空，返回null
  3.         if(head.next == null) {
  4.             return null;//没有找到
  5.         }
  6.         //第一个遍历得到链表的长度(节点个数)
  7.         int size = getLength(head);
  8.         //第二次遍历  size-index 位置，就是我们倒数的第K个节点
  9.         //先做一个index的校验
  10.         if(index <=0 || index > size) {
  11.             return null; 
  12.         }
  13.         //定义给辅助变量， for 循环定位到倒数的index
  14.         HeroNode cur = head.next; //3 // 3 - 1 = 2
  15.         for(int i =0; i< size - index; i++) {
  16.             cur = cur.next;
  17.         }
  18.         return cur;
  20.     }
  22.     //方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
  23.     /**
  24.      * 
  25.      * @param head 链表的头节点
  26.      * @return 返回的就是有效节点的个数
  27.      */
  28.     public static int getLength(HeroNode head) {
  29.         if(head.next == null) { //空链表
  30.             return 0;
  31.         }
  32.         int length = 0;
  33.         //定义一个辅助的变量, 这里我们没有统计头节点
  34.         HeroNode cur = head.next;
  35.         while(cur != null) {
  36.             length++;
  37.             cur = cur.next; //遍历
  38.         }
  39.         return length;
  40.     }
  42. }

类似题:删除链表的倒数第n个节点

image.png

  1. import java.util.*;
  3. /*
  4.  * public class ListNode {
  5.  *   int val;
  6.  *   ListNode next = null;
  7.  * }
  8.  */
  10. public class Solution {
  11.     /**
  12.      * 
  13.      * @param head ListNode类 
  14.      * @param n int整型 
  15.      * @return ListNode类
  16.      */
  17.     public ListNode removeNthFromEnd (ListNode head, int n) {
  18.         ListNode cur = head;
  19.         ListNode cur2=head;
  20.         if(head.next == null) return null;
  21.         //只有一个节点，根据题目，n合法，所以肯定删去这个节点
  22.         for(int i=0;i<n;i++){
  23.             cur=cur.next;
  24.         }
  25.          if(cur == null)//待删除节点是头节点
  26.             return head.next;
  27.         while(cur.next!=null){
  28.             cur=cur.next;
  29.             cur2=cur2.next;
  30.         }
  31.         cur2.next=cur2.next.next;
  32.         return head;
  33.     }
  34. }

考题2

链表合并：将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。

字符串

字符串替换replace() 

  1. public class Main {
  2.     public static void main(String args[]) {
  3.         String Str = new String("Runoob");
  5.         System.out.print("返回值 :" );
  6.         System.out.println(Str.replace('o', 'T'));
  8.         System.out.print("返回值 :" );
  9.         System.out.println(Str.replace('u', 'D'));
  10.     }
  11. }
  12. //返回值 :RunTTb
  13. //返回值 :RDnoob

charAt

public char charAt(int index)

  1. public class Test {
  2.     public static void main(String args[]) {
  3.         String s = "www.runoob.com";
  4.         char result = s.charAt(6);
  5.         System.out.println(result);
  6.     }
  7. }

转换为字符数组

  1. public class Test {
  2.     public static void main(String args[]) {
  3.         String Str = new String("www.runoob.com");
  5.         System.out.print("返回值 :" );
  6.         System.out.println( Str.toCharArray() );
  7.     }
  8. }

动态规划

image.png
求解步骤：
a. 找出最优解的性质，并刻划其结构特征。
b. 递归地定义最优值。
c. 以自底向上的方式计算出最优值。
d. 根据计算最优值时得到的信息，构造最优解

放苹果

image.png

最长回文数

机器人走路

一个机器人在m×n大小的地图的左上角（起点）。
机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？
首先，我们可以发现第一行和第一列的位置只能有一种方法到达
image.png
对于其它位置来说，到达这个位置有两种情况：
一种是从上面的格子走过来的
另一种是从左边的格子走过来的
image.png
所以，我们定义一个𝑚×𝑛大小的二维数组𝑑𝑝
𝑑𝑝[𝑖][𝑗]表示从起点到达第𝑖行第𝑗列的方案数。
先把第一行第一列赋值为1
然后从第二行第二列的元素开始循环
𝑑𝑝[𝑖][𝑗]=𝑑𝑝[𝑖−1][𝑗]+𝑑𝑝[𝑖][𝑗−1]
右下角的dp值就是我们要求的答案
image.png

BFS

DFS

字符串