剑指offer-较难篇

Posted on | In ,

滑动窗口的最大值

题目描述：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,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
public ArrayList<Integer> maxInWindows(int [] num, int size){
  if (num == null || num.length == 0 || size <= 0 || num.length < size) {
    return new ArrayList<Integer>();
  }
  
  ArrayList<Integer> res = new ArrayList<>();
  LinkedList<Integer> queue = new LinkedList<>();
  
  for(int i = 0;i < num.length; i++){
    while(!queue.isEmpty() && num[queue.peekLast()] < num[i]){
      queue.pollLast();
    }
    
    queue.addLast(i);
    
    //判断头索引是否超出size
    if(queue.peekFirst() <= i - size){
      queue.pollFirst();
    }
    
    //将最大值加入结果集
    if(i >= size-1){
      res.add(num[queue.peekFirst()]);
    }
  }
  return res;
}


二叉搜索树的第k个结点

题目描述：给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

思路：中序遍历第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
public class Solution {
  private TreeNode res;
  private int index = 0;//计数器
  
  TreeNode KthNode(TreeNode pRoot, int k){
		inOrder(pRoot, k);
    return res;
  }

  private void inOrder(TreeNode root, int k){
    if(root == null){
      return;
    }
    inOrder(root.left, k);
    
    index++;
    if(index == k){
      res = root;
    }
    
    inOrder(root.right, k);
  }

}


序列化二叉树

题目描述：请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为”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
public class Solution {
  public int index = -1;
  String Serialize(TreeNode root) {

    if(root == null){
      return "#";
    }
    return root.val + "," + Serialize(root.left) + "," + Serialize(root.right);
  }


  TreeNode Deserialize(String str) {
    index++;    
    String[] strr = str.split(",");
    TreeNode node = null;
    if(!strr[index].equals("#")){
      node = new TreeNode(Integer.valueOf(strr[index]));
      node.left = Deserialize(str);
      node.right = Deserialize(str);
    }

    return node;
  }
}


按之字形顺序打印二叉树

题目描述：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

思路：使用队列

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
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
  if(pRoot == null) return new ArrayList();
  
  ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(pRoot);
  int count = 1;//记录行数

  while(!queue.isEmpty()){
    int n = queue.size();
    ArrayList<Integer> list = new ArrayList<Integer>();
    for(int i = 0; i<n; i++){
      TreeNode node = queue.poll();
      list.add(node.val);
      if(node.left != null) queue.add(node.left);
      if(node.right != null) queue.add(node.right);
    }

    if(count % 2 == 1){//奇数行
      res.add(list);
      count++;
    }else{//偶数行
      Collections.reverse(list);
      res.add(list);
      count++;
    }
  }
  return res;
}


删除链表中重复的结点

题目描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路：三指针

删除链表中重复的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode deleteDuplication(ListNode pHead){
  if (pHead==null || pHead.next==null) return pHead;
  ListNode newHead = new ListNode(-1);
  newHead.next = pHead;
  ListNode pre = newHead;
  ListNode last = newHead.next;
  while(last != null){

    if (last.next != null && last.val == last.next.val){
      while(last.next != null && last.val == last.next.val) {
        last = last.next;
      }
      pre.next = last.next;
      last = last.next;
    } else {
      pre = pre.next;
      last = last.next;
    }
  }
  return newHead.next;
}


把字符串转换成整数

题目描述：将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

输入描述:

1
2
3
4
输入一个字符串,包括数字字母符号,可以为空
例：
+2147483647
1a33

输出描述:

1
2
3
4
如果是合法的数值表达则返回该数字，否则返回0
例：
2147483647
0

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int StrToInt(String str) {
  if(str.length() == 0 || str == null){
    return 0;
  }
  int res = 0;
  for(int i = 0; i<str.length(); i++){
    char c = str.charAt(i);
    if(c == '0' || c == '+' || c == '-'){
      continue;
    }

    if(c < '0' || c > '9'){
      return 0;
    }

    res = res*10 +(c-'0');

  }
  return str.charAt(0) == '-' ? -res : res;
}


翻转单词顺序列

题目描述：将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

思路：先反转每个单词，再反转整个句子;

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
public String ReverseSentence(String str) {
  //先反转每个单词，再反转整个句子
  char[] chars = str.toCharArray();
  int n = chars.length;
  int i = 0;
  int j = 0;
  while(j <= n){
    if(j == n || chars[j] == ' '){ // 利用短路特性，否则会报数组越界
      reverse(chars, i, j-1);
      i = j+1;
    }
    j++;
  }
  reverse(chars, 0, n-1);
  return new String(chars);
}

