头像

henhen敲

吉林大学


访客:1070

离线:4天前



每个数会依次乘以2、3、5,从中找到最小的作为下一个待排序丑数 
class Solution {
    public int getUglyNumber(int n) {
        int[] ans = new int[n];
        ans[0] = 1;
        int i2, i3, i5;
        i2 = 0; i3 = 0; i5 = 0;
        for(int i=1; i<n; i++){
            ans[i] = Math.min(2*ans[i2], Math.min(3*ans[i3], 5*ans[i5]));
            if(ans[i]==2*ans[i2]) i2++;
            if(ans[i]==3*ans[i3]) i3++;
            if(ans[i]==5*ans[i5]) i5++;
        }
        return ans[n-1];
    }
}



henhen敲
10天前

    public static void main(String[] args)throws Exception{
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] h = new int[n];
        int[] m = new int[n];
        int[] s = new int[n+1];//前缀和 
        for(int i=0; i<n; i++){
           h[i] = in.nextInt();  
           s[i+1] = s[i] + h[i];
        } 
        Stack<Integer> st = new Stack<>();//单调栈
        for(int i=n-1; i>=0; i--){
            int x = h[i];
            int t = i;
            while(st.size()>0&&x>h[st.peek()]) t = st.pop();
            m[i] = st.size()==0?t:st.peek();
            st.push(i);
        }
        int cur = 0;
        int sum = 0;
        while(cur<n-1){
            int r = h[m[cur]];
            int l = h[cur];
            sum += m[cur]-cur<0? 0:(m[cur]-cur-1)*Math.min(r, l) - (s[m[cur]]-s[cur+1]) ;
            cur = m[cur];
        }
        System.out.print(sum);
    }




henhen敲
12天前
依次遍历num中每个元素 删除nums[i+1]<nums[i]的元素i 
注意边界问题 (1)头部是0 忽略(2)结束时k>0 从后向前删除 直到k=0

    int k;
    String nums;
    Scanner in = new Scanner(System.in);
    nums = in.next();
    k = in.nextInt();
    if(nums==null||nums.length()==0){
       System.out.print("0");
       return;
    } 
    StringBuilder ans = new StringBuilder();
    for(int i=0; i<nums.length(); i++){
        while(ans.length()>0&&nums.charAt(i)-'0'<ans.charAt(ans.length()-1)-'0'&&k>0){//删除num[i]
            ans.deleteCharAt(ans.length()-1);
            k--;
        }
        if(ans.length()==0&&nums.charAt(i)=='0') continue;//头部是0 忽略
        ans.append(nums.charAt(i));
    }
    while(k>0&&ans.length()>0){//k>0
        ans.deleteCharAt(ans.length()-1);
        k--;
    } 
    if(ans.length()==0){
       System.out.print("0");
    }else
        System.out.print(ans.toString());





henhen敲
17天前
先求异或和 最后结果为 这两个数字的x y 的异或x^y值
该值一定不为0 所以找到任意一个不为1的位数 则 x y在该位置一定不同 即一个为1 一个为0 
只需将所有这个位置为1的在重新异或和 就能求出该值 (位置为0的也行)
class Solution {
    public int[] findNumsAppearOnce(int[] nums) {
        int sum = 0;
        for(int x:nums) 
            sum ^= x;
        int k = 0;
        while((sum>>k&1)==0) k++;
        int first = 0;
        for(int x: nums)
            if((x>>k&1)==1)
                first ^= x;
        int[] ans = {first, sum^first};
        return ans;
    }
}



henhen敲
18天前
分别判断e/E 前后字符串是否满足条件 前:是数字; 后:是整数;
(1)首先去掉多个小数点 以及正负号不在正确位置的情况 ;
(2)标记已经存在小数点 和 数字的情况 
(3)存在以上其它字符 除掉

最后判断是否存在数字 
整数的情况只需(1)中修改就可 

class Solution {

    public boolean isNum(String s, int start, int end, boolean point){
        if(s.length()==0||start>=end) return false;
        int len = s.length();
        boolean flag = false;
        for(int i=start; i<end; i++){
            char cur = s.charAt(i);
            boolean first = ((cur=='+'||cur=='-')&&i!=start)||(point&&cur=='.');
            if(first) return false;
            if(cur=='.') point = true;
            else if(cur-'0'>=0&&cur-'0'<=9) flag = true;
            else if(cur!='+'&&cur!='-'&&cur!='.')return false;
        }
        if(!flag) return false;

        return true;
    }

