#include<vector>

classSolution {

intsingleNumber(vector<int>& nums) {

int res =0;

for (int num : nums) {

res ^= num;

}

return res;

}

};

136\. Single Number

Easy

Given a**non-empty** array of integers`nums`, every element appears_twice_ except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

**Example 1:**

**Input:** nums =[2,2,1]

**Output:** 1

**Example 2:**

**Input:** nums =[4,1,2,1,2]

**Output:** 4

**Example 3:**

**Input:** nums =[1]

**Output:** 1

**Constraints:**

* <code>1 <= nums.length <= 3 * 10⁴</code>

* <code>-3 * 10⁴ <= nums[i] <= 3 * 10⁴</code>

* Each element in the array appears twice except for one element which appears only once.

To solve the "Single Number" problem in Java with a`Solution` class, we'll use bitwise XOR operation. Below are the steps:

1.**Create a`Solution` class**: Define a class named`Solution` to encapsulate our solution methods.

2.**Create a`singleNumber` method**: This method takes an array`nums` as input and returns the single number that appears only once.

3.**Initialize a variable to store the result**: Initialize a variable`singleNumber` to 0.

4.**Iterate through the array and perform bitwise XOR operation**: Iterate through the array`nums`. For each number`num` in the array, perform bitwise XOR operation with the`singleNumber`.

5.**Return the result**: After iterating through the entire array, the`singleNumber` variable will store the single number that appears only once. Return`singleNumber`.

Here's the Java implementation:

classSolution {

publicintsingleNumber(int[]nums) {

int singleNumber=0;// Initialize variable to store result

for (int num: nums) {

singleNumber^= num;

}

return singleNumber;// Return the single number

}

}

This implementation follows the steps outlined above and efficiently finds the single number that appears only once in the given array using bitwise XOR operation in Java.

classSolution {

Node*copyRandomList(Node* head) {

if (head ==nullptr) {

returnnullptr;

}

Node* curr = head;

while (curr !=nullptr) {

Node* clonedNode =newNode(curr->val, curr->next,nullptr);

curr->next = clonedNode;

curr = clonedNode->next;

}

curr = head;

while (curr !=nullptr) {

if (curr->random !=nullptr) {

curr->next->random = curr->random->next;

}

curr = curr->next->next;

}

curr = head;

Node* newHead = curr->next;

while (curr !=nullptr) {

Node* clonedNode = curr->next;

curr->next = clonedNode->next;

if (clonedNode->next !=nullptr) {

clonedNode->next = clonedNode->next->next;

}

curr = curr->next;

}

return newHead;

}

};

138\. Copy List with Random Pointer

Medium

A linked list of length`n` is given such that each node contains an additional random pointer, which could point to any node in the list, or`null`.