//反转单词
private void reverse(char[] chars, int i, int j){
  while(i < j){
    char temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
    i++;
    j--;
  }  
}


把数组排成最小的数

题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路：可以看成是一个排序问题，在比较两个字符串 S1 和 S2 的大小时，应该比较的是 S1+S2 和 S2+S1 的大小，如果 S1+S2 < S2+S1，那么应该把 S1 排在前面，否则应该把 S2 排在前面。

补充：

Comparator：对任意类型集合对象进行整体排序，排序时将此接口的实现传递给Collections.sort方法或者Arrays.sort方法排序.
实现int compare(T o1, T o2);方法，返回正数，零，负数各代表大于，等于，小于。

compareTo()：的返回值是整型，它是先比较对应字符的大小(ASCII码顺序)，如果第一个字符和参数的第一个字符不等,结束比较，返回他们之间的差值，如果第一个字符和参数的第一个字符相等，则以第二个字符和参数的第二个字符做比较,以此类推,直至比较的字符或被比较的字符有一方全比较完，这时就比较字符的长度. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String PrintMinNumber(int [] numbers) {
  String[] str = new String[numbers.length];
  for(int i = 0; i<numbers.length; i++){
    str[i] = numbers[i]+"";
  }
  StringBuilder res = new StringBuilder();

  Arrays.sort(str,new Comparator<String>(){
    @Override
    public int compare(String s1, String s2) {
      String c1 = s1 + s2;
      String c2 = s2 + s1;
      return c1.compareTo(c2);
    }
  });

  for(int i = 0;i<str.length;i++){
    res.append(str[i]);
  }

  return res.toString();
}


二叉树中和为某一值的路径

题目描述：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路：深度遍历：

二叉树和为某个值的路径

以上面的树模拟先序遍历的过程

  • 10–>5–>4 已近到达叶子结点，不满足要求22，因此该路径访问结束，需要访问下一个路径

    因为在访问节点的过程中，我们并不知道该路径是否满足要求，所以我们每访问一个节点就要记录该结点

    访问下有一个结点前，要先从结点4退回到结点5，再访问下一个结点7，因为4不在去往7的路径上，所以要在路径中将4删除

  • 10–>5–>7 满足要求，保存该路径

    访问下一个结点，从结点7回到结点5再回到结点10

  • 10–>12，满足要求，保存该路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
  ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  ArrayList<Integer> list = new ArrayList<Integer>();
  public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    if(root == null) {
      return res;
    }
    target = target - root.val;
    list.add(root.val);
    if(target == 0 && root.left == null && root.right == null){
      res.add(new ArrayList(list));
    }
    FindPath(root.left, target);
    FindPath(root.right, target);
    list.remove(list.size()-1);//回退
    return res;
  }
}


最小的K个数

题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路：

1
2
3
4
5
6
7
8
9
10
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
  ArrayList<Integer> res = new ArrayList<Integer>();
  if(k > input.length) return res;
  Arrays.sort(input);
  for(int i = 0; i<k;i++){
    res.add(input[i]);
  }

  return res;
}


二叉搜索树的后序遍历序列

题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean VerifySquenceOfBST(int [] sequence) {
  if(sequence.length == 0) return false;
  return judge(sequence, 0, sequence.length-1);
}

public boolean judge(int [] sequence, int begin, int end){
  if(begin >= end){
    return true;
  }
  int i = begin;
  //找到以end节点为根节点的左子树
  while(sequence[i] < sequence[end]){
    i++;
  }

  for(int j = i; j < end; j++){
    //右子树如果有小于根节点的，则返回false
    if(sequence[j] < sequence[end]){
      return false;
    }
  }
  return judge(sequence, begin, i-1) && judge(sequence, i, end-1);
}


二维数组中的查找

题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：从二维数组的右上角开始遍历，比当前值小的就在左边，比当前值大的就在下边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean Find(int target, int [][] array) {
  int row = array.length;//行数
  int col = array[0].length;//列数
  //从右上角开始搜索
  int i = 0;
  int j = col - 1;
  while(i < row && j >= 0){
    if(array[i][j] == target){
      return true;
    }else if(array[i][j] < target){
      i++;
    }else{
      j--;
    }
  }
  return false;
}


替换空格

