25. K 个一组翻转链表

  1. class Solution {
  2.     class ListNode{
  3.         int value;
  4.         ListNode next;
  5.         public ListNode(int value, ListNode next) {
  6.             this.value = value;
  7.             this.next = next;
  8.         }
  9.         public ListNode(int value) {
  10.             this.value = value;
  11.         }
  12.         public ListNode() {
  13.         }
  14.     }
  15.     public ListNode reverseKGroup(ListNode head, int k) {
  16.         //使用栈来保存节点
  17.         Stack<ListNode>stack=new Stack<>();
  18.         //设置虚拟节点
  19.         ListNode virtualNode=new ListNode(0);
  20.         ListNode dummy=virtualNode;
  21.         ListNode temp=head;
  22.         while (true){
  23.             int count=0;
  24.             //往栈中压入k个节点
  25.             while (temp!=null&&count<k){
  26.                 stack.push(temp);
  27.                 temp=temp.next;
  28.                 count++;
  29.             }
  30.             //如果count!=k，那就把虚拟节点的next指向指向头结点
  31.             if(count!=k){
  32.                 dummy.next=head;
  34.                 break;//这里必须要退出
  35.             }
  36.             //如果count==k,那就建链表
  37.             while (!stack.isEmpty()){
  38.                 dummy.next=stack.pop();
  39.                 dummy=dummy.next;
  40.             }
  41.             //将新节点的next指向指向temp节点
  42.             dummy.next=temp;
  43.             //前面k组已经反转完，所以需要把头节点设置为temp
  44.             head=temp;
  45.         }
  46.         return virtualNode.next;
  47.     }
  48. }

92. 反转链表 II

  1. public ListNode reverseBetween(ListNode head, int left, int right) {
  2.         if(left==right){
  3.             return head;
  4.         }
  5.         ListNode virtualNode = new ListNode(0);
  6.         virtualNode.next=head;
  7.         //1.先找到反转链表的起始节点的前置节点和末尾节点
  8.         //前置节点
  9.         ListNode pre=virtualNode;
  10.         //末尾节点
  11.         ListNode end=virtualNode;
  12.         for(int i=0;i<left-1;i++){
  13.             pre=pre.next;
  14.             end=end.next;
  15.         }
  16.         for(int i=0;i<right-left+1;i++){
  17.             end=end.next;
  18.         }
  19.         //当前反转的起始节点
  20.         ListNode cur=pre.next;
  21.         //当前反转末尾节点的下一个节点
  22.         ListNode curr=end.next;
  23.         //2.切断链表
  24.         pre.next=null;
  25.         end.next=null;
  26.         //3.反转这中间的链表
  27.         ListNode node = reverse(cur);
  28.         //4.搭接链表
  29.         pre.next=node;
  30.         cur.next=curr;
  31.         return virtualNode.next;
  32.     }
  33.     private ListNode reverse(ListNode head){
  34.         ListNode pre=null;
  35.         ListNode cur=head;
  36.         //3.反转这中间的链表
  37.         while (cur!=null){
  38.             ListNode next=cur.next;
  39.             cur.next=pre;
  40.             pre=cur;
  41.             cur=next;
  42.         }
  43.         return pre;
  44.     }

82. 删除排序链表中的重复元素 II

  1. public ListNode deleteDuplicates(ListNode head) {
  2.         ListNode virtualNode = new ListNode(0);
  3.         ListNode temp = virtualNode;
  4.         while (head != null) {
  5.             //如果head已到末尾节点,或者当前节点有效
  6.             if (head.next == null || head.val != head.next.val) {
  7.                 temp.next = head;
  8.                 temp = temp.next;
  9.             }
  10.             //如果当前节点与下一节点重复
  11.             while (head.next != null && head.val == head.next.val) {
  12.                 //就一直跳过重复节点
  13.                 head = head.next;
  14.             }
  15.             head = head.next;
  16.         }
  17.         temp.next = null;
  18.         return virtualNode.next;
  19.     }

41. 缺失的第一个正数

  1. public int firstMissingPositive(int[] nums) {
  2.         int n=nums.length;
  3.         for(int i=0;i<n;i++){
  4.             //nums[i]应该存放在i-1的位置上
  5.             while (nums[i]>=1&&nums[i]<=n&&nums[i]!=nums[nums[i]-1]){
  6.                 swap(nums,i,nums[i]-1);
  7.             }
  8.         }
  9.         for(int i=0;i<n;i++){
  10.             if(nums[i]!=i+1){
  11.                 return i+1;
  12.             }
  13.         }
  14.         return n+1;
  15.     }
  16.     private void swap(int []nums,int left,int right){
  17.         int temp=nums[right];
  18.         nums[right]=nums[left];
  19.         nums[left]=temp;
  20.         return;
  21.     }