Construct a[**deep copy**](https://en.wikipedia.org/wiki/Object_copying#Deep_copy) of the list. The deep copy should consist of exactly`n`**brand new** nodes, where each new node has its value set to the value of its corresponding original node. Both the`next` and`random` pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state.**None of the pointers in the new list should point to nodes in the original list**.

For example, if there are two nodes`X` and`Y` in the original list, where`X.random --> Y`, then for the corresponding two nodes`x` and`y` in the copied list,`x.random --> y`.

Return_the head of the copied linked list_.

The linked list is represented in the input/output as a list of`n` nodes. Each node is represented as a pair of`[val, random_index]` where:

*`val`: an integer representing`Node.val`

*`random_index`: the index of the node (range from`0` to`n-1`) that the`random` pointer points to, or`null` if it does not point to any node.

Your code will**only** be given the`head` of the original linked list.

**Example 1:**

**Input:** head =[[7,null],[13,0],[11,4],[10,2],[1,0]]

**Output:**[[7,null],[13,0],[11,4],[10,2],[1,0]]

**Example 2:**

**Input:** head =[[1,1],[2,1]]

**Output:**[[1,1],[2,1]]

**Example 3:**

**Input:** head =[[3,null],[3,0],[3,null]]

**Output:**[[3,null],[3,0],[3,null]]

**Example 4:**

**Input:** head =[]

**Output:**[]

**Explanation:** The given linked list is empty (null pointer), so return null.

**Constraints:**

*`Node.random` is`null` or is pointing to some node in the linked list.

To solve the "Copy List with Random Pointer" problem in Java with a`Solution` class, we'll use a HashMap to maintain a mapping between the original nodes and their corresponding copied nodes. Below are the steps:

1.**Create a`Solution` class**: Define a class named`Solution` to encapsulate our solution methods.

2.**Create a`copyRandomList` method**: This method takes the head node of the original linked list as input and returns the head node of the copied linked list.

3.**Initialize a HashMap**: Create a HashMap named`nodeMap` to store the mapping between original nodes and their corresponding copied nodes.

4.**Create a deep copy of the list**: Iterate through the original linked list and create a deep copy of each node. For each node`originalNode` in the original linked list:

- Create a new node`copyNode` with the same value as`originalNode`.

- Put the mapping between`originalNode` and`copyNode` in the`nodeMap`.

- Set the`copyNode`'s`next` and`random` pointers accordingly.

- Attach the`copyNode` to the copied linked list.

5.**Return the head of the copied linked list**: After creating the deep copy of the entire list, return the head node of the copied linked list.

Here's the Java implementation:

importjava.util.HashMap;

importjava.util.Map;

classSolution {

publicNodecopyRandomList(Nodehead) {

if (head==null)returnnull;// Check for empty list

Map<Node,Node> nodeMap=newHashMap<>();// Initialize HashMap to store mapping between original and copied nodes

Node current= head;

while (current!=null) {

Node copyNode=newNode(current.val);// Create a new copy node

nodeMap.put(current, copyNode);// Put mapping between original and copied nodes in the map

current= current.next;// Move to the next node

}

current= head;

while (current!=null) {

Node copyNode= nodeMap.get(current);// Get copied node

copyNode.next= nodeMap.getOrDefault(current.next,null);// Set next pointer

copyNode.random= nodeMap.getOrDefault(current.random,null);// Set random pointer

current= current.next;// Move to the next node

}

return nodeMap.get(head);// Return the head of the copied linked list

}

classNode {

int val;

Node next, random;

Node(intval) {

this.val= val;

this.next=null;

this.random=null;

}

}

}

This implementation follows the steps outlined above and efficiently constructs a deep copy of the linked list with random pointers in Java.

#include<string>

#include<vector>

#include<unordered_set>

classSolution {

boolwordBreak(string s, vector<string>& wordDict) {

unordered_set<string> set;

int maxLen =0;

vector<bool>flag(s.length() +1,false);

for (const string& word : wordDict) {

set.insert(word);

maxLen =max(maxLen, (int)word.length());

}

for (int i =1; i <= maxLen; ++i) {

if (dfs(s,0, i, maxLen, set, flag)) {

returntrue;

}

}

returnfalse;

}

booldfs(const string& s,int start,int end,int maxLen, unordered_set<string>& set, vector<bool>& flag) {

if (!flag[end] && set.count(s.substr(start, end - start))) {

flag[end] =true;

if (end == s.length()) {

returntrue;

}

for (int i =1; i <= maxLen; ++i) {

if (end + i <= s.length() &&dfs(s, end, end + i, maxLen, set, flag)) {

returntrue;

}

}

}

returnfalse;

}

};

139\. Word Break

Medium

Given a string`s` and a dictionary of strings`wordDict`, return`true` if`s` can be segmented into a space-separated sequence of one or more dictionary words.

**Note** that the same word in the dictionary may be reused multiple times in the segmentation.

**Example 1:**

**Input:** s = "leetcode", wordDict =["leet","code"]

**Output:** true

**Explanation:** Return true because "leetcode" can be segmented as "leet code".

**Example 2:**

**Input:** s = "applepenapple", wordDict =["apple","pen"]

**Output:** true

**Explanation:** Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

**Example 3:**

**Input:** s = "catsandog", wordDict =["cats","dog","sand","and","cat"]

**Output:** false

**Constraints:**

*`s` and`wordDict[i]` consist of only lowercase English letters.

* All the strings of`wordDict` are**unique**.

classSolution {

boolhasCycle(ListNode* head) {

if (head ==nullptr) {

returnfalse;

}

ListNode* fast = head->next;

ListNode* slow = head;

while (fast !=nullptr && fast->next !=nullptr) {

if (fast == slow) {

returntrue;

}

fast = fast->next->next;

slow = slow->next;

}

returnfalse;

}

};