ReSQL.ru
     
powered by simpleCommunicator - 2.0.18     © 2024 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Map
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Решаю задачи для leetcode
4 сообщений из 29, страница 2 из 2
  2  все
Решаю задачи для leetcode
    #39784305
Фотография Valentin Kolesnikov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valentin Kolesnikov
Участник
Не могу решить задачу 126. ( https://leetcode.com/problems/word-ladder-ii/)

Нужно перевести этот код с java на php.

 
Код: java
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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
class Solution {
    HashMap<String, List<String>> map = new HashMap<>();
    List<List<String>> res = new ArrayList<>();
    List<String> list = new ArrayList<>();
        
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {        
        if(wordList.isEmpty())  return res;
        HashSet<String> set = new HashSet<>();
        HashSet<String> unvisited = new HashSet<>(wordList);
        set.add(beginWord);
        unvisited.remove(beginWord);
        boolean found = false;
        while(!set.isEmpty()){
            if(found)   break;
            HashSet<String> temp = new HashSet<>();
            for(String s: set){
                for(int i=0; i<s.length(); i++){
                    StringBuilder sb = new StringBuilder(s);
                    for(char c = 'a'; c<='z'; c++){
                        sb.setCharAt(i, c);
                        String newWord = sb.toString();
                        if(unvisited.contains(newWord)){
                            if(newWord.equals(endWord))
                                found=true;
                            temp.add(newWord);
                            
                            //building the neighbour map
                            if(map.containsKey(newWord))
                                map.get(newWord).add(s);
                            else{
                                List<String> neighbours = new ArrayList<>();
                                neighbours.add(s);
                                map.put(newWord, neighbours);
                            }
                        }
                    }
                }
            }
            unvisited.removeAll(temp);
            set = temp;
        }
        
        backTrace(beginWord, endWord);
        return res;
    }
    
    private void backTrace(String beginWord, String endWord){
        if(beginWord.equals(endWord)){
            list.add(0, beginWord);
            res.add(new ArrayList<String>(list));
            list.remove(0);
            return;
        }
        if(map.containsKey(endWord)){
            list.add(0, endWord);
            for(String pre: map.get(endWord)){
                backTrace(beginWord, pre);
            }
            list.remove(0);
        }
    }
}



Хорошего Вам дня!
...
Рейтинг: 0 / 0
10.03.2019, 20:25
| Ответить | Цитировать | Написать  
Решаю задачи для leetcode
    #39789877
Фотография Valentin Kolesnikov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valentin Kolesnikov
Участник
Решил 150 задач!

Хорошего Вам дня!
...
Рейтинг: 0 / 0
22.03.2019, 07:03
| Ответить | Цитировать | Написать  
Решаю задачи для leetcode
    #39936166
Фотография Valentin Kolesnikov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valentin Kolesnikov
Участник
Valentin Kolesnikov
Не могу решить задачу 126. ( https://leetcode.com/problems/word-ladder-ii )

Нужно перевести этот код с java на php.

 
Код: java
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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
class Solution {
    HashMap<String, List<String>> map = new HashMap<>();
    List<List<String>> res = new ArrayList<>();
    List<String> list = new ArrayList<>();
        
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {        
        if(wordList.isEmpty())  return res;
        HashSet<String> set = new HashSet<>();
        HashSet<String> unvisited = new HashSet<>(wordList);
        set.add(beginWord);
        unvisited.remove(beginWord);
        boolean found = false;
        while(!set.isEmpty()){
            if(found)   break;
            HashSet<String> temp = new HashSet<>();
            for(String s: set){
                for(int i=0; i<s.length(); i++){
                    StringBuilder sb = new StringBuilder(s);
                    for(char c = 'a'; c<='z'; c++){
                        sb.setCharAt(i, c);
                        String newWord = sb.toString();
                        if(unvisited.contains(newWord)){
                            if(newWord.equals(endWord))
                                found=true;
                            temp.add(newWord);
                            
                            //building the neighbour map
                            if(map.containsKey(newWord))
                                map.get(newWord).add(s);
                            else{
                                List<String> neighbours = new ArrayList<>();
                                neighbours.add(s);
                                map.put(newWord, neighbours);
                            }
                        }
                    }
                }
            }
            unvisited.removeAll(temp);
            set = temp;
        }
        
        backTrace(beginWord, endWord);
        return res;
    }
    
    private void backTrace(String beginWord, String endWord){
        if(beginWord.equals(endWord)){
            list.add(0, beginWord);
            res.add(new ArrayList<String>(list));
            list.remove(0);
            return;
        }
        if(map.containsKey(endWord)){
            list.add(0, endWord);
            for(String pre: map.get(endWord)){
                backTrace(beginWord, pre);
            }
            list.remove(0);
        }
    }
}





Так и не смог решить эту задачу на php.

Хорошего вам дня!
...
Рейтинг: 0 / 0
11.03.2020, 08:01
| Ответить | Цитировать | Написать  
Период между сообщениями больше года.
Решаю задачи для leetcode
    #40067632
Фотография Valentin Kolesnikov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valentin Kolesnikov
Участник
Valentin Kolesnikov
Не могу решить задачу 126. (https://leetcode.com/problems/word-ladder-ii/)

Нужно перевести этот код с java на php.

 
Код: java
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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
class Solution {
    HashMap<String, List<String>> map = new HashMap<>();
    List<List<String>> res = new ArrayList<>();
    List<String> list = new ArrayList<>();
        
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {        
        if(wordList.isEmpty())  return res;
        HashSet<String> set = new HashSet<>();
        HashSet<String> unvisited = new HashSet<>(wordList);
        set.add(beginWord);
        unvisited.remove(beginWord);
        boolean found = false;
        while(!set.isEmpty()){
            if(found)   break;
            HashSet<String> temp = new HashSet<>();
            for(String s: set){
                for(int i=0; i<s.length(); i++){
                    StringBuilder sb = new StringBuilder(s);
                    for(char c = 'a'; c<='z'; c++){
                        sb.setCharAt(i, c);
                        String newWord = sb.toString();
                        if(unvisited.contains(newWord)){
                            if(newWord.equals(endWord))
                                found=true;
                            temp.add(newWord);
                            
                            //building the neighbour map
                            if(map.containsKey(newWord))
                                map.get(newWord).add(s);
                            else{
                                List<String> neighbours = new ArrayList<>();
                                neighbours.add(s);
                                map.put(newWord, neighbours);
                            }
                        }
                    }
                }
            }
            unvisited.removeAll(temp);
            set = temp;
        }
        
        backTrace(beginWord, endWord);
        return res;
    }
    
    private void backTrace(String beginWord, String endWord){
        if(beginWord.equals(endWord)){
            list.add(0, beginWord);
            res.add(new ArrayList<String>(list));
            list.remove(0);
            return;
        }
        if(map.containsKey(endWord)){
            list.add(0, endWord);
            for(String pre: map.get(endWord)){
                backTrace(beginWord, pre);
            }
            list.remove(0);
        }
    }
}



Хорошего Вам дня!


Решение для задачи

Код: php
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.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
class Solution {

    /**
     * @param String $beginWord
     * @param String $endWord
     * @param String[] $wordList
     * @return String[][]
     */
    function findLadders($beginWord, $endWord, $wordList) {
        $maskToWords = [];
        $wordToMasks = [];
        $closestWords = [];
        $allwords = $wordList;
        $allwords[] = $beginWord;
        foreach($allwords as $word){
            for($i=0;$i<strlen($word);$i++){
                $mask = $word;
                $mask[$i] = '_';
                $maskToWords[$mask][$word] = true;
                $wordToMasks[$word][$mask] = true;
            }
        }
        foreach($allwords as $word){
            foreach($wordToMasks[$word] as $mask => $notUsed){
                foreach($maskToWords[$mask] as $linkedWord => $notUsed){
                    $closestWords[$word][$linkedWord] = true;
                }
            }
        }
        unset($maskToWords);
        unset($wordToMasks);
        unset($allwords);
        $queue = new SplQueue();
        $visitedNodes = [];
        return (new Node($beginWord, $visitedNodes))->breadthFirstSearch($queue,$endWord,$closestWords);
    }
}

class Node {
    private $name;
    private $distance;
    private $parent;
    private $visitedNodes;
    function __construct($name, &$visitedNodes, $parent = null, $distance = 1){
        $this->name = $name;
        $this->parent = $parent;
        $this->distance = $distance;
        $this->visitedNodes = &$visitedNodes;
    }
    private function getNextNodes(&$closestWords){
        $nodes = [];
        foreach($closestWords[$this->name] as $linkedWord => $notUsed){
            if(!isset($this->visitedNodes[$linkedWord])){
                $nodes[] = new Node($linkedWord, $this->visitedNodes, $this, $this->distance+1);
            }
        }
        return $nodes;
    }
    private function getPath(){
        $node = $this;
        $path = new SplDoublyLinkedList();
        while($node){
            $path->unshift($node->name);
            $node = $node->parent;
        }
        $pathArray = [];
        foreach($path as $item){
            $pathArray[] = $item;
        }
        return $pathArray;
    }
    function traverse($queue,&$closestWords){
        $this->visitedNodes[$this->name] = true;
        foreach($this->getNextNodes($closestWords) as $node){
            $queue->enqueue($node);
        }
    }
    function breadthFirstSearch($queue,$endWord,&$closestWords){
        $this->traverse($queue,$closestWords);
        $paths = [];
        $bestDistance = null;
        while(!$queue->isEmpty()){
            $nextNode = $queue->dequeue();
            if(!is_null($bestDistance) && $bestDistance < $nextNode->distance)
                break;
            if($nextNode->name===$endWord) {
                if(is_null($bestDistance))
                    $bestDistance = $nextNode->distance;
                $paths[] = $nextNode->getPath();
            }
            $nextNode->traverse($queue,$closestWords);
        }
        return $paths;
    }
}
...
Рейтинг: 0 / 0
30.04.2021, 15:14
| Ответить | Цитировать | Написать  
4 сообщений из 29, страница 2 из 2
  2  все
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Решаю задачи для leetcode
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (1): Анонимы (1)
Читали форум (1): Анонимы (1)
Пользователи онлайн (28): Анонимы (25), Yandex Bot, Bing Bot, Google Bot 8 мин.
Польз. соглашение
NoSQL.ru, Чат Кролика       Пашэ: Рисунки, Чат       Фотоальбом: Участники, Встречи
Закрыть
Start [/forum/topic.php?fid=23&tid=1459482&gotonew=1]:
 0ms
get settings:
 1ms
get forum list:
 13ms
check forum access:
 1ms
check topic access:
 1ms
track hit:
 43ms
get topic data:
 16ms
get first new msg:
 1ms
get forum data:
 0ms
get page messages:
 11ms
update_topic_read_status (1459482): 30.04.2021 15:14:46:
 0ms
get tp. blocked users:
 0ms
get online users:
 31ms
check new:
 1ms
others: 96ms
total:  215ms
созд. / загр.: 215ms (нв.: 1ms)
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]