93. 复原 IP 地址

  1.     List<String> res = new ArrayList<>();
  2.     Deque<String> path = new ArrayDeque<>(4);
  4.     public List<String> restoreIpAddresses(String s) {
  5.         if (s == null || s.length() <= 3 || s.length() > 12) {
  6.             return res;
  7.         }
  8.         int len = s.length();
  9.         backTrack(s, len, 0, 4);
  10.         return res;
  11.     }
  13.     //restSeg变量用来表示还有多少段没有被分割
  14.     private void backTrack(String str, int len, int begin, int restSeg) {
  15.         //如果已经遍历到末尾了
  16.         if (begin == len) {
  17.             //并且所有段都已被分割
  18.             if (restSeg == 0) {
  19.                 res.add(String.join(".", path));
  20.             }
  21.             //只要遍历到末尾就返回
  22.             return;
  23.         }
  24.         //每段最多为取3位
  25.         for (int i = begin; i < begin + 3; i++) {
  26.             if (i >= len) {
  27.                 break;
  28.             }
  29.             //如果剩下的数字无法被完全3位数分割
  30.             if (restSeg * 3 < len - i) {
  31.                 continue;
  32.             }
  33.             if (check(str, begin, i)) {
  34.                 String segment = str.substring(begin, i + 1);
  35.                 path.addLast(segment);
  36.                 backTrack(str, len, i + 1, restSeg - 1);
  37.                 path.removeLast();
  38.             }
  39.         }
  40.     }
  42.     private boolean check(String str, int left, int right) {
  43.         int len = right - left + 1;
  44.         //如果是01这种就不行
  45.         if (len > 1 && str.charAt(left) == '0') {
  46.             return false;
  47.         }
  48.         int res = 0;
  49.         while (left <= right) {
  50.             res = res * 10 + (str.charAt(left) - '0');
  51.             left++;
  52.         }
  53.         return res >= 0 && res <= 255;
  54.     }

43. 字符串相乘

  1. public String multiply(String num1, String num2) {
  2.   if(num1.equals("0")||num2.equals("0")){
  3.     return "0";
  4.   }
  5.   char[] chars1 = num1.toCharArray();
  6.   char[] chars2 = num2.toCharArray();
  7.   //预分配空间，存储运算结果
  8.   int[] temp = new int[num1.length() + num2.length()];
  9.   //先不考虑进位问题，先将结果存放于临时数组中，把index=0的位置空出来，用于存放进位
  10.   for (int i = 0; i < chars1.length; i++) {
  11.     for (int j = 0; j < chars2.length; j++) {
  12.       temp[i + j + 1] += (chars1[i] - '0') * (chars2[j] - '0');
  13.     }
  14.   }
  15.   //从后往前进行进位处理
  16.   for (int i = temp.length - 1; i > 0; i--) {
  17.     if (temp[i] >= 10) {
  18.       //打个比方，如果是25，那temp[i]就变成5，让前置位+2
  19.       temp[i - 1] += temp[i] / 10;
  20.       temp[i] %= 10;
  21.     }
  22.   }
  23.   StringBuilder res = new StringBuilder();
  24.   for (int i : temp) {
  25.     res.append(i);
  26.   }
  27.   //如果前置位是0的话，就需要去掉0
  28.   if (res.charAt(0) == '0') {
  29.     res.deleteCharAt(0);
  30.   }
  31.   return res.toString();
  32.     }

165. 比较版本号

  1. String[] ver1 = version1.split("\\.");
  2. String[] ver2 = version2.split("\\.");
  3. int max = Math.max(ver1.length, ver2.length);
  4. for (int i = 0; i < max; i++) {
  5.   int nums1;
  6.   int nums2;
  7.   if (i >= ver1.length) {
  8.     nums1 = 0;
  9.   } else {
  10.     nums1 = Integer.parseInt(ver1[i]);
  11.   }
  12.   if (i >= ver2.length) {
  13.     nums2 = 0;
  14.   } else {
  15.     nums2 = Integer.parseInt(ver2[i]);
  16.   }
  17.   if (nums1 == nums2) {
  18.     continue;
  19.     //此时version1>version2
  20.   } else if (nums1 > nums2) {
  21.     return 1;
  22.   } else {
  23.     return -1;
  24.   }
  25. }
  26. return 0;

470. 用 Rand7() 实现 Rand10()

  1. //rand7()-1可以获取0、1、2、3、4、5、6
  2. //*7后可以获取到0、7、14、21、28、35、42
  3. //再加7可以获取到1、2、3、4、5、6、7
  4. //然后再把二者相加获取1-10的数据
  5. int num = (rand7() - 1) * 7 + rand7();
  6. //如果当前数据>10，需要按照这个算法再次获取
  7. while (num > 10) {
  8.   num = (rand7() - 1) * 7 + rand7();
  9. }
  10. return num;