题目描述：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
public String replaceSpace(StringBuffer str) {
  String strs = str.toString();
  char[] strChars = strs.toCharArray();
  StringBuilder sb = new StringBuilder();
  for(int i = 0; i<strChars.length; i++){
    if(strChars[i] == ' '){
      sb.append("%20");
    }else{
      sb.append(strChars[i]);
    }
  }
  return sb.toString();
}


从尾到头打印链表

题目描述：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

思路：利用栈，实现逆序打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
  ArrayList<Integer> res = new ArrayList<Integer>();
  Stack<ListNode> stack = new Stack<>();
  while(listNode != null){
    stack.push(listNode);
    listNode = listNode.next;
  }
  
  while(!stack.isEmpty()){
    ListNode node = stack.pop();
    res.add(node.val);
  }
  
  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
26
27
28
public void reOrderArray(int [] array) {
  int count = 0;
  //统计数组中奇数的个数
  for(int num : array){
    if(num % 2 == 1){
      count++;
    }
  }
  
  //创建拷贝数组
  int[] copy = new int[array.length];
  for(int i = 0; i<array.length; i++){
    copy[i] = array[i];
  }
  
  //调整位置
  int i = 0;//奇数索引
  int j = count;//偶数索引
  for(int num : copy){
    if(num % 2 == 1){
      array[i] = num;
      i++;
    }else{
      array[count] = num;
      count++;
    }
  }
}


链表中倒数第k个结点

题目描述：输入一个链表，输出该链表中倒数第k个结点。

思路：创建两个指针，都指向头节点。第一个比第二个多走 k 个节点，然后两指针同时向后遍历，直到第一个指针遍历到结尾，返回第二个指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode FindKthToTail(ListNode head,int k) {
  ListNode p1 = head;
  ListNode p2 = head;
  for(int i = 0; i<k; i++){
    if(p1 != null){
      p1 = p1.next;
    }else{
      return null;
    }    
  }
  
  while(p1 != null){
    p1 = p1.next;
    p2 = p2.next;
  }
  return p2;
}


树的子结构

题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：先编写方法 isSubTree() 判断B树与A树从根开始是有否相同的结构；再从头遍历A二叉树判断是否有和B树相同的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
  public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    if(root1 == null || root2 == null) return false;
    if(isSubTree(root1, root2)) return true;
    return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);	
  }

  public boolean isSubTree(TreeNode root1, TreeNode root2){
    if(root2 == null) return true;
    if(root1 == null) return false;
    if(root1.val != root2.val) return false;
    return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
  }
}


顺时针打印矩阵

题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路：创建四个指针，根据顺时针顺序进行顺序输出；注意条件：在添加最后一列和最后一行的时候增加判断条件：r1 != r2，c1 != c2

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
public class Solution {
  public ArrayList<Integer> printMatrix(int [][] matrix) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    
    int r1 = 0;
    int r2 = matrix.length-1;
    int c1 = 0;
    int c2 = matrix[0].length-1;
    
    while(r1 <= r2 && c1 <= c2){
      //添加当前矩阵第一行
      for(int i = c1; i <= c2; i++){
        res.add(matrix[r1][i]);
      }
      
      //添加当前矩阵最后一列
      for(int i = r1+1; i <= r2; i++){
        res.add(matrix[i][c2]);
      }
      
      //添加当前矩阵最后一行
      if (r1 != r2){
        for(int i = c2-1; i >= c1; i--){
          res.add(matrix[r2][i]);
        }
      }
      //添加当前矩阵第一列
      if(c1 != c2){
        for(int i = r2-1; i > r1; i--){
        	res.add(matrix[i][c1]);
      	}
      }  
      r1++;
      r2--;
      c1++;
      c2--;
    }
    return res;
  }
}


二叉树中和为某一值的路径

题目描述：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
  ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  ArrayList<Integer> list = new ArrayList<Integer>();
  public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
    if(root == null) return res;
    target -= root.val;
    list.add(root.val);
    if(target == 0 && root.left == null && root.right == null){
      res.add(new ArrayList<Integer>(list));
    }
    FindPath(root.left, target);
    FindPath(root.right, target);
    list.remove(list.size()-1);
    return res;
  }
}


复杂链表的复制

题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

思路：第一步，在每个节点的后面插入复制的节点；第二步，建立 random 链接；第三步， 拆分；