    public boolean isNumber(String s) {
        int i;
        if(s==null||s.length()==0) return false;
        int len = s.length();
        char w = ' ';
        for(i=0; i<len; i++){
            w = s.charAt(i);
            if(w=='E'||w=='e') break;
        }
        boolean ans = isNum(s, 0, i, false);
        return (w=='E'||w=='e')?ans&&isNum(s, i+1, s.length(), true):ans;
    }
}



henhen敲
19天前
记住迭代关系 
f[n] = f[n-1] + Ak.//(k对应人数n时 所选)n代表当前人数 


static int DP(int[]a, int n, int m, int k){
    if(n==1) return 0;
    return (DP(a, n-1, m, (k+1)%m) + a[k])%n; 
}

public static void main(String[] args)throws Exception{

    int T = nextInt();
    int n, m;

    while(T--!=0){
        n = nextInt(); m = nextInt();
        int []a = new int[m];
        for(int i=0; i<m; i++) a[i] = nextInt();
        int f = 0;
        int start = (n - 2) % m;
        for(int i=0; i<n-1; i++){
            f += a[(n-2-i)%m];
            f %= (i+2);
        }
       // out.println(DP(a, n, m, 0));
    }
    out.close();

}



henhen敲
21天前

和c++一样的代码 咋就过不去啊




henhen敲
21天前


class Solution {
    public ListNode cur;
    public ListNode reverseKGroup(ListNode head, int k) {
        cur = head;
        ListNode pre, ans;
        ans = null;
        pre = null;
        while(cur!=null){
            head = cur;
            ListNode t = reverse(cur, k);
            if(pre!=null) pre.next = t;
            else ans = t==null? cur: t;
            if(ans==null) return head;
            if(t==null) pre.next = head;
            pre = head; 
        }
        return ans;
    }

    public ListNode reverse(ListNode head, int k){
        if(head==null||(head.next==null&&k>1)) return cur = null;
        if(k==1){
            cur = head.next;
            return head;
        } 
        ListNode t = reverse(head.next, k-1);
        if(t!=null){
            head.next.next = head;
            head.next = null;
        }
        return t;
    }
}
正常思路 
记住pre start end 三点就可以了

个一组翻转链表.png

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dumy = new ListNode(0);
        dumy.next = head;
        ListNode pre, end, start;
        pre = dumy;
        end = dumy;
        while(end!=null){
            for(int i=0; i<k&&end!=null; i++) end = end.next;
            if(end==null) break;
            ListNode next = end.next;
            start = pre.next;
            reverse(start, k);
            pre.next = end;
            pre = start;
            pre.next = next;
            end = pre;
        }
        return dumy.next;

    }
    public void reverse(ListNode start, int k){
        ListNode pre, cur, next;
        pre = null;
        cur = start;
        for(int i=0; i<k; i++){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}



henhen敲
22天前
快慢指针法 其实本题只需掌握两个点就可以了 
首先令first second 分别为每次走一步 走两步的指针
第一个时间点:当first刚好经过x步进入环的入口e时 second已经走了2x个node 且已经在环中 走了x个node了 
此时令second与first距离y个node  同时也可指 环的大小为x+y
第二个时间点: 当两者相遇时 一定是在距离入口点y的地方 只需在经过x个node又回到入口了 这是让first从起点开始 
second从现在的点开始 每次一步 最终一定会相遇

class Solution {
    public ListNode entryNodeOfLoop(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode first = head;
        ListNode second = head;
        do{
            if(first.next!=null) first = first.next;
            else return null;
            if(second.next!=null&&second.next.next!=null) second = second.next.next;
            else return null;
            if(first==second) break;
        }while(true);
        first = head;
        while(first!=second){
            first = first.next;
            second = second.next;
        }
        return first;
    }
}



henhen敲
23天前
分别用pnode bnode 存储小于和大于head链表 留下head  将排好序的链表与head拼接起来
class Solution {
    public ListNode quickSortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode bnode, pnode;
        bnode = null;
        pnode = null;
        while(head.next!=null){
            ListNode node = head.next;
            head.next = node.next;
            if(node.val<head.val){
                if(pnode==null){
                    pnode = node;
                    pnode.next = null;
                } else{
                    node.next = pnode;
                    pnode = node;
                }

            }
            if(node.val>=head.val){
                if(bnode==null){
                    bnode = node; 
                    bnode.next = null;
                }else{
                    node.next = bnode;
                    bnode = node; 
                }

            }

        }
        ListNode n1 = quickSortList(pnode);
        ListNode n2 = quickSortList(bnode);
        head.next = n2;
        if(n1!=null)getTail(n1).next = head;
        else return head;
        return n1;

    }

    public ListNode getTail(ListNode node){
        if(node==null||node.next==null) return node;
        return getTail(node.next);
    }
}