662. 二叉树最大宽度

  1. public int widthOfBinaryTree(TreeNode root) {
  2.   Deque<TreeNode> queue = new LinkedList<>();
  3.   Deque<Integer> numQueue = new LinkedList<>();
  4.   queue.addLast(root);
  5.   numQueue.addLast(1);
  6.   while (!queue.isEmpty()) {
  7.     int size = queue.size();
  8.     int left = -1;
  9.     int right = -1;
  10.     int tempWidth = 0;
  11.     for (int i = 0; i < size; i++) {
  12.       TreeNode node = queue.pollFirst();
  13.       int position = numQueue.pollFirst();
  14.       if (i == 0) {
  15.         left = position;
  16.       }
  17.       if (i == size - 1) {
  18.         right = position;
  19.       }
  20.       if (node.left != null) {
  21.         queue.addLast(node.left);
  22.         numQueue.addLast(position * 2);
  23.       }
  24.       if (node.right != null) {
  25.         queue.addLast(node.right);
  26.         numQueue.addLast(position * 2 + 1);
  27.       }
  28.     }
  29.     tempWidth = right - left + 1;
  30.     res = Math.max(res, tempWidth);
  31.   }
  32.   return res;
  33. }

227. 基本计算器 II

  1. Stack<Integer> stack = new Stack<>();
  2. char[] chars = s.toCharArray();
  3. int index = 0;
  4. while (index < chars.length) {
  5.   //如果是空格的话就直接跳过
  6.   if (chars[index] == ' ') {
  7.     index++;
  8.     continue;
  9.   }
  10.   char temp = chars[index];
  11.   //如果是加减乘除的话，如果后面有空格就一直++，直到不是空格
  12.   if (temp == '+' || temp == '-' || temp == '*' || temp == '/') {
  13.     index++;
  14.     while (index < chars.length && chars[index] == ' ') {
  15.       index++;
  16.     }
  17.   }
  18.   int num = 0;
  19.   while (index < chars.length && Character.isDigit(chars[index])) {
  20.     num = num * 10 + (chars[index++] - '0');
  21.   }
  22.   if (temp == '-') {
  23.     num = -num;
  24.   } else if (temp == '*') {
  25.     num = stack.pop() * num;
  26.   } else if (temp == '/') {
  27.     num = stack.pop() / num;
  28.   }
  29.   stack.push(num);
  30. }
  31. int res = 0;
  32. while (!stack.isEmpty()) {
  33.   res += stack.pop();
  34. }
  35. return res;

498. 对角线遍历

  1. int m = mat.length;
  2. int n = mat[0].length;
  3. int[] res = new int[m * n];
  4. int row = 0;
  5. int col = 0;
  6. for (int i = 0; i < res.length; i++) {
  7.   res[i] = mat[row][col];
  8.   //如果row+col%2==0的话，那就按右上方向走
  9.   if ((row + col) % 2 == 0) {
  10.     //如果列已到达最后一列，就需要往下走一格，否则会越界
  11.     if (col == mat[0].length - 1) {
  12.       row++;
  13.       //如果行的坐标是0的话，就往右走一格
  14.     } else if (row == 0) {
  15.       col++;
  16.     } else {
  17.       //其他情况，按照右上走
  18.       row--;
  19.       col++;
  20.     }
  21.     //如果row+col%2==1的话，那就按左下方向走
  22.   } else {
  23.     //如果行已到最后一行，就必须往右走了，否则会越界
  24.     if (row == mat.length - 1) {
  25.       col++;
  26.       //如果列的坐标是0的话，就往右走一格
  27.     } else if (col == 0) {
  28.       row++;
  29.     } else {
  30.       //其他情况，按照左下走
  31.       row++;
  32.       col--;
  33.     }
  34.   }
  35. }
  36. return res;

402. 移掉 K 位数字

  1. public String removeKdigits(String num, int k) {
  2.         char[] chars = num.toCharArray();
  3.         if (chars.length <= k) {
  4.             return "0";
  5.         }
  6.         //维护一个单调不下降的队列
  7.         Deque<Character>queue=new LinkedList<>();
  8.         for (int i = 0; i < chars.length; i++) {
  9.             char ch = chars[i];
  10.             //如果当前元素大于队列尾元素并且k>0，就弹出队列尾部元素
  11.             while (k > 0 && !queue.isEmpty() && ch < queue.peekLast()) {
  12.                 k--;
  13.                 queue.pollLast();
  14.             }
  15.             //如果是0123这种情况，0就不需要添加
  16.             if (i == 0 && ch == '0') {
  17.                 continue;
  18.             //其他情况，加入队列中
  19.             } else {
  20.                 queue.addLast(ch);
  21.             }
  22.         }
  23.         //如果此时k还大于0的话;比如123,k=1这种情况，那就需要弹出尾部元素
  24.         while (k>0&&!queue.isEmpty()){
  25.             queue.pollLast();
  26.             k--;
  27.         }
  28.         StringBuilder res = new StringBuilder();
  29.         //设置一个布尔标记为，如果队列首元素是0的话就continue
  30.         boolean flag=true;
  31.         while (!queue.isEmpty()) {
  32.             Character ch = queue.pollFirst();
  33.             if(flag&&ch=='0'){
  34.                 continue;
  35.             }
  36.             flag=false;
  37.             res.append(ch);
  38.         }
  39.         if(res.length()==0){
  40.             return "0";
  41.         }
  42.         return res.toString();
  43.     }