复杂链表复制

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
public class Solution {
  public RandomListNode Clone(RandomListNode pHead){
		if(pHead == null) return null;
    //插入新节点
    RandomListNode cur = pHead;
    while(cur != null){
      RandomListNode clone = new RandomListNode(cur.label);
      clone.next = cur.next;
      cur.next = clone;
      cur = clone.next;
    }
    
    //建立random连接
    cur = pHead;
    while(cur != null){
      RandomListNode clone = cur.next;
      if (cur.random != null){
        clone.random = cur.random.next;
      }
      cur = clone.next;
    }
    
    //拆分
    cur = pHead;
    RandomListNode cloneHead = cur.next;
    while(cur != null){
      RandomListNode next = cur.next;
      cur.next = next.next;
      cur = next;    
    }
    return cloneHead;
  }
  
}


把数组排成最小的数

题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路：Comparator的用法：https://blog.csdn.net/yongh701/article/details/44131051?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.compare&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.compare

compareTo方法：https://www.iteye.com/blog/chenfeng0104-409754

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String PrintMinNumber(int [] numbers) {
  String[] strs = new String[numbers.length];
  for(int i = 0; i<numbers.length; i++){
    strs[i] = numbers[i] + "";
  }

  //Collections也有类似的用法
  Arrays.sort(strs, new Comparator<Object>(){
    public int compare(Object s1, Object s2){
      String c1 = (String)s1+(String)s2;
      String c2 = (String)s2+(String)s1;
      return c1.compareTo(c2);
    }
  });

  StringBuilder res = new StringBuilder();
  for(String s : strs){
    res.append(s);
  }
  return res.toString();
}


丑数

题目描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路：

我们没有必要维护三个队列，只需要记录三个指针显示到达哪一步；“|”表示指针,arr表示丑数数组；

（1）1

|2

|3

|5

目前指针指向0,0,0，队列头arr[0] * 2 = 2, arr[0] * 3 = 3, arr[0] * 5 = 5

（2）1 2

2 |4

|3 6

|5 10

目前指针指向1,0,0，队列头arr[1] * 2 = 4, arr[0] * 3 = 3, arr[0] * 5 = 5

（3）1 2 3

2| 4 6

3 |6 9

|5 10 15

目前指针指向1,1,0，队列头arr[1] * 2 = 4, arr[1] * 3 = 6, arr[0] * 5 = 5

………………

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int GetUglyNumber_Solution(int N) {
  if(N < 7) return N;
  int i2 = 0;//质因子为2的指针
  int i3 = 0;//质因子为3的指针
  int i5 = 0;//质因子为5的指针
  int[] dp = new int[N];//丑数数组
  dp[0] = 1;
  for(int i = 1; i<N; i++){
    int next2 = dp[i2] * 2;
    int next3 = dp[i3] * 3;
    int next5 = dp[i5] * 5;
    dp[i] = Math.min( next2,(Math.min(next3,next5)) );
    if(dp[i] == next2) i2++;
    if(dp[i] == next3) i3++;
    if(dp[i] == next5) i5++;
  }
  return dp[N-1];
}


第一个只出现一次的字符

题目描述：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

思路：使用数组统计字符出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int FirstNotRepeatingChar(String str) {
  int[] count = new int[256];//用来统计字符出现过的次数
  
  //统计字符出现过的次数
  for(int i = 0; i < str.length(); i++){
    char c = str.charAt(i);
    count[c]++;
  }
  
  //找到第一个只出现一次的字符
  for(int i = 0; i < str.length(); i++){
    char c = str.charAt(i);
    if(count[c] == 1){
      return i;
    }
  }
  return -1;
}


机器人的运动范围

题目描述：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

思路：递归回溯：

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
public class Solution {
  private int rows;
  private int cols;
  private int threshold;
  public int movingCount(int threshold, int rows, int cols){
    this.rows = rows;
    this.cols = cols;
    this.threshold = threshold;
    boolean isVisited[][] = new boolean[rows][cols];
    int count = dfs(0, 0, isVisited);
    return count;
  }

  private int dfs(int i, int j, boolean[][] isVisited){
    if(i < 0 || i >= rows || j < 0 || j >= cols ||
       (numSum(i) + numSum(j)) > threshold || isVisited[i][j]){
      return 0;
    }
    isVisited[i][j] = true;
    return dfs(i+0, j+1, isVisited)+
      dfs(i+1, j+0, isVisited)+
      dfs(i-1, j+0, isVisited)+
      dfs(i+0, j-1, isVisited)+1;
  }

  private int numSum(int threshold){
    int sum = 0;
    while((threshold / 10) > 0){
      sum += threshold%10;
      threshold = threshold/10;
    }
    sum = sum+threshold;
    return sum;
  }
}