分类目录归档:算法题

word-break

题目描述

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s =”leetcode”,
dict =[“leet”, “code”].
Return true because”leetcode”can be segmented as”leet code”.

思路

动态规划
dp数组 dp[i]表示s[0->i]是否可分
j从0到i-1 如果s[0–>j]可分,则尝试判定s[j–>]是否可分,如果可分,那么s[0–>i]也可分

代码

import java.util.*;
public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if (s == null || s.length() == 0 || dict == null || dict.size() == 0) return false;
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

candy

题目描述

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

思路

思路1:
找出最小值,分成两段,根据左右的情况填这个最小值,然后这两段带边界值递归。
思路2:
左右各扫一遍,遇到不符合要求的加1

代码

public class Solution {
    public int candy(int[] ratings) {
        if(ratings==null||ratings.length==0){
            return 0;
        }
        if(ratings.length==1){
            return 1;
        }
        int[] nums = new int[ratings.length];
        for (int i = 0; i < nums.length; i++) {
            nums[i]=1;
        }
        //scan from left to right
        for (int i = 1; i < ratings.length; i++) {
            if(ratings[i]>ratings[i-1]){
                nums[i]=nums[i-1]+1;
            }
        }
        //scan from right to left
        for (int i = ratings.length-2; i >= 0; i--) {
            if(ratings[i]>ratings[i+1]&&nums[i]<=nums[i+1]){
                nums[i]=nums[i+1]+1;
            }
        }
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result+=nums[i];
        }
        return result;
    }
}

single-number-ii

题目描述

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

思路

真大佬在这,感觉智商被碾压
https://www.nowcoder.com/questionTerminal/1097ca585245418ea2efd0e8b4d9eb7a

public class Solution {
    public int singleNumber(int[] a) {
        if(a==null)return 0;
        int ones = 0;
        int twos = 0;
        int threes;
        for (int i = 0; i < a.length; i++) {
            int t = a[i];
            twos |= ones&t;
            ones ^= t;
            threes = ones&twos;
            ones &= ~threes;
            twos &= ~threes;
        }
        return ones;
    }
}

single-number

题目描述

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

代码

public int singleNumber(int[] a) {
        if(a==null)return 0;
        int result=0;
        for (int i = 0; i < a.length; i++) {
            result^=a[i];
        }
        return result;
    }

linked-list-cycle

题目描述

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

思路

使用快慢指针,如果有环必定会相遇

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //快慢指针判断是否有环
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}

inked-list-cycle-ii

题目描述

Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.
Follow up:
Can you solve it without using extra space?

思路

https://www.nowcoder.com/questionTerminal/6e630519bf86480296d0f1c868d425ad

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //探测环
    public ListNode detectCycle(ListNode head) {
        if(head == null){
            return null;
        }
        //寻找相遇节点
        ListNode meetNode = findMeetingNode(head);
        if(meetNode==null){
            return null; //无环
        }
        ListNode p1 = head;
        ListNode p2 = meetNode;
        while (p1!=p2){
            p1 = p1.next;
            p2 = p2.next;
        }

        return p1;
    }
    private ListNode findMeetingNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(slow == fast){
                return slow;
            }
        }
        return null;
    }
}

reorder-list

题目描述

Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…
You must do this in-place without altering the nodes’ values.
For example,
Given{1,2,3,4}, reorder it to{1,4,2,3}.

思路

见注释

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head==null||head.next==null)
            return;
        //快慢指针找中点
        ListNode fast=head;
        ListNode slow=head;
        while (fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //从中间拆分链表
        ListNode right=slow.next;
        slow.next=null;
        //翻转后半部分链表
        ListNode pre=null;
        while (right!=null){
            ListNode temp = right.next;
            right.next=pre;
            pre=right;
            right=temp;
        }
        //合并链表
        ListNode left = head;
        right = pre;
        while (left!=null&&right!=null){
            ListNode lTemp=left.next;
            ListNode rTemp=right.next;
            left.next=right;
            left=lTemp;
            right.next=left;
            right=rTemp;
        }
    }
}

binary-tree-postorder-traversal

题目描述

Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree{1,#,2,3},
1
\
2
/
3

return[3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

思路

递归遍历

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    //后序遍历
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer>  result = new ArrayList<>();
        postOrderTraversalCore(result,root);
        return result;
    }
    private void postOrderTraversalCore(ArrayList<Integer>  result,TreeNode root){
        if(root == null) return;
        postOrderTraversalCore(result,root.left);
        postOrderTraversalCore(result,root.right);
        result.add(root.val);
    }
}

binary-tree-preorder-traversal

题目描述

Given a binary tree, return the preorder traversal of its nodes’ values.
For example:
Given binary tree{1,#,2,3},
1
\
2
/
3

return[1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?

思路

递归遍历

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    //前序遍历
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer>  result = new ArrayList<>();
        preOrderTraversalCore(result,root);
        return result;
    }
    private void preOrderTraversalCore(ArrayList<Integer>  result,TreeNode root){
        if(root == null) return;
        result.add(root.val);
        preOrderTraversalCore(result,root.left);
        preOrderTraversalCore(result,root.right);
    }
}

insertion-sort-list

题目描述

Sort a linked list using insertion sort.

思路

新建一个链表,从原来的表中不断的取数据,再插入的过程中保证有序。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode p = head;
        while (p!=null){
            ListNode next = p.next;
            insert(dummy,p);
            p = next;
        }
        return dummy.next;
    }
    //dummy 是已经排序好的链表,第一个节点不用
    private void  insert(ListNode dummy,ListNode node){
        ListNode p = dummy;
        while (p.next!=null&& p.next.val<node.val){
            p=p.next;
        }
        ListNode next = p.next;
        p.next=node;
        node.next=next;
    